线性约束非凸二次规划的有限分支定界算法

A Finite Branch-and-bound Algorithm for Non-convex Quadratic Programming with Linear Constraints

针对线性约束非凸二次规划问题,从其KKT点出发得到它的一个线性松弛规划,并递归地向该松弛规划中加入原问题的互补松弛条件的线性等式,从而得到一个有限分支定界算法,并对其收敛性进行了证明,经数值实验表明该算法是有效的.

In this paper,we obtain a linear programming relaxation from Karush-Kuhn-Tucker（KKT） point for non-convex quadratic programming with linear constraints.Thus we propose a finite branch-and-bound algorithm by adding recursively the linear equations of the complementarity constraints of the primal problem to the relaxation programming.Therefore,the convergence of the algorithm is proved and the numerical computations show that the proposed algorithm is effective.