Quadratic regularizations in an interior-point method for primal block-angular problems

One of the most efficient interior-point methods for some classes of primal block-angular problems solves the normal equations by a combination of Cholesky factorizations and preconditioned conjugate gradient for, respectively, the block and linking constraints. Its efficiency depends on the spectral radius—in [0,1)—of a certain matrix in the definition of the preconditioner. Spectral radius close to 1 degrade the performance of the approach. The purpose of this work is twofold. First, to show that a regularization term in the objective reduces the spectral radius, significantly improving the overall performance in some classes of instances. Second, to consider a regularization term which decreases with the barrier function, thus with no need for an extra parameter. Computational experience with some primal block-angular problems confirms the efficiency of the regularized approach. In particular, for some difficult problems, the solution time is reduced by a factor of two to ten by the regularization term, outperforming state-of-the-art commercial solvers.

Citation

J. Castro, J. Cuesta, Quadratic regularizations in an interior-point method for primal block-angular problems, Research Report DR 2008/07, Dept. of Statistics and Operations Research, Universitat Politècnica de Catalunya, 2008.

Article

Download

View Quadratic regularizations in an interior-point method for primal block-angular problems