Solving Constrained Variational Inequalities via an Interior Point Method
We develop an interior-point approach to solve constrained variational
inequality (cVI) problems. Inspired by the efficacy of the alternating
direction method of multipliers (ADMM) method in the single-objective context,
we generalize ADMM to derive a first-order method for cVIs, that we refer to as
ADMM-based interior point method for constrained VIs (ACVI). We provide
convergence guarantees for ACVI in two general classes of problems: (i) when
the operator is $\xi$-monotone, and (ii) when it is monotone, the constraints
are active and the game is not purely rotational. When the operator is in
addition L-Lipschitz for the latter case, we match known lower bounds on rates
for the gap function of $\mathcal{O}(1/\sqrt{K})$ and $\mathcal{O}(1/K)$ for
the last and average iterate, respectively. To the best of our knowledge, this
is the first presentation of a first-order interior-point method for the
general cVI problem that has a global convergence guarantee. Moreover, unlike
previous work in this setting, ACVI provides a means to solve cVIs when the
constraints are nontrivial. Empirical analyses demonstrate clear advantages of
ACVI over common first-order methods. In particular, (i) cyclical behavior is
notably reduced as our methods approach the solution from the analytic center,
and (ii) unlike projection-based methods that oscillate when near a constraint,
ACVI efficiently handles the constraints.