自适应线性锥优化算法在非凸二次约束二次优化问题中的研究

Nonconvex quadratically constrained quadratic programming (QCQP) problem is in general NP-hard, hence, it is difficult to find its global optimal solution. Using the cone of nonnegative quadratic functions, any QCQP problem can be equivalently represented as a linear conic programming problem. However, this linear conic programming problem usually can not be solved in polynomial-time. Thus we use some computable cones to do an inner and/or outer approximation to the cone of nonnegative quadratic functions. The optimal value of the corresponding computable problem will provide an upper and/or lower bound of the QCQP problem. This leads to a totally new way to study the QCQP problem. However, such study is has not been well-developed yet. In this proposal, we aim to analyze the extreme points of the cone of nonnegative quadratic functions to find more computable domains, build new ways to approximate the cone of nonnegative quadratic functions by using the special structure of computable cones, design adaptive linear conic programming algorithms with redundant constraints and polar cuts, compare the new algorithms with the known methods and apply the new results to solve portfolio management problems. Our main objective is to provide new ideas and more efficient algorithms for solving the QCQP problem.

非凸二次约束二次优化问题一般情况下是NP难问题，其求解较为困难。利用非负二次函数锥，任意非凸二次约束二次优化问题均可等价转化为一个线性锥优化问题。但通常此问题是不可多项式时间计算的，需通过可计算锥对非负二次函数锥进行内外逼近，从而得到一个可计算的线性锥优化问题为原问题提供上下界估计值。这就为求解非凸二次约束二次优化问题提供了全新的角度和思路。当前该方面的研究尚处于起步阶段。本项目将通过分析非负二次函数锥极点的性质探寻更多可计算的特殊定义域，根据可计算锥自身的结构特点建立逼近非负二次函数锥的新方式，分析一些特定非凸二次约束二次优化问题中自适应策略的理论性质，配合冗余约束和有效极切割约束设计自适应线性锥优化新算法，对比新算法与已知算法的效果和计算效率，将新算法应用于资产投资领域，为非凸二次约束二次优化问题的求解的提供新的思路和高效算法。

非凸二次约束二次优化问题属于优化研究领域中的基础问题，有着广泛的应用。其问题的求解或较高精度的逼近在理论和实际上都有着非常重要的意义。通过这三年对自适应线性锥优化算法在非凸二次约束二次优化问题中的系统研究，本项目预期研究目标均已顺利完成。本项目从线性锥优化的这一全新角度来研究了非凸二次约束二次优化问题的求解，由代数结构入手探寻了更多可计算的特殊定义域，建立了用可计算锥逼近非负二次函数锥的新方式，分析了自适应策略在某些特定问题中的理论性质，设计了基于线性锥优化的自适应新算法并将相应成果运用到了诸多领域，如投资组合管理、天线信号检测、支持向量机机器学习、金融拒绝推断和保险破产预测等等。本项目为非凸二次优化问题未来的研究和应用提供了新的方向、思路、理论和计算依据。