@misc{Potra2000, author = {Potra, Florian}, title = {A path-following method for linear complementarity problems based on the affine invariant Kantorovich Theorem}, doi = {10.1007/s10107-003-0501-8}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5981}, number = {00-30}, year = {2000}, abstract = {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.}, language = {en} }