Further Development of Multiple Centrality Correctors for Interior Point Methods
Marco Colombo (m.colomboed.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.
Entry Submitted: 10/19/2005
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|