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