锥优化方法在含有线性互补约束的二次规划问题中的研究

Quadratic optimization with linear complementarity constraints contains many classic combinational optimization problems, hence it deserves us to study the solving algorithms. It is NP-hard, even finding a feasible solution is difficult. There is no interior point contained in the feasible domain, thus this increases the problem solving difficulty. Common approaches for deriving a lower bound for this problem are semidefinite relaxation and completely positive cone relaxation. The thought of conic programming over the cone of nonnegative quadratic functions provides a new conic relaxation method. In this proposal, the study aims to design reasonable conic relaxation over the cone of nonnegative quadratic functions for the problem, add valid second-order cone constraints to improve the conic relaxation, and then provide new visions and more efficient algorithms for the problem. The specific research topic in this proposal includes: discussing the strict feasibility of conic programming over the cone of nonnegative quadratic functions, building the elaborate cover for the feasible region in order to design a conic relaxation over the cone of nonnegative quadratic functions, adding valid second-order cone constraints to the conic relaxation for improving the lower bound, designing a branch-and-bound algorithm based on the set covers and applying the new algorithm to solve practical issues in economics and signal processing field.

含有线性互补约束的二次规划模型包含了许多经典的组合优化问题，因此对该问题求解方法的研究具有很好的应用价值。该问题是一个NP难问题，即使找到它的一个可行解也是很困难的。此外，该问题的可行域不包含内点，这也加大了求解难度。传统方法主要使用半正定松弛以及共正锥松弛等方法获得下界，而非负二次函数锥规划思想的提出为该问题提供了新的锥松弛手段。本项目旨在设计原问题合理的非负二次函数锥松弛，并在此基础上通过添加有效的二阶锥约束来进一步改进锥松弛效果，从而为该问题提供新的求解思路和高效的计算工具。具体内容包括：对非负二次函数锥规划问题的严格可行性进行深入探讨；为原问题可行域构造精细覆盖从而设计原问题的非负二次函数锥松弛；在锥松弛问题中添加有效的二阶锥约束来改进下界；设计基于集合覆盖的分支定界算法；将新算法应用到经济、信号处理等领域的实际问题中去。

线性互补约束二次规划问题属于优化领域的基础问题，具有广泛的应用前景，因此对该问题求解的深入研究具有理论和实际意义。在项目研究过程中，我们将DC分解理论和两个半正定矩阵同时对角化技术有效地融合于锥松弛方法的设计过程中，从而针对线性互补约束二次规划问题设计了高效的锥松弛方法，数值实验表明基于同时对角化的锥松弛能够有效地平衡下界质量和计算复杂度，进而设计了该问题的全局算法。在此理论研究基础上，我们将相应成果运用到非凸二次约束二次规划问题的求解过程中，如广义信赖域问题、凸二次规划非凸二次规划问题，复数二次约束二次规划问题等。本项目为线性互补约束二次规划问题和非凸二次规划问题的未来研究和应用提供了新的思路和视角。