Groupe d’études et de recherche en analyse des décisions


The ACCPM 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, Marcotte, and Zhu (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, but 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 which illustrate the substantial improvement that quadratic cuts can yield over linear cuts.

, 33 pages

Ce cahier a été révisé en octobre 2002