A search-free $O(1\mathrm{/}{k}^{3\mathrm{/}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 $\rho >0$, our main algorithm exhibits pointwise $O\left(\frac{1}{\rho }\right)$ and ergodic $O\left(\frac{1}{{\rho }^{2\mathrm{/}3}}\right)$ iteration-complexities. From a practical perspective, preliminary numerical experiments indicate that our main algorithm outperforms some previous proximal-Newton schemes.