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.