权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Collaborative research: polynomial optimization and its application to power systems

合作研究：多项式优化及其在电力系统中的应用

基本信息

批准号：
2023032
负责人：
Cedric Josz
金额：
$ 38.58万
依托单位：
Columbia University
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2020
资助国家：
美国
起止时间：
2020-09-01 至 2025-08-31
项目状态：
未结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=2023032&HistoricalAwards=false
关键词：
Collaborative research polynomial optimization its

项目摘要

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.

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