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

Eine Augmented-Lagrangian-Methode auf GPU für sicherheitsbeschränkte AC-Optimalleistungsflussberechnung

Grundinformationen

  • Papier-ID: 2510.13333
  • Titel: An Augmented Lagrangian Method on GPU for Security-Constrained AC Optimal Power Flow
  • Autoren: François Pacaud, Armin Nurkanović, Anton Pozharskiy, Alexis Montoison, Sungho Shin
  • Klassifizierung: math.OC (Optimierung und Steuerung)
  • Veröffentlichungsdatum: 15. Oktober 2025
  • Papierlink: https://arxiv.org/abs/2510.13333

Zusammenfassung

In diesem Artikel wird ein neuer Algorithmus zur Lösung großskaliger sicherheitsbeschränkter AC-Optimalleistungsflussberechnung (AC-SCOPF) vorgestellt. Die Methode basiert auf der nichtlinearen beschränkten Augmented-Lagrangian-Methode (NCL) und verwendet Innenpunktmethoden zur Lösung von Teilproblemen. Die NCL bietet zwei wesentliche Vorteile für großskalige SC-OPF: Erstens kann die NCL schwierige Probleme wie unlösbare Probleme oder Modelle mit komplementären Beschränkungen bewältigen; zweitens regularisiert der Augmented-Lagrangian-Term natürlicherweise das Newton-Linearsystem in der Innenpunktmethode, was die Lösung des Newton-Systems mittels pivotfreier Zerlegung ermöglicht, die auf GPUs effizient parallelisiert werden kann. Numerische Ergebnisse zeigen, dass MadNCL ein AC-SCOPF mit 500 Knoten und 256 Fehlern auf einer GPU in weniger als 3 Minuten vollständig lösen kann, während Knitro über 3 Stunden benötigt, um eine äquivalente Lösung zu finden.

Forschungshintergrund und Motivation

Problembeschreibung

In Übertragungsnetzen wird die optimale Einsatzplanung üblicherweise durch Lösen von sicherheitsbeschränkter Optimalleistungsflussberechnung (SCOPF) berechnet. Diese Einsatzplanung minimiert ein gegebenes Kriterium (Kosten oder Netzverluste) unter Berücksichtigung physikalischer Beschränkungen (Leistungsfluss, Leitungsflussgrenzwerte) und Generatorkapazitäten. Darüber hinaus sollte die Einsatzplanung unter einer Reihe von Notfallsituationen, die Leitungs- oder Generatorausfällen entsprechen, machbar bleiben (N-1-Sicherheitskriterium).

Bedeutung des Problems

SCOPF wird üblicherweise als großskaliges lineares Programmierproblem formuliert, das als DC-SCOPF bezeichnet wird und dessen Größe linear mit der Anzahl der Fehler wächst. Dies erfolgt jedoch auf Kosten der Linearisierung nichtlinearer physikalischer Beschränkungen, was die Genauigkeit der Lösung beeinträchtigt. Die Lösung von AC-SCOPF mit der ursprünglichen nichtlinearen Formulierung bleibt jedoch eine offene Herausforderung.

Einschränkungen bestehender Methoden

Die nichtlineare Formulierung weist zwei Probleme auf:

  1. AC-SCOPF ist ein riesiges nichtlineares Programmierproblem, dessen Größe die Fähigkeiten modernster nichtlinearer Optimierungslöser wie Ipopt oder Knitro übersteigt
  2. Komplementäre Beschränkungen im AC-SCOPF-Modell sind numerisch schwer zu handhaben und erfordern spezialisierte Algorithmen

Forschungsmotivation

Die Charakteristiken großskaliger AC-SCOPF treiben Algorithmen an ihre Grenzen, da die Anzahl der komplementären Beschränkungen linear mit der Anzahl der Fehler wächst. Um diese Herausforderung zu bewältigen, schlagen die Autoren die Verwendung einer auf der nichtlinearen beschränkten Augmented-Lagrangian-Methode (NCL) basierenden Augmented-Lagrangian-Methode zur Lösung von AC-SCOPF vor.

Kernbeiträge

  1. Erste Anwendung der Augmented-Lagrangian-Methode: Erstmalige Anwendung eines auf Augmented-Lagrangian basierenden Algorithmus zur Lösung von korrigierendem SCOPF mit komplementären Beschränkungen
  2. GPU-beschleunigte Implementierung: Entwicklung von MadNCL, einer GPU-beschleunigten NCL-Implementierung, die NVIDIA cuDSS für die lineare Lösung nutzt
  3. Behandlung komplementärer Beschränkungen: Demonstration, dass MadNCL komplementäre Beschränkungen in AC-SCOPF gut bewältigt und unlösbare Probleme effektiv erkennt
  4. Erhebliche Leistungssteigerung: Realisierung erheblicher Beschleunigung gegenüber traditionellen Methoden auf großskaligen Instanzen, wobei die GPU-Version über 6-mal schneller als die CPU-Version ist

Methodische Erklärung

Aufgabendefinition

Das Problem der sicherheitsbeschränkten AC-Optimalleistungsflussberechnung (AC-SCOPF) wird definiert als:

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

unter Beschränkungen:

  • Basisfälle: g0(x0,u0)=0g^0(x^0, u^0) = 0, h0(x0,u0)≤0h^0(x^0, u^0) \leq 0
  • Für jeden Fehler 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

wobei die komplementären Beschränkungen aus folgenden Quellen stammen:

  1. Automatische Erzeugungsregelung (AGC): Wirkleistungsregelung für Frequenz
  2. PV/PQ-Umschaltung: Spannungsregelung und Blindleistungsgrenzen

Modellarchitektur

MPCC-Umstrukturierung

Umstrukturierung von AC-SCOPF als mathematisches Programm mit komplementären Beschränkungen (MPCC):

c(w) = 0, \quad w_0 \geq 0 \\ 0 \leq w_1 \perp w_2 \geq 0 \end{cases}$$ #### NCL-Algorithmus Die NCL operiert auf zwei Ebenen: - **Äußere Iteration**: Aktualisierung des Strafparameters $\rho^{(n)}$ und Multiplikatorschätzungen $(λ^{(n)}, ν_0^{(n)})$ - **Innere Iteration**: Lösung des beschränkten nichtlinearen Teilproblems: $$\min_{w,r,t} L_ρ(w, r, t, λ^{(n)}, ν_0^{(n)})$$ unter Beschränkungen: $$c(w) - r = 0, \quad W_1W_2e \leq t, \quad (w_0, w_1, w_2) \geq 0$$ #### Newton-Systemstruktur Das Newton-System des Teilproblems hat die folgende Struktur: $$\begin{bmatrix} A & B^⊤ \\ B & -C \end{bmatrix} \begin{bmatrix} Δw \\ Δy \end{bmatrix} = \begin{bmatrix} r_1 \\ r_2 \end{bmatrix}$$ wobei die durch den Augmented-Lagrangian-Term bereitgestellte Regularisierung die Verwendung pivotfreier Zerlegung ermöglicht. ### Technische Innovationen 1. **Natürliche Regularisierung**: Der Augmented-Lagrangian-Term regularisiert das Newton-Linearsystem natürlicherweise und erhält die Nichtsingularität des Systems auch dann, wenn strikte Komplementarität nicht erfüllt ist 2. **Pivotfreie Zerlegung**: Die Regularisierung ermöglicht die Verwendung pivotfreier Methoden wie symbolische Cholesky-Zerlegung, die auf GPUs effizient parallelisiert werden können 3. **Unlösbarkeitsdetektierung**: Wenn das Problem unlösbar ist, fällt die NCL automatisch auf das Machbarkeitsproblem zurück, indem der Strafparameter $ρ^{(n)}$ gegen Unendlich erhöht wird ## Experimentelle Einrichtung ### Datensätze Verwendung von Instanzen aus der MATPOWER-Bibliothek: - 118ieee, ACTIVSg200, 300ieee, ACTIVSg500 - 1354pegase, ACTIVSg2000, 2869pegase - Fehlerzahlen von 2 bis 256 ### Bewertungsmetriken - **Lösungszeit**: Gesamtlösungszeit und Zeit pro Iteration - **Iterationszahl**: Iterationszahl der Innenpunktmethode - **Zielwert**: Zielwert der optimalen Lösung - **Machbarkeit**: Fähigkeit zur Erkennung unlösbarer Fehler ### Vergleichsmethoden - **Knitro**: Modernster Optimierungslöser mit MPCC-Unterstützung, verwendet $\ell_1$-exakte Strafmethode - **MadNCL-CPU**: CPU-Version mit HSL MA57 - **MadNCL-GPU**: GPU-Version mit NVIDIA cuDSS ### Implementierungsdetails - **Programmiersprache**: Julia 1.11 - **Konvergenztoleranz**: 1e-6 - **Minimaler Barriereparameter**: $μ_{min} = 10^{-7}$ - **Hardware**: AMD EPYC 7430-Prozessor, NVIDIA A30 GPU (24GB VRAM) ## Experimentelle Ergebnisse ### Hauptergebnisse #### Fehlersiebungsleistung Bei der Fehlersiebungsaufgabe übertrifft MadNCL Knitro erheblich: | Instanz | Knitro (s) | MadNCL-CPU (s) | |---------|------------|----------------| | 118ieee | 0,5 | 0,01 | | ACTIVSg500 | 5,4 | 0,3 | | 2869pegase | 238,4 | 14,1 | MadNCL ist bei Instanzen mit über 300 Knoten mindestens 10-mal schneller. #### Großskalige AC-SCOPF-Lösung Für die ACTIVSg500-Instanz mit zunehmender Fehlerzahl: | K | Variablenzahl | Knitro-Zeit (s) | MadNCL-GPU-Zeit (s) | Beschleunigung | |---|---------------|-----------------|---------------------|----------------| | 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× | ### Ablationsexperimente #### GPU vs. CPU-Leistung Leistungssteigerung von MadNCL-GPU gegenüber MadNCL-CPU: - Für K≥64 ist die GPU-Version etwa 6-mal schneller als die CPU-Version - Für K≥64 ist die GPU-Version etwa 20-mal schneller als Knitro #### Zeitanalyse pro Iteration Mit zunehmender Fehlerzahl zeigt MadNCL-GPU das langsamste Wachstum der Zeit pro Iteration und demonstriert gute Skalierbarkeit. ### Experimentelle Erkenntnisse 1. **Skalierbarkeit**: MadNCL zeigt hervorragende Skalierbarkeit und kann Probleme mit fast einer Million Variablen bewältigen 2. **Robustheit**: NCL kann unlösbare Probleme automatisch erkennen und behandeln 3. **Parallelisierungseffizienz**: Die GPU-Implementierung nutzt die Vorteile der Parallelberechnung vollständig 4. **Numerische Stabilität**: Die Regularisierung durch Augmented-Lagrangian verbessert die numerische Stabilität ## Verwandte Arbeiten ### Hauptforschungsrichtungen 1. **MPCC-Lösungsmethoden**: Einschließlich direkter Methoden, Regularisierungsmethoden und Strafmethoden 2. **Elektroenergieerzeugungsoptimierung**: Verschiedene Lösungsstrategien für DC-SCOPF und AC-SCOPF 3. **GPU-beschleunigte Optimierung**: Portierung von Optimierungsalgorithmen auf GPU-Plattformen ### Beitrag dieses Artikels Im Vergleich zu bestehenden Arbeiten wendet dieser Artikel erstmals die Augmented-Lagrangian-Methode auf AC-SCOPF mit komplementären Beschränkungen an und realisiert eine effiziente GPU-Beschleunigung. ## Schlussfolgerungen und Diskussion ### Hauptschlussfolgerungen 1. MadNCL kann großskalige AC-SCOPF-Probleme mit fast einer Million Variablen effektiv lösen 2. Die GPU-beschleunigte Version erreicht gegenüber traditionellen CPU-Lösern eine Leistungssteigerung um das Vielfache 3. Die Augmented-Lagrangian-Methode bietet eine robuste Lösung zur Behandlung komplementärer Beschränkungen ### Einschränkungen 1. **Konditionszahlprobleme**: Mit zunehmender Problemgröße verschlechtert sich die Konditionszahl des Linearsystems 2. **Konvergenz**: Bei einigen großskaligen Instanzen ist die Konvergenz nicht ausreichend stabil 3. **Speicherbegrenzung**: GPU-Speicherbegrenzung schränkt die maximale Problemgröße ein ### Zukünftige Richtungen 1. Lösung von Konditionszahlproblemen im Newton-System der Innenpunktmethode 2. Erweiterung auf größere Instanzen (zehntausende Knoten, hunderte Fehler) 3. Verbesserung von Vorkonditionierungstechniken zur Erhöhung der numerischen Stabilität ## Tiefgreifende Bewertung ### Stärken 1. **Methodische Innovativität**: Erstmalige Anwendung von NCL auf AC-SCOPF mit neuartiger technischer Route 2. **Implementierungsqualität**: Hochwertige GPU-Implementierung, die die Vorteile der Parallelberechnung vollständig nutzt 3. **Umfassende Experimente**: Vollständige experimentelle Bewertung einschließlich Skalierbarkeits- und Robustheitstests 4. **Praktischer Wert**: Erhebliche Leistungssteigerung ermöglicht großskalige Echtzeitanwendungen ### Mängel 1. **Theoretische Analyse**: Fehlende Konvergenztheorieanalyse der NCL für SCOPF-Probleme 2. **Numerische Stabilität**: Numerische Stabilitätsprobleme bei maximalen Instanzgrößen 3. **Allgemeingültigkeit**: Die Anwendbarkeit der Methode ist hauptsächlich auf die Elektroenergieerzeugungsoptimierung beschränkt ### Einflussfähigkeit 1. **Akademischer Beitrag**: Bietet neue Lösungsideen für großskalige nichtkonvexe Optimierung 2. **Praktischer Wert**: Wichtiger praktischer Wert für den Betrieb und die Planung von Elektroenergieerzeugungssystemen 3. **Technologietransfer**: Erfolgreiches Beispiel für GPU-beschleunigte Optimierungsalgorithmen ### Anwendungsszenarien 1. **Elektroenergieerzeugungseinsatzplanung**: Sicherheitsbeschränkte Optimierung für Echtzeit- und Tagesmarkt 2. **Großskalige nichtkonvexe Optimierung**: Andere technische Optimierungsprobleme mit komplementären Beschränkungen 3. **GPU-Hochleistungsberechnung**: Optimierungsanwendungen, die schnelle Lösungen erfordern ## Literaturverzeichnis Der Artikel zitiert 31 relevante Literaturquellen, die SCOPF-Modellierung, MPCC-Lösungsmethoden, Augmented-Lagrangian-Theorie sowie GPU-Optimierung und andere wichtige Arbeiten abdecken und eine solide theoretische Grundlage für die Forschung bieten.