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

用于可扩展圆锥优化的矩阵分解及其在分布式控制和机器学习中的应用

• 批准号: 2154650
• 负责人: Yang Zheng
• 金额: $ 35万
• 依托单位: University of California-San Diego
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2022
• 资助国家: 美国
• 起止时间: 2022-08-15 至 2025-07-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2154650&HistoricalAwards=false
• 关键词: Matrix; Decomposition; Scalable; Conic; Optimization

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.

凸优化对控制理论，离散和非线性优化以及理论计算机科学的某些基本问题产生了深远的影响。它也是确保许多工程系统（例如电网，运输系统和机器人技术）的高效，弹性和安全操作的基本工具。这些领域的优化通常采用圆锥优化的形式，尤其是半决赛程序（SDP）。虽然理论上可以使用具有多项式时间复杂性的内点算法来解决SDP，但在现实生活应用中遇到的大规模SDP通常在实践中通常需要大量的计算资源。稀疏基质分解的最新进展显示在提高可伸缩性方面的性能惊人，但是所有这些方法都需要对足够稀疏结构的共同基础假设。该项目的目的是开发矩阵分解方法，这些方法适用于由现实世界应用引起的稀疏和密集圆锥优化。该项目中的理论和算法将应用于分布式控制和神经网络验证中的优化问题。该项目还制定了一项教育和宣传计划，其目的是开发有关圆锥形优化的新课程，涉及本科生的研究，并向K-12学生和当地社区进行宣传。该项目的核心想法是分解一个较大的积极的半决赛矩阵，以使其易于构成阳性的结构性超级阳性。然后将焦点从对大型矩阵变量的优化转变为对一组计算更简单变量的优化，从而有希望的可扩展性。该提案的目标如下：1）开发基于块的图理论矩阵分解策略，以稀疏和密集的圆锥优化并研究其溶液质量； 2）基于这些基质分解策略来设计数值算法以实现可伸缩性； 3）在分布式控制和机器学习中追求大规模问题的申请。该项目的成功完成将系统地推进矩阵分解策略，以解决大规模的圆锥优化问题。该项目的结果将使更广泛的控制和优化社区受益，并在电网，运输和机器人技术中应用。预计研究进度将促进多学科合作，包括控制理论，机器学习，优化和图理论等。该奖项反映了NSF的法定任务，并被认为是值得通过基金会的知识分子优点和更广泛影响的评估来审查标准的评估值得支持的。

项目成果

Escaping High-order Saddles in Policy Optimization for Linear Quadratic Gaussian (LQG) Control

线性二次高斯 (LQG) 控制策略优化中摆脱高阶鞍点

• DOI: 10.1109/cdc51059.2022.9993305
• 发表时间: 2022
• 期刊: IEEE 61st Conference on Decision and Control (CDC
• 作者: Zheng, Yang;Sun, Yue;Fazel, Maryam;Li, Na
• 通讯作者: Li, Na

Iterative Inner/outer Approximations for Scalable Semidefinite Programs using Block Factor-width-two Matrices

使用块因子宽度二矩阵的可扩展半定程序的迭代内/外近似

• DOI: 10.1109/cdc51059.2022.9992734
• 发表时间: 2022
• 期刊: IEEE 61st Conference on Decision and Control (CDC
• 作者: Liao, Feng-Yi;Zheng, Yang
• 通讯作者: Zheng, Yang

Convex Parameterization of Stabilizing Controllers and its LMI-based Computation via Filtering

稳定控制器的凸参数化及其基于LMI的滤波计算

• DOI: 10.1109/cdc51059.2022.9993254
• 发表时间: 2022
• 期刊: IEEE 61st Conference on Decision and Control (CDC
• 作者: de Oliveira, Mauricio C.;Zheng, Yang
• 通讯作者: Zheng, Yang

Iteratively Enhanced Semidefinite Relaxations for Efficient Neural Network Verification

• DOI: 10.1609/aaai.v37i12.26744
• 发表时间: 2023-06
• 期刊: Proceedings of the 17th Conference on Embedded Networked Sensor Systems
• 作者: Jianglin Lan;Yang Zheng;A. Lomuscio

On Controller Reduction in Linear Quadratic Gaussian Control with Performance Bounds

关于具有性能界限的线性二次高斯控制中的控制器简化

• 发表时间: 2023
• 期刊: Proceedings of Machine Learning Research
• 作者: Ren, Zhaolin;Zheng, Yang;Fazel, Maryam;Li, Na
• 通讯作者: Li, Na