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 Newtons method when relied upon in a path following algorithm for linear complementarity problems.Given a point z that approximates a point z() on the central path with complementarity gap , a parameter (0,1) is determined for which the point z satisfies the hypothesis of the affine invariant form of the Kantorovich Theorem, with regards to the equation defining z((1–)). The resulting iterative algorithm produces a point with complementarity gap less than in at most Newton steps, or simplified Newton steps, where ₀ is the complementarity gap of the starting point and n is the dimension of the problem. Thus we recover the best complexity results known to date and, in addition, we obtain the best bounds for Newtons method in this context.Mathematics Subject Classification (2000): 49M15, 65H10, 65K05, 90C33Work supported by the National Science Foundation under Grants No. 9996154, 0139701Acknowledgement The original version of this paper [38] was written when the author was visiting the Konrad-Zuse-Zentrum für Informationstechnik Berlin (ZIB). The author would like to thank Peter Deuflhard, President of ZIB, for the excellent working conditions at ZIB, and for very interesting discussions on various mathematical problems related to the subject of the present paper. The author would also like to thank two anonymous referees whose comments and suggestions led to a better presentation of our results.