非凸二次约束二次规划的隐凸性与近似算法

Quadratic constrained quadratic programming is a hot-spot topic in the field of operations research. It has widespread applications. The proposal will present the hidden convexity and approximation algorithms for nonconvex quadratic constrained quadratic programming. Firstly, we will propose a new second-order cone programming relaxation for quadratic constrained quadrtic programming (QCQP). Then we establish a new sufficient condition to reveal the hidden convexity of (QCQP). And we will show different applications in some specific problems. Secondly, we plan to show the computation complexity of Chebyshev center of the intersection of balls. With the help of a newly introduced linear programming relaxation, we propose an approximation algorithm to solve it. Also, we will detect the sufficient conditons of the polynomial solvability for the problem. Besides, some extensions will be also included. Thirdly, we will propose a unified on-line version of Tammes problem, Fekete problem, Fejes Toth problem and other problems. Then we give an analysis on the optimal approximation ratio between the on-line and off-line problems. Through the research of the above problems, the proposal will promote the development of quadratic constrained quadratic programming and its application.

二次约束二次规划是最优化领域最具有代表性的分支之一，具有十分广泛的应用。 本项目围绕非凸二次约束二次规划的隐凸性理论和近似算法两方面展开研究。首先，针对一般的二次约束二次规划模型，提出一个新的二阶锥规划松弛。根据二阶锥规划松弛建立二次约束二次规划具有隐凸性的充分性条件，并将该结果应用到一些具体问题上。第二，本项目希望给出球交集的切比雪夫中心问题的计算复杂度。基于新的线性规划松弛，提出近似算法求解球交集的切比雪夫中心，并探索该问题是多项式时间可解的充分性条件。此外，将球交集的切比雪夫中心问题进行推广。第三，从Tammes问题的“线上”版本出发，进一步融合Fekete问题、Fejes Toth问题等，提出一个统一的“线上”版本问题，并寻求“线上”与“线下”问题的最优近似比。通过对上述问题的研究，本项目将推进二次规划的发展和应用。

本项目主要针对一类二次约束二次规划问题进行了研究，分别从隐凸性理论和近似算法两方面展开。首先，在提出新的二阶锥规划松弛的前提下，给出了一般非凸二次约束二次规划具有隐凸性的充分性条件，并将结果应用到具体问题上来。第二，完成了多球交集的切比雪夫中心问题的相关研究，分析了该问题的计算复杂度，并且设计出了求解这类问题的近似算法。第三，对多属性决策问题的相关方法进行了研究。最后，针对球面点散布这类经典的数学问题进行了相关研究，设计出求解这类问题的近似算法并给出近似比分析的结果。通过以上研究，本项目刷新了一些理论性结果并且推进了二次规划的发展。