Improving an interior-point approach for large block-angular problems by hybrid preconditioners

•Interior-point method for block-angular problems based on hybrid approach.•Hybrid preconditioner combining power series and splitting preconditioners.•New switching criteria between preconditioners based on Ritz values.•Computational results provided for three classes of problems.•The hybrid approa...

Full description

Saved in:
Bibliographic Details
Published in:European journal of operational research 2013-12, Vol.231 (2), p.263-273
Main Authors: Bocanegra, Silvana, Castro, Jordi, Oliveira, Aurelio R.L.
Format: Article
Language:English
Subjects:
Algorithms
Blocking
Computation
Conjugate gradients
Interior-point methods
Iterative methods
Large-scale optimization
Linear equations
Mathematical analysis
Mathematical models
Mathematical problems
Mathematical programming
Power series
Preconditioned conjugate gradient
Structured problems
Studies
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:•Interior-point method for block-angular problems based on hybrid approach.•Hybrid preconditioner combining power series and splitting preconditioners.•New switching criteria between preconditioners based on Ritz values.•Computational results provided for three classes of problems.•The hybrid approach resulted more efficient for most instances. The computational time required by interior-point methods is often dominated by the solution of linear systems of equations. An efficient specialized interior-point algorithm for primal block-angular problems has been used to solve these systems by combining Cholesky factorizations for the block constraints and a conjugate gradient based on a power series preconditioner for the linking constraints. In some problems this power series preconditioner resulted to be inefficient on the last interior-point iterations, when the systems became ill-conditioned. In this work this approach is combined with a splitting preconditioner based on LU factorization, which works well for the last interior-point iterations. Computational results are provided for three classes of problems: multicommodity flows (oriented and nonoriented), minimum-distance controlled tabular adjustment for statistical data protection, and the minimum congestion problem. The results show that, in most cases, the hybrid preconditioner improves the performance and robustness of the interior-point solver. In particular, for some block-angular problems the solution time is reduced by a factor of 10.
ISSN:0377-2217
1872-6860
DOI:10.1016/j.ejor.2013.04.007