1、1基于 D.C.分解的一类箱型约束的非凸二次规划的新型分支定界算法摘要提出了一类求解带有箱约束的非凸二次规划的新型分支定界算法.首先，把原问题目标函数进行 D.C.分解（分解为两个凸函数之差） ，利用次梯度方法，求出其线性下界逼近函数的一个最优值，也即原问题的一个下界.然后，利用全局椭球算法获得原问题的一个上界，并根据分支定界方法把原问题的求解转化为一系列子问题的求解.最后，理论上证明了算法的收敛性，数值算例表明算法是有效可行的. 关键词非凸二次规划；箱约束；分支定界算法 中图分类号 O 221 文献标识号 A 1 引言 考虑下面带有箱约束的非凸二次规划（QPB） 其中： A 是一个 nn 阶
2、实对称不定矩阵， l，u，b，xRn，并且lixiui， i = 1，n. 带有箱约束的二次规划，在工程领域中有非常广泛的应用1？3.在解偏微分方程，线性最小二乘问题也时常遇到.另外，带有箱约束的二次规划在非线性规划中占有重要地位，其可看成连续二次规划方法中的子问题. （QPB）吸引了众多学者的研究.从复杂性来看， （QPB）是NP？Hard 的4. Hansen 等5研究了（QPB）的最优性必要条件； Yajima 和 Fujie6提出了一个多面体逼近方法； Le 和 Pham7提出一2个基于 D.C.规划和椭球技术相结合的分支定界算法. Vandenbussche 和Nemhauser8，
3、9用一类不等式作为割平面提出了一个分支定界算法，并且研究了多面体与在箱约束非凸二次规划中的一些应用. Vandenbussche10用半定松弛作为一个有限步的分支策略，针对求解箱约束非凸二次规划也是有效的.进一步了解该问题的一些求解方法可参见文献11-13. 文中提出一种求解（QPB）的新型分支定界算法.新算法中涉及获得原问题（QPB）的下界，不同于文献7确定下界的方法，而是通过 D.C.分解，利用次梯度方法，获得原问题的一个下界.之后，利用球约束二次规划的全局椭球算法（文献7中关于球约束二次规划的 GDCABQ 算法）得到原问题的一个上界.然后把可行域进行二分，转化为一系列类似（QPB）的子
4、问题，通过分支定界算法，不断消减分支，逐步优化最优值，直至得到最优解.最后，对提出的新算法进行了收敛性分析，数值算例表明了算法是有效可行的. 例 3 考虑问题 min f2（x） =1 2xTAx + bTx，s.t. lxu 其中： A 为 nn 阶随机产生的实对称不定矩阵，其生成的方法是，利用 matlab中的 rand 函数， tril 函数及 triu 函数，产生一个在区间？10，10均匀分布的 n 阶实对称随机矩阵，然后选取主对角线上元素值有正有负的矩阵作为文中所需要实对称不定矩阵. bRn 是随机产生的向量， li，uiR，i = 1，n 在实区间0，10上随机产生的. 例 1、例
5、 2 的计算结果参见表 1，文献14是利用神经网络智能算法，通过随机产生 100 个初始点，有 42 次收敛到局部最优解3（1，？1，？0.6667，1）T，对应的最优值为？10.8333.也就是说并非所有的初始点均能收敛到全局最优解（？0.6667，1，1，？1）T，而本文的算法每次均可收敛到全局最优解（？0.6667，1，1，？1）T.对应的全局最优值为？11.3333.例 3 的计算结果参见下面表 2，对于例 3 的每种情况，我们做 10 次随机实验，然后取计算结果的平均值.从这些数值实验结果的比较可以看出，我们的方法是有效可行的.表 1，表 2 中的算法14，11，7分别表示文献14，
6、11，7中的算法. 参考文献 1 Bajirov A M， Rubinov A M. Global optimization of marginal functions with applications to economic equilibrium. Journal of Global Optimization， 2001， 20（3-4）： 215-237. 2 Konnoc H. Portfolio optimization problem under concave transaction costs and minimal transaction unit constraints.
7、 Mathematical Programming， 2001， 89（2）： 233-250. 3 Sherali H D， Smith E P. A global optimization approach to a water distribution network design problem. Journal of Global Optimization， 1997， 11（2）： 107-132. 4 Pardalos P M， Vavasis S A. Quadratic programming with one negative eigenvalue is np-hard.
8、Journal of Global Optimization， 1991， 1（1）： 15-22. 5 Hansen P， Jaumard B， Ruiz M， Xiong J. Global minimization of indefinite quadratic functions subject to box 4constraints. Naval Research Logistics， 1993， 40（3）： 373-392. 6 Yajima Y， Fujie T. A polyhedral approach for nonconvex quadratic programming
9、 problems with box constraints. Journal of Global Optimization， 1998， 13（2）： 151-170. 7 Le Thi H A， Pham Dinh T. A branch and bound method via d.c. optimization algorithms and ellipsoidal technique for box constrained nonconvex quadratic problems. Journal of Global Optimization， 1998， 13（2）： 171-206
10、. 8 Vandenbussche D， Nemhauser G L. A branch-and-cut algorithm for nonconvex quadratic programs with box constraints. Mathematical Programming， 2005， 102（3）：559- 575. 9 Vandenbussche D， Nemhauser G L. A polyhedral study of nonconvex quadratic programs with box constraints. Mathematical Programming，
11、2005， 102（3）： 531-557. 10 Samuel B， Dieter V. Globally solving box-constrained nonconvex quadratic programs with semidefinite-basedfinite branch-and-bound. Computational Optimization and Applications， 2009， 43（2）： 181-195. 11 Li Jian-ling ， Wang Peng， Ma Lin. A new algorithm for the general quadrati
12、c programming problems with box constraints. Numerical Algorithms， 2010， 55（1）： 79-85. 512 David Yang Gao， Ning Ruan. Solutions to quadratic minimization problems with box and integer constraints. Journal of Global Optimization， 2010， 47（1）： 463-484. 13 Samuel Burer， Chen Jie-qiu. Relaxing the optimality conditions of box QP. Computational Optimization and Applications， 2011， 48（3）： 653-673. 14李有梅，彭济根，徐宗本.求解有界约束二次规划问题神经网络模型的收敛性分析.系统工程理论与实践， 2003， 9：98-104，128. 15袁亚湘，孙文瑜.最优化理论与方法.科学出版社，1997.
