The Analytic-Center Cutting-Plane Method for Variational Inequalities: A Quadratic-Cut Approach

We introduce a cutting-plane, analytic-center algorithm for strongly monotone variational inequalities (VIs). The approach extends that of Goffin et al. (1997) and Denault and Goffin (1999). The VI is still treated as a convex feasibility problem, with linear cuts progressively shrinking a localization set that contains the solution of the VI. However, a quadratic cut is used to improve the positioning of the point at which the next cut will be generated. Our approach uses quadratic, ellipsoidal cuts, based on the symmetrized Jacobian of the VI. Since it cannot be guaranteed that such quadratic cuts do not cut off the solution of the VI, they are used only for direction, and are not integrated as such in the localization set; only the linear part of the quadratic cuts can safely be added to the localization set. The introduction of the quadratic cut together with the drop of the quadratic part of the previous cut is studied carefully. Numerical results are given that illustrate the substantial improvement that quadratic cuts can yield over linear cuts.