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.

[DVI] [IP PAGE] [SEARCH AGAIN]