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

Un Metodo Lagrangiano Aumentato su GPU per il Flusso Ottimale di Potenza AC Vincolato dalla Sicurezza

Informazioni Fondamentali

  • ID Articolo: 2510.13333
  • Titolo: An Augmented Lagrangian Method on GPU for Security-Constrained AC Optimal Power Flow
  • Autori: François Pacaud, Armin Nurkanović, Anton Pozharskiy, Alexis Montoison, Sungho Shin
  • Classificazione: math.OC (Ottimizzazione e Controllo)
  • Data di Pubblicazione: 15 ottobre 2025
  • Link Articolo: https://arxiv.org/abs/2510.13333

Riassunto

Questo articolo propone un nuovo algoritmo per risolvere il problema su larga scala del flusso ottimale di potenza AC vincolato dalla sicurezza (AC-SCOPF). Il metodo si basa sul metodo Lagrangiano aumentato con vincoli non lineari (NCL), utilizzando il metodo dei punti interni per risolvere i sottoproblemi. L'NCL presenta due vantaggi chiave per l'SC-OPF su larga scala: in primo luogo, l'NCL è in grado di gestire problemi difficili come problemi infattibili o modelli con vincoli di complementarità; in secondo luogo, il termine Lagrangiano aumentato regolarizza naturalmente il sistema lineare di Newton nel metodo dei punti interni, consentendo di risolvere il sistema di Newton mediante fattorizzazione senza pivot, che può essere parallelizzata efficientemente su GPU. I risultati numerici mostrano che MadNCL può risolvere completamente un AC-SCOPF con 500 nodi e 256 contingenze su GPU in meno di 3 minuti, mentre Knitro richiede più di 3 ore per trovare una soluzione equivalente.

Contesto di Ricerca e Motivazione

Descrizione del Problema

Nelle reti di trasmissione, la programmazione ottimale viene generalmente calcolata risolvendo il flusso ottimale di potenza vincolato dalla sicurezza (SCOPF). Questa programmazione minimizza un criterio dato (costo o perdite di rete) considerando i vincoli fisici (flussi, limiti di corrente delle linee) e le capacità dei generatori. Inoltre, la programmazione deve rimanere fattibile in una serie di scenari di contingenza corrispondenti a guasti di linee o generatori (criterio di sicurezza N-1).

Importanza del Problema

L'SCOPF è generalmente formulato come un grande problema di programmazione lineare denominato DC-SCOPF, la cui dimensione cresce linearmente con il numero di contingenze. Tuttavia, ciò avviene al costo della linearizzazione dei vincoli fisici non lineari, influenzando l'accuratezza della soluzione. Tuttavia, la risoluzione dell'AC-SCOPF con la formulazione non lineare originale rimane una sfida aperta.

Limitazioni dei Metodi Esistenti

La formulazione non lineare presenta due problemi:

  1. L'AC-SCOPF è un problema di programmazione non lineare di dimensioni enormi, che supera le capacità dei risolutori di ottimizzazione non lineare all'avanguardia come Ipopt o Knitro
  2. I vincoli di complementarità nel modello AC-SCOPF sono numericamente difficili da gestire e richiedono algoritmi specializzati

Motivazione della Ricerca

Le caratteristiche dell'AC-SCOPF su larga scala spingono l'algoritmo ai suoi limiti, poiché il numero di vincoli di complementarità cresce linearmente con il numero di contingenze. Per affrontare questa sfida, gli autori propongono l'utilizzo di un metodo Lagrangiano aumentato basato su NCL (Nonlinear Constraint Lagrangian) per risolvere l'AC-SCOPF.

Contributi Principali

  1. Prima Applicazione del Metodo Lagrangiano Aumentato: Prima applicazione di un algoritmo basato su Lagrangiano aumentato per risolvere l'SCOPF correttivo con vincoli di complementarità
  2. Implementazione Accelerata su GPU: Sviluppo di MadNCL, un'implementazione NCL con supporto per accelerazione GPU, utilizzando NVIDIA cuDSS per la risoluzione lineare
  3. Gestione dei Vincoli di Complementarità: Dimostrazione che MadNCL gestisce bene i vincoli di complementarità nell'AC-SCOPF e rileva efficacemente i problemi infattibili
  4. Significativo Miglioramento delle Prestazioni: Realizzazione di accelerazione significativa rispetto ai metodi tradizionali su istanze su larga scala, con la versione GPU più veloce di oltre 6 volte rispetto alla versione CPU

Spiegazione Dettagliata del Metodo

Definizione del Compito

Il problema del flusso ottimale di potenza AC vincolato dalla sicurezza (AC-SCOPF) è definito come:

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

Soggetto a:

  • Caso base: g0(x0,u0)=0g^0(x^0, u^0) = 0, h0(x0,u0)≤0h^0(x^0, u^0) \leq 0
  • Per ogni contingenza 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

Dove i vincoli di complementarità derivano da:

  1. Controllo Automatico della Generazione (AGC): Regolazione della potenza attiva per la frequenza
  2. Commutazione PV/PQ: Controllo della tensione e limiti di potenza reattiva

Architettura del Modello

Riformulazione MPCC

Riformulazione dell'AC-SCOPF come programmazione matematica con vincoli di complementarità (MPCC):

c(w) = 0, \quad w_0 \geq 0 \\ 0 \leq w_1 \perp w_2 \geq 0 \end{cases}$$ #### Algoritmo NCL L'NCL opera su due livelli: - **Iterazione esterna**: Aggiornamento del parametro di penalità $\rho^{(n)}$ e delle stime dei moltiplicatori $(λ^{(n)}, ν_0^{(n)})$ - **Iterazione interna**: Risoluzione del sottoproblema non lineare vincolato: $$\min_{w,r,t} L_ρ(w, r, t, λ^{(n)}, ν_0^{(n)})$$ Soggetto a: $$c(w) - r = 0, \quad W_1W_2e \leq t, \quad (w_0, w_1, w_2) \geq 0$$ #### Struttura del Sistema di Newton Il sistema di Newton del sottoproblema ha la seguente struttura: $$\begin{bmatrix} A & B^⊤ \\ B & -C \end{bmatrix} \begin{bmatrix} Δw \\ Δy \end{bmatrix} = \begin{bmatrix} r_1 \\ r_2 \end{bmatrix}$$ Dove la regolarizzazione fornita dal termine Lagrangiano aumentato consente l'utilizzo di fattorizzazione senza pivot. ### Punti di Innovazione Tecnica 1. **Regolarizzazione Naturale**: Il termine Lagrangiano aumentato regolarizza naturalmente il sistema lineare di Newton, mantenendo la non singolarità del sistema anche quando la complementarità stretta non è soddisfatta 2. **Fattorizzazione Senza Pivot**: La regolarizzazione consente l'utilizzo di metodi senza pivot come la fattorizzazione simbolica di Cholesky, che possono essere parallelizzati efficientemente su GPU 3. **Rilevamento dell'Infattibilità**: Quando il problema è infattibile, l'NCL si riconduce automaticamente a un problema di fattibilità, aumentando il parametro di penalità $ρ^{(n)}$ all'infinito ## Configurazione Sperimentale ### Dataset Utilizzo di istanze dalla libreria MATPOWER: - 118ieee, ACTIVSg200, 300ieee, ACTIVSg500 - 1354pegase, ACTIVSg2000, 2869pegase - Numero di contingenze da 2 a 256 ### Metriche di Valutazione - **Tempo di Risoluzione**: Tempo totale di risoluzione e tempo per iterazione - **Numero di Iterazioni**: Numero di iterazioni del metodo dei punti interni - **Valore Obiettivo**: Valore della funzione obiettivo della soluzione ottimale - **Fattibilità**: Capacità di rilevare contingenze infattibili ### Metodi di Confronto - **Knitro**: Risolutore di ottimizzazione all'avanguardia con supporto MPCC, utilizza il metodo di penalità esatta $\ell_1$ - **MadNCL-CPU**: Versione CPU utilizzando HSL MA57 - **MadNCL-GPU**: Versione GPU utilizzando NVIDIA cuDSS ### Dettagli di Implementazione - **Linguaggio di Programmazione**: Julia 1.11 - **Tolleranza di Convergenza**: 1e-6 - **Parametro di Barriera Minimo**: $μ_{min} = 10^{-7}$ - **Hardware**: Processore AMD EPYC 7430, GPU NVIDIA A30 (24GB memoria) ## Risultati Sperimentali ### Risultati Principali #### Prestazioni di Screening delle Contingenze Nel compito di screening delle contingenze, MadNCL supera significativamente Knitro: | Istanza | Knitro (s) | MadNCL-CPU (s) | |---------|------------|----------------| | 118ieee | 0.5 | 0.01 | | ACTIVSg500 | 5.4 | 0.3 | | 2869pegase | 238.4 | 14.1 | MadNCL è almeno 10 volte più veloce su istanze con oltre 300 nodi. #### Risoluzione dell'AC-SCOPF su Larga Scala Per l'istanza ACTIVSg500, al variare del numero di contingenze: | K | Numero di Variabili | Tempo Knitro (s) | Tempo MadNCL-GPU (s) | Fattore di Accelerazione | |---|---------------------|------------------|----------------------|--------------------------| | 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× | ### Esperimenti di Ablazione #### Prestazioni GPU vs CPU Miglioramento delle prestazioni di MadNCL-GPU rispetto a MadNCL-CPU: - Per K≥64, la versione GPU è circa 6 volte più veloce della versione CPU - Per K≥64, la versione GPU è oltre 20 volte più veloce di Knitro #### Analisi del Tempo per Iterazione Al variare del numero di contingenze, il tempo per iterazione di MadNCL-GPU cresce più lentamente, dimostrando eccellente scalabilità. ### Scoperte Sperimentali 1. **Scalabilità**: MadNCL dimostra eccellente scalabilità, in grado di gestire problemi con quasi un milione di variabili 2. **Robustezza**: L'NCL rileva e gestisce automaticamente i problemi infattibili 3. **Efficienza Parallela**: L'implementazione GPU sfrutta pienamente i vantaggi del calcolo parallelo 4. **Stabilità Numerica**: La regolarizzazione Lagrangiana aumentata migliora la stabilità numerica ## Lavori Correlati ### Principali Direzioni di Ricerca 1. **Metodi di Risoluzione MPCC**: Includono metodi diretti, metodi di regolarizzazione e metodi di penalità 2. **Ottimizzazione dei Sistemi Elettrici**: Varie strategie di risoluzione per DC-SCOPF e AC-SCOPF 3. **Accelerazione GPU dell'Ottimizzazione**: Trasferimento di algoritmi di ottimizzazione su piattaforme GPU ### Contributi dell'Articolo Rispetto ai lavori esistenti, questo articolo applica per la prima volta il metodo Lagrangiano aumentato all'AC-SCOPF con vincoli di complementarità e realizza un'accelerazione GPU efficiente. ## Conclusioni e Discussione ### Conclusioni Principali 1. MadNCL è in grado di risolvere efficacemente problemi AC-SCOPF su larga scala, gestendo quasi un milione di variabili 2. La versione accelerata su GPU realizza miglioramenti di prestazioni di decine di volte rispetto ai risolutori CPU tradizionali 3. Il metodo Lagrangiano aumentato fornisce una soluzione robusta per gestire i vincoli di complementarità ### Limitazioni 1. **Problema del Numero di Condizionamento**: Il numero di condizionamento del sistema lineare si deteriora al crescere della dimensione del problema 2. **Convergenza**: La convergenza non è sufficientemente stabile su alcune istanze su larga scala 3. **Limitazioni di Memoria**: I limiti di memoria GPU limitano la dimensione massima del problema gestibile ### Direzioni Future 1. Affrontare il problema del cattivo condizionamento nel sistema di Newton del metodo dei punti interni 2. Estensione a istanze ancora più grandi (decine di migliaia di nodi, centinaia di contingenze) 3. Miglioramento delle tecniche di precondizionamento per aumentare la stabilità numerica ## Valutazione Approfondita ### Vantaggi 1. **Innovazione del Metodo**: Prima applicazione dell'NCL all'AC-SCOPF, percorso tecnico innovativo 2. **Qualità dell'Implementazione**: Implementazione GPU di alta qualità, che sfrutta pienamente i vantaggi del calcolo parallelo 3. **Valutazione Sperimentale Completa**: Valutazione sperimentale completa, includendo test di scalabilità e robustezza 4. **Valore Pratico**: Il significativo miglioramento delle prestazioni rende possibili applicazioni in tempo reale su larga scala ### Insufficienze 1. **Analisi Teorica**: Manca l'analisi teorica della convergenza dell'NCL sul problema SCOPF 2. **Stabilità Numerica**: Persistono problemi di stabilità numerica sulle istanze di dimensione massima 3. **Generalità**: L'applicabilità del metodo è principalmente limitata al campo dell'ottimizzazione dei sistemi elettrici ### Impatto 1. **Contributo Accademico**: Fornisce nuovi approcci di risoluzione per l'ottimizzazione non convessa su larga scala 2. **Valore Pratico**: Ha importante valore pratico per l'operazione e la pianificazione dei sistemi elettrici 3. **Promozione Tecnologica**: Caso di successo di algoritmi di ottimizzazione accelerati su GPU ### Scenari Applicabili 1. **Programmazione dei Sistemi Elettrici**: Ottimizzazione vincolata dalla sicurezza per i mercati in tempo reale e giorno prima 2. **Ottimizzazione Non Convessa su Larga Scala**: Altri problemi di ottimizzazione ingegneristica con vincoli di complementarità 3. **Calcolo ad Alte Prestazioni su GPU**: Applicazioni di ottimizzazione che richiedono risoluzione veloce ## Bibliografia L'articolo cita 31 articoli correlati, coprendo molteplici aspetti della modellazione SCOPF, metodi di risoluzione MPCC, teoria Lagrangiana aumentata e ottimizzazione GPU, fornendo una solida base teorica per la ricerca.