An analytic center cutting plane method for solving semi-infinite variational inequality problems

Abstract

We study a variational inequality problem VI(X, F) with X being defined by infinitely many inequality constraints and F being a pseudomonotone function. It is shown that such problem can be reduced to a problem of finding a feasible point in a convex set defined by infinitely many constraints. An analytic center based cutting plane algorithm is proposed for solving the reduced problem. Under proper assumptions, the proposed algorithm finds an ε-optimal solution in O* (n2/ρ2) iterations, where O* (·) represents the leading order, n is the dimension of X, ε is a user-specified tolerance, and ρ is the radius of a ball contained in the ε-solution set of VI(X, F).