0-1二次约束二次优化问题的非凸二次松弛

0-1 quadratically constrained quadratic programming problem (0-1 QCQP in short) is widely applied in many areas. But the problem itself is NP-hard in general and it is difficult to find its optimal solution. A common approach for deriving a lower bound for 0-1 QCQP is relaxing it into a convex programming problem, such as linear program, second-order cone program or semi-definite program. However, the nonconvex relaxations are not extensively studied in the current literature. In this proposal, we will focus on deriving nonconvex quadratic relaxations for 0-1 QCQP, analyzing their theoretical properties and designing algorithms based on these noncovex quadratic relaxations. The specific research topics in this proposal include: finding more polynomial-time solvable 0-1 quadratic programming problems, deriving nonconvex quadratic relaxations by quadratic reformulation method, comparing the new lower bounds obtained from nonconvex quadratic relaxations with those from convex relaxations, building the approximation strategies for 0-1 QCQP, exploring new techniques for generating valid inequalities and analyzing their effects on nonconvex quadratic relaxations, designing branch-and-bound algorithms based on nonconvex quadratic relaxations and applying the new algorithms to solve portfolio selection problems. The study aims to provide new visions and more efficient algorithms for 0-1 QCQP problem.

0-1二次约束二次优化问题在许多领域都有广泛应用，但该问题本身是NP难的，其求解较为困难。传统方法主要使用凸优化问题，如线性优化，二阶锥优化，半正定优化等，作为松弛问题以获得下界，但是使用非凸优化作为松弛问题的研究方法尚未被深入探讨过。本项目主要研究0-1二次约束二次优化问题的非凸二次松弛，拟从非凸二次松弛的构造方法、理论性质以及基于非凸二次松弛的算法设计展开研究。具体内容包括：寻找更多的多项式时间可解的0-1二次优化问题；利用二次重构方法构造非凸二次松弛；比较非凸二次松弛与凸松弛所得下界；设计非凸二次松弛对0-1二次约束二次优化问题的逼近策略；探索有效不等式的新生成技术及其对非凸二次松弛的影响；设计基于非凸二次松弛的分支定界算法，并将新算法运用到投资组合选择问题中，为0-1二次约束二次优化问题提供新的求解思路和高效的计算工具。

0-1二次约束二次优化问题是数学优化领域中的基础研究问题，在现实中有着广泛的应用。其全局优化算法在理论和实际上都有着非常重要的意义。通过这三年对0-1二次约束二次优化问题的松弛和全局求解方法的研究，本项目预期目标大部分顺利完成。本项目从寻找0-1非凸二次优化问题的可解子类出发，研究了多种特殊形式下的非凸二次优化问题，发现了用以提升下界质量的各种有效不等式和极割，开发了自适应策略以提升算法的收敛速度，设计了基于可计算非凸二次松弛和半正定松弛的分支定界算法。此外，我们将新算法运用到项目组合选择问题，非线性支持向量机二元分类问题以及机组组合问题，并取得了良好的效果。本项目为离散约束下的二次优化问题提供了新的理论，求解思路和工具。