(251g) Nonlinear Programming on GPUs for AI-Assisted Decision-Making and Beyond

The advances in GPU computing have enabled the tremendous success of AI. The large language models, like ChatGPT, have neural net models with trillions of parameters, and without the powerful parallel computing capabilities of GPUs, it is impossible to train and utilize such large AI models. GPU computing is making profound impacts not only in AI but also in classical mathematical programming---solving decision-making problems. The recent successful development of various mathematical optimization solvers running on GPUs, such as OSQP [1], cuPDLP [2], and MadNLP [3] represent significant opportunities in utilizing the capabilities of GPUs for solving large-scale and complex mathematical programs.

In this presentation, we will discuss this exciting new frontier of mathematical programming on GPUs, focusing on the nonlinear optimization aspect. Despite the impressive performance of GPUs in deep learning, their usage in solving large-scale nonlinear programming has been traditionally limited due to the practical difficulties in implementing sparse automatic differentiation and sparse matrix factorization routines. In particular, the previous generations of GPU-accelerated solutions tools have been significantly slower than the alternative tools on CPUs [4]. In our recent approaches [3], we have overcome the previous challenges with two novel strategies: single instruction, multiple data (SIMD) abstractions for NLPs, which addresses the issue of sparse automatic differentiation, and a condensed-space interior point method with inequality relaxation, which resolves the challenges associated with sparse linear algebra. Our empirical results on AC optimal power flow problems highlight the considerable advantages of utilizing GPUs. Our software implementations, ExaModels and MadNLP, when executed on GPUs, deliver performance gains exceeding 20 times that of the fastest CPU-based alternatives. We also compare this approach with the previously proposed Hybrid KKT [5] and reduced-space approaches [6] and discuss the current limitation of the GPU solvers---the numerical instability due to ill-conditioning and limited portability.

Additionally, we will present our initial empirical results on solving AI-assisted decision-making problems---more specifically, neural-network-constrained optimization problems---using GPU solvers. There has been growing interest in these problems, as neural network surrogate models are increasingly employed in different applications [7]. These optimization problems embed large-scale neural networks in their objective and constraints, and the complexity of neural net surrogate models makes their solution computationally challenging. We will present numerical results highlighting the effectiveness of the GPU-accelerated solution approaches in handling the complexity of neural network surrogate models.

[1] M. Schubiger, G. Banjac, and J. Lygeros, “GPU acceleration of ADMM for large-scale quadratic programming,” Journal of Parallel and Distributed Computing, vol. 144, pp. 55–67, Oct. 2020, doi: 10.1016/j.jpdc.2020.05.021.
[2] H. Lu et al., “cuPDLP-C: A Strengthened Implementation of cuPDLP for Linear Programming by C language.” arXiv, Jan. 07, 2024. doi: 10.48550/arXiv.2312.14832.
[3] S. Shin, F. Pacaud, and M. Anitescu, “Accelerating Optimal Power Flow with GPUs: SIMD Abstraction of Nonlinear Programs and Condensed-Space Interior-Point Methods.” arXiv, Jul. 31, 2023. doi: 10.48550/arXiv.2307.16830.
[4] B. Tasseff, C. Coffrin, A. Wächter, and C. Laird, “Exploring Benefits of Linear Solver Parallelism on Modern Nonlinear Optimization Applications.” arXiv, Sep. 17, 2019. doi: 10.48550/arXiv.1909.08104.
[5] S. Regev et al., “HyKKT: a hybrid direct-iterative method for solving KKT linear systems,” Optimization Methods and Software, vol. 38, no. 2, pp. 332–355, Mar. 2023, doi: 10.1080/10556788.2022.2124990.
[6] F. Pacaud, S. Shin, M. Schanen, D. A. Maldonado, and M. Anitescu, “Accelerating Condensed Interior-Point Methods on SIMD/GPU Architectures,” J Optim Theory Appl, Feb. 2023, doi: 10.1007/s10957-022-02129-5.
[7] F. Ceccon et al., “OMLT: Optimization & Machine Learning Toolkit,” Journal of Machine Learning Research, vol. 23, no. 349, pp. 1–8, 2022.