Collaborative research: polynomial optimization and its application to power systems

电力系统的运营商面临着一项艰巨的任务，即通过管理成千上万台发电机的输出和成千上万条输电线路的电力流，不断平衡电力的供需。为了保持可靠和低成本的供电，系统操作员依赖于数学优化领域的算法。为了获得更易于处理的数学公式，现有的工业实践对最能代表电力系统物理特性的非线性模型进行线性近似。使用这些线性近似的优化问题提供了固有地遭受近似误差的工作点，从而降低了电力系统运行的可靠性和效率。优化理论的最新进展为通过直接解决非线性优化问题来避免这些近似误差提供了重要的希望。例如，能源部和联邦能源管理委员会估计，改进的优化算法每年仅在美国电力市场就可以节省数十亿美元。将电网建模为多项式方程系统，我们的初步工作表明，多项式优化理论可以可靠地为具有挑战性的非线性问题提供解决方案。在我们初步工作的基础上，该项目将开发和分析新的优化算法，提供显著的计算速度提高和额外的建模灵活性。这些算法及其对收敛性和解决方案质量的严格保证是电力系统可靠运行的关键工具，特别是在高应力条件下。本项目旨在发展新的半代数技术，以解决电力系统运行中出现的大规模多项式优化问题。鉴于电力系统日益复杂，在未来几年，运营决策工具迫切需要创新的解决方案。为了实现这一目标，我们建议使用多项式优化理论中的一个强大工具（称为矩/平方和层次）来设计易于处理和严格的算法。与局部搜索算法相反，矩/平方和层次结构具有全局收敛保证，不会陷入不希望的局部最小值或鞍点。然而，使这种层次结构易于处理实际的大规模问题是一个主要挑战。因此，我们提出了新的半代数技术来全局解决大规模多项式优化的一个重要的通用实例，即所谓的最优潮流问题。该问题寻求电力系统的最小运行成本点，同时满足工程对线路流、电压幅值等的限制以及模拟网络物理的潮流方程。除了本身是一个重要的问题外，最优潮流是更复杂问题的关键组成部分，包括用于模拟竞争电力市场和确定关键电力系统组件的双层优化问题。我们的初步结果表明，矩/平方和松弛可以解决来自工业的实际最优潮流测试用例，其规模前所未有，具有数千个变量和数万个非凸约束。我们计划设计新的方法来利用电力系统的特定特性（特定的对称性和稀疏性）来实现大规模计算，以及解决多项式优化问题的新层次结构。我们这个项目的具体目标包括：1)使用最近提出的系统地加强松弛的拉格朗日乘子表达式大幅提高矩/平方和层次的计算速度；2)开发快速检查候选局部解是否实际上是全局最优的方法，从而利用数十年的局部搜索算法研究成果；3)将多项式优化工具应用于工业相关的双层优化问题，其中松弛全局最优性证书对于确保整体双层问题的可行性至关重要；4)创建适合电力系统特定特性的新松弛层次，同时利用为机器学习应用开发的计算方法的效率。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Operators of electric power systems face the difficult task of continuously balancing the supply and demand of power by managing the outputs of thousands of generators and the power flows through tens of thousands of transmission lines. To maintain a reliable and low-cost power supply, system operators rely on algorithms from the field of mathematical optimization. To obtain more tractable mathematical formulations, existing industry practices linearly approximate the nonlinear models which best represent the physics of electric power systems. Optimization problems that use these linear approximations provide operating points which inherently suffer from approximation errors, thus reducing the reliability and efficiency of power system operations. Recent advancements in optimization theory hold significant promise for avoiding these approximation errors by directly solving nonlinear optimization problems. For instance, the Department of Energy and the Federal Energy Regulatory Commission estimate that improved optimization algorithms could save billions of dollars annually in the US electricity markets alone. Modeling power networks as systems of polynomial equations, our preliminary work demonstrated that polynomial optimization theory can reliably provide solutions to challenging nonlinear problems. Building on our preliminary work, this project will develop and analyze new optimization algorithms that provide significant computational speed improvements and additional modeling flexibility. These algorithms and their associated rigorous guarantees on convergence and solution quality are key enabling tools for reliably operating power systems, especially during heavily stressed conditions.This project aims to develop new semi-algebraic techniques for solving large-scale polynomial optimization problems arising from the operation of electric power systems. Given the increasing complexity of power systems, operational decision-making tools crucially require innovative solutions in the coming years. To achieve this, we propose to design tractable and rigorous algorithms using a powerful tool from polynomial optimization theory known as the moment/sum-of-squares hierarchy. Contrary to local search algorithms, the moment/sum-of-squares hierarchy has global convergence guarantees and cannot get stuck in undesired local minima or saddle points. However, making this hierarchy tractable for practical large-scale problems is a major challenge. We thus propose new semi-algebraic techniques for globally solving an important and generic instance of large-scale polynomial optimization, namely the so-called optimal power flow problem. This problem seeks the minimum cost operating point for an electric power system while satisfying engineering limits on the line flows, voltage magnitudes, etc. as well as the power flow equations which model the network physics. In addition to being an important problem in its own right, optimal power flow is a key building block of more complex problems, including bilevel optimization problems used to model competitive electricity markets and to identify critical power system components. Our preliminary results show that moment/sum-of-squares relaxations can solve practical optimal power flow test cases coming from industry on an unprecedented scale, with thousands of variables and tens of thousands of non-convex constraints. We plan to design new ways to exploit power system specific characteristics (particular symmetries and sparsity) to enable large-scale computations, as well as new hierarchies for solving polynomial optimization problems. Our specific objectives for this project include 1) substantially improving the computational speed of the moment/sum-of-squares hierarchies using recently proposed Lagrange multiplier expressions that systematically strengthen the relaxations, 2) developing methods for quickly checking whether a candidate local solution is, in fact, globally optimal, thus leveraging decades of research in local search algorithms, 3) applying polynomial optimization tools to industrially relevant bilevel optimization problems, where the relaxations global optimality certificates are essential to ensuring feasibility of the overall bilevel problem, and 4) creating new relaxation hierarchies that are tailored to power system specific characteristics while simultaneously exploiting the efficiency of computational methods developed for machine learning applications.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.