##
Complexity of predictor-corrector algorithms for LCP based on
a large neighborhood of the central path

###
Clovis C. Gonzaga

The predictor-corrector approach for following the central path of
monotone linear complementarity and linear programming problems is
simple, elegant and efficient. Although it has excellent theoretical
properties when working on narrow neighborhoods of the central path,
its proved complexity assumes a frustrating high value of O(n^{1.5}L)
iterations when based on an l_{\infty} neighborhood and several
Newton corrector steps per iteration. This paper shows that by carefully
stating the line searches in each step, the complexity assumes the
value $ O(nL) $, as should be expected for a method based on this
neighborhood.
Contact: clovis@mtm.ufsc.br