Preprint D116/2014
Conditional extragradient algorithms for variational inequalities
Jose Yunier Bello Cruz | Reinier Díaz Millán | Hung M. Phan

In this paper, we generalize the classical extragradient algorithm for solving variational inequality problems
by utilizing non-null normal vectors of the feasible set. In particular, two conceptual algorithms are proposed and each of them has three different variants which are related to modified extragradient algorithms.

Our analysis contains two main parts: The first part
contains two different linesearches, one on the boundary of the
feasible set and the other one along the feasible direction. The
linesearches allow us to find suitable halfspaces containing the
solution set of the problem. By using non-null normal vectors of the
feasible set, these linesearches can potentially accelerate the
convergence. If all normal vectors are chosen as zero, then some of
these variants reduce to several well-known projection methods
proposed in the literature for solving the variational inequality
problem. The second part consists of three special projection steps,
generating three sequences with different interesting features.

Convergence analysis of both conceptual algorithms is
established assuming existence of solutions, continuity and a weaker
condition than pseudomonotonicity on the operator. Examples, on each
variant, show that the modifications proposed here perform better
than previous classical variants. These results suggest that our
scheme may significantly improve the extragradient variants.