##
A path-following method for linear complementarity problems
based on the affine invariant Kantorovich Theorem

###
Florian A. Potra

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.
ZIB-Report 00-30, August 2000, Konrad-Zuse-Zentrum,
Berlin, 2000

Contact: potra@math.umbc.edu