基于D.C.分解的一类箱型约束的非凸二次规划的新型分支定界算法

A New Branch and Bound Algorithm Based on D.C. Decomposition about Nonconvex Quadratic Programming with Box Constrained

提出了一类求解带有箱约束的非凸二次规划的新型分支定界算法.首先,把原问题目标函数进行D.C.分解(分解为两个凸函数之差),利用次梯度方法,求出其线性下界逼近函数的一个最优值,也即原问题的一个下界.然后,利用全局椭球算法获得原问题的一个上界,并根据分支定界方法把原问题的求解转化为一系列子问题的求解.最后,理论上证明了算法的收敛性,数值算例表明算法是有效可行的.

In this paper, we present a class new branch and bound algorithm for solving nonconvex quadratic programming with box constrained. At the first, the objective func- tion of the original problem has a D.C.（two different of convex function） decomposition. Calculated an optimal value of the function which is linear lower bound approximation, i.e. a lower bound of the original problem. Then obtain an upper bound of the original problem by global ellipsoid algorithm. And then, by using the branch and bound algo- rithm, we can solve the original problem by solving a series of subproblems. Finally, the convergence is proved and numerical experiments show that the algorithm works well.