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.