×

HyKKT: a hybrid direct-iterative method for solving KKT linear systems. (English) Zbl 1515.90133

Summary: 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 \times 1\) or \(2 \times 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 \(\mathrm{LBL}^T\) factorization of the full system.

MSC:

90C30 Nonlinear programming
90C51 Interior-point methods

References:

[1] Acemoglu, D., Chernozhukov, V., Werning, I., and Whinston, M.D., Optimal targeted lockdowns in a multi-group sir model, Working Paper no. 27102, National Bureau of Economic Research, 10:w27102, 2020. Available at http://www.nber.org/papers/w27102.
[2] Andronescu, M.; Condon, A.; Hoos, H. H.; Mathews, D. H.; Murphy, K. P., Computational approaches for RNA energy parameter estimation, RNA, 16, 12, 2304-2318 (2010)
[3] Bell, N. and Garland, M., Efficient sparse matrix-vector multiplication on CUDA, NVIDIA Technical Report NVR-2008-004, NVIDIA Corporation, December 2008.
[4] Benzi, M.; Liu, J., Block preconditioning for saddle point systems with indefinite (1, 1) block, Int. J. Comput. Math., 84, 8, 1117-1129 (2007) · Zbl 1123.65028
[5] Booth, J.D., Rajamanickam, S., and Thornquist, H., Basker: A threaded sparse LU factorization utilizing hierarchical parallelism and data layouts, 2016 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW), IEEE, 2016, pp. 673-682.
[6] Byrd, R. H.; Nocedal, J.; Waltz, R. A., Knitro: An Integrated Package for Nonlinear Optimization, 35-59 (2006), Springer US: Springer US, Boston, MA · Zbl 1108.90004
[7] Chakrabarti, S., Kraning, M., Chu, E., Baldick, R., and Boyd, S., Security constrained optimal power flow via proximal message passing, 2014 Clemson University Power Systems Conference, IEEE, 2014, pp. 1-8.
[8] Chen, Y.; Davis, T. A.; Hager, W. W.; Rajamanickam, S., Algorithm 887: CHOLMOD, supernodal sparse Cholesky factorization and update/downdate, ACM Trans. Math. Softw., 35, 3, 22:1-22:14 (2008)
[9] Chiang, N.-Y.; Zavala, V. M., An inertia-free filter line-search algorithm for large-scale nonlinear programming, Comput. Optim. Appl., 64, 2, 327-354 (2016) · Zbl 1350.90031
[10] Davis, T. A.; Natarajan, E. P., Algorithm 907: KLU, a direct sparse solver for circuit simulation problems, ACM Trans. Math. Softw., 37, 3, 1-17 (2010) · Zbl 1364.65066
[11] Dollar, H.; Gould, N.; Schilders, W.; Wathen, A., Implicit-factorization preconditioning and iterative solvers for regularized saddle-point systems, SIAM J. Matrix Anal. Appl., 28, 170-189 (2006) · Zbl 1104.65310
[12] Duff, I. S., MA57-a code for the solution of sparse symmetric definite and indefinite systems, ACM Trans. Math. Softw., 30, 2, 118-144 (2004) · Zbl 1070.65525
[13] Duff, I.; Hogg, J.; Lopez, F., A new sparse LDL^T solver using a posteriori threshold pivoting, SIAM J. Optim., 42, 2, C23-C42 (2019) · Zbl 1434.65049
[14] Golub, G. H.; Greif, C., On solving block-structured indefinite linear systems, SIAM J. Sci. Comput., 6, 24, 2076-2092 (2003) · Zbl 1036.65033
[15] Golub, G. H.; Van Loan, C. F., Matrix Computations (2013), The Johns Hopkins University Press: The Johns Hopkins University Press, Baltimore · Zbl 1268.65037
[16] Gondzio, J., HOPDM (version 2.12)–a fast LP solver based on a primal-dual interior point method, Eur. J. Oper. Res., 85, 1, 221-225 (1995) · Zbl 0925.90284
[17] He, K.; Tan, S. X.-D.; Wang, H.; Shi, G., GPU-accelerated parallel sparse LU factorization method for fast circuit analysis, IEEE Trans. Very Large Scale Integr. (VLSI) Syst., 24, 3, 1140-1150 (2015)
[18] Hestenes, M. R.; Stiefel, E. L., Methods of conjugate gradients for solving linear systems, J. Res. Nat. Bureau Standards, 49, 409-436 (1952) · Zbl 0048.09901
[19] Hénon, P.; Ramet, P.; Roman, J., PaStiX: A high-performance parallel direct solver for sparse symmetric definite systems, Parallel. Comput., 28, 2, 301-321 (2002) · Zbl 0984.68208
[20] Jerez, J., Merkli, S., Bennani, S., and Strauch, H., FORCES-RTTO: A tool for on-board real-time autonomous trajectory planning, 10th International ESA Conference on Guidance, Navigation and Control Systems, ESA Salzburg, Austria, 2017, pp. 1-22.
[21] Keller, M.; Geiger, S.; Günther, M.; Pischinger, S.; Abel, D.; Albin, T., Model predictive air path control for a two-stage turbocharged spark-ignition engine with low pressure exhaust gas recirculation, Int. J. Eng. Res., 21, 10, 1835-1845 (2020)
[22] Kourounis, D.; Fuchs, A.; Schenk, O., Toward the next generation of multiperiod optimal power flow solvers, IEEE Trans. Power Syst., 33, 4, 4005-4014 (2018)
[23] Li, X. S., An overview of SuperLU: Algorithms, implementation, and user interface, ACM Trans. Math. Softw., 31, 3, 302-325 (2005) · Zbl 1136.65312
[24] Ma, Y.; Matuško, J.; Borrelli, F., Stochastic model predictive control for building hvac systems: Complexity and conservatism, IEEE. Trans. Control. Syst. Technol., 23, 1, 101-116 (2014)
[25] Maack, J. and Abhyankar, S., ACOPF sparse linear solver test suite, 2020. Available at github.com/NREL/opf_matrices.
[26] Molzahn, D. K.; Dörfler, F.; Sandberg, H.; Low, S. H.; Chakrabarti, S.; Baldick, R.; Lavaei, J., A survey of distributed optimization and control algorithms for electric power systems, IEEE. Trans. Smart. Grid., 8, 6, 2941-2962 (2017)
[27] Montoison, A.; Orban, D., Tricg and trimr: Two iterative methods for symmetric quasi-definite systems, SIAM J. Sci. Comput., 43, 4, 302-325 (2021) · Zbl 07378167
[28] Nocedal, J.; Wright, S. J., Numerical Optimization (2006), Springer Verlag: Springer Verlag, New York · Zbl 1104.65059
[29] Paige, C. C.; Saunders, M. A., Solution of sparse indefinite systems of linear equations, SIAM J. Numer. Anal., 12, 617-629 (1975) · Zbl 0319.65025
[30] Petra, C.G. and Chiang, N.-Y., HiOp-User Guide, Technical Report LLNL-SM-743591, Lawrence Livermore National Laboratory. Available at https://github.com/LLNL/hiop/blob/develop/doc/hiop_usermanual.pdf.
[31] Petra, C.; Gavrea, B.; Anitescu, M.; Potra, F., A computational study of the use of an optimization-based method for simulating large multibody systems, Optim. Methods. Softw., 24, 6, 871-894 (2009) · Zbl 1237.90280
[32] Petra, C.G., Chiang, N.-Y., Peles, S., Mancinelli, A., Rutherford, C., Ryan, J.K., and Schanen, M., HPC solver for nonlinear optimization problems, 2017. Available at https://github.com/LLNL/hiop/tree/master.
[33] Pyzara, A., Bylina, B., and Bylina, J., The influence of a matrix condition number on iterative methods’ convergence, Proceedings of the Federated Conference on Computer Science and Information System, IEEE, 2011, pp. 459-464.
[34] Rees, T.; Scott, J., A comparative study of null-space factorizations for sparse symmetric saddle point systems: A comparative study of null-space factorizations, Numer. Linear Algebra Appl., 25, e2103 (2017) · Zbl 1424.65060
[35] Reinert, P.; Krebs, H.; Epelbaum, E., Semilocal momentum-space regularized chiral two-nucleon potentials up to fifth order, Euro. Phys. J. A, 54, 5, 1-49 (2018)
[36] Rennich, S. C.; Stosic, D.; Davis, T. A., Accelerating sparse Cholesky factorization on GPUs, Parallel. Comput., 59, 140-150 (2016)
[37] Rouet, F.-H.; Li, X. S.; Ghysels, P.; Napov, A., A distributed-memory package for dense hierarchically semi-separable matrix computations using randomization, ACM Trans. Math. Softw., 42, 4, 1-35 (2016) · Zbl 1369.65043
[38] Rozložník, J., Saddle-point Problems and Their Iterative Solution (2018), Birkhäuser: Birkhäuser, Cham · Zbl 1494.65001
[39] Ruiz, D., A scaling algorithm to equilibrate both rows and columns norms in matrices, Technical Report RAL-TR-2001-034, Rutherford Appleton Laboratory, 2001.
[40] Searle, S. R., Matrix Algebra Useful for Statistics (1982), John Wiley and Sons: John Wiley and Sons, Hoboken, NJ · Zbl 0555.62002
[41] Silva, C. J.; Torres, D. F.M., Optimal control for a tuberculosis model with reinfection and post-exposure interventions, Math. Biosci., 244, 2, 154-164 (2013) · Zbl 1280.92028
[42] Sleiman, J.-P., Carius, J., Grandia, R., Wermelinger, M., and Hutter, M., Contact-implicit trajectory optimization for dynamic object manipulation, 2019 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), IEEE, 2019, pp. 6814-6821.
[43] Świrydowicz, K.; Darve, E.; Maack, J.; Regev, S.; Saunders, M. A.; Thomas, S. J.; Peleš, S., Linear solvers for power grid optimization problems: A review of GPU-accelerated linear solvers, Parallel. Comput. Volume 111, Article 102870 (2022)
[44] Tasseff, B., Coffrin, C., Wächter, A., and Laird, C., Exploring benefits of linear solver parallelism on modern nonlinear optimization applications, 2019.
[45] Top500 List, June 2021. Available at https://www.top500.org/lists/top500/2021/06/.
[46] Uzawa, H., Iterative Methods for Concave Programming (1958), Stanford University Press: Stanford University Press, Stanford, CA
[47] Vanderbei, R. J., LOQO: An interior point code for quadratic programming, Optim. Methods. Softw., 11, 1, 451-484 (1999) · Zbl 0973.90518
[48] Varoquaux, N.; Ay, F.; Noble, W. S.; Vert, J.-P., A statistical approach for inferring the 3D structure of the genome, Bioinformatics, 30, 12, i26-i33 (2014)
[49] Wächter, A.; Biegler, L. T., Line search filter methods for nonlinear programming: Motivation and global convergence, SIAM J. Optim., 16, 1, 1-31 (2005) · Zbl 1114.90128
[50] Wächter, A.; Biegler, L. T., On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming, Math. Program., 106, 1, 25-57 (2006) · Zbl 1134.90542
[51] Wang, A.; Jasour, A.; Williams, B. C., Non-Gaussian chance-constrained trajectory planning for autonomous vehicles under agent uncertainty, IEEE Robot. Autom. Lett., 5, 4, 6041-6048 (2020)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.