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

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

通过解线性规划问题,寻找包含原问题可行域的超矩形,利用剖分技术对这个超矩形进行分枝和收缩以减少算法的迭代次数,从而用线性规划松弛方法来确定原问题在每个小超矩形上的最优值的下界,提出一种新的带有二次约束的二次规划问题的收缩分枝定界算法,并证明了该算法是收敛的.

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.