The Kantorovich Theorem and interior point methods.

The Kantorovich Theorem is a fundamental tool in nonlinear analysis which has been extensively used in classical numerical analysis. In this paper we show that it can also be used in analyzing interior point methods. We obtain optimal bounds for Newton’s method when relied upon in a path following algorithm for linear complementarity problems.Given a pointzthat approximates a pointz(t) on the central path with complementarity gapt, a parameter?? (0,1) is determined for which the pointzsatisfies the hypothesis of the affine invariant form of the Kantorovich Theorem, with regards to the equation definingz((1-?)t). The resulting iterative algorithm produces a point with complementarity gap less thanein at mostNewton steps, or simplified Newton steps, wheree0 is the complementarity gap of the starting point andnis the dimension of the problem. Thus we recover the best complexity results known to date and, in addition, we obtain the best bounds for Newton’s method in this context. [ABSTRACT FROM AUTHOR]