##
On the superlinear convergence of an O(n^3L) interior point
algorithm for monotone LCP

###
Kevin McShane

Karmarkar's partial updating scheme is applied to a polynomial,
superlinearly convergent algorithm for monotone LCP. This modification
reduces the bound on the number of arithmetic operations necessary to
achieve epsilon optimality by a factor of sqrt(n). The complementarity
gap sequence generated by the resulting algorithm converges q-quadratically
to zero if the LCP is nondegenerate with a strictly complementary optimal
solution. In general, the convergence rate is q-superlinear if the
iterates are assumed to converge to a strictly complementary optimal solution.

To appear in *SIAM Journal of Optimization*.

Contact: mcshane@DGS.dgsys.com