François Pacaud

Centre Automatique et Systèmes, Mines Paris-PSL.

Thursday, April 10, 2025, 11:00 - 12:15

SR 01-012

The interior-point method (IPM) is one of the standard algorithms for solving large-scale optimization problems. IPM solves a sequence of symmetric indefinite linear systems, known as Karush-Kuhn-Tucker (KKT) systems, that are increasingly ill-conditioned as the solution is approached. For that reason, the KKT systems are solved using complicated factorization routines. The standard sparse Bunch-Parlett factorization, implemented in HSL and MUMPS, requires numerical pivoting, making parallelization difficult. We present two novel interior-point methods that circumvent this issue. The first method intervenes at the level of linear algebra: it condenses IPM's KKT system into a symmetric positive-definite matrix, which can be solved stably without pivoting using a Cholesky factorization. 

Although condensed KKT systems are more prone to ill-conditioning than the original ones, they exhibit structured ill-conditioning that mitigates the loss of accuracy. The second method combines IPM with an Augmented Lagrangian method (Auglag-IPM). The Augmented Lagrangian term introduces an implicit dual regularization, leading to the formulation of KKT systems factorizable using a signed Cholesky factorization (LDL). We show how to retain fast local convergence of the Augmented Lagrangian algorithm using an extrapolation step. Both methods have been implemented on the GPU using MadNLP.jl, an optimization solver interfaced with the NVIDIA sparse linear solver cuDSS and with the GPU-accelerated modeler ExaModels.jl. Our experiments on large-scale nonlinear programs reveal that GPUs can attain up to a tenfold speed increase compared to CPUs. In addition, Auglag-IPM can solve complex optimization problems that are not tractable for classical IPM algorithms, including mathematical programs with complementarity constraints (MPCC).


François Pacaud's homepage: https://frapac.github.io/