[1]田朝薇,宋海洲.求非凸二次约束二次规划全局解的凸规划方法[J].华侨大学学报(自然科学版),2011,32(4):458-462.[doi:10.11830/ISSN.1000-5013.2011.04.0458]
　TIAN Zhao-wei,SONG Hai-zhou.A Convex Optimization Method for Global Optimal Solution of Quadratic Programming Problem with Non-Convex Quadratic Constraints[J].Journal of Huaqiao University(Natural Science),2011,32(4):458-462.[doi:10.11830/ISSN.1000-5013.2011.04.0458]
点击复制

求非凸二次约束二次规划全局解的凸规划方法()
分享到：

《华侨大学学报（自然科学版）》[ISSN:1000-5013/CN:35-1079/N]

卷:
第32卷
期数:
2011年第4期
页码:
458-462
栏目:
出版日期:
2011-07-20

文章信息/Info

Title:
A Convex Optimization Method for Global Optimal Solution of Quadratic Programming Problem with Non-Convex Quadratic Constraints
文章编号:
1000-5013(2011)04-0458-05
作者:
田朝薇; 宋海洲
华侨大学数学科学学院
Author(s):
TIAN Zhao-wei;  SONG Hai-zhou
School of Mathematical Sciences, Huaqiao University, Quanzhou 362021, China
关键词:
非凸;  二次约束二次规划;  全局解;  分支定界;  区域删减策略
Keywords:
non-convex quadratic programming;  global optimization;  branch-bound method;  region-deleting rules
分类号:
O221.2
DOI:
10.11830/ISSN.1000-5013.2011.04.0458
文献标志码:
A
摘要:
针对非凸二次约束二次规划(QCQP)问题,将问题中二次函数的凸函数部分保留,达到所得松弛规划的可行域更加紧致的目的,得到原问题更好的下界.利用正交变换的方法得到原问题的一个凸规划松弛模型,再利用分支定界算法求其全局最优解.根据问题的最优性和可行性原则,提出一种能整体删除或缩小算法迭代过程中产生的分割子区域的区域删减策略.数值算例表明,算法及区域删减策略均是有效的.
Abstract:
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.

参考文献/References:

[1] YE Y Y. Approximating global quadratic programming with convex quadratic constraints [J]. Journal of Global Optimization, 1999(1):1-17.doi:10.1023/A:1008370723217.
[2] KOZLOV M K, TARASOV S P, KHACHIYAN L G. Polynomial solvability of convex quadratic programming [J]. Doklady Akademii Nauk SSSR, 1979(5):1049-1051.
[3] PARDALOS P M, VAVASIS S A. Qradratic programming with one negative eigenvalue is NP-bard [J]. Global Optimization, 1991(1):15-22.
[4] SHERALI H D, TUNCBOLEK C H. A reformulation-convexification approach for solving nonconvex quadratic programming problems [J]. Global Optimization, 1995(1):1-31.
[5] ANSTREICHER K M. Semidefinite programming versus the reformulation-linearization technique for nonconvex quadratically constrained quadratic programming [J]. Global Optimization, 2009, (2/3):471-484.
[6] TIM V V, FAIZ A A. Difference of convex solution of quadratically constrained optimization problems [J]. European Journal of Operational Research, 2003, (2):349-362.doi:10.1016/S0377-2217(02)00432-0.
[7] QU Shao-jian, ZHANG Ke-cun, JI Ying. A global optimization algorithm using parametric linearization relaxation [J]. Applied Mathematics and Computation, 2007(1):763-771.doi:10.1016/j.amc.2006.08.028.
[8] 吴慧卓, 段东东, 张可村. 一种新的求解带有非凸二次约束的非凸二次规划问题的加速全局优化方法 [J]. 工程数学学报, 2009(1):75-84.doi:10.3969/j.issn.1005-3085.2009.01.011.
[9] 申培萍, 刘利敏. 带非凸二次约束二次规划问题全局解的线性化方法 [J]. 高等学校计算数学学报, 2008(3):261-267.doi:10.3969/j.issn.1000-081X.2008.03.007.

备注/Memo

备注/Memo:
福建省自然科学基金资助项目(Z0511028); 华侨大学科研基金资助项(10HZR26)
更新日期/Last Update: 2014-03-23