CAREER: Efficient computational methods for nonlinear optimization and machine learning problems with applications to power systems

职业：非线性优化和机器学习问题的有效计算方法及其在电力系统中的应用

• 批准号: 2045829
• 负责人: Somayeh Sojoudi
• 金额: $ 50万
• 依托单位: University of California-Berkeley
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2021
• 资助国家: 美国
• 起止时间: 2021-01-15 至 2025-12-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2045829&HistoricalAwards=false
• 关键词: CAREER; Efficient; computational; methods; nonlinear

Optimization is an important tool for the design, analysis, control and operation of real-world systems, such as power systems. It also plays a central role in machine learning and artificial intelligence, particularly in deep learning, reinforcement leaning, and statistical learning. The mathematical foundation of optimization has heavily relied on the notion of convexity since convex optimization problems can be solved using fast algorithms. Nevertheless, many optimization problems in real-world applications are non-convex, and therefore it is extremely difficult to solve those problems reliably and efficiently using the existing methods. As an example, this issue is one of the main bottlenecks in the upgrade of the legacy power grids and has been incurring billions of dollars annually in the United States. This CAREER project aims to develop a set of computational tools for solving complex optimization and learning problems using efficient computational methods. This project has a significant impact on many societal problems through the development of a rich mathematical foundation for non-convex optimization, and its outcomes can be exploited in a variety of fields. The developed techniques enable solving large-scale computational problems for improving the efficiency, reliability, resiliency and sustainability of power grids, which has major societal, economical, and environmental impacts. Moreover, these tools significantly extend the application of artificial intelligence to safety-critical systems. This project has a wide range of outreach plans for K-12 and underrepresented students, and it also has several educational activities at both undergraduate and graduate levels. The state-of-the-art techniques for solving non-convex problems are based on various approximation and relaxation methods, whose practical use remains limited due to their scalability issues for real-world systems. On the other hand, the staggering advances made in artificial intelligence in the last 5 years (e.g., in deep learning) are due, in part, to handling computationally-intensive machine learning problems directly as non-convex optimization without relying on convex optimization. Motivated by the resounding success of local search methods for artificial intelligence, this CAREER project aims to design low-complexity computational methods for non-convex optimization problems. To this end, it studies the notion of spurious solutions, which are those solutions of an optimization problem that satisfy the local optimality conditions but are not globally optimal. The main property of convex optimization is the absence of spurious solutions. This project introduces the class of global functions which is far broader than the class of convex functions but benefits from the same spurious-solution-free property. Using the notions of global functions and kernel structure property, four objectives will be addressed: (i) analysis of the spurious solutions of key non-convex problems in machine learning and studying how the amount of data and the structural properties of each problem affects the inexistence of such solutions, (ii) analysis of the spurious solutions of an arbitrary polynomial optimization problem via its conversion to a machine learning problem and then discovering what structural properties guarantee the inexistence of spurious solutions, (iii) approximation of an arbitrary polynomial optimization problem having a spurious solution with a sequence of spurious-minima-free non-convex problems in a higher-dimensional space, (iv) software development and performing case studies on key problems for power systems and machine learning. This project is interdisciplinary and contributes to the areas of optimization theory, machine learning, control theory, and energy.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.

优化是设计、分析、控制和操作现实世界系统（如电力系统）的重要工具。它在机器学习和人工智能中也发挥着核心作用，特别是在深度学习、强化学习和统计学习中。优化的数学基础在很大程度上依赖于凸性的概念，因为凸优化问题可以使用快速算法来解决。然而，在现实世界中的许多优化问题是非凸的，因此它是非常困难的，可靠和有效地解决这些问题使用现有的方法。例如，这个问题是传统电网升级的主要瓶颈之一，每年在美国造成数十亿美元的损失。这个CAREER项目旨在开发一套计算工具，用于使用有效的计算方法解决复杂的优化和学习问题。该项目通过为非凸优化开发丰富的数学基础，对许多社会问题产生了重大影响，其成果可以在各种领域中利用。所开发的技术能够解决大规模计算问题，以提高电网的效率，可靠性，弹性和可持续性，这对社会，经济和环境都有重大影响。此外，这些工具将人工智能的应用扩展到安全关键系统。该项目为K-12和代表性不足的学生制定了广泛的推广计划，并在本科和研究生层面开展了几项教育活动。用于解决非凸问题的最先进的技术是基于各种近似和松弛方法，其实际使用仍然受到限制，由于其可扩展性问题的现实世界的系统。另一方面，过去5年人工智能取得的惊人进步（例如，在深度学习中），部分原因是直接将计算密集型机器学习问题处理为非凸优化，而不依赖于凸优化。受人工智能局部搜索方法的巨大成功的启发，这个CAREER项目旨在为非凸优化问题设计低复杂度的计算方法。为此，研究了伪解的概念，伪解是指满足局部最优性条件但不是全局最优的优化问题的解。凸优化的主要性质是不存在伪解。 这个项目引入了全局函数类，它比凸函数类广泛得多，但受益于相同的无伪解属性。使用全局函数和内核结构属性的概念，将解决四个目标：（i）分析机器学习中关键非凸问题的伪解，并研究每个问题的数据量和结构特性如何影响此类解的不存在，（二）通过将任意多项式优化问题转换为机器学习问题来分析其伪解，然后发现性质保证虚假解决方案的不存在，（iii）近似的任意多项式优化问题，具有虚假解决方案与一系列的虚假最小的非凸问题在高维空间，（iv）软件开发和执行案例研究的关键问题，电力系统和机器学习。该项目是跨学科的，对优化理论、机器学习、控制理论和能源领域做出了贡献。该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

Sample Complexity of Block-Sparse System Identification Problem

块稀疏系统辨识问题的样本复杂度

• 发表时间: 2021
• 期刊: IEEE transactions on control of network systems
• 影响因子: 4.2
• 作者: Fattahi, Salar;Sojoudi, Somayeh
• 通讯作者: Sojoudi, Somayeh

Projected Randomized Smoothing for Certified Adversarial Robustness

• DOI: 10.48550/arxiv.2309.13794
• 发表时间: 2023-09
• 期刊: ArXiv
• 作者: Samuel Pfrommer;Brendon G. Anderson;S. Sojoudi

A MILP for Optimal Measurement Choice in Robust Power Grid State Estimation

鲁棒电网状态估计中最优测量选择的 MILP

• 发表时间: 2022
• 期刊: IEEE Power Energy Society General Meeting
• 作者: Glista, Elizabeth;Sojoudi, Somayeh
• 通讯作者: Sojoudi, Somayeh

A Sequential Framework Towards an Exact SDP Verification of Neural Networks

• DOI: 10.1109/dsaa53316.2021.9564161
• 发表时间: 2020-10
• 期刊: 2021 IEEE 8th International Conference on Data Science and Advanced Analytics (DSAA)
• 作者: Ziye Ma;S. Sojoudi

On the Absence of Spurious Local Trajectories in Time-Varying Nonconvex Optimization

• DOI: 10.1109/tac.2021.3137147
• 发表时间: 2020-11
• 期刊: IEEE Transactions on Automatic Control
• 影响因子: 6.8
• 作者: S. Fattahi;C. Josz;Yuhao Ding;R. Mohammadi;J. Lavaei;S. Sojoudi