On the Solution of Variational Inequalities by the Ellipsoid Method

Source abstract

Variational inequalities provide a convenient mathematical approach for unifying results relating to extremum and equilibrium problems. In this paper we demonstrate the applicability of the ellipsoid method to solve monotone variational inequalities. A convergence proof is given, which, for example, in case of convex optimization explains the linear convergence of the record points. We compare this result with Goffin's convergence proof by extending his proof technique to the constrained case in the appendix.