×

Updating constraint preconditioners for KKT systems in quadratic programming via low-rank corrections. (English) Zbl 1323.65064

Summary: This work focuses on the iterative solution of sequences of Karush-Kuhn-Tucker (KKT) linear systems arising in interior point methods applied to large convex quadratic programming problems. This task is the computational core of the interior point procedure, and an efficient preconditioning strategy is crucial for the efficiency of the overall method. Constraint preconditioners are very effective in this context; nevertheless, their computation may be very expensive for large-scale problems, and resorting to approximations of them may be convenient. Here we propose a procedure for building inexact constraint preconditioners by updating a seed constraint preconditioner computed for a KKT matrix at a previous interior point iteration. These updates are obtained through low-rank corrections of the Schur complement of the (1,1) block of the seed preconditioner. The updated preconditioners are analyzed both theoretically and computationally. The results obtained show that our updating procedure, coupled with an adaptive strategy for determining whether to reinitialize or update the preconditioner, can enhance the performance of interior point methods on large problems.

MSC:

65K05 Numerical mathematical programming methods
90C20 Quadratic programming
90C25 Convex programming
90C51 Interior-point methods
65F08 Preconditioners for iterative methods

Software:

CHOLMOD; QMRPACK; CUTEst
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] V. Baryamureeba, T. Steihaug, and Y. Zhang, {\it Properties of a Class of Preconditioners for Weighted Least Squares Problems}, Technical Report 170, Department of Informatics, University of Bergen, Bergen, Norway, and Technical Report TR99-16, Department of Computational and Applied Mathematics, Rice University, Houston, TX, 1999. · Zbl 0946.65045
[2] S. Bellavia, {\it Inexact interior-point method}, J. Optim. Theory Appl., 96 (1998), pp. 109-121. · Zbl 0897.90182
[3] S. Bellavia, D. Bertaccini, and B. Morini, {\it Nonsymmetric preconditioner updates in Newton-Krylov methods for nonlinear systems}, SIAM J. Sci. Comput., 33 (2011), pp. 2595-2619. · Zbl 1232.65049
[4] S. Bellavia, V. De Simone, D. di Serafino, and B. Morini, {\it Efficient preconditioner updates for shifted linear systems}, SIAM J. Sci. Comput., 33 (2011), pp. 1785-1809. · Zbl 1236.65029
[5] S. Bellavia, V. De Simone, D. di Serafino, and B. Morini, {\it A preconditioning framework for sequences of diagonally modified linear systems arising in optimization}, SIAM J. Numer. Anal., 50 (2012), pp. 3280-3302. · Zbl 1267.65035
[6] S. Bellavia, B. Morini, and M. Porcelli, {\it New updates of incomplete LU factorizations and applications to large nonlinear systems}, Optim. Methods Softw., 29 (2014), pp. 321-340. · Zbl 1285.90064
[7] M. Benzi and D. Bertaccini, {\it Approximate inverse preconditioning for shifted linear systems}, BIT, 43 (2003), pp. 231-244. · Zbl 1037.65043
[8] M. Benzi and V. Simoncini, {\it On the eigenvalues of a class of saddle point matrices}, Numer. Math., 103 (2006), pp. 173-196. · Zbl 1103.65033
[9] L. Bergamaschi, {\it Eigenvalue distribution of constraint-preconditioned symmetric saddle point matrices}, Numer. Linear Algebra Appl., 19 (2012), pp. 754-772. · Zbl 1274.65084
[10] L. Bergamaschi, R. Bru, A. Martinez, and M. Putti, {\it Quasi-Newton preconditioners for the inexact Newton method}, Electron. Trans. Numer. Anal., 23 (2006), pp. 76-87. · Zbl 1112.65045
[11] L. Bergamaschi, J. Gondzio, and G. Zilli, {\it Preconditioning indefinite systems in interior point methods for optimization}, Comput. Optim. Appl., 28 (2004), pp. 149-171. · Zbl 1056.90137
[12] L. Bergamaschi, J. Gondzio, M. Venturin, and G. Zilli, {\it Inexact constraint preconditioners for linear systems arising in interior point methods}, Comput. Optim. Appl., 36 (2007), pp. 137-147. · Zbl 1148.90349
[13] S. Cafieri, M. D’Apuzzo, V. De Simone, and D. di Serafino, {\it On the iterative solution of KKT systems in potential reduction software for large-scale quadratic problems}, Comput. Optim. Appl., 38 (2007), pp. 27-45. · Zbl 1171.90548
[14] S. Cafieri, M. D’Apuzzo, V. De Simone, and D. di Serafino, {\it Stopping criteria for inner iterations in inexact potential reduction methods: A computational study}, Comput. Optim. Appl., 36 (2007), pp. 165-193. · Zbl 1148.90348
[15] S. Cafieri, M. D’Apuzzo, V. De Simone, and D. di Serafino, {\it On the use of an approximate constraint preconditioner in a potential reduction algorithm for quadratic programming}, in Applied and Industrial Mathematics in Italy II, V. Cutello, G. Fotia, and L. Puccio, eds., Ser. Adv. Math. Appl. Sci. 75, World Scientific, Singapore, 2007, pp. 220-230. · Zbl 1171.90548
[16] S. Cafieri, M. D’Apuzzo, V. De Simone, D. di Serafino, and G. Toraldo, {\it Convergence analysis of an inexact potential reduction method for convex quadratic programming}, J. Optim. Theory Appl., 135 (2007), pp. 355-366. · Zbl 1146.90049
[17] C. Calgaro, J. P. Chehab, and Y. Saad, {\it Incremental incomplete ILU factorizations with applications}, Numer. Linear Algebra Appl., 17 (2010), pp. 811-837. · Zbl 1240.65091
[18] B. Carpentieri, I. S. Duff, and L. Giraud, {\it A class of spectural two-level preconditioners}, SIAM J. Sci. Comput., 25 (2003), pp. 749-765. · Zbl 1048.65043
[19] M. D’Apuzzo, V. De Simone, and D. di Serafino, {\it On mutual impact of numerical linear algebra and large-scale optimization with focus on interior point methods}, Comput. Optim. Appl., 45 (2010), pp. 283-310. · Zbl 1187.90194
[20] M. D’Apuzzo, V. De Simone, and D. di Serafino, {\it Starting-point strategies for an infeasible potential reduction method}, Optim. Lett., 4 (2010), pp. 131-146. · Zbl 1181.90210
[21] T. A. Davis and W. W. Hager, {\it Dynamic supernodes in sparse Cholesky update/downdate and triangular solves}, ACM Trans. Math. Softw., 35 (2009), 27.
[22] H. S. Dollar, {\it Constraint-style preconditioners for regularized saddle-point problems}, SIAM J. Matrix Anal. Appl., 29 (2007), pp. 672-684. · Zbl 1144.65032
[23] H. S. Dollar, N. I. M. Gould, W. H. A. Schilders, and A. J. Wathen, {\it Implicit-factorization preconditioning and iterative solvers for regularized saddle-point systems}, SIAM J. Matrix Anal. Appl., 28 (2006), pp. 170-189. · Zbl 1104.65310
[24] H. S. Dollar and A. J. Wathen, {\it Approximate factorization constraint preconditioners for saddle-point matrices}, SIAM J. Sci. Comput., 27 (2006), pp. 1555-1572. · Zbl 1105.65047
[25] J. Duintjer Tebbens and M. Tu̇ma, {\it Efficient preconditioning of sequences of nonsymmetric linear systems}, SIAM J. Sci. Comput., 29 (2007), pp. 1918-1941. · Zbl 1155.65036
[26] C. Durazzi and V. Ruggiero, {\it Indefinitely preconditioned conjugate gradient method for large sparse equality and inequality constrained quadratic problems}, Numer. Linear Algebra Appl., 10 (2003), pp. 673-688. · Zbl 1071.65512
[27] R.W. Freund and N. M. Nachtigal, {\it QMR: A quasi-minimal residual method for non-Hermitian linear systems}, Numer. Math., 60 (1991), pp. 315-339. · Zbl 0754.65034
[28] R. W. Freund and N. W. Nachtigal, {\it Software for simplified Lanczos and QMR algorithms}, Appl. Numer. Math., 19 (1995), pp. 319-341. · Zbl 0853.65041
[29] R. W. Freund and N. W. Nachtigal, {\it QMRPACK: A package of QMR algorithms}, ACM Trans. Math. Softw., 22 (1996), pp. 46-77. · Zbl 0884.65027
[30] G. Fasano and M. Roma, {\it Preconditioning Newton-Krylov methods in non-convex large scale optimization}, Comput. Optim. Appl., 56 (2013), pp. 253-290. · Zbl 1314.90063
[31] A. Forsgren, P. E. Gill, and J. D. Griffin, {\it Iterative solution of augmented systems arising in interior methods}, SIAM J. Optim., 18 (2007), pp. 666-690. · Zbl 1143.49024
[32] L. Giraud, S. Gratton, and E. Martin, {\it Incremental spectral preconditioners for sequences of linear systems}, Appl. Numer. Math., 57 (2007), pp. 1164-1180. · Zbl 1123.65031
[33] G. H. Golub and C. F. van Loan, {\it Matrix Computations}, 3rd ed., The Johns Hopkins University Press, Baltimore, MD, 1996. · Zbl 0865.65009
[34] J. Gondzio, {\it Interior point methods \(25\) years later}, Eur. J. Oper. Res., 218 (2012), pp. 587-601. · Zbl 1244.90007
[35] N. I. M. Gould, D. Orban, and Ph. L. Toint, {\it CUTEst: A constrained and unconstrained testing environment with safe threads}, Comput. Optim. Appl., 60 (2015), pp. 545-557. · Zbl 1325.90004
[36] S. Gratton, A. Sartenaer, and J. Tshimanga, {\it On a class of limited memory preconditioners for large scale linear systems with multiple right-hand sides}, SIAM J. Optim., 21 (2011), pp. 912-935. · Zbl 1273.65044
[37] C. Keller, N. I. M. Gould, and A. J. Wathen, {\it Constraint preconditioning for indefinite linear systems}, SIAM J. Matrix Anal. Appl., 21 (2000), pp. 1300-1317. · Zbl 0960.65052
[38] D. Loghin, D. Ruiz, and A. Touhami, {\it Adaptive preconditioners for nonlinear systems of equations}, J. Comput. Appl. Math., 189 (2006), pp. 362-374. · Zbl 1088.65048
[39] L. Lukšan and J. Vlček, {\it Indefinitely preconditioned inexact Newton method for large sparse equality constrained non-linear programming problems} Numer. Linear Algebra Appl., 5 (1998), pp. 219-247. · Zbl 0937.65066
[40] G. Meurant, {\it On the incomplete Cholesky decomposition of a class of perturbed matrices}, SIAM J. Sci. Comput., 23 (2001), pp. 419-429. · Zbl 0992.65019
[41] J. L. Morales and J. Nocedal, {\it Automatic preconditioning by limited memory quasi-Newton updating}, SIAM J. Optim., 10 (2000), pp. 1079-1096. · Zbl 1020.65019
[42] I. Perugia and V. Simoncini, {\it Block-diagonal and indefinite symmetric preconditioners for mixed finite element formulations}, Numer. Linear Algebra Appl., 7 (2000), pp. 585-616. · Zbl 1051.65038
[43] Y. Saad and M. H. Schultz, {\it GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems}, SIAM J. Sci. Stat. Comput., 7 (1986), pp. 856-869. · Zbl 0599.65018
[44] D. Sesana and V. Simoncini, {\it Spectral analysis of inexact constraint preconditioning for symmetric saddle point matrices}, Linear Algebra Its Appl., 438 (2013), pp. 2683-2700. · Zbl 1263.65029
[45] W. Wang and D. P. O’Leary, {\it Adaptive use of iterative methods in predictor-corrector interior point methods for linear programming}, Numer. Algorithms, 25 (2000), pp. 387-406. · Zbl 0977.65054
[46] S. J. Wright, {\it Primal-Dual Interior-Point Methods}, SIAM, Philadelphia, 1997. · Zbl 0863.65031
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.