Sparse Solutions to Classes of Quadratic Programming Problems: Theoretical Fundamentals, Solving Strategies and Applications

该奖项的研究目标是描述图像处理和投资组合选择等应用程序中出现的优化问题的稀疏解决方案。其主要目标是发展一种新的理论框架，它将建立一类棘手和非凸二次优化问题的稀疏最优解或近似解的存在性，并推导出基本优化问题最稀疏最优或近似解的稀疏性的精确概率特征。这些理论结果将通过全面的数值实验得到验证。所开发的最优解的稀疏性将被用来为某些类型的二次优化问题设计可证明良好的高效算法。该项目中开发的新算法将进行测试，并与文献中现有的传统方法进行比较。如果成功，该项目不仅将改变人们对稀疏解的理解，帮助解决投资组合理论和优化中几个长期悬而未决的问题，而且还将为解决目前计算困难的一类非凸二次优化问题提供有效工具。通过该项目开发的工具将在通过新的多样化技术降低投资风险和从不同数据来源提取有意义的模式方面具有实际好处。

The research objective of this award is to characterize sparse solutions to optimization problems arising from applications such as image processing and portfolio selection. The primary goal is to develop a new theoretical framework that will establish the existence of sparse optimal or approximate solutions to classes of intractable and non-convex quadratic optimization problems and derive precise probabilistic characterization of the sparsity of the sparsest optimal or approximate solutions to the underlying optimization problem. These theoretical results will be validated via comprehensive numerical experiments. The exploited sparsity at the optimal solution will be used to design provably-good efficient algorithms for certain classes of quadratic optimization problems. The new algorithms developed in the project will be tested and compared with existing conventional approaches in the literature. If successful, the project will not only transform understanding of sparse solutions and help solve several long-standing open problems in portfolio theory and optimization, but also provide effective tools for solving classes of non-convex quadratic optimization problems that are at present computationally intractable. The tools developed through the project will have practical benefit in lowering investment risk via novel diversification techniques and in extracting meaningful patterns from different data sources.