Accelerating Condensed Interior-Point Methods on SIMD/GPU Architectures

François Pacaud (), Sungho Shin, Michel Schanen, Daniel Adrian Maldonado and Mihai Anitescu
Additional contact information
François Pacaud: Argonne National Laboratory
Sungho Shin: Argonne National Laboratory
Michel Schanen: Argonne National Laboratory
Daniel Adrian Maldonado: Argonne National Laboratory
Mihai Anitescu: Argonne National Laboratory

Journal of Optimization Theory and Applications, 2024, vol. 202, issue 1, No 9, 184-203

Abstract: Abstract The interior-point method (IPM) has become the workhorse method for nonlinear programming. The performance of IPM is directly related to the linear solver employed to factorize the Karush–Kuhn–Tucker (KKT) system at each iteration of the algorithm. When solving large-scale nonlinear problems, state-of-the art IPM solvers rely on efficient sparse linear solvers to solve the KKT system. Instead, we propose a novel reduced-space IPM algorithm that condenses the KKT system into a dense matrix whose size is proportional to the number of degrees of freedom in the problem. Depending on where the reduction occurs, we derive two variants of the reduced-space method: linearize-then-reduce and reduce-then-linearize. We adapt their workflow so that the vast majority of computations are accelerated on GPUs. We provide extensive numerical results on the optimal power flow problem, comparing our GPU-accelerated reduced-space IPM with Knitro and a hybrid full-space IPM algorithm. By evaluating the derivatives on the GPU and solving the KKT system on the CPU, the hybrid solution is already significantly faster than the CPU-only solutions. The two reduced-space algorithms go one step further by solving the KKT system entirely on the GPU. As expected, the performance of the two reduction algorithms depends critically on the number of available degrees of freedom: They underperform the full-space method when the problem has many degrees of freedom, but the two algorithms are up to three times faster than Knitro as soon as the relative number of degrees of freedom becomes smaller.

Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10957-022-02129-5 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joptap:v:202:y:2024:i:1:d:10.1007_s10957-022-02129-5

Ordering information: This journal article can be ordered from
http://www.springer. ... cs/journal/10957/PS2

DOI: 10.1007/s10957-022-02129-5

Access Statistics for this article

Journal of Optimization Theory and Applications is currently edited by Franco Giannessi and David G. Hull

More articles in Journal of Optimization Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().