Further Development of Multiple Centrality
Correctors for Interior Point Methods

Technical Report MS 2005-001

Marco Colombo and J. Gondzio

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.

Key words: Linear Programming, Quadratic Programming, Interior Point Methods, Centrality Correctors.

PDF MS05-001.pdf.
Written: October 18, 2005, revised March 9, 2006, September 7, 2006.
Published: Computational Optimization and Applications 41 (2008) No 3, pp. 277-305.
Related Software:
HOPDM Higher Order Primal Dual Method.