Approximate Analytic Center Quadratic Cut Method for Strongly Monotone Variational Inequalities

For strongly monotone variational inequality problems (VIP) convergence of an algorithm is investigated which, at each iteration k, adds a quadratic cut through an approximate analytic center x k of the subsequently shrinking convex body. First it is shown that the sequence of x k converges to the unique solution x* of the VIP at \(O(1/\sqrt k )\) . As an interesting detail note that — for increasingly accurate analytic centers — the complexity constants converge to the quantities obtained for ACQCM with exact centers. Secondly we show that the arithmetic complexity to update from x k to x k +1 after inserting a quadratic cut through x k is bounded by a constant number of Newton iterations plus \(O(n\cdot \ln \ln [\varsigma \cdot \frac{{{k^2}}}{{{\varepsilon ^4}}}])\) , where n is the space-dimension, e is the final solution accuracy ‖x k — x*‖, and ζ depends on some problem-specific constants only.