大规模稀疏二次规划问题的求解算法及应用

In recent years, with the development of big data, there has been an increased interest in solving optimization problems that restrict or minimize the number of nonzero elements of the solution vector. This project aims to study the L0- and Lp (p≥1)-regularized quadratic program and its applications in financial investment and supervised machine learning. In the existing literature, there has not been any study on such sparse optimization model. The L0-norm constraint can accurately control the sparsity of the solution while the Lp-norm constraint can enhance the stability of the solution. Therefore, the proposed model has wide applications in practice. For instance, in portfolio selection, a key problem in financial investment, the L0-norm constraint is adopted to control the number of invested assets and hence the trading and management costs; the L1-norm and L2-norm constraints are used to stabilize the optimal strategy and reduce the portfolio leverage risk and volatility risk. This study includes developing theoretical framework and computational algorithm based on a combination of successive convex approximation and augmented Lagrangian method for solving the L0-norm and Lp-norm constrained quadratic program, and analyzing effects and interplay of the L0-norm and Lp-norm. In particular, the design of the algorithm incorporates the model's data structure for the purpose of efficiently solving large-scale practical problems and ensuring the quality of the solution. We hope the results of this project can facilitate further studies on the theories and applications of regularized quadratic programs, and help with decision-making in financial investment as well as feature selection in machine learning.

近年来随着大数据的发展，求解稀疏优化问题愈发受到关注。本项目重点研究同时含有L0和Lp（p≥1）范数约束的稀疏二次规划问题及其在金融投资和监督机器学习中的应用。现有文献中还未有对该优化模型的研究。L0范数项能够精确控制解的稀疏性，Lp范数项能够加强解的稳定性，因而该模型有广泛的实际应用。例如，在金融领域的经典问题“投资组合选取”中利用L0正则项控制投资的资产数目从而控制资产的交易和管理成本，利用L1和L2正则项获取稳定的投资策略并降低杠杆风险与波动率风险。本项目的研究内容主要包括构造基于序列凸近似和增广拉格朗日方法的求解这类问题的理论框架和数值算法，并从理论和实际两个方面分析L0和Lp范数约束的作用。其中算法设计着重于结合问题的数据结构从而可以高效地求解大规模实际问题并保证解的质量。本项目的研究成果对稀疏二次规划的理论研究和算法设计、金融投资决策的制定及机器学习中特征的筛选有重大促进意义。

近年来随着大数据的发展，如何高效、精准地求解稀疏优化问题愈发受到关注。本项目重点研究含有l_0和l_p (p≥1)范数的稀疏二次规划问题及其在金融投资和风险管理领域的应用。创新性研究成果集中在：一，基于高级优化理论分析最优解的解析性质，探讨正则项、模型参数和约束等对最优解和最优值的影响；推导最优解的l_0范数上界并且刻画l_0和l_p范数具有同向和反向作用的条件。二，设计具有普遍适用性的求解含正则项的二次规划和分布式鲁棒优化模型的算法；开发l_1重加权算法和次梯度-凸差算法近似求解大规模非凸问题；将近似解分解为除l_0项的最优解和稀疏调整项两部分，解析l_0项的作用；分析近似解的质量，其目标函数值相较分支定界法的最优解平均相对误差小于0.1%；四，利用实际数据测试模型和算法的效果，从数值和实证角度进一步验证正则项的作用以及在实际应用中对于投资组合表现的提升。目前文献中主要从算法和仿真实验角度关注稀疏优化模型，对于其最优解或近似解的解析性质的讨论还很有限。本项目获取半闭式解以便更加直观地了解正则项和模型其他参数对于最优解的作用；从理论角度分析迭代算法近似解的特点及其与最优解的联系，为算法的适用性和有效性提供理论指导和支撑；通过实证结果充分说明加入正则项可以提升模型表现。本项目的理论和计算结果为建立符合实际的数学规划模型和制定最优决策提供指导。