A quadratically convergent polynomial long-step algorithm
for a class of nonlinear monotone complementarity problems
Jie Sun and Gongyun Zhao
Several interior point algorithms have been proposed for solving nonlinear
monotone complementarity problems. Some of them have polynomial
worst-case complexity but have to confine to short steps, whereas some
of the others can take long steps but no polynomial complexity is proven.
This paper presents an algorithm which is both long-step and polynomial.
In addition,
the sequence generated by the algorithm, as well as the corresponding
complementarity gap, converges quadratically.
The proof of the polynomial complexity requires that the monotone
mapping satisfies a scaled Lipschitz condition, while the
quadratic rate of convergence is derived under the assumptions
that the problem has a strictly complementary solution and
that the Jacobian of the mapping satisfies certain regularity conditions.
National Univ. of Singapore, January, 1996.