A search-free O(1/k3/2) homotopy inexact proximal-Newton extragradient algorithm for monotone variational inequalities

We present and study the iteration-complexity of a relative-error inexact proximal-Newton extragradient algorithm for solving smooth monotone variational inequality problems in real Hilbert spaces. We removed a search procedure from Monteiro and Svaiter (2012) by introducing a novel approach based on homotopy, which requires the resolution (at each iteration) of a single strongly monotone linear variational inequality. For a given tolerance ρ>0, our main algorithm exhibits pointwise Oleft(frac1ρright) and ergodic Oleft(frac1ρ2/3right) iteration-complexities. From a practical perspective, preliminary numerical experiments indicate that our main algorithm outperforms some previous proximal-Newton schemes.