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.