锥规划在非凸二次优化中的应用研究

Non-Convex quadratic optimization has wide applications in communication design, power generation scheduling, financial and statistical optimization, etc. However, its difficulty confines its applicability, making it one of the hot topics in the field of optimization. This project aims at utilizing easy conic programming problems to uncover hidden convex structures in non-convex quadratic optimization problems, reduce the problem difficulty and push forward the development of theories and solution methods for non-convex quadratic optimization problems. For sub-problems of non-convex quadratic optimization with different constraint structures, we utilize conic programming to design new models and algorithms from three different perspectives: transformation, simplification and approximation. We study the generalized and extended trust region sub-problem and derive its equivalent second-order cone programming formulation without the assumptions required in the literature. We study the semi-continuous or probabilistically-constrained quadratic programming problems and by analyzing the discrete constraint structures, we use semidefinite programming to search for the equivalent mixed-integer quadratic programming formulation that is most suitable for brand-and-bound algorithms. We study general quadratic optimization with non-convex quadratic constraints and by decomposing and relinking non-convex quadratic constraints, we propose tighter semidefinite programming relaxations. We use real financial data to conduct numerical comparison experiments for our models and algorithms in order to test the effectiveness of our new methods.

非凸二次优化问题在通讯设计、发电调度、金融以及统计优化等领域中有着广泛的应用，但是求解的困难制约了其适用范围，使其成为最优化研究领域的热点问题。本项目旨在研究利用容易求解的锥规划问题，发掘非凸二次优化问题中隐含的凸结构，降低非凸二次优化问题的求解难度，推进非凸二次优化问题的相关理论与求解方法的发展。针对带有不同约束结构的非凸二次优化问题及其子问题，利用锥规划从转化、简化与逼近三个不同角度设计新的模型与算法。研究广义与延伸信赖域子问题的等价二阶锥规划形式，去除文献中已有方法所需要的前提条件；研究带半连续变量的二次优化问题和带概率约束的二次优化问题，利用约束条件的离散结构对目标函数进行凸化，通过半正定规划寻找连续松弛下界最紧的等价模型；研究一般带非凸二次约束的二次优化问题，利用非凸二次约束的分解与耦合，提出更紧的半正定规划松弛。利用真实金融数据对模型与算法进行数值对比实验，实证新方法的有效性。

非凸二次优化问题在通讯设计、发电调度、金融以及统计优化等领域中有着广泛的应用，但是求解的困难制约了其适用范围，使其成为最优化研究领域的热点问题。本项目研究利用容易求解的锥规划问题，发掘非凸二次优化问题中隐含的凸结构，降低非凸二次优化问题的求解难度，推进了非凸二次优化问题的相关理论与求解方法的发展。针对带有不同约束结构的非凸二次优化问题及其子问题，利用锥规划从转化、简化与逼近三个不同角度设计新的模型与算法。推导了广义与延伸信赖域子问题的等价二阶锥规划形式，去除文献中已有方法所需要的前提条件；针对带半连续变量的二次优化问题和带概率约束的二次优化问题，利用约束条件的离散结构对目标函数进行凸化，通过半正定规划寻找到连续松弛下界最紧的等价模型；针对一般带非凸二次约束的二次优化问题，利用非凸二次约束的分解与耦合，提出更紧的半正定规划松弛。利用真实金融数据对模型与算法进行数值对比实验，证实了新方法的有效性。