Matrix Decomposition for Scalable Conic Optimization with Applications to Distributed Control and Machine Learning

点击翻译按钮获取中文摘要

Convex optimization has profound impacts on some fundamental problems in control theory, discrete and nonlinear optimization, and theoretical computer science. It is also a fundamental tool to ensure efficient, resilient, and safe operations of many engineering systems, such as power grids, transportation systems, and robotics. Optimization in these areas often takes the form of conic optimization, especially semidefinite programs (SDPs). While SDPs can theoretically be solved using interior-point algorithms with polynomial-time complexity, the large-scale SDPs encountered in real-life applications often require large computational resources in practice. Some recent progress on sparse matrix decomposition has shown striking performance in improving scalability, but all these methods require a common underlying assumption on sufficiently sparse structures. The objective of this project is to develop matrix decomposition methods that are applicable for both sparse and dense conic optimization arising from real-world applications. The theory and algorithms in this project will be applied to optimization problems in distributed control and neural network verification. The project also has an educational and outreach plan with the goal of developing a new interdisciplinary course on conic optimization, involving undergraduate students in research, and outreach to K-12 students and local communities.The central idea of this project is to decompose a large positive semidefinite matrix as a sum of structured ones for which it is easier to impose positive semidefiniteness. The focus is then shifted from optimizing over a large matrix variable to optimizing over a set of computationally simpler variables, thereby promising scalability. The goals of this proposal are as follows: 1) developing block-based graph-theoretic matrix decomposition strategies for sparse and dense conic optimization and investigating their solution quality; 2) designing numerical algorithms based on these matrix decomposition strategies to achieve scalability; and 3) pursuing applications to large-scale problems in distributed control and machine learning. Successful completion of this project will systematically advance matrix decomposition strategies for solving large-scale conic optimization problems. The results of this project will benefit the broader control and optimization communities, with applications in power grids, transportation, and robotics. It is expected that the research progress will promote multidisciplinary collaborations including control theory, machine learning, optimization, and graph theory, among many others.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.