TY - GEN A1 - Potra, Florian T1 - A path-following method for linear complementarity problems based on the affine invariant Kantorovich Theorem N2 - A path following algorithm for linear complementarity problems is presented. Given a point $z$ that approximates a point $z(\tau)$ on the central path with complementarity gap $\tau$, one determines a parameter $\theta\in (0,1)$ so that this point satisfies the hypothesis of the affine invariant Kantorovich Theorem for the equation defining $z((1-\theta)\tau)$. It is shown that $\theta$ is bounded below by a multiple of $n^{-1/2}$, where $n$ is the dimension of the problem. Since the hypothesis of of the Kantorovich Theorem is satisfied the sequence generated by Newton's method, or by the simplified Newton method, will converge to $z((1-\theta)\tau)$. We show that the number of steps required to obtain an acceptable approximation of $z((1-\theta)\tau)$ is bounded above by a number independent of $n$. Therefore the algorithm has $O(\sqrt{n}L)$-iteration complexity. The parameters of the algorithm can be determined in such a way that only one Newton step is needed each time the complementarity gap is decreased. T3 - ZIB-Report - 00-30 KW - Linear complementarity problem KW - interior-point algorithm KW - path-following KW - Kantorovich Theorem Y1 - 2000 UR - https://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/598 UR - https://nbn-resolving.org/urn:nbn:de:0297-zib-5981 ER -