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

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

项目编号： No.11471052

项目类型： 面上项目

立项/批准年度： 2015

项目学科： 数理科学和化学

项目作者： 艾文宝

作者单位： 北京邮电大学

项目金额： 70万元

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

中文关键词： 非线性规划；非凸二次规划；二次锥；广义信赖域；信号处理

英文摘要： 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.

英文关键词： nonlinear programming;nonconvex quadratic programming;second-order cone;extended trust region;signal processing