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)：

c(w) = 0, \quad w_0 \geq 0 \\ 0 \leq w_1 \perp w_2 \geq 0 \end{cases}$$ #### NCL算法 NCL在两个层次上操作： - **外层迭代**：更新惩罚参数$\rho^{(n)}$和乘数估计$(λ^{(n)}, ν_0^{(n)})$ - **内层迭代**：求解约束非线性子问题： $$\min_{w,r,t} L_ρ(w, r, t, λ^{(n)}, ν_0^{(n)})$$ 受约束于： $$c(w) - r = 0, \quad W_1W_2e \leq t, \quad (w_0, w_1, w_2) \geq 0$$ #### 牛顿系统结构 子问题的牛顿系统具有以下结构： $$\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)}$到无穷大 ## 实验设置 ### 数据集 使用MATPOWER库中的实例： - 118ieee, ACTIVSg200, 300ieee, ACTIVSg500 - 1354pegase, ACTIVSg2000, 2869pegase - 故障数量从2到256不等 ### 评价指标 - **求解时间**：总求解时间和每次迭代时间 - **迭代次数**：内点法迭代次数 - **目标值**：最优解的目标函数值 - **可行性**：检测不可行故障的能力 ### 对比方法 - **Knitro**：最先进的支持MPCC的优化求解器，使用$\ell_1$精确惩罚方法 - **MadNCL-CPU**：使用HSL MA57的CPU版本 - **MadNCL-GPU**：使用NVIDIA cuDSS的GPU版本 ### 实现细节 - **编程语言**：Julia 1.11 - **收敛容差**：1e-6 - **最小障碍参数**：$μ_{min} = 10^{-7}$ - **硬件**：AMD EPYC 7430处理器，NVIDIA A30 GPU (24GB显存) ## 实验结果 ### 主要结果 #### 故障筛选性能 在故障筛选任务中，MadNCL显著优于Knitro： | 实例 | Knitro (s) | MadNCL-CPU (s) | |------|------------|----------------| | 118ieee | 0.5 | 0.01 | | ACTIVSg500 | 5.4 | 0.3 | | 2869pegase | 238.4 | 14.1 | MadNCL在超过300个节点的实例上至少快10倍。 #### 大规模AC-SCOPF求解 对于ACTIVSg500实例，随着故障数量增加： | K | 变量数 | Knitro时间(s) | MadNCL-GPU时间(s) | 加速比 | |---|--------|---------------|-------------------|--------| | 64 | 241,900 | 2159.59 | 27.96 | 77.2× | | 128 | 480,300 | 4852.33 | 46.40 | 104.6× | | 256 | 957,100 | 11136.08 | 170.75 | 65.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优化等多个方面的重要工作，为研究提供了坚实的理论基础。