Optimization Online


Further Development of Multiple Centrality Correctors for Interior Point Methods

Marco Colombo (m.colombo***at***ed.ac.uk)
Jacek Gondzio (j.gondzio***at***ed.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. Published in COAP, 41 (2008), pp. 277-305.

Download: [PDF]

Entry Submitted: 10/19/2005
Entry Accepted: 10/19/2005
Entry Last Modified: 11/05/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