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

GPU上の拡張ラグランジュ法によるセキュリティ制約付きAC最適潮流

基本情報

論文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（最適化と制御）
発表日: 2025年10月15日
論文リンク: https://arxiv.org/abs/2510.13333

要約

本論文は、大規模セキュリティ制約付きAC最適潮流（AC-SCOPF）を求解するための新しいアルゴリズムを提案している。本手法は非線形制約ラグランジュ（NCL）法に基づいており、内点法を用いて部分問題を求解する。NCLは大規模SC-OPFに対して2つの重要な利点を有する。第1に、NCLは実行不可能問題や相補制約を含むモデルなどの困難な問題を処理できる。第2に、拡張ラグランジュ項は内点法におけるニュートン線形システムを自然に正則化し、ピボットなし分解によるニュートンシステムの求解を可能にし、これはGPU上で効率的に並列化できる。数値結果は、MadNCLが500ノード256故障のAC-SCOPFをGPU上で3分以内に完全に求解でき、一方Knitroは同等の解を見つけるのに3時間以上を要することを示している。

研究背景と動機

問題の説明

送電網における最適スケジューリングは通常、セキュリティ制約付き最適潮流（SCOPF）を求解することで計算される。このスケジューリングは、物理的制約（潮流、線路流量制限）および発電機容量を考慮しながら、与えられた基準（コストまたはネットワーク損失）を最小化する。さらに、スケジューリングは線路または発電機故障に対応する一連の緊急事態下で実行可能性を維持する必要がある（N-1安全基準）。

問題の重要性

SCOPFは通常、DC-SCOPFと呼ばれる大規模線形計画問題として定式化され、その規模は故障数に応じて線形に増加する。しかし、これは非線形物理制約の線形化の代償として、解の精度に影響を与える。しかし、元の非線形定式化を用いたAC-SCOPFの求解は依然として未解決の課題である。

既存手法の限界

非線形定式化には2つの問題がある：

AC-SCOPFは巨大規模の非線形計画問題であり、その規模はIpoptやKnitroなどの最先端の非線形最適化ソルバーの能力を超えている
AC-SCOPFモデルの相補制約は数値的に扱いが難しく、特殊なアルゴリズムを採用する必要がある

研究動機

大規模AC-SCOPFの特性は相補制約の数が故障数に応じて線形に増加するため、アルゴリズムを限界に追いやる。この課題に対処するため、著者らは拡張ラグランジュ法に基づくNCLを用いてAC-SCOPFを求解することを提案している。

核心的貢献

拡張ラグランジュ法の初適用：相補制約を含む是正的SCOPFの求解に拡張ラグランジュベースのアルゴリズムを初めて適用
GPU加速実装：NVIDIA cuDSSを用いた線形求解を活用するGPU加速対応のNCL実装であるMadNCLを開発
相補制約の処理：MadNCLがAC-SCOPF内の相補制約を適切に処理でき、実行不可能問題を効果的に検出することを実証
顕著な性能向上：大規模インスタンスで従来手法と比較して顕著な高速化を実現、GPU版はCPU版より6倍以上高速

手法の詳細

タスク定義

セキュリティ制約付きAC最適潮流（AC-SCOPF）問題は以下のように定義される：

$\min_{x,u} f(x^0, u^0)$

制約条件：

基準ケース： $g^0(x^0, u^0) = 0$ , $h^0(x^0, u^0) \leq 0$
各故障 $k \in \{1, \cdots, K\}$ $k \in {1, \dots, K}$ に対して：
- $g^k(u^0, x^k, u^k) = 0$
- $h^k(x^k, u^k) \leq 0$
- $0 \leq G(x^k, u^k) \perp H(x^k, u^k) \geq 0$

ここで相補制約は以下から生じる：

自動発電制御（AGC）：周波数調整のための有効電力調整
PV/PQスイッチング：電圧制御と無効電力制限

外層反復：ペナルティパラメータ $\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}$

ここで拡張ラグランジュ項により提供される正則化により、ピボットなし分解の使用が可能になる。

技術的革新点

自然な正則化：拡張ラグランジュ項はニュートン線形システムを自然に正則化し、厳密な相補性が成立しない場合でもシステムの非特異性を保持
ピボットなし分解：正則化により符号付きCholesky分解などのピボットなし手法の使用が可能になり、これらはGPU上で効率的に並列化できる
実行不可能性検出：問題が実行不可能な場合、NCLは自動的に実行可能性問題にフォールバックし、ペナルティパラメータ $ρ^{(n)}$ を無限大に増加させる