Updating Constraint Preconditioners for KKT Systems in Quadratic Programming Via Low-Rank Corrections
From MaRDI portal
Publication:2947227
DOI10.1137/130947155zbMATH Open1323.65064arXiv1312.0047OpenAlexW2964263181WikidataQ58832740 ScholiaQ58832740MaRDI QIDQ2947227FDOQ2947227
V. De Simone, Stefania Bellavia, D. di Serafino, Benedetta Morini
Publication date: 22 September 2015
Published in: SIAM Journal on Optimization (Search for Journal in Brave)
Abstract: This work focuses on the iterative solution of sequences of 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.
Full work available at URL: https://arxiv.org/abs/1312.0047
interior point methodsnumerical examplesSchur complementconvex quadratic programmingKKT systemsconstraint preconditionersmatrix updatesKarush-Kuhn-Tucker (KKT) linear systems
Numerical mathematical programming methods (65K05) Quadratic programming (90C20) Convex programming (90C25) Interior-point methods (90C51) Preconditioners for iterative methods (65F08)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- QMRPACK
- CUTEst: a constrained and unconstrained testing environment with safe threads for mathematical optimization
- GMRES: A Generalized Minimal Residual Algorithm for Solving Nonsymmetric Linear Systems
- QMR: A quasi-minimal residual method for non-Hermitian linear systems
- Interior point methods 25 years later
- On the eigenvalues of a class of saddle point matrices
- On A Class of Limited Memory Preconditioners For Large Scale Linear Systems With Multiple Right-Hand Sides
- Preconditioning Newton-Krylov methods in nonconvex large scale optimization
- Constraint Preconditioning for Indefinite Linear Systems
- Automatic Preconditioning by Limited Memory Quasi-Newton Updating
- Software for simplified Lanczos and QMR algorithms
- Block-diagonal and indefinite symmetric preconditioners for mixed finite element formulations
- Constraint-Style Preconditioners for Regularized Saddle Point Problems
- Approximate Factorization Constraint Preconditioners for Saddle-Point Matrices
- Implicit-Factorization Preconditioning and Iterative Solvers for Regularized Saddle-Point Systems
- A Class of Spectral Two-Level Preconditioners
- Inexact interior-point method
- On mutual impact of numerical linear algebra and large-scale optimization with focus on interior point methods
- Indefinitely preconditioned conjugate gradient method for large sparse equality and inequality constrained quadratic problems
- Efficient Preconditioner Updates for Shifted Linear Systems
- Nonsymmetric Preconditioner Updates in Newton–Krylov Methods for Nonlinear Systems
- Efficient Preconditioning of Sequences of Nonsymmetric Linear Systems
- Incremental incomplete LU factorizations with applications
- Incremental spectral preconditioners for sequences of linear systems
- Adaptive preconditioners for nonlinear systems of equations
- Approximate inverse preconditioning for shifted linear systems
- A Preconditioning Framework for Sequences of Diagonally Modified Linear Systems Arising in Optimization
- New updates of incomplete LU factorizations and applications to large nonlinear systems
- Preconditioning indefinite systems in interior point methods for optimization
- Iterative Solution of Augmented Systems Arising in Interior Methods
- Quasi-Newton preconditioners for the inexact Newton method
- On the incomplete Cholesky decomposition of a class of perturbed matrices
- Inexact constraint preconditioners for linear systems arising in interior point methods
- Adaptive use of iterative methods in predictor-corrector interior point methods for linear programming
- Convergence analysis of an inexact potential reduction method for convex quadratic programming
- Starting-point strategies for an infeasible potential reduction method
- On the iterative solution of KKT systems in potential reduction software for large-scale quadratic problems
- Spectral analysis of inexact constraint preconditioning for symmetric saddle point matrices
- On eigenvalue distribution of constraint‐preconditioned symmetric saddle point matrices
- Stopping criteria for inner iterations in inexact potential reduction methods: a computational study
Cited In (11)
- A matrix-free smoothing algorithm for large-scale support vector machines
- A matrix-free approach to build band preconditioners for large-scale bound-constrained optimization
- Block preconditioners for linear systems in interior point methods for convex constrained optimization
- On preconditioner updates for sequences of saddle-point linear systems
- Preconditioners for Krylov subspace methods: An overview
- On the update of constraint preconditioners for regularized KKT systems
- Non-interior-point smoothing Newton method for CP revisited and its application to support vector machines
- Efficient Preconditioners for Interior Point Methods via a New Schur Complement-Based Strategy
- Limited memory preconditioners for symmetric indefinite problems with application to structural mechanics
- Parameterized approximate block LU preconditioners for generalized saddle point problems
- On partial Cholesky factorization and a variant of quasi-Newton preconditioners for symmetric positive definite matrices
Uses Software
This page was built for publication: Updating Constraint Preconditioners for KKT Systems in Quadratic Programming Via Low-Rank Corrections
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2947227)
