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 p > 0, our main algorithm exhibits pointwise O(1/P) and ergodic O(1/p(2/3)) iteration-complexities. From a practical perspective, preliminary numerical experiments indicate that our main algorithm outperforms some previous proximal-Newton schemes.