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

快速数值算法的发展对于在电力系统、机器学习、控制理论、交通运输和运筹学等广泛领域出现的大规模优化问题至关重要。主要的挑战是现有的方法无法处理许多现实问题的非线性（非凸性）。圆锥优化通过凸化的概念，能够以严格和原则性的方式将这些非凸问题求解到全局最优。尽管有成熟的凸化理论，但由于这种技术大大增加了问题的维度，实际应用仍然有限。由于缺乏有效的二次曲线优化数值算法，研究人员普遍将二次曲线优化视为一种强大的理论工具，无法用于实际应用。本文的目标是设计低复杂度的二次优化算法，直接利用给定问题的结构来降低复杂度。该项目的成果将在现实世界系统的设计、分析、操作和控制的所有领域产生广泛的社会影响。该项目有一些推广和教育活动，如参与多个项目，为来自代表性不足的群体的学生，促进本科研究，组织辅导课和研讨会。本项目通过利用问题结构开发稀疏二次优化的数值算法，特别强调稀疏半定规划。该方法使用树分解的概念来解决近线性时间和线性记忆中的稀疏问题。本文的主要目标是：1)识别控制稀疏二次优化计算复杂度的图论结构；2)在此图形分析的基础上设计数值算法以达到最佳复杂度；3)开发这些算法的并行和分布式版本，用于实时计算。这是一个跨学科的项目，其理论基础是图论、数值算法、矩阵补全、二次优化、低秩矩阵优化和代数几何，以及在电力系统和机器学习中的应用。本课题将设计的数值算法应用于具有数万个参数的非线性功率优化问题，以证明其影响。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.