Global linear and local quadratic convergence of a long-step
adaptive-mode interior point method for some monotone
variational inequality problems
Jie Sun and Gongyun Zhao
An interior point method is proposed to solve variational inequality
problems for monotone functions and polyhedral sets. The method has
the following advantages. 1. Given an initial interior feasible
solution with duality gap $\mu_0$, the algorithm requires at most
$O[n \log(\mu_0/\epsilon)]$ iterations to obtian an $\epsilon$-optimal
solution. 2. The rate of convergence of the duality gap is quadratic.
3. At each iteration, a long-step improvement based on a line search
is allowed. 4. The algorithm can automatically transfer from a linear
mode to a quadratic mode to accelerate the local convergence.
Technical Report, March, 1996.