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.
Citation
Technical Report MS 2005-001, School of Mathematics, The University of Edinburgh. Published in COAP, 41 (2008), pp. 277-305.
Article
View Further Development of Multiple Centrality Correctors for Interior Point Methods