非凸二次约束优化问题的全局算法研究及其在信号处理中的应用

Nonconvex quadratic constrained programming model is one of basic and hard nonlinear constrained programming models. Research on its global algorithms is an important research branch of nonlinear constrained programming. In 2013, Burer et al have proven that application of second-order cones to some special noncovex quadratic constrained programming can be delete copletely the positive dual gap of the original instances. This shows potential power of second-order cones applied to nonconvex quadratic constrained programming. However，since now there is preliminary research on second-order cone relaxation of nonconvex quadratic constrained programming, a lot of theoretic and applied problems need to be studied. In this proposal it is discussed that how and where does the second-order cone relaxation work validly and how to construct the second-order cones. Then we will design corresponding algorithms for some nonconvex quadratic constrained programming models. Furthermore complex second-order cone relaxation and corresponding algorithm design for complex quadratic constrained programming are studied.

非凸二次约束二次优化问题属于非线性约束规划中的基础性和难点性的问题之一，对它们的全局算法研究是非线性约束规划的一个重要研究方向。 Burer等人在2013年证明了使用二次锥松弛技术能够完全消除某些非凸二次约束优化问题的对偶间隙从而获得原问题的全局最优解，这些结果显示了二次锥松弛技术在非凸二次约束优化问题的全局算法上的巨大应用潜力。有关这方面的研究才刚刚兴起，许多理论性和应用性问题亟待解决。本项目拟通过对非凸二次约束优化问题的二次锥松弛的作用机理、作用范围、构造方法展开研究，建立起二次松弛技术求解非凸二次优化问题的理论基础，为若干重要的非凸二次优化问题提供更加有效的全局算法。此外，复数二次约束优化问题在信号处理领域具有广泛应用，本项目拟同时对二次锥松弛技术在复数二次约束优化问题的应用机制展开研究，并将相关研究结果应用到信号处理的优化模型的算法设计中。

本项目研究主要分为最优化理论与算法研究、最优化方法在信号处理中的应用研究两个部分。. 在最优化理论与算法研究中，我们聚焦于非凸二次约束优化问题全局最优解的理论与算法研究。非凸二次约束优化问题是约束优化领域中的基础性和难点性问题。当一个非凸二次约束优化问题实例具有正的对偶间隙时，一般将它称为难解情况，难解情况下全局最优解很难求得，即使求得也往往无法证明它就是全局最优解，所以针对难解情况的研究成果非常少。在本项目中，我们针对带有两个线性约束的信赖域子问题和CDT问题的难解情况展开了研究，在二次锥松弛约束在这两类二次约束优化问题的作用机理上取得了突破，获得如下主要结果：第一，首次在理论上证明了通过添加一个二阶锥约束可以缩小广义CDT问题的对偶间隙，并给出了该添加的二阶锥约束可以缩小对偶间隙所需要满足的充要条件。第二，证明了几类特殊的CDT问题可以通过添加一个二阶锥约束完全消除对偶间隙（比如所有二维CDT问题），我们对目前为止公开发表论文中出现的所有有对偶间隙的二维经典CDT实例进行了数值计算，数值结果表明通过我们的二阶锥重塑模型的确完全消除了它们的对偶间隙。第三，对带有两个线性约束的广义信赖域子问题，给出并证明了它的二阶锥重塑模型可以完全消除对偶间隙的充要条件，而Ye-Zhang在2003年的相关结果以及Burer等人在2013年及2015年的相关结果都包含于该充要条件下。进一步，我们证明了两个线性约束相交情况下信赖域被分割成四个区域时至少有三个区域是可以通过二阶锥重塑技术来完全消除对偶间隙的。上述部分结果曾获得2017年北京运筹学会年会青年优秀论文一等奖。. 在最优化方法在信号处理的应用研究中，我们分别对声音定位问题、光子晶体非线性效应增强最优结构问题、MIMO无线通信网络的传输速率最大化问题及传输安全问题等进行了高效算法设计。这些应用性问题多数都是非凸优化问题，具有一定的难解性。我们给出的一些新算法在精度或计算效率上优于原有算法，数值实验也表明了这些算法是有效的。