Block preconditioners for linear systems in interior point methods for convex constrained optimization. (English) Zbl 1500.65013
Summary: In this paper, we address the preconditioned iterative solution of the saddle-point linear systems arising from the (regularized) Interior Point method applied to linear and quadratic convex programming problems, typically of large scale. Starting from the well-studied Constraint Preconditioner, we review a number of inexact variants with the aim to reduce the computational cost of the preconditioner application within the Krylov subspace solver of choice. In all cases we illustrate a spectral analysis showing the conditions under which a good clustering of the eigenvalues of the preconditioned matrix can be obtained, which foreshadows (at least in case PCG/MINRES Krylov solvers are used), a fast convergence of the iterative method. Results on a set of large size optimization problems confirm that the Inexact variants of the Constraint Preconditioner can yield efficient solution methods.
MSC:
| 65F08 | Preconditioners for iterative methods |
| 65F10 | Iterative numerical methods for linear systems |
| 65K05 | Numerical mathematical programming methods |
| 90C20 | Quadratic programming |
| 90C25 | Convex programming |
| 90C06 | Large-scale problems in mathematical programming |
| 90C51 | Interior-point methods |
Keywords:
interior point method; preconditioned conjugate gradient; MINRES; preconditioning; saddle-point linear system; normal equations; BFGS update; constraint preconditionerReferences:
| [1] | Altman, A.; Gondzio, J., Regularized symmetric indefinite systems in interior point methods for linear and quadratic optimization, Optim. Methods Softw., 11-12, 275-302 (1999) · Zbl 0957.90101 · doi:10.1080/10556789908805754 |
| [2] | Andersen, ED; Gondzio, J.; Mészáros, C.; Xu, X.; Terlaky, T., Implementation of interior point methods for large scale linear programming, Interior Point Methods in Mathematical Programming, 189-252 (1996), Dordrecht: Kluwer Academic Publishers, Dordrecht · Zbl 0874.90127 · doi:10.1007/978-1-4613-3449-1_6 |
| [3] | Bellavia, S.; De Simone, V.; di Serafino, D.; Morini, B., Updating constraint preconditioners for KKT systems in quadratic programming via low-rank corrections, SIAM J. Optim., 25, 1787-1808 (2015) · Zbl 1323.65064 · doi:10.1137/130947155 |
| [4] | Bellavia, S.; De Simone, V.; di Serafino, D.; Morini, B., On the update of constraint preconditioners for regularized KKT systems, Comput. Optim. Appl., 65, 339-360 (2016) · Zbl 1366.90153 · doi:10.1007/s10589-016-9830-4 |
| [5] | Bergamaschi, L., On the eigenvalue distribution of constraint-preconditioned symmetric saddle point matrices, Numer. Lin. Alg. Appl., 19, 754-772 (2012) · Zbl 1274.65084 · doi:10.1002/nla.806 |
| [6] | Bergamaschi, L., A survey of low-rank updates of preconditioners for sequences of symmetric linear systems, Algorithms, 13, 100 (2020) · doi:10.3390/a13040100 |
| [7] | Bergamaschi, L.; Bru, R.; Martínez, A., Low-rank update of preconditioners for the inexact Newton method with SPD jacobian, Math. Comput. Model., 54, 1863-1873 (2011) · Zbl 1235.65049 · doi:10.1016/j.mcm.2010.11.064 |
| [8] | Bergamaschi, L.; De Simone, V.; di Serafino, D.; Martínez, A., BFGS-like updates of constraint preconditioners for sequences of KKT linear systems, Numer. Lin. Alg. Appl., 25, 1-19 (2018) · Zbl 1513.65176 · doi:10.1002/nla.2144 |
| [9] | Bergamaschi, L.; Facca, E.; Martínez, A.; Putti, M., Spectral preconditioners for the efficient numerical solution of a continuous branched transport model, J. Comput. Appl. Math., 254, 259-270 (2019) · Zbl 1419.65052 · doi:10.1016/j.cam.2018.01.022 |
| [10] | Bergamaschi, L.; Ferronato, M.; Gambolati, G., Mixed constraint preconditioners for the solution to FE coupled consolidation equations, J. Comput. Phys., 227, 9885-9897 (2008) · Zbl 1154.65015 · doi:10.1016/j.jcp.2008.08.002 |
| [11] | Bergamaschi, L.; Gondzio, J.; Martínez, A.; Pearson, J.; Pougkakiotis, S., A new preconditioning approach for an interior point-proximal method of multipliers for linear and convex quadratic programming, Numer. Linear Algebr. Appl., 28, e2361 (2021) · Zbl 07396244 · doi:10.1002/nla.2361 |
| [12] | Bergamaschi, L.; Gondzio, J.; Venturin, M.; Zilli, G., Inexact constraint preconditioners for linear systems arising in interior point methods, Comput. Optim. Appl., 36, 137-147 (2007) · Zbl 1148.90349 · doi:10.1007/s10589-006-9001-0 |
| [13] | Bergamaschi, L.; Gondzio, J.; Venturin, M.; Zilli, G., Erratum to: Inexact constraint preconditioners for linear systems arising in interior point methods, Comput. Optim. Appl., 49, 401-406 (2011) · Zbl 1279.90192 · doi:10.1007/s10589-009-9298-6 |
| [14] | Bergamaschi, L.; Gondzio, J.; Zilli, G., Preconditioning indefinite systems in interior point methods for optimization, Comput. Optim. Appl., 28, 149-171 (2004) · Zbl 1056.90137 · doi:10.1023/B:COAP.0000026882.34332.1b |
| [15] | Bergamaschi, L.; Martínez, A., RMCP: Relaxed mixed constraint preconditioners for saddle point linear systems arising in geomechanics, Comp. Methods App. Mech. Engrg., 221-222, 54-62 (2012) · Zbl 1253.74032 · doi:10.1016/j.cma.2012.02.004 |
| [16] | Bertsekas, PD, Constrained Optimization and Lagrange Multiplier Methods (1996), Nashua: Athena Scientific, Nashua · Zbl 0572.90067 |
| [17] | Bocanegra, S.; Campos, F.; Oliveira, ARL, Using a hybrid preconditioner for solving large-scale linear systems arising from interior point methods, Comput. Optim. Appl., 36, 149-164 (2007) · Zbl 1148.90350 · doi:10.1007/s10589-006-9009-5 |
| [18] | Cafieri, S.; D’Apuzzo, M.; De Simone, V.; di Serafino, D., On the iterative solution of KKT systems in potential reduction software for large-scale quadratic problems, Comput. Optim. Appl., 38, 27-45 (2007) · Zbl 1171.90548 · doi:10.1007/s10589-007-9035-y |
| [19] | Cafieri, S.; D’Apuzzo, M.; De Simone, V.; di Serafino, D., Stopping criteria for inner iterations in inexact potential reduction methods: a computational study, Comput. Opim. Appl., 36, 165-193 (2007) · Zbl 1148.90348 · doi:10.1007/s10589-006-9007-7 |
| [20] | Cafieri, S.; D’Apuzzo, M.; De Simone, V.; di Serafino, D.; Toraldo, G., Convergence analysis of an inexact potential reduction method for convex quadratic programming, J. Optim. Theory Appl., 135, 355-366 (2007) · Zbl 1146.90049 · doi:10.1007/s10957-007-9264-3 |
| [21] | Cao, Y.; Laird, CD; Zavala, VM, Clustering-based preconditioning for stochastic programs, Comput. Optim. Appl., 64, 379-406 (2016) · Zbl 1350.90026 · doi:10.1007/s10589-015-9813-x |
| [22] | Castro, J., A specialized interior-point algorithm for multicommodity network flows, SIAM J. Optim., 10, 852-877 (2000) · Zbl 0955.90087 · doi:10.1137/S1052623498341879 |
| [23] | Castro, J.; Cuesta, J., Quadratic regularizations in an interior-point method for primal block-angular problems, Math. Program., 130, 415-455 (2011) · Zbl 1229.90086 · doi:10.1007/s10107-010-0341-2 |
| [24] | Chai, J-S; Toh, K-C, Preconditioning and iterative solution of symmetric indefinite linear systems arising from interior point methods for linear programming, Comput. Optim. Appl., 36, 221-247 (2007) · Zbl 1148.90352 · doi:10.1007/s10589-006-9006-8 |
| [25] | D’Apuzzo, M.; De Simone, V.; di Serafino, D., On mutual impact of numerical linear algebra and large-scale optimization with focus on interior point methods, Comput. Optim. Appl., 45, 283-310 (2010) · Zbl 1187.90194 · doi:10.1007/s10589-008-9226-1 |
| [26] | De Simone, V., di Serafino, D., Gondzio, J., Pougkakiotis, S., Viola, M.: Sparse approximations with interior point methods (2021). arXiv:2102.13608 |
| [27] | di Serafino, D.; Orban, D., Constraint-preconditioned krylov solvers for regularized saddle-point systems, SIAM J. Sci. Comput., 43, A1001-A1026 (2021) · doi:10.1137/19M1291753 |
| [28] | Dollar, H.; Wathen, A., Approximate factorization constraint preconditioners for saddle-point matrices, SIAM J. Sci. Comput., 27, 1555-1572 (2006) · Zbl 1105.65047 · doi:10.1137/04060768X |
| [29] | Durazzi, C.; Ruggiero, V., Indefinitely preconditioned conjugate gradient method for large sparse equality and inequality constrained quadratic problems, Numer. Lin. Alg. Appl., 10, 673-688 (2003) · Zbl 1071.65512 · doi:10.1002/nla.308 |
| [30] | Elman, H.C., Silvester, D.J., Wathen, A.J.: Finite Elements and Fast Iterative Solvers: with Applications in Incompressible Fluid Dynamics. Numerical Mathematics and Scientific Computation, Oxford University Press, 2nd ed. (2014) · Zbl 1304.76002 |
| [31] | Fisher, M.; Gratton, S.; Gürol, S.; Trémolet, Y.; Vasseur, X., Low rank updates in preconditioning the saddle point systems arising from data assimilation problems, Optim. Meth. Softw., 33, 45-69 (2018) · Zbl 1398.90178 · doi:10.1080/10556788.2016.1264398 |
| [32] | Freund, RW; Nachtigal, NM, Software for simplified Lanczos and QMR algorithms, Appl. Numer. Math., 19, 319-341 (1995) · Zbl 0853.65041 · doi:10.1016/0168-9274(95)00089-5 |
| [33] | Gill, PE; Murray, W.; Ponceleon, DB; Saunders, MA, Preconditioners for indefinite systems arising in optimization, SIAM J. Matrix Anal. Appl., 13, 292-311 (1992) · Zbl 0749.65037 · doi:10.1137/0613022 |
| [34] | Golub, GH; Wathen, AJ, An iteration for indefinite systems and its application to the Navier-Stokes equations, SIAM J. Sci. Comput., 19, 530-539 (1998) · Zbl 0912.76053 · doi:10.1137/S106482759529382X |
| [35] | Gondzio, J., HOPDM (version 2.12) - a fast LP solver based on a primal-dual interior point method, Eur. J. Oper. Res., 85, 221-225 (1995) · Zbl 0925.90284 · doi:10.1016/0377-2217(95)00163-K |
| [36] | Gondzio, J., Interior point methods 25 years later, Eur. J. Oper. Res., 218, 587-601 (2013) · Zbl 1244.90007 · doi:10.1016/j.ejor.2011.09.017 |
| [37] | Gould, NIM; Orban, D.; Toint, PL, Cutest: a constrained and unconstrained testing environment with safe threads for mathematical optimization, Comput. Optim. Appl., 60, 545-557 (2015) · Zbl 1325.90004 · doi:10.1007/s10589-014-9687-3 |
| [38] | Gratton, S.; Mercier, S.; Tardieu, N.; Vasseur, X., Limited memory preconditioners for symmetric indefinite problems with application to structural mechanics, Numer. Linear Algebra Appl., 23, 865-887 (2016) · Zbl 1413.65041 · doi:10.1002/nla.2058 |
| [39] | Gratton, S.; Sartenaer, A.; Tshimanga, J., On a class of limited memory preconditioners for large scale linear systems with multiple right-hand sides, SIAM J. Optim., 21, 912-935 (2011) · Zbl 1273.65044 · doi:10.1137/08074008 |
| [40] | Greenbaum, A.: Iterative Methods for Solving Linear Systems. Society for Industrial and Applied Mathematics (1997). doi:10.1137/1.9781611970937 · Zbl 0883.65022 |
| [41] | Hestenes, MR, Multiplier and gradient methods, J. Optim. Theory Appl., 4, 303-320 (1969) · Zbl 0174.20705 · doi:10.1007/BF00927673 |
| [42] | Hestenes, MR; Stiefel, E., Methods of conjugate gradients for solving linear systems, J. Res. Natl. Bur. Stand., 49, 409-436 (1952) · Zbl 0048.09901 · doi:10.6028/jres.049.044 |
| [43] | Júdice, JJ; Patricio, J.; Portugal, LF; Resende, MGC; Veiga, G., A study of preconditioners for network interior point methods, Comput. Optim. Appl., 24, 5-35 (2003) · Zbl 1035.90101 · doi:10.1023/A:1021882330897 |
| [44] | Keller, C.; Gould, NIM; Wathen, AJ, Constraint preconditioning for indefinite linear systems, SIAM J. Matrix Anal. Appl., 21, 1300-1317 (2000) · Zbl 0960.65052 · doi:10.1137/S0895479899351805 |
| [45] | Kuznetsov, YA, Efficient iterative solvers for elliptic finite element problems on nonmatching grids, Russ. J. Numer. Anal. Math. Model., 10, 187-211 (1995) · Zbl 0839.65031 · doi:10.1515/rnam.1995.10.3.187 |
| [46] | Loghin, D., Ruiz, D., Touhami, A.: Adaptive preconditioners for nonlinear systems of equations. J. Comput. Appl. Math. 189, 362-374 (2006) · Zbl 1088.65048 |
| [47] | Lukšan, L.; Vlček, J., Indefinitely preconditioned inexact Newton method for large sparse equality constrained nonlinear programming problems, Numer. Lin. Alg. Appl., 5, 219-247 (1998) · Zbl 0937.65066 · doi:10.1002/(SICI)1099-1506(199805/06)5:3<219::AID-NLA134>3.0.CO;2-7 |
| [48] | Lukšan, L., Vlček, J.: Interior point method for nonlinear nonconvex optimization. Tech. Report 836, Institute of Computer Science, Academy of Sciences of the Czech Republic, 18207 Prague, Czech Republic (2001) |
| [49] | Maros, I.; Mészáros, C., A repository of convex quadratic programming problems, Optim. Methods Softw., 11, 671-681 (1999) · Zbl 0973.90520 · doi:10.1080/10556789908805768 |
| [50] | Martínez, A., Tuned preconditioners for the eigensolution of large SPD matrices arising in engineering problems, Numer. Lin. Alg. Appl., 23, 427-443 (2016) · Zbl 1413.65101 · doi:10.1002/nla.2032 |
| [51] | Murphy, MF; Golub, GH; Wathen, AJ, A note on preconditioning for indefinite linear systems, SIAM J. Sci. Comput., 21, 1969-1972 (2000) · Zbl 0959.65063 · doi:10.1137/S1064827599355153 |
| [52] | Nash, SG; Nocedal, J., A numerical study of the limited memory BFGS method and the truncated-Newton method for large scale optimization, SIAM J. Optim., 1, 358-372 (1991) · Zbl 0756.65091 · doi:10.1137/0801023 |
| [53] | Oliveira, ARL; Sorensen, DC, A new class of preconditioners for large-scale linear systems from interior point methods for linear programming, Linear Algebra Appl., 394, 1-24 (2005) · Zbl 1071.65088 · doi:10.1016/j.laa.2004.08.019 |
| [54] | Paige, CC; Saunders, MA, Solution of sparse indefinite systems of linear equations, SIAM J. Numer. Anal., 12, 617-629 (1975) · Zbl 0319.65025 · doi:10.1137/0712047 |
| [55] | Parikh, N.; Boyd, S., Proximal algorithms, Found. Trends Optim., 3, 123-231 (2014) |
| [56] | Pearson, JW; Gondzio, J., Fast interior point solution of quadratic programming problems arising from PDE-constrained optimization, Numer. Math., 137, 959-999 (2017) · Zbl 1379.65042 · doi:10.1007/s00211-017-0892-8 |
| [57] | Pearson, JW; Porcelli, M.; Stoll, M., Interior point methods and preconditioning for PDE-constrained optimization problems involving sparsity terms, Numer. Linear Algebra Appl., 27 (2019) · Zbl 07177902 |
| [58] | Perugia, I.; Simoncini, V., Block-diagonal and indefinite symmetric preconditioners for mixed finite elements formulations, Numer. Lin. Alg. Appl., 7, 585-616 (2000) · Zbl 1051.65038 · doi:10.1002/1099-1506(200010/12)7:7/8<585::AID-NLA214>3.0.CO;2-F |
| [59] | Pougkakiotis, S.; Gondzio, J., Dynamic non-diagonal regularization in interior point methods for linear and convex quadratic programming, J. Optim. Theory Appl., 181, 905-945 (2019) · Zbl 1420.90082 · doi:10.1007/s10957-019-01491-1 |
| [60] | Pougkakiotis, S.; Gondzio, J., An interior point-proximal method of multipliers for convex quadratic programming, Comput. Optim. Appl., 78, 307-351 (2021) · Zbl 1469.90158 · doi:10.1007/s10589-020-00240-9 |
| [61] | Powell, MJD; Fletcher, R., A method for nonlinear constraints in minimization problems, Optimization, 283-298 (1969), New York, NY: Academic Press, New York, NY · Zbl 0194.47701 |
| [62] | Rockafellar, RT, Augmented Lagrangians and applications of the proximal point algorithm in convex programming, Math. Oper. Res., 1, 97-116 (1976) · Zbl 0402.90076 · doi:10.1287/moor.1.2.97 |
| [63] | Rockafellar, RT, Monotone operators and the proximal point algorithm, SIAM J. Control. Optim., 14, 877-898 (1976) · Zbl 0358.90053 · doi:10.1137/0314056 |
| [64] | Rozlozník, M.; Simoncini, V., Krylov subspace methods for saddle point problems with indefinite preconditioning, SIAM J. Matrix Anal. Appl., 24, 368-391 (2002) · Zbl 1021.65016 · doi:10.1137/S0895479800375540 |
| [65] | Saad, Y., Yeung, M., Erhel, J., Guyomarc’h, F.: A deflated version of the conjugate gradient algorithm. SIAM J. Sci. Comput. 21, 1909-1926 (2000). Iterative methods for solving systems of algebraic equations (Copper Mountain, CO, 1998) · Zbl 0955.65021 |
| [66] | Schenk, O.; Wächter, A.; Weiser, M., Inertia-revealing preconditioning for large-scale nonconvex constrained optimization, Comput. Optim. Appl., 31, 939-960 (2008) · Zbl 1194.35029 |
| [67] | Schnabel, R.B.: Quasi-Newton methods using multiple secant equations. Tech. Report CU-CS-247- CU-CS-247-83, Department of Computer Sciences, University of Colorado, Boulder, CO (1983) |
| [68] | Silvester, D.; Wathen, A., Fast iterative solution of stabilized Stokes systems, Part II: Using general block preconditioners, SIAM J. Numer. Anal., 31, 1352-1367 (1994) · Zbl 0810.76044 · doi:10.1137/0731070 |
| [69] | Tebbens, J.D., T \(\mathring{{\rm u}}\) ma, M.: Efficient preconditioning of sequences of nonsymmetric linear systems, SIAM J. Sci. Comput. 29, 1918 - 1941 (2007) · Zbl 1155.65036 |
| [70] | Tshimanga, J.: On a class of limited memory preconditioners for large scale linear nonlinear least-squares problems (with application to variational ocean data assimilation), PhD thesis, Facultés Universitaires Notre Dame de la Paix, Namur (2007) |
| [71] | Wang, W.; O’Leary, DP, Adaptive use of iterative methods in predictor-corrector interior point methods for linear programming, Numer. Algorithms, 25, 387-406 (2000) · Zbl 0977.65054 · doi:10.1023/A:1016614603137 |
| [72] | Wright, S.J.: Primal-Dual Interior-Point Methods. SIAM, Philadelphia (1997) · Zbl 0863.65031 |
| [73] | Zanetti, F., Bergamaschi, L.: Scalable block preconditioners for linearized Navier-Stokes equations at high Reynolds number. Algorithms 13, 199 (2020) |
| [74] | Zanetti, F., Gondzio, J.: A new stopping criterion for Krylov solvers applied in Interior Point methods, arXiv:2106.16090 [math.OC] |
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.
