基于交替凸搜索和凸松弛技术的非凸二次规划新全局算法及其在金融中的应用

Nonconvex quadratic programming (QP) is one of the most challenging continuous optimization problems that has a wide range of applications in many important areas such as engineering, economic and finance. It has become a research topic of the field of optimization in recent years. Though many results have been obtained in the study of theory and algorithm for non-convex QP, finding a global solution or a good approximation solution to large scale non-convex QP remains a challenge in both theory and computation. This project aims to integrate several existing simple and effective optimization techniques such as alternating convex search (ACS) method and convex relaxation, and introduce new linear search and initialization techniques to develop effective global algorithm for nonconvex QP and conduct numeric experiments to evaluate the performance of the new algorithm. We will investigate new ACS method based on biconvex QP reformulation for nonconvex QP, and introduce new notions such as approximate local optimal solution in optimization to establish the local convergence of the proposed algorithm. We will propose the new linear search algorithm based on convex relaxation and then combine the new ACS method with new line search and initialization technique to develop effective global algorithm for QP with a few negative eigenvalues and estimate the complexity of the new global algorithm. We will develop new global algorithms for general nonconvex QP by integrating the new ACS method, convex relaxation, initialization and branch-and-bound framework, investigate convergence and complexity of the algorithm, and compare with the existing global algorithms in the literature. We will investigate the new successive linear optimization (SLO) approach for nonconvex quadratically constrained quadratic programming (QCQP) problems and develop global algorithms for QCQP by combining the new SLO method, convex relaxation and branch-and-bound framework. Finally, we will apply the new global optimization algorithms to the estimate of systemic risk in a financial system, the optimal portfolio liquidation with market impact and the factor-risk-constrained mean-variance portfolio selection.

非凸二次规划(QP)是最具挑战性的连续优化问题之一，在工程和金融中有广泛的应用，是近年优化领域的前沿课题。非凸QP的算法与理论研究迄今已取得丰富的成果，但寻找大规模非凸QP的全局解或近似解在理论和计算上仍是一个挑战。本项目旨在结合一些现有简单实用优化技术如交替凸搜索(ACS)方法和凸松弛并引入新的搜索技巧和初始化技术来设计非凸QP问题有效的全局算法，并进行算法实现。我们将研究非凸QP的基于双凸QP变换的新ACS方法及其局部收敛性；对具有几个负特征值的QP问题，提出基于凸松弛的新线搜索算法，结合新ACS方法、线搜索和初始化技术提出新的全局算法，估计新算法的复杂性；研究一般非凸QP的基于新ACS方法、凸松弛、初始化和分支定界框架的新全局算法及其复杂性；研究非凸QCQP的新SLO方法和基于新SLO方法、凸松弛和分支定界的全局算法。将新算法应用到金融中不确定性系统风险估计问题、最优去杠杆化问题。

非凸二次规划(QP)是最具挑战性的连续优化问题之一，在工程、经济和金融等领域中有广泛的应用，但寻找大规模非凸QP的全局解或近似解在计算上仍是一个挑战。本项目旨在结合现有简单实用优化技术如交替方向法(ADM)、凸松弛方法和初始化技术来设计非凸QP问题有效的全局算法，并进行算法实现。本项目经过四年的研究，基本实现了项目立项时的研究目标，对项目立项时的研究内容进行了重点研究。项目取得了一系列重要的研究成果，发表了7篇SCI学术论文，另有3篇论文正在SCI源刊二审之中，包括国际运筹与优化权威期刊Math.Program.Comput., INFORMs J.Comput., Math.Finance，Comput.Optim.Appl., J.Glob.Optim., J.Optim.Theory Appl.。以下是项目取得的主要研究成果：(1)给出了非凸QP的基于双凸QP变换的新ADM方法，证明了算法收敛于问题的拟近似局部解。(2)对具有几个负特征值的QP问题，结合新ADM方法、凸松弛、分支定界框架和初始化技术提出新的全局算法，建立了新算法的全局收敛性和复杂性。(3)对具有一个负特征值的QP问题(QP1NE)，给出了新ADM算法的复杂性，证明了它收敛于问题的半局部最优解；提出了基于凸松弛的新线搜索算法，给出了其复杂性估计；结合新ADM方法、线搜索算法、凸松弛和初始化技术提出了QP1NE问题的新全局搜索算法，估计了新算法的复杂性。(4)对带凸二次约束的非凸QP问题，证明了新ADM算法收敛于问题的局部最优解；结合ADM方法、半定松弛和disjunctive割技术在分支割框架下提出了新全局算法，建立了新算法的复杂性。(5)对于不确定性下最坏情形线性优化问题，证明它是强NP-难问题；提出了序列凸优化(SCO)算法，证明了SCO算法收敛于变换问题的KKT点；提出了基于SCO方法、凸松弛和分支定界框架的全局算法，建立了算法的全局收敛性和复杂性，并将全局算法应用到金融系统中的不确定性系统性风险估计问题。(6)给出了非凸二次约束QP问题的基于罚方法的非线性SDP松弛，提出了求解非线性SDP松弛的迭代算法和二分搜索算法。(7)对于金融中带有市场影响的最优去杠杆化问题和带有因素风险约束的均值方差投资组合选择问题，给出了基于SCO方法、凸松弛和分支定界技术的新全局算法及其数值实现。