Optimization Online


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

Jordi Castro(jordi.castro***at***upc.edu)
Jordi Cuesta(jordi.cuesta***at***urv.cat)

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.

Download: [PDF]

Entry Submitted: 09/02/2008
Entry Accepted: 09/02/2008
Entry Last Modified: 09/02/2008

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society