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.
