.
To our knowledge the proposed ACQCM
is the first analytic center cut method which profits explicitly
from the curvature of quadratic cuts.
An Analytic Center Quadratic Cut Method (ACQCM) for
Strongly Monotone Variational Inequality Problems
Hans-Jakob Lüthi and Benno Büeler,
Institute for Operations Research,
Swiss Federal Institute
of Technology;
e-mail: {luethi, bueeler}@ifor.math.ethz.ch
For strongly monotone variational inequality problems (VIP)
convergence of an algorithm is investigated which, at each iteration,
adds a quadratic cut through the analytic center of the subsequently
shrinking convex body. It is shown that the sequence of analytic
centers converges to the unique solution at .
To our knowledge the proposed ACQCM
is the first analytic center cut method which profits explicitly
from the curvature of quadratic cuts.
This work complements the recent result of Nesterov and Vial (NV)
as follows.
First, our algorithm converges with respect to 
, whereas
NV's algorithm converges with respect to the dual gap function.
Second, NV embed the original problem in a conic space, while we
can carry
out the analysis in the original space.
Third, our solution iterates are simply the consequent analytic
centers, whereas
NV's approach uses a genius weighted average of all analytic
centers. As a consequence, their approach might have more numerical
problems
in a real implementation than our approach. This is supported by NV's
analysis for approximate centers.
To conclude, while NV's fascinating approach requires monotonicity only whereas we assume strong monotonicity, we can use second order information by means of quadratic cuts, facilitating the analysis and making hopefully our algorithm numerically more robust.