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

• 成果类型: Article
• 署名作者: Castro, Jordi; Cuesta, Jordi
• 署名单位: Universitat Politecnica de Catalunya; Universitat Rovira i Virgili
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-010-0341-2
• 发表日期: 2011
• 页码: 415-445
• 关键词: indefinite systems; algorithms

摘要

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 separable quadratic 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.