HyKKT: a hybrid direct-iterative method for solving KKT linear systems. (4th March 2023)

• Record Type: Journal Article
• Authors: Regev, Shaked; Chiang, Nai-Yuan; Darve, Eric; Petra, Cosmin G.; Saunders, Michael A.; Świrydowicz, Kasia; Peleš, Slaven
• Is Part Of: Optimization methods and software. Volume 38:Number 2(2023)
• Page Start: 332
• Page End: 355
• Publication Date: 2023-03-04
• Subjects: Optimization -- interior methods -- KKT systems -- sparse matrix factorization -- GPU; Mathematical optimization -- Periodicals; Algorithms -- Periodicals; 519.7
• DOI: 10.1080/10556788.2022.2124990
• Languages: English
• ISSNs: 1055-6788

Abstract

Abstract : We propose a solution strategy for the large indefinite linear systems arising in interior methods for nonlinear optimization. The method is suitable for implementation on hardware accelerators such as graphical processing units (GPUs). The current gold standard for sparse indefinite systems is the LBLT factorization where L is a lower triangular matrix and B is 1 × 1 or 2 × 2 block diagonal. However, this requires pivoting, which substantially increases communication cost and degrades performance on GPUs. Our approach solves a large indefinite system by solving multiple smaller positive definite systems, using an iterative solver on the Schur complement and an inner direct solve (via Cholesky factorization) within each iteration. Cholesky is stable without pivoting, thereby reducing communication and allowing reuse of the symbolic factorization. We demonstrate the practicality of our approach on large optimal power flow problems and show that it can efficiently utilize GPUs and outperform LBL T factorization of the full system.