非凸二次规划全局极小问题的新型分枝定界算法

计算机工程与应用 ›› 2008, Vol. 44 ›› Issue (17): 49-52.

非凸二次规划全局极小问题的新型分枝定界算法

杜廷松¹,费浦生²,蹇继贵¹

1. 三峡大学非线性与复杂系统研究所，湖北宜昌 443002
2. 武汉大学数学与计算科学学院，武汉 430072

收稿日期:2007-09-14 修回日期:2007-12-27 出版日期:2008-06-11 发布日期:2008-06-11
通讯作者: 杜廷松

New branch and bound algorithm for nonconvex quadratic programming global minimization

DU Ting-song¹,FEI Pu-sheng²,JIAN Ji-gui¹

1. Institute of Nonlinear and Complex Systems，China Three Gorges University，Yichang，Hubei 443002，China
2. College of Mathematics and Computer Science，Wuhan University，Wuhan 430072，China

Received:2007-09-14 Revised:2007-12-27 Online:2008-06-11 Published:2008-06-11
Contact: DU Ting-song

摘要/Abstract

摘要： 针对求解多面集上二次函数的全局近似最优解问题，利用逐步缩小对偶间隙的处理办法，提出了一个新型分枝定界算法。新算法的主要改进之处是利用了Lagrange 对偶性获取下界。最后,用构造和随机产生的问题实例,对提出的新算法和传统的分枝定界算法做了初步的数值比较实验。计算实验表明算法对求解中大规模非凸二次规划问题的有效性。

Abstract: In this paper，by using a technique for reducing the duality gap，a new branch and bound algorithm is developed for quadratic programming global minimization.The major improvement of the new algorithm is that the algorithm uses Lagrangian duality to obtain lower bounds.In the last，two different algorithms（namely，the proposed algorithm，the traditional branch and bound algorithm）have been implemented for same construction problems and random instances.Computation results indicate that the proposed algorithm can solve large-scale nonconvex quadratic problems.

杜廷松¹,费浦生²,蹇继贵¹. 非凸二次规划全局极小问题的新型分枝定界算法[J]. 计算机工程与应用, 2008, 44(17): 49-52.

DU Ting-song¹,FEI Pu-sheng²,JIAN Ji-gui¹. New branch and bound algorithm for nonconvex quadratic programming global minimization[J]. Computer Engineering and Applications, 2008, 44(17): 49-52.