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

凸优化对控制理论、离散和非线性优化以及理论计算机科学中的一些基本问题有着深远的影响。它也是确保许多工程系统（如电网、运输系统和机器人）高效、有弹性和安全运行的基本工具。这些领域的优化通常采用二次优化的形式，特别是半确定规划（sdp）。虽然理论上可以使用具有多项式时间复杂度的内点算法求解sdp，但实际应用中遇到的大规模sdp在实践中往往需要大量的计算资源。最近在稀疏矩阵分解方面的一些进展在提高可伸缩性方面显示出惊人的性能，但是所有这些方法都需要对足够稀疏的结构有一个共同的基本假设。这个项目的目标是开发矩阵分解方法，适用于稀疏和密集的二次优化产生的现实世界的应用。本课题的理论和算法将应用于分布式控制和神经网络验证中的优化问题。该项目还有一个教育和推广计划，目标是开发一门新的关于经济优化的跨学科课程，让本科生参与研究，并向K-12学生和当地社区推广。这个项目的中心思想是将一个大的正半定矩阵分解为一个结构化矩阵的和，这样更容易施加正半定。然后将重点从对大型矩阵变量的优化转移到对一组计算上更简单的变量的优化，从而保证可伸缩性。本文的目标是：1)开发基于分块的稀疏和密集二次曲线优化图论矩阵分解策略，并研究其解的质量；2)基于这些矩阵分解策略设计数值算法，实现可扩展性；3)在分布式控制和机器学习中寻求大规模问题的应用。本课题的成功完成将系统地推进求解大规模二次优化问题的矩阵分解策略。该项目的结果将有利于更广泛的控制和优化社区，应用于电网，交通运输和机器人。预计研究进展将促进多学科合作，包括控制理论，机器学习，优化和图论等。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.