Further Development of Multiple Centrality Correctors for Interior Point Methods

Marco Colombo (m.colomboed.ac.uk)
Jacek Gondzio (j.gondzioed.ac.uk)

Abstract: This paper addresses the role of centrality in the implementation of interior point methods. Theoretical arguments are provided to justify the use of a symmetric neighbourhood. These are translated into computational practice leading to a new insight into the role of re-centering in the implementation of interior point methods. Arguments are provided to show that second-order correctors, such as Mehrotra's predictor-corrector, can occasionally fail. A remedy to such difficulties is derived from a new interpretation of multiple centrality correctors. Extensive numerical experience is provided to show that the proposed centrality correcting scheme leads to noteworthy savings over second-order predictor-corrector technique and previous implementation of multiple centrality correctors.

Keywords: Linear Programming, Quadratic Programming, Interior Point Methods, Centrality Correctors.

Category 1: Linear, Cone and Semidefinite Programming (Linear Programming )

Citation: Technical Report MS 2005-001 School of Mathematics The University of Edinburgh 10/2005, revised 11/2006

Download: [PDF]

Entry Submitted: 10/19/2005
Entry Accepted: 10/19/2005
Entry Last Modified: 05/18/2007

Modify/Update this entry