Block preconditioners for linear systems in interior point methods for convex constrained optimization

被引：0
作者：
Zilli G. [1 ]
Bergamaschi L. [2 ]
机构：
[1] Department of Mathematical Methods and Models for Scientific Application, University of Padua, Padua
[2] Department of Civil Environmental and Architectural Engineering, University of Padova, Via Marzolo 9, Padova
来源：
ANNALI DELL'UNIVERSITA' DI FERRARA | 2022年 / 68卷 / 2期
关键词：
BFGS update; Constraint preconditioner; Interior point method; MINRES; Normal equations; Preconditioned conjugate gradient; Preconditioning; Saddle-point linear system;
D O I：
10.1007/s11565-022-00422-9
中图分类号：
学科分类号：
摘要：
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. © 2022, The Author(s).
引用
收藏
页码：337 / 368
页数：31
相关论文
共 74 条
  • [1] Altman A., Gondzio J., Regularized symmetric indefinite systems in interior point methods for linear and quadratic optimization, Optim. Methods Softw., 11-12, pp. 275-302, (1999)
  • [2] Andersen E.D., Gondzio J., Meszaros C., Xu X., Implementation of interior point methods for large scale linear programming, Interior Point Methods in Mathematical Programming, pp. 189-252, (1996)
  • [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, pp. 1787-1808, (2015)
  • [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, pp. 339-360, (2016)
  • [5] Bergamaschi L., On the eigenvalue distribution of constraint-preconditioned symmetric saddle point matrices, Numer. Lin. Alg. Appl., 19, pp. 754-772, (2012)
  • [6] Bergamaschi L., A survey of low-rank updates of preconditioners for sequences of symmetric linear systems, Algorithms, 13, (2020)
  • [7] Bergamaschi L., Bru R., Martinez A., Low-rank update of preconditioners for the inexact Newton method with SPD jacobian, Math. Comput. Model., 54, pp. 1863-1873, (2011)
  • [8] Bergamaschi L., De Simone V., di Serafino D., Martinez A., BFGS-like updates of constraint preconditioners for sequences of KKT linear systems, Numer. Lin. Alg. Appl., 25, pp. 1-19, (2018)
  • [9] Bergamaschi L., Facca E., Martinez A., Putti M., Spectral preconditioners for the efficient numerical solution of a continuous branched transport model, J. Comput. Appl. Math., 254, pp. 259-270, (2019)
  • [10] Bergamaschi L., Ferronato M., Gambolati G., Mixed constraint preconditioners for the solution to FE coupled consolidation equations, J. Comput. Phys., 227, pp. 9885-9897, (2008)
12345678