Quadratic regularizations in an interior-point method for primal block-angular problems
Abstract: 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.
Keywords: interior-point methods · primal block-angular problems · multicommodity network flows · preconditioned conjugate gradient · regularizations · large-scale computational optimization
Category 1: Linear, Cone and Semidefinite Programming
Category 2: Nonlinear Optimization (Quadratic Programming )
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.
Entry Submitted: 09/02/2008
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|