混合0－1非凸二次约束二次规划问题的理论与算法及其应用研究

The mixed 0-1 non-convex quadratically constrained quadratic programming (QCQP) problem, is the current frontier and hot research problem in the international optimization, information and wireless communication, and many other related areas, which is also the key problem in both the discrete optimization and continuous optimization research direction. The new development on this problem will have important theoretic value and wide applications. There have been many good results on QCQP problem with only continuous variables, however, this is not the case in the mixed 0-1 QCQP problem. In this project, we focus on the following several important problems: 1) Construct more tight convex relaxation problem for MBQCQP problem, which should also be easy to solve. Moreover, since the semi-definite programming problem can be equivalently transformed to be a special matrix eigenvalue optimization problem, and by reasonable model transform, new first order method or other fast methods will be developed for solving new relaxation problem. 2) By using the inner structure of the new relaxation problem, we design new approximation algorithm based on new rounding method, and prove the approximation bound for the relaxation problem; Moreover, we develop new fast convex approximation algorithm to solve the original problem, and build iteration complexity for it. Furthermore, we propose and analyze a Hierarchy of SDP Relaxations method for solving MBQCQP problem in complex field. 3) For the several new arising key problems in information and wireless communication areas, we build the MBQCQP model for them and analyze their corresponding complexity; we develop new approximation algorithm and distributed algorithm for solving the related large scale problems. This project will not only enrich the theory and algorithm for MBQCQP problem, promote the blending of discrete optimization and continuous optimization, but also provide new theory and new method in information and wireless communication field.

混合0-1非凸二次约束二次规划(MBQCQP)问题是国际最优化、信息通信等很多领域的研究前沿和热点，是离散优化与连续优化交叉方向的核心问题，对其研究有重要理论价值和广泛应用前景。国际上纯连续变量QCQP问题的研究已取得很好的成果，但对MBQCQP问题的研究比较欠缺。本项目主要研究：1)MBQCQP问题更紧的且易于求解的凸松弛,并以半定规划可等价转化为矩阵特征值优化问题为切入点，设计快速求解松弛问题的一阶方法。2)利用新松弛问题设计新的近似算法，证明近似界；进一步构造系列凸逼近快速算法，建立迭代复杂性；提出求解复数域上MBQCQP问题的层级SDP逼近方法。3)建立信息通信领域几类新兴核心问题的MBQCQP模型，分析复杂度；设计新的近似算法和分布式算法求解相关大规模问题。本项目的实施将丰富MBQCQP问题的理论与算法，促进离散优化与连续优化的交叉与融合，还将为信息通信等领域提供新理论与新方法。

混合0-1非凸二次约束二次规划(MBQCQP)问题是国际最优化、信息通信等很多领域的研究前沿和热点，对其研究有重要理论价值和广泛应用前景。. 对于一般的MBQCQP问题，本项目研究了半定规划(SDP)松弛问题紧的充分条件，以及存在有限近似界的充分条件。对于在信号处理和无线通信应用中带有特殊结构的MBQCQP问题，结合问题本身的具体结构，构造更紧的凸松弛，甚至非凸或者非光滑松弛问题。设计求解较大规模凸松弛问题的快速一阶优化算法。对带有特殊结构的MBQCQP问题，深入挖掘隐含结构，量身定制特殊的快速求解方法；在此基础上，设计求解新的凸松弛问题的更为快速有效的一阶优化算法,分析其收敛性和迭代复杂性。. 本项目利用实际问题的具体结构，比如联合准入控制与能量传输问题中离散变量和连续变量的潜在可分性，设计新的凸松弛问题的舍入方法，构造原问题的近似解，得到新的近似算法。针对问题的不同结构，建立解的近似比或近似界等相关理论性质，为算法提供理论保障；并依据分析得到的近似界等理论结果，构造新的系列凸逼近方法来快速求解原问题。. 对于信息通信领域中几类新兴的重点研究问题，包括联合准入控制与beamforming问题等问题，一方面，从问题实际结构出发，建立合适的MBQCQP模型，并分析模型的复杂度，证明其是否为NP-难问题，从本质上刻画出问题求解的难度、揭示问题的内在结构，为设计算法提供必要的理论指导；另一方面，利用前面的结果，结合问题本身的结构，构造更紧的凸松弛问题，并设计高效快速求解的近似算法，进行近似比或近似界等相关理论分析，设计相应的分布式算法，考虑其分布式应用。推广这些算法用于求解信息通信等领域中的较大规模问题。. 项目团队基本按原计划开展了研究，取得了预期的研究成果，超额完成了预期的考核指标。本项目的实施将丰富MBQCQP问题的理论与算法，促进离散优化与连续优化的交叉与融合，还将为信息通信等领域提供新理论与新方法。