Global linear and local quadratic convergence of a long-step adaptive-mode interior point method for some monotone variational inequality problems

Abstract

An interior point (IP) 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 μ0, the algorithm requires at most O[n log(μ0/ε)] iterations to obtain an ε-optimal solution. 2. The rate of convergence of the duality gap is q-quadratic. 3. At each iteration, a long-step improvement is allowed. 4. The algorithm can automatically transfer from a linear mode to a quadratic mode to accelerate the local convergence.