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

Basic Information

  • Paper ID: 2510.13333
  • Title: An Augmented Lagrangian Method on GPU for Security-Constrained AC Optimal Power Flow
  • Authors: François Pacaud, Armin Nurkanović, Anton Pozharskiy, Alexis Montoison, Sungho Shin
  • Classification: math.OC (Optimization and Control)
  • Publication Date: October 15, 2025
  • Paper Link: https://arxiv.org/abs/2510.13333

Abstract

This paper proposes a novel algorithm for solving large-scale security-constrained AC optimal power flow (AC-SCOPF). The method is based on the nonlinear constraint Lagrangian (NCL) approach, utilizing interior-point methods to solve subproblems. NCL offers two key advantages for large-scale SC-OPF: first, it can handle difficult problems such as infeasible instances or models with complementarity constraints; second, the augmented Lagrangian term naturally regularizes the Newton linear system in the interior-point method, enabling the use of pivot-free decomposition to solve the Newton system, which can be efficiently parallelized on GPUs. Numerical results demonstrate that MadNCL can completely solve a 500-node AC-SCOPF with 256 contingencies on GPU in less than 3 minutes, whereas Knitro requires over 3 hours to find an equivalent solution.

Research Background and Motivation

Problem Description

In transmission networks, optimal scheduling is typically computed by solving security-constrained optimal power flow (SCOPF). This scheduling minimizes a given criterion (cost or network losses) while considering physical constraints (power flow, line flow limits) and generator capacity. Furthermore, the scheduling should remain feasible under a series of contingency scenarios corresponding to line or generator failures (N-1 security criterion).

Problem Significance

SCOPF is typically formulated as a large-scale linear programming problem called DC-SCOPF, whose scale grows linearly with the number of contingencies. However, this comes at the cost of linearizing nonlinear physical constraints, affecting solution accuracy. Solving AC-SCOPF with the original nonlinear formulation remains an open challenge.

Limitations of Existing Methods

The nonlinear formulation presents two problems:

  1. AC-SCOPF is a massive-scale nonlinear programming problem whose scale exceeds the capabilities of state-of-the-art nonlinear optimization solvers such as Ipopt or Knitro
  2. Complementarity constraints in the AC-SCOPF model are numerically difficult to handle and require specialized algorithms

Research Motivation

The characteristics of large-scale AC-SCOPF push algorithms to their limits, as the number of complementarity constraints grows linearly with the number of contingencies. To address this challenge, the authors propose using an augmented Lagrangian method based on the nonlinear constraint Lagrangian (NCL) to solve AC-SCOPF.

Core Contributions

  1. First Application of Augmented Lagrangian Method: First application of augmented Lagrangian-based algorithms to solve corrective SCOPF with complementarity constraints
  2. GPU-Accelerated Implementation: Develops MadNCL, an NCL implementation supporting GPU acceleration, utilizing NVIDIA cuDSS for linear system solving
  3. Handling Complementarity Constraints: Demonstrates that MadNCL effectively handles complementarity constraints in AC-SCOPF and efficiently detects infeasible problems
  4. Significant Performance Improvement: Achieves substantial acceleration compared to traditional methods on large-scale instances, with GPU version being over 6 times faster than CPU version

Methodology Details

Problem Formulation

The security-constrained AC optimal power flow (AC-SCOPF) problem is defined as:

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

Subject to:

  • Base case: g0(x0,u0)=0g^0(x^0, u^0) = 0, h0(x0,u0)≤0h^0(x^0, u^0) \leq 0
  • For each contingency 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

Where complementarity constraints arise from:

  1. Automatic Generation Control (AGC): Active power adjustment for frequency regulation
  2. PV/PQ Switching: Voltage control and reactive power limits

Model Architecture

MPCC Reformulation

Reformulates AC-SCOPF as Mathematical Programming with Complementarity Constraints (MPCC):

c(w) = 0, \quad w_0 \geq 0 \\ 0 \leq w_1 \perp w_2 \geq 0 \end{cases}$$ #### NCL Algorithm NCL operates at two levels: - **Outer iteration**: Updates penalty parameter $\rho^{(n)}$ and multiplier estimates $(λ^{(n)}, ν_0^{(n)})$ - **Inner iteration**: Solves the constrained nonlinear subproblem: $$\min_{w,r,t} L_ρ(w, r, t, λ^{(n)}, ν_0^{(n)})$$ Subject to: $$c(w) - r = 0, \quad W_1W_2e \leq t, \quad (w_0, w_1, w_2) \geq 0$$ #### Newton System Structure The Newton system of the subproblem has the following structure: $$\begin{bmatrix} A & B^⊤ \\ B & -C \end{bmatrix} \begin{bmatrix} Δw \\ Δy \end{bmatrix} = \begin{bmatrix} r_1 \\ r_2 \end{bmatrix}$$ Where the regularization provided by the augmented Lagrangian term enables the use of pivot-free decomposition. ### Technical Innovations 1. **Natural Regularization**: The augmented Lagrangian term naturally regularizes the Newton linear system, maintaining system non-singularity even when strict complementarity does not hold 2. **Pivot-Free Decomposition**: Regularization enables the use of pivot-free methods such as symbolic Cholesky decomposition, which can be efficiently parallelized on GPUs 3. **Infeasibility Detection**: When the problem is infeasible, NCL automatically falls back to a feasibility problem by increasing the penalty parameter $ρ^{(n)}$ to infinity ## Experimental Setup ### Datasets Instances from the MATPOWER library: - 118ieee, ACTIVSg200, 300ieee, ACTIVSg500 - 1354pegase, ACTIVSg2000, 2869pegase - Number of contingencies ranging from 2 to 256 ### Evaluation Metrics - **Solution Time**: Total solution time and per-iteration time - **Iteration Count**: Number of interior-point method iterations - **Objective Value**: Objective function value at optimal solution - **Feasibility**: Ability to detect infeasible contingencies ### Comparison Methods - **Knitro**: State-of-the-art optimization solver supporting MPCC, using $\ell_1$ exact penalty method - **MadNCL-CPU**: CPU version using HSL MA57 - **MadNCL-GPU**: GPU version using NVIDIA cuDSS ### Implementation Details - **Programming Language**: Julia 1.11 - **Convergence Tolerance**: 1e-6 - **Minimum Barrier Parameter**: $μ_{min} = 10^{-7}$ - **Hardware**: AMD EPYC 7430 processor, NVIDIA A30 GPU (24GB memory) ## Experimental Results ### Main Results #### Contingency Screening Performance MadNCL significantly outperforms Knitro in contingency screening: | Instance | Knitro (s) | MadNCL-CPU (s) | |----------|------------|----------------| | 118ieee | 0.5 | 0.01 | | ACTIVSg500 | 5.4 | 0.3 | | 2869pegase | 238.4 | 14.1 | MadNCL is at least 10 times faster on instances with over 300 nodes. #### Large-Scale AC-SCOPF Solution For the ACTIVSg500 instance, as the number of contingencies increases: | K | Variables | Knitro Time (s) | MadNCL-GPU Time (s) | Speedup | |---|-----------|-----------------|---------------------|---------| | 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× | ### Ablation Studies #### GPU vs CPU Performance Performance improvement of MadNCL-GPU compared to MadNCL-CPU: - For K≥64, GPU version is approximately 6 times faster than CPU version - For K≥64, GPU version is over 20 times faster than Knitro #### Per-Iteration Time Analysis As the number of contingencies increases, MadNCL-GPU shows the slowest per-iteration time growth, demonstrating excellent scalability. ### Experimental Findings 1. **Scalability**: MadNCL demonstrates excellent scalability, capable of handling problems with nearly one million variables 2. **Robustness**: NCL automatically detects and handles infeasible problems 3. **Parallel Efficiency**: GPU implementation fully leverages the advantages of parallel computing 4. **Numerical Stability**: Regularization from augmented Lagrangian improves numerical stability ## Related Work ### Main Research Directions 1. **MPCC Solution Methods**: Including direct methods, regularization methods, and penalty methods 2. **Power System Optimization**: Various solution strategies for DC-SCOPF and AC-SCOPF 3. **GPU-Accelerated Optimization**: Porting optimization algorithms to GPU platforms ### Contributions of This Work Compared to existing work, this paper is the first to apply augmented Lagrangian methods to AC-SCOPF with complementarity constraints and implements efficient GPU acceleration. ## Conclusions and Discussion ### Main Conclusions 1. MadNCL can effectively solve large-scale AC-SCOPF problems, handling nearly one million variables 2. GPU-accelerated version achieves tens of times performance improvement compared to traditional CPU solvers 3. Augmented Lagrangian method provides a robust solution for handling complementarity constraints ### Limitations 1. **Condition Number Issues**: Linear system condition number deteriorates as problem scale increases 2. **Convergence**: Convergence stability is insufficient on certain large-scale instances 3. **Memory Constraints**: GPU memory limits the maximum problem size that can be handled ### Future Directions 1. Address ill-conditioning issues in Newton systems of interior-point methods 2. Extend to larger-scale instances (thousands of nodes, hundreds of contingencies) 3. Improve preconditioning techniques to enhance numerical stability ## In-Depth Evaluation ### Strengths 1. **Methodological Innovation**: First application of NCL to AC-SCOPF with novel technical approach 2. **Implementation Quality**: High-quality GPU implementation fully leveraging parallel computing advantages 3. **Comprehensive Experiments**: Thorough experimental evaluation including scalability and robustness testing 4. **Practical Value**: Significant performance improvement enables large-scale real-time applications ### Weaknesses 1. **Theoretical Analysis**: Lacks convergence theory analysis of NCL on SCOPF problems 2. **Numerical Stability**: Numerical stability issues remain on largest-scale instances 3. **Generalizability**: Method applicability is primarily limited to power system optimization domain ### Impact 1. **Academic Contribution**: Provides new solution approaches for large-scale nonconvex optimization 2. **Practical Value**: Important practical value for power system operation and planning 3. **Technology Promotion**: Successful case study of GPU-accelerated optimization algorithms ### Applicable Scenarios 1. **Power System Scheduling**: Real-time and day-ahead market security-constrained optimization 2. **Large-Scale Nonconvex Optimization**: Other engineering optimization problems with complementarity constraints 3. **GPU High-Performance Computing**: Optimization applications requiring rapid solution ## References The paper cites 31 relevant references covering multiple aspects including SCOPF modeling, MPCC solution methods, augmented Lagrangian theory, and GPU optimization, providing a solid theoretical foundation for the research.