| 基于DC分解的非凸二次规划SDP近似解 |
| |
| 引用本文： | 王延菲,郑小金. 基于DC分解的非凸二次规划SDP近似解[J]. 应用数学与计算数学学报, 2009, 23(2): 102-110 |
| |
| 作者姓名： | 王延菲 郑小金 |
| |
| 作者单位： | 1. 复旦大学管理学院管理科学系,上海,200433
2. 上海大学数学系,上海,200444 |
| |
| 摘 要： | 本文提出一类基于DC分解的非凸二次规划问题SDP松弛方法,并通过求解一个二阶锥问题得到原问题的近似最优解.我们首先对非凸二次目标函数进行DC分解,然后利用线性下逼近得到一个凸二次松弛问题,而最优的DC分解可通过求解一个SDP问题得到.数值试验表明,基于DC分解的SDP近似解平均优于经典SDP松弛和随机化方法产生的近似解。
|
| 关 键 词： | 非凸二次规划问题 凸二次约束 SDP松弛 DC分解方法 随机化方法 |
Approximate Solutions Based on SDP Relaxation of D.C. Decompositions for a Class of Nonconvex QCQP Problems |
| |
| Wang Yanfei,Zheng Xiaojin. Approximate Solutions Based on SDP Relaxation of D.C. Decompositions for a Class of Nonconvex QCQP Problems[J]. Communication on Applied Mathematics and Computation, 2009, 23(2): 102-110 |
| |
| Authors: | Wang Yanfei Zheng Xiaojin |
| |
| Affiliation: | Wang Yanfei Zheng Xiaojin(1. Department of Management Science, Fudan University, Shanghai 200433, China2. Department of Mathematics, Shanghai University, Shanghai 200444, China) |
| |
| Abstract: | We propose in this paper an SDP relaxation method based on D.C. de-compostions for a class of nonconvex quadratic programs. By solving a second-order cone problem we can obtain an approximate optimal solution to the primal problem. The SDP relaxation is obtained by finding the best convex relaxation constructed by D.C. decom-postion and linear underestimation. Computational results show that the approximate solutions based on SDP relaxation of D.C. decompostion dominate the approximate solu-tions generated by the conventional SDP relaxation and randomized method on average. |
| |
| Keywords: | nonconvex quadratically constrained quadratic programming problems convex quadratic constraints SDP relexation D.C. decompositions randomized method |
| 本文献已被 维普 万方数据 等数据库收录！ |
