Recycling basic columns of the splitting preconditioner in interior point methods

Theoretical results and numerical experiments show that the linear systems originating from the last iterations of interior point methods (IPM) are very ill-conditioned. For this reason, preconditioners are necessary to approach this problem. In addition to that, in large-scale problems, the use of...

Full description

Saved in:
Bibliographic Details
Published in:Computational optimization and applications 2023-09, Vol.86 (1), p.49-78
Main Authors: Castro, Cecilia Orellana, Heredia, Manolo Rodriguez, Oliveira, Aurelio R. L.
Format: Article
Language:English
Subjects:
Convex and Discrete Geometry
Iterative methods
Linear programming
Linear systems
Management Science
Mathematical analysis
Mathematics
Mathematics and Statistics
Matrices (mathematics)
Matrix algebra
Methods
Numerical methods
Operations Research
Operations Research/Decision Theory
Optimization
Recycling
Robustness (mathematics)
Splitting
Statistics
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Theoretical results and numerical experiments show that the linear systems originating from the last iterations of interior point methods (IPM) are very ill-conditioned. For this reason, preconditioners are necessary to approach this problem. In addition to that, in large-scale problems, the use of iterative methods and implicit preconditioners is essential because we only compute matrix–vector multiplications. Preconditioners with a lower computational cost than the splitting preconditioner only have good performance in the initial iterations of the IPM, so this preconditioner has become very important in the last iterations. The study of improvements thereof is justified. This paper studies the variation of the diagonal matrix D entries that appear in the linear systems to be solved to try to reuse or recycle some linearly independent columns of the splitting preconditioner base previously computed in a given IPM iteration to build another basis in the next one. It is justified by the fact that a subset of linearly independent columns remains linearly independent, and from that available subset, one may complete the number of columns necessary to form the new base. The numerical results show that the column recycling proposal improves the speed and robustness of the original approach for a test set, especially for large-scale problems.
ISSN:0926-6003
1573-2894
DOI:10.1007/s10589-023-00492-1