Collaborative research: polynomial optimization and its application to power systems

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

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.