应用数学与计算数学学报
應用數學與計算數學學報
응용수학여계산수학학보
COMMUNICATION ON APPLIED MATHEMATICS AND COMPUTATION
2009年
2期
102-110
,共9页
非凸二次规划问题%凸二次约束%SDP松弛%DC分解方法%随机化方法
非凸二次規劃問題%凸二次約束%SDP鬆弛%DC分解方法%隨機化方法
비철이차규화문제%철이차약속%SDP송이%DC분해방법%수궤화방법
nonconvex quadratically constrained quadratic programming problems%convex quadratic constraints%SDP relexation%D.C. decompositions%randomized method
本文提出一类基于DC分解的非凸二次规划问题SDP松弛方法,并通过求解一个二阶锥问题得到原问题的近似最优解.我们首先对非凸二次目标函数进行DC分解,然后利用线性下逼近得到一个凸二次松弛问题,而最优的DC分解可通过求解一个SDP问题得到.数值试验表明,基于DC分解的SDP近似解平均优于经典SDP松弛和随机化方法产生的近似解.
本文提齣一類基于DC分解的非凸二次規劃問題SDP鬆弛方法,併通過求解一箇二階錐問題得到原問題的近似最優解.我們首先對非凸二次目標函數進行DC分解,然後利用線性下逼近得到一箇凸二次鬆弛問題,而最優的DC分解可通過求解一箇SDP問題得到.數值試驗錶明,基于DC分解的SDP近似解平均優于經典SDP鬆弛和隨機化方法產生的近似解.
본문제출일류기우DC분해적비철이차규화문제SDP송이방법,병통과구해일개이계추문제득도원문제적근사최우해.아문수선대비철이차목표함수진행DC분해,연후이용선성하핍근득도일개철이차송이문제,이최우적DC분해가통과구해일개SDP문제득도.수치시험표명,기우DC분해적SDP근사해평균우우경전SDP송이화수궤화방법산생적근사해.
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.
