论文部分内容阅读
非凸二次规划是一类重要的最优化问题,在工程、经济管理和金融优化等领域有广泛的应用,如生产计划问题,规模效益问题,工程设计与控制中的问题,许多具有挑战性的NP-难非凸优化问题和组合优化问题都可以表示为非凸二次规划问题.本文研究凸二次约束非凸二次规划问题,并提出一类基于D.C.分解的SDP松弛方法,该方法通过目标函数的D.C.分解和对凹函数进行线性逼近来构建原问题的凸松弛.本文考虑了两种D.C.分解方法：第一种是利用一组非零向量构造目标函数的D.C.分解,并对凹部分线性逼近；第二种是利用约束系数矩阵的正交变换构造目标函数的D.C.分解,并对凹部分进行分段线性逼近.我们证明了通过最优D.C.分解可以得到原问题的SDP松弛,并证明所得到的SDP界比经典的SDP界更紧.本文提出的D.C.分解方法的另一个优点是可以在得到SDP界的同时通过求解一个二阶锥规划得到原问题的一个近似最优解.数值结果表明,本文提出的SDP松弛可以产生比典型SDP松弛更紧的界,同时,数值结果还表明,基于SDP松弛的近似算法可以得到比传统随机化算法更好的近似最优解.本文分为五个部分.第一部分介绍非凸二次规划问题的研究背景与本文的主要工作.第二部分介绍非凸二次规划问题的现有算法,主要包括分支定界算法,半定规划松弛,以及基于半定规划松弛的随机化近似算法.第三部分是本文的主要结果,我们提出基于D.C.分解的SDP松弛方法.第四部分给出了基于D.C.分解的SDP松弛和近似算法的数值结果与数值分析.第五部分是全文的总结.