求非凸二次约束二次规划全局解的凸规划方法  

A Convex Optimization Method for Global Optimal Solution of Quadratic Programming Problem with Non-Convex Quadratic Constraints

作　　者：田朝薇[1] 宋海洲[1] 

机构地区：[1]华侨大学数学科学学院,福建泉州362021

出　　处：《华侨大学学报（自然科学版）》2011年第4期458-462,共5页Journal of Huaqiao University(Natural Science)

基　　金：福建省自然科学基金资助项目(Z0511028);华侨大学科研基金资助项(10HZR26)

摘　　要：针对非凸二次约束二次规划(QCQP)问题,将问题中二次函数的凸函数部分保留,达到所得松弛规划的可行域更加紧致的目的,得到原问题更好的下界.利用正交变换的方法得到原问题的一个凸规划松弛模型,再利用分支定界算法求其全局最优解.根据问题的最优性和可行性原则,提出一种能整体删除或缩小算法迭代过程中产生的分割子区域的区域删减策略.数值算例表明,算法及区域删减策略均是有效的.In this paper,we obtain a sharper low bound by reserving the part of the convex function of the quadratic function for a non-convex quadratic programming with non-convex quadratic constraints（QCQP）.The QCQP problem is first transformed into a convex quadratic programming with linear constraints by employing the orthogonal transformation and then the latter is solved by the branch-bound method.In order to improve the convergence of the proposed algorithm,two region-prunning techniques are given to delete or contract the sub-regions in which does not contain the optimal solutions of QCQP according to the optimality and feasibility of the problem.The numerical results show that the proposed algorithm and the prunning techniques are effective.

关 键 词：非凸 二次约束二次规划 全局解 分支定界 区域删减策略 

分 类 号：O221.2[理学—运筹学与控制论]