带有二次约束的二次规划问题的一个收缩分枝定界算法  

A reduced branch and bound approach for solving quadratic programming problem with quadratic constraints

作　　者：高岳林[1] 马小华[1] 袁玉波[2] 

机构地区：[1]西北第二民族学院信息与计算科学系,宁夏银川750021 [2]西安交通大学理学院,陕西西安710049

出　　处：《宁夏大学学报（自然科学版）》2003年第1期16-18,共3页Journal of Ningxia University(Natural Science Edition)

基　　金：国家自然科学基金资助项目(19971065)

摘　　要：通过解线性规划问题,寻找包含原问题可行域的超矩形,利用剖分技术对这个超矩形进行分枝和收缩以减少算法的迭代次数,从而用线性规划松弛方法来确定原问题在每个小超矩形上的最优值的下界,提出一种新的带有二次约束的二次规划问题的收缩分枝定界算法,并证明了该算法是收敛的.In solving linear programs, the rectangular with feasible field of the former problem is about to be found out. The number of the iteration in the algorithm is decreased by the use of partition technique on the rectangular so the lower bound of the optimal value of the former problem is determined by linear programming relaxation method. Also a reduced branch and bound algorithm for solving quadratic programming problem with quadratic constraints is put forward by the branch and bound technique, and its convergence is proved.

关 键 词：二次规划 二次约束 收缩分枝定界算法 线性规划 超矩形 松弛方法 最优值 

分 类 号：O221.2[理学—运筹学与控制论]