2025-11-18T17:07:13.972479

An Augmented Lagrangian Method on GPU for Security-Constrained AC Optimal Power Flow

Pacaud, Nurkanović, Pozharskiy et al.
We present a new algorithm for solving large-scale security-constrained optimal power flow in polar form (AC-SCOPF). The method builds on Nonlinearly Constrained augmented Lagrangian (NCL), an augmented Lagrangian method in which the subproblems are solved using an interior-point method. NCL has two key advantages for large-scale SC-OPF. First, NCL handles difficult problems such as infeasible ones or models with complementarity constraints. Second, the augmented Lagrangian term naturally regularizes the Newton linear systems within the interior-point method, enabling to solve the Newton systems with a pivoting-free factorization that can be efficiently parallelized on GPUs. We assess the performance of our implementation, called MadNCL, on large-scale corrective AC-SCOPFs, with complementarity constraints modeling the corrective actions. Numerical results show that MadNCL can solve AC-SCOPF with 500 buses and 256 contingencies fully on the GPU in less than 3 minutes, whereas Knitro takes more than 3 hours to find an equivalent solution.
academic

An Augmented Lagrangian Method on GPU for Security-Constrained AC Optimal Power Flow

基本信息

  • 论文ID: 2510.13333
  • 标题: An Augmented Lagrangian Method on GPU for Security-Constrained AC Optimal Power Flow
  • 作者: François Pacaud, Armin Nurkanović, Anton Pozharskiy, Alexis Montoison, Sungho Shin
  • 分类: math.OC (Optimization and Control)
  • 发表时间: 2025年10月15日
  • 论文链接: https://arxiv.org/abs/2510.13333

摘要

本文提出了一种求解大规模安全约束交流最优潮流(AC-SCOPF)的新算法。该方法基于非线性约束增广拉格朗日(NCL)方法，使用内点法求解子问题。NCL对于大规模SC-OPF具有两个关键优势：首先，NCL能处理困难问题如不可行问题或带有互补约束的模型；其次，增广拉格朗日项自然地正则化了内点法中的牛顿线性系统，使得可以用无枢轴分解求解牛顿系统，这可以在GPU上高效并行化。数值结果显示，MadNCL可以在不到3分钟内在GPU上完全求解500个节点和256个故障的AC-SCOPF，而Knitro需要超过3小时才能找到等价解。

研究背景与动机

问题描述

在输电网络中，最优调度通常通过求解安全约束最优潮流(SCOPF)来计算。该调度在考虑物理约束(潮流、线路流量限制)和发电机容量的同时，最小化给定准则(成本或网络损耗)。此外，调度应在一系列对应于线路或发电机故障的应急情况下保持可行性(N-1安全准则)。

问题重要性

SCOPF通常被表述为称为DC-SCOPF的大规模线性规划问题，其规模随故障数量线性增长。但这以线性化非线性物理约束为代价，影响解的精度。然而，用原始非线性公式求解AC-SCOPF仍然是一个开放挑战。

现有方法局限性

非线性公式存在两个问题：

  1. AC-SCOPF是一个巨大规模的非线性规划问题，其规模超出了Ipopt或Knitro等最先进非线性优化求解器的能力
  2. AC-SCOPF模型中的互补约束在数值上难以处理，必须采用专门的算法

研究动机

大规模AC-SCOPF的特点将算法推向边界，因为互补约束的数量随故障数量线性增长。为了应对这一挑战，作者提出使用基于非线性约束增广拉格朗日(NCL)的增广拉格朗日方法求解AC-SCOPF。

核心贡献

  1. 首次应用增广拉格朗日方法：首次将基于增广拉格朗日的算法用于求解带有互补约束的纠正性SCOPF
  2. GPU加速实现：开发了MadNCL，一个支持GPU加速的NCL实现，利用NVIDIA cuDSS进行线性求解
  3. 处理互补约束：展示了MadNCL能很好地处理AC-SCOPF中的互补约束，并有效检测不可行问题
  4. 显著性能提升：在大规模实例上实现了相比传统方法的显著加速，GPU版本比CPU版本快6倍以上

方法详解

任务定义

安全约束交流最优潮流(AC-SCOPF)问题定义为：

min⁡x,uf(x0,u0)\min_{x,u} f(x^0, u^0)

受约束于：

  • 基准情况：g0(x0,u0)=0g^0(x^0, u^0) = 0, h0(x0,u0)≤0h^0(x^0, u^0) \leq 0
  • 对于每个故障k∈{1,⋯ ,K}k \in \{1, \cdots, K\}：
    • gk(u0,xk,uk)=0g^k(u^0, x^k, u^k) = 0
    • hk(xk,uk)≤0h^k(x^k, u^k) \leq 0
    • 0≤G(xk,uk)⊥H(xk,uk)≥00 \leq G(x^k, u^k) \perp H(x^k, u^k) \geq 0

其中互补约束来自于：

  1. 自动发电控制(AGC)：有功功率调节频率
  2. PV/PQ开关：电压控制和无功功率限制

模型架构

MPCC重构

将AC-SCOPF重构为数学规划与互补约束(MPCC)：

min⁡w∈Rnϕ(w)s.t.{c(w)=0,w0≥00≤w1⊥w2≥0\min_{w \in \mathbb{R}^n} \phi(w) \quad \text{s.t.} \quad \begin{cases} c(w) = 0, \quad w_0 \geq 0 \\ 0 \leq w_1 \perp w_2 \geq 0 \end{cases}

NCL算法

NCL在两个层次上操作：

  • 外层迭代：更新惩罚参数ρ(n)\rho^{(n)}和乘数估计(λ(n),ν0(n))(λ^{(n)}, ν_0^{(n)})
  • 内层迭代：求解约束非线性子问题：

min⁡w,r,tLρ(w,r,t,λ(n),ν0(n))\min_{w,r,t} L_ρ(w, r, t, λ^{(n)}, ν_0^{(n)})

受约束于： c(w)−r=0,W1W2e≤t,(w0,w1,w2)≥0c(w) - r = 0, \quad W_1W_2e \leq t, \quad (w_0, w_1, w_2) \geq 0

牛顿系统结构

子问题的牛顿系统具有以下结构：

[AB⊤B−C][ΔwΔy]=[r1r2]\begin{bmatrix} A & B^⊤ \\ B & -C \end{bmatrix} \begin{bmatrix} Δw \\ Δy \end{bmatrix} = \begin{bmatrix} r_1 \\ r_2 \end{bmatrix}

其中增广拉格朗日项提供的正则化使得可以使用无枢轴分解。

技术创新点

  1. 自然正则化：增广拉格朗日项自然地正则化牛顿线性系统，即使在严格互补性不成立时也保持系统的非奇异性
  2. 无枢轴分解：正则化允许使用符号Cholesky分解等无枢轴方法，这些方法可以在GPU上高效并行化
  3. 不可行性检测：当问题不可行时，NCL自动回退到可行性问题，通过增加惩罚参数ρ(n)ρ^{(n)}到无穷大

实验设置

数据集

使用MATPOWER库中的实例：

  • 118ieee, ACTIVSg200, 300ieee, ACTIVSg500
  • 1354pegase, ACTIVSg2000, 2869pegase
  • 故障数量从2到256不等

评价指标

  • 求解时间：总求解时间和每次迭代时间
  • 迭代次数：内点法迭代次数
  • 目标值：最优解的目标函数值
  • 可行性：检测不可行故障的能力

对比方法

  • Knitro：最先进的支持MPCC的优化求解器，使用ℓ1\ell_1精确惩罚方法
  • MadNCL-CPU：使用HSL MA57的CPU版本
  • MadNCL-GPU：使用NVIDIA cuDSS的GPU版本

实现细节

  • 编程语言：Julia 1.11
  • 收敛容差：1e-6
  • 最小障碍参数：μmin=10−7μ_{min} = 10^{-7}
  • 硬件：AMD EPYC 7430处理器，NVIDIA A30 GPU (24GB显存)

实验结果

主要结果

故障筛选性能

在故障筛选任务中，MadNCL显著优于Knitro：

实例Knitro (s)MadNCL-CPU (s)
118ieee0.50.01
ACTIVSg5005.40.3
2869pegase238.414.1

MadNCL在超过300个节点的实例上至少快10倍。

大规模AC-SCOPF求解

对于ACTIVSg500实例，随着故障数量增加：

K变量数Knitro时间(s)MadNCL-GPU时间(s)加速比
64241,9002159.5927.9677.2×
128480,3004852.3346.40104.6×
256957,10011136.08170.7565.2×

消融实验

GPU vs CPU性能

MadNCL-GPU相比MadNCL-CPU的性能提升：

  • 对于K≥64，GPU版本比CPU版本快约6倍
  • 对于K≥64，GPU版本比Knitro快约20倍以上

每次迭代时间分析

随着故障数量增加，MadNCL-GPU的每次迭代时间增长最为缓慢，展现出良好的可扩展性。

实验发现

  1. 可扩展性：MadNCL展现出优异的可扩展性，能够处理近百万变量的问题
  2. 鲁棒性：NCL能够自动检测和处理不可行问题
  3. 并行效率：GPU实现充分利用了并行计算的优势
  4. 数值稳定性：增广拉格朗日的正则化提高了数值稳定性

相关工作

主要研究方向

  1. MPCC求解方法：包括直接方法、正则化方法和惩罚方法
  2. 电力系统优化：DC-SCOPF和AC-SCOPF的各种求解策略
  3. GPU加速优化：将优化算法移植到GPU平台

本文贡献

相比现有工作，本文首次将增广拉格朗日方法应用于带互补约束的AC-SCOPF，并实现了高效的GPU加速。

结论与讨论

主要结论

  1. MadNCL能够有效求解大规模AC-SCOPF问题，处理近百万变量
  2. GPU加速版本相比传统CPU求解器实现了数十倍的性能提升
  3. 增广拉格朗日方法为处理互补约束提供了鲁棒的解决方案

局限性

  1. 条件数问题：随着问题规模增大，线性系统的条件数恶化
  2. 收敛性：在某些大规模实例上收敛性不够稳定
  3. 内存限制：GPU内存限制了可处理的最大问题规模

未来方向

  1. 解决内点法牛顿系统中的病态条件问题
  2. 扩展到更大规模的实例(万个节点，百个故障)
  3. 改进预条件技术以提高数值稳定性

深度评价

优点

  1. 方法创新性：首次将NCL应用于AC-SCOPF，技术路线新颖
  2. 实现质量：高质量的GPU实现，充分利用并行计算优势
  3. 实验充分：全面的实验评估，包括可扩展性和鲁棒性测试
  4. 实用价值：显著的性能提升使得大规模实时应用成为可能

不足

  1. 理论分析：缺乏NCL在SCOPF问题上的收敛性理论分析
  2. 数值稳定性：在最大规模实例上仍存在数值稳定性问题
  3. 通用性：方法的适用性主要限于电力系统优化领域

影响力

  1. 学术贡献：为大规模非凸优化提供了新的求解思路
  2. 实用价值：对电力系统运行和规划具有重要实用价值
  3. 技术推广：GPU加速优化算法的成功案例

适用场景

  1. 电力系统调度：实时和日前市场的安全约束优化
  2. 大规模非凸优化：其他带互补约束的工程优化问题
  3. GPU高性能计算：需要快速求解的优化应用

参考文献

论文引用了31篇相关文献，涵盖了SCOPF建模、MPCC求解方法、增广拉格朗日理论以及GPU优化等多个方面的重要工作，为研究提供了坚实的理论基础。