二阶锥约束在非凸二次优化问题中的研究

Nonconvex quadratic optimization model is widely applied in many areas. Since it is in general NP-hard, finding its global optimal solution is very difficult. Relaxing it into a linear conic optimization problem by lifting and linearization is a common approach while studying this problem. To improve the lower bound obtained by the relaxation problem, people usually introduce valid linear constraints and semidefinite constraint. Recent study reveals that the lower bound can be significantly refined by introducing rank-2 second-order constraints into the relaxation. Second-order cone constraints are extensively studied in areas like linear second-order cone optimization, convex quadratic optimization and so on. However, it is less developed in applying such constraints in solving nonconvex quadratic optimization problem. In this study, we will focus on generating new valid rank-2 second-order cone constraints, analyzing their theory in the relaxation problems and designing efficient algorithms based on these second-order cone constraints for solving nonconvex quadratic optimization problems. The main issues that will be studied in this problem include: studying the technique for generating valid rank-2 second-order cone constraints, establishing the theoretic foundations of using second-order cone constraints in relaxation problems, finding polynomial time computable subclass of nonconvex quadratic optimization problems, comparing the new lower bound with existing lower bounds and designing or improving algorithms for solving nonconvex quadratic optimization problems. The study aims to provide new vision and more efficient algorithms for solving nonconvex quadratic optimization problems.

非凸二次优化模型在许多领域都有广泛应用，但其本身是NP难问题，求解较为困难。将其升维后松弛为线性锥优化问题是研究该问题的重要研究方法。为了改善松弛问题的下界，传统上主要采用引入有效线性约束、半定约束等方法。研究表明，在松弛问题中引入秩2-二阶锥约束能有效改善所得下界。二阶锥约束在线性二阶锥优化、凸二次优化问题研究较多，但在非凸二次优化问题中尚处于不充分。本项目拟从秩2-二阶锥约束的生成技术、在新松弛问题中的理论分析、非凸二次优化问题基于秩2-二阶锥约束的算法分析与设计展开研究。具体内容包括：探讨秩2-二阶锥约束生成技术；建立秩2-二阶锥约束在松弛问题中的理论基础；识别多项式可计算子类问题；比较新方法与现有方法所得下界；针对一些非凸二次优化问题的特点设计或改进求解算法，从而为求解非凸二次优化问题提供新的思路与高效算法

非凸二次优化模型在许多领域都有广泛应用，但其本身是NP难问题，求解较为困难。将其 升维后松弛为线性锥优化问题是研究该问题的重要研究方法。为了改善松弛问题的下界，在理论分析上，我们研究了包括二阶锥约束在内的更广泛的锥约束下非凸二次优化问题解的全局最优性条件，引入非负二次函数锥表达形式，从而提供原问题的等价表达以及更紧的松弛形式。在算法设计上，我们探讨了如何利用非负二次函数锥表达形式来逼近非凸二次优化问题，并利用二阶锥约束及其等价形式设计了一系列逼近算法，用来求解不同约束下的非凸二次优化问题。此外，我们还针对目标函数海森矩阵负特征根对目标函数的影响建立相应的等价表达形式和松弛问题，并利用该等价表达式设计了高效的分枝定界算法。我们通过数值实验说明了上述算法相比目前已有算法具有显著地优势。在应用方面，我们研究了基数约束下资产投资组合选择问题，通过一系列等价变化，可以将该问题转为带有二阶锥约束的非凸二次优化问题，从而可以利用前面的结果设计算法进行求解。数值试验表明，我们的算法在求解这类问题时可以快速有效的逼近最优解。