线性互补约束二次规划问题的一个全局算法研究

Quadratic optimization with linear complementarity constraints contains many classic combinational optimization problems, hence it deserves us to study how to solve the problem. It is NP-hard, thus there is no polynomial-time algorithm unless P=NP. In this project, we aim to study how to find a global optimal solution for quadratic optimization with linear complementarity constraints through branch-and-bound method. During the algorithm design, we focus on the following research items: Firstly, how to add valid linear constraints and second order cone constraints based on the characteristics of problem itself; secondly, how to provide an upper bound for the primal problem in order to give a cutting branches condition; and at last how to preprocess the primal problem if the objective function is nonconvex for purpose of improving the efficiency of the algorithm.

线性互补约束二次规划模型包含了许多经典的组合优化问题，因此对该问题求解方法的研究具有很好的应用价值。该问题是一个NP难问题，所以不存在多项式时间算法除非P=NP。本项目旨在探讨在二阶锥松弛的基础上，应用分枝定界算法求解线性互补约束二次规划问题的全局最优解。在算法设计过程中，侧重研究：如何利用问题本身特点在松弛问题中添加有效的线性约束和二阶锥约束，从而提高问题的松弛效果；如何给出原问题的上界求解方法，进而提供减枝条件；对于目标函数也是非凸的情形如何进行预处理，从而提高算法的效率。

本项目研究了线性互补约束二次规划问题与其锥重组问题和锥对偶问题的等价性和严格可行性，分别给出了锥重组和锥松弛问题严格可行和不严格可行的充分条件。在此基础上我们采用椭球和一个二次约束的交集来覆盖原可行域，得到原问题的一个可计算锥松弛问题，从而求得该问题的下界，并采用自适应的手段来不断地改进该覆盖，进而改进锥松弛效果。基于以上理论结果，我们设计了一个锥逼近算法。为了验证算法的有效性，我们选取了两类典型的线性互补约束二次规划问题测试算例，应用锥逼近算法进行求解，并与两种已有的算法进行比较，从计算结果的比较中可以看到我们的锥逼近算法在求解大规模的数值算例时具有很大的优势。受此启发，针对非凸二次约束二次规划问题，我们给出了基于半正定规划和二阶锥规划的混合锥松弛方法，并且设计了有效的分支定界算法。在算法中我们引入了敏感特征向量的思想，从而显著提高了计算效率，该思想也对我们今后的研究很有启发意义。