论文部分内容阅读
二次约束二次规划(QCQP)问题可描述系列离散优化和连续优化问题,如组合优化中的最大割、最大团、0-1二次背包问题,经典的线性规划、金融投资领域的马科维茨方差—均值模型等。因此对QCQP问题的研究有着重要的理论和应用价值。当QCQP问题的目标函数及约束函数都是凸函数时,该问题可以结合内点算法在多项式时间内求解,但一般的QCQP问题已被证明为NPH问题。针对QCQP问题目前有多个研究热点,但主要集中在问题的松弛及估界、最优解的判定条件、寻找多项式时间内的可解子问题类、设计全局最优搜索算法。在一般的QCQP问题的研究中,最常用的工具是SDP松弛和拉格朗日对偶理论,此外也常将RLT不等式加入到SDP松弛中,且往往这种处理方式比单独用SDP松弛或RLT不等式的效果都要好。本文首先就QCQP问题的研究背景、意义、目前的研究热点、常用的处理方法进行了简单的介绍,之后本文研究了凸约束下的非凸二次规划问题在不升维下的凸松弛方法,并设计了求解这类QCQP问题全局最优解的算法,接着从理论上给出了算法的收敛性及最坏情形下的迭代次数,同时通过求解一些随机算例将本文算法同SDP松弛下的分支定界算法进行了对比。数值结果表明当问题维度及负特征根个数较少时本文算法具有一定的优势。然后本文研究了有界区域上的一般的QCQP问题,给出了不升维下松弛原问题的方法,并设计了分支定界算法且从理论上论证了算法的收敛性和最坏情形下的迭代次数。最后经过数值实验表明算法在问题维度较低、负特征根较少的情形下迭代次数及运行时间都同SDP松弛下的分支定界算法效果相近,当负特征根增加时本文算法的运行时间会明显增加。本文主要的创新点如下:(1)针对一般的QCQP问题给出了在不升维的框架下用直线代替凹二次函数来松弛原问题问题的方法,并通过理论分析设计了相应的分支定界算法搜索原问题的全局最优解;(2)从理论上证明了本文设计的分支定界算法的收敛性及最坏情形下的迭代次数,并分别给出了本文算法、SDP松弛下的分支定界算法以及Baron的数值实验结果且对结果进行了对比分析;