非负二次函数锥规划研究

非负二次函数锥规划是现有的共正锥规划的扩展，是锥规划研究的一个新的研究方向,其研究将为经典的非凸二次规划问题提供新的理论与算法，并从中得到比传统研究方法更深刻的结果。首先，本项目将深入研究非负二次函数锥的理论性质，并根据其性质，设计可计算的内逼近锥，最终将可计算逼近锥应用于非负二次函数锥规划问题的逼近算法上。其次，将可计算内逼近锥方法应用在典型二次规划和组合优化等问题，进一步改进半定规划等方法的下界估计效果。最后，根据问题本身的结构特征，找到针对某一类问题表现效果更佳的内逼近锥，以更好的计算效果逼近共正规划问题，以及非负二次函数锥规划问题。

本项目主要研究二次约束二次规划（QCQP）问题的性质及其计算方法，主要研究手段是通过线性锥规划理论的研究，给出QCQP问题的线性锥规划等价模型，最优性条件和求解全局最优解或近似全局最优解的算法及收敛性分析。主要成果如下:. 第一，建立了正则对偶方法在最优化领域应用的数学理论。针对QCQP问题，我们利用Lagrange对偶的观点，给出了正则对偶方法的理论结果和在一些优化问题中的应用，在理论上给出了利用正则对偶方法如何构建QCQP的可行解，全局最优解的最优性条件和构造全局最优解的计算方法。. 第二，给出了用非负二次函数锥判断全局最优解的一个充分条件。通过一个非负二次函数锥的表示，我们给出一个QCQP可行解为全局最优解的一个充分条件。这一结果为我们首次发现，并一直应用在我们后续的研究问题中。由于判断一个矩阵是否属于这个非负二次函数锥是一个NP完全问题，后期的工作给出了这个锥的可计算近似表示。. 第三，系统给出非负二次函数锥的椭球覆盖和二阶锥覆盖逼近的计算理论与算法。在最优目标值相同的观点下，QCQP问题可以等价地表示成一个定义域在非负二次函数锥上的线性锥优化问题。因该锥的难度而无法多项式时间求解这个线性锥优化问题，我们成功地用椭圆或二阶锥覆盖可行解区域的系统方法，求解到任意逼近QCQP最优目标值的近似全局最优解，并给出了系统的理论。. 近些年的工作已整理并完成专著《线性锥优化》，2013年由科学出版社出版基金资助出版。课题负责人多次在国际国内会议上报告与本课题相关的研究成果。据不完全统计，大会邀请报告次数超过6次，标注自然科学基金资助文章19篇、专著1部。在与本课题时间重合期间培养的研究生（已毕业）包括：4名博士生，6名硕士生。