Low-Complexity Algorithms for Sparse Conic Optimization with Applications to Energy Systems and Machine Learning

University Of California-Berkeley, Berkeley CA

Investigators

Abstract

The development of fast numerical algorithms is crucial for large-scale optimization problems arising in a wide range of areas, such as power systems, machine learning, control theory, transportations and operations research. The main challenge is the inability of the existing methods in handling the nonlinearity (non-convexity) of many real-world problems. Conic optimization is able to solve these nonconvex problems to global optimality in a rigorous and principled manner through the notion of convexification. Despite a mature theory on convexification, the practical use of conic optimization remains limited since this technique greatly increases the dimension of a problem. It is common amongst researchers to view conic optimization as a powerful theoretical tool that is inaccessible for real-world applications, due to the lack of efficient numerical algorithms for conic optimization. The objective of this proposal is to design low-complexity algorithms for conic optimization that directly exploit the structure of a give problem to reduce the complexity. The outcomes of this project will lead to wide-ranging societal impact in all areas of design, analysis, operation, and control in real-world systems. This project has several outreach and educational activities, such as participation in multiple programs for students from underrepresented groups, fostering undergraduate research, and organizing tutorial sessions and workshops. This project develops numerical algorithms for sparse conic optimization by exploiting problem structure, with a particular emphasis on sparse semidefinite programs. The proposed approach uses the notion of tree decomposition to solve sparse problems in near-linear time and linear memory. The main objectives of this proposal are as follows: 1) to identify graph-theoretic structures that control the computational complexity of sparse conic optimization; 2) to design numerical algorithms based on this graphical analysis to achieve best complexities; 3) to develop parallel and distributed versions of these algorithms for real-time computing. This is an interdisciplinary project theoretically underpinned by graph theory, numerical algorithms, matrix completion, conic optimization, low-rank matrix optimization, and algebraic geometry, and finding applications in power systems and machine learning. The proposed project will apply the designed numerical algorithms to nonlinear power optimization problems with tens of thousands of parameters to demonstrate its impact. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.