Une Méthode du Lagrangien Augmenté sur GPU pour le Flux Optimal de Puissance AC Contraint en Sécurité

Informations Fondamentales

• ID de l'article: 2510.13333
• Titre: An Augmented Lagrangian Method on GPU for Security-Constrained AC Optimal Power Flow
• Auteurs: François Pacaud, Armin Nurkanović, Anton Pozharskiy, Alexis Montoison, Sungho Shin
• Classification: math.OC (Optimisation et Contrôle)
• Date de publication: 15 octobre 2025
• Lien de l'article: https://arxiv.org/abs/2510.13333

Résumé

Cet article propose un nouvel algorithme pour résoudre le problème du flux optimal de puissance AC contraint en sécurité (AC-SCOPF) à grande échelle. La méthode est basée sur la méthode du Lagrangien augmenté avec contraintes non linéaires (NCL), utilisant une méthode de points intérieurs pour résoudre les sous-problèmes. La méthode NCL présente deux avantages clés pour les problèmes SC-OPF à grande échelle : premièrement, elle peut traiter les problèmes difficiles tels que les problèmes infaisables ou les modèles avec contraintes de complémentarité ; deuxièmement, le terme du Lagrangien augmenté régularise naturellement le système linéaire newtonien dans la méthode de points intérieurs, permettant la résolution du système newtonien par décomposition sans pivot, ce qui peut être parallélisé efficacement sur GPU. Les résultats numériques montrent que MadNCL peut résoudre complètement un AC-SCOPF avec 500 nœuds et 256 défaillances sur GPU en moins de 3 minutes, tandis que Knitro nécessite plus de 3 heures pour trouver une solution équivalente.

Contexte et Motivation de la Recherche

Description du Problème

Dans les réseaux de transport d'électricité, l'ordonnancement optimal est généralement calculé en résolvant le problème du flux optimal de puissance contraint en sécurité (SCOPF). Cet ordonnancement minimise un critère donné (coût ou pertes du réseau) tout en respectant les contraintes physiques (flux de puissance, limites de flux de ligne) et les capacités des générateurs. De plus, l'ordonnancement doit rester réalisable dans une série de scénarios d'urgence correspondant à des défaillances de lignes ou de générateurs (critère de sécurité N-1).

Importance du Problème

Le SCOPF est généralement formulé comme un problème de programmation linéaire à grande échelle appelé DC-SCOPF, dont la taille croît linéairement avec le nombre de défaillances. Cependant, cela se fait au détriment de la linéarisation des contraintes physiques non linéaires, affectant la précision de la solution. Néanmoins, la résolution du AC-SCOPF avec la formulation non linéaire originale reste un défi ouvert.

Limitations des Méthodes Existantes

La formulation non linéaire présente deux problèmes :

1. Le AC-SCOPF est un problème de programmation non linéaire de très grande taille, dépassant les capacités des solveurs d'optimisation non linéaire de pointe tels que Ipopt ou Knitro
2. Les contraintes de complémentarité dans le modèle AC-SCOPF sont numériquement difficiles à traiter et nécessitent des algorithmes spécialisés

Motivation de la Recherche

Les caractéristiques du AC-SCOPF à grande échelle poussent l'algorithme à ses limites, car le nombre de contraintes de complémentarité croît linéairement avec le nombre de défaillances. Pour relever ce défi, les auteurs proposent d'utiliser une méthode du Lagrangien augmenté basée sur la méthode NCL (Lagrangien augmenté avec contraintes non linéaires) pour résoudre le AC-SCOPF.

Contributions Principales

1. Première application de la méthode du Lagrangien augmenté: Première utilisation d'un algorithme basé sur le Lagrangien augmenté pour résoudre le SCOPF correctif avec contraintes de complémentarité
2. Implémentation accélérée par GPU: Développement de MadNCL, une implémentation NCL supportant l'accélération GPU, utilisant NVIDIA cuDSS pour la résolution linéaire
3. Traitement des contraintes de complémentarité: Démonstration que MadNCL gère bien les contraintes de complémentarité dans le AC-SCOPF et détecte efficacement les problèmes infaisables
4. Amélioration significative des performances: Réalisation d'une accélération considérable par rapport aux méthodes traditionnelles, avec la version GPU étant plus de 6 fois plus rapide que la version CPU

Détails de la Méthode

Définition de la Tâche

Le problème du flux optimal de puissance AC contraint en sécurité (AC-SCOPF) est défini comme :

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

Soumis aux contraintes :

• Cas de base : $g^0(x^0, u^0) = 0$, $h^0(x^0, u^0) \leq 0$
• Pour chaque défaillance $k \in \{1, \cdots, 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$

Où les contraintes de complémentarité proviennent de :

1. Contrôle automatique de la génération (AGC): Régulation de la puissance active pour la fréquence
2. Commutation PV/PQ: Contrôle de tension et limites de puissance réactive

Architecture du Modèle

Reformulation MPCC

Reformulation du AC-SCOPF en tant que programmation mathématique avec contraintes de complémentarité (MPCC) :

$\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}$

Algorithme NCL

L'algorithme NCL opère sur deux niveaux :

• Itérations externes: Mise à jour du paramètre de pénalité $\rho^{(n)}$ et des estimations des multiplicateurs $(λ^{(n)}, ν_0^{(n)})$
• Itérations internes: Résolution du sous-problème non linéaire contraint :

$\min_{w,r,t} L_ρ(w, r, t, λ^{(n)}, ν_0^{(n)})$

Soumis aux contraintes : $c(w) - r = 0, \quad W_1W_2e \leq t, \quad (w_0, w_1, w_2) \geq 0$

Structure du Système Newtonien

Le système newtonien du sous-problème possède la structure suivante :

$\begin{bmatrix} A & B^⊤ \\ B & -C \end{bmatrix} \begin{bmatrix} Δw \\ Δy \end{bmatrix} = \begin{bmatrix} r_1 \\ r_2 \end{bmatrix}$

Où la régularisation fournie par le terme du Lagrangien augmenté permet l'utilisation de décompositions sans pivot.

Points d'Innovation Technique

1. Régularisation naturelle: Le terme du Lagrangien augmenté régularise naturellement le système linéaire newtonien, maintenant la non-singularité du système même lorsque la complémentarité stricte n'est pas satisfaite
2. Décomposition sans pivot: La régularisation permet l'utilisation de méthodes sans pivot telles que la décomposition de Cholesky symbolique, qui peuvent être parallélisées efficacement sur GPU
3. Détection d'infaisabilité: Lorsque le problème est infaisable, NCL bascule automatiquement vers un problème de faisabilité, en augmentant le paramètre de pénalité $ρ^{(n)}$ à l'infini

Configuration Expérimentale

Ensembles de Données

Utilisation d'instances de la bibliothèque MATPOWER :

• 118ieee, ACTIVSg200, 300ieee, ACTIVSg500
• 1354pegase, ACTIVSg2000, 2869pegase
• Nombre de défaillances variant de 2 à 256

Métriques d'Évaluation

• Temps de résolution: Temps total de résolution et temps par itération
• Nombre d'itérations: Nombre d'itérations de la méthode de points intérieurs
• Valeur objective: Valeur de la fonction objective à la solution optimale
• Faisabilité: Capacité à détecter les défaillances infaisables

Méthodes de Comparaison

• Knitro: Solveur d'optimisation de pointe supportant MPCC, utilisant la méthode de pénalité exacte $\ell_1$
• MadNCL-CPU: Version CPU utilisant HSL MA57
• MadNCL-GPU: Version GPU utilisant NVIDIA cuDSS

Détails d'Implémentation

• Langage de programmation: Julia 1.11
• Tolérance de convergence: 1e-6
• Paramètre de barrière minimal: $μ_{min} = 10^{-7}$
• Matériel: Processeur AMD EPYC 7430, GPU NVIDIA A30 (24 Go de mémoire)

Résultats Expérimentaux

Résultats Principaux

Performance du Criblage des Défaillances

Dans la tâche de criblage des défaillances, MadNCL surpasse significativement Knitro :

MadNCL est au moins 10 fois plus rapide sur les instances dépassant 300 nœuds.

Résolution du AC-SCOPF à Grande Échelle

Pour l'instance ACTIVSg500, avec l'augmentation du nombre de défaillances :

Expériences d'Ablation

Performance GPU vs CPU

Amélioration des performances de MadNCL-GPU par rapport à MadNCL-CPU :

• Pour K≥64, la version GPU est environ 6 fois plus rapide que la version CPU
• Pour K≥64, la version GPU est environ 20 fois plus rapide que Knitro

Analyse du Temps par Itération

Avec l'augmentation du nombre de défaillances, le temps par itération de MadNCL-GPU augmente le plus lentement, démontrant une excellente scalabilité.

Découvertes Expérimentales

1. Scalabilité: MadNCL démontre une excellente scalabilité, capable de traiter des problèmes avec près d'un million de variables
2. Robustesse: NCL peut automatiquement détecter et traiter les problèmes infaisables
3. Efficacité parallèle: L'implémentation GPU exploite pleinement les avantages du calcul parallèle
4. Stabilité numérique: La régularisation du Lagrangien augmenté améliore la stabilité numérique

Travaux Connexes

Directions de Recherche Principales

1. Méthodes de résolution MPCC: Incluant les méthodes directes, les méthodes de régularisation et les méthodes de pénalité
2. Optimisation des systèmes électriques: Diverses stratégies de résolution pour DC-SCOPF et AC-SCOPF
3. Optimisation accélérée par GPU: Portage d'algorithmes d'optimisation sur plateforme GPU

Contribution de cet Article

Par rapport aux travaux existants, cet article applique pour la première fois la méthode du Lagrangien augmenté au AC-SCOPF avec contraintes de complémentarité et réalise une accélération GPU efficace.

Conclusions et Discussion

Conclusions Principales

1. MadNCL peut résoudre efficacement les problèmes AC-SCOPF à grande échelle, traitant près d'un million de variables
2. La version accélérée par GPU réalise une amélioration des performances de plusieurs dizaines de fois par rapport aux solveurs CPU traditionnels
3. La méthode du Lagrangien augmenté fournit une solution robuste pour traiter les contraintes de complémentarité

Limitations

1. Problèmes de conditionnement: Le nombre de conditionnement du système linéaire se détériore avec l'augmentation de la taille du problème
2. Convergence: La convergence n'est pas suffisamment stable sur certaines instances à grande échelle
3. Limitations de mémoire: Les limites de mémoire GPU limitent la taille maximale des problèmes pouvant être traités

Directions Futures

1. Résoudre les problèmes de mauvais conditionnement du système newtonien dans la méthode de points intérieurs
2. Extension à des instances plus grandes (dizaines de milliers de nœuds, centaines de défaillances)
3. Amélioration des techniques de préconditionnement pour augmenter la stabilité numérique

Évaluation Approfondie

Avantages

1. Innovativité de la méthode: Première application de NCL au AC-SCOPF, approche technique novatrice
2. Qualité de l'implémentation: Implémentation GPU de haute qualité, exploitant pleinement les avantages du calcul parallèle
3. Évaluation expérimentale complète: Évaluation expérimentale exhaustive, incluant les tests de scalabilité et de robustesse
4. Valeur pratique: L'amélioration significative des performances rend possible les applications en temps réel à grande échelle

Insuffisances

1. Analyse théorique: Manque d'analyse théorique de la convergence de NCL sur les problèmes SCOPF
2. Stabilité numérique: Problèmes de stabilité numérique subsistent sur les instances de plus grande taille
3. Généralité: L'applicabilité de la méthode est principalement limitée au domaine de l'optimisation des systèmes électriques

Impact

1. Contribution académique: Fournit une nouvelle approche de résolution pour l'optimisation non convexe à grande échelle
2. Valeur pratique: Importance pratique considérable pour l'exploitation et la planification des systèmes électriques
3. Promotion technologique: Cas de succès de l'accélération GPU pour les algorithmes d'optimisation

Scénarios d'Application

1. Ordonnancement des systèmes électriques: Optimisation contraint en sécurité pour les marchés en temps réel et jour d'avance
2. Optimisation non convexe à grande échelle: Autres problèmes d'optimisation d'ingénierie avec contraintes de complémentarité
3. Calcul haute performance sur GPU: Applications d'optimisation nécessitant une résolution rapide

Références

L'article cite 31 références pertinentes, couvrant plusieurs aspects importants incluant la modélisation SCOPF, les méthodes de résolution MPCC, la théorie du Lagrangien augmenté et l'optimisation GPU, fournissant une base théorique solide pour la recherche.