Solving Constrained Variational Inequalities via a First-order Interior Point-based Method

arXiv2206.10575MaRDI QIDQ6402778

Author name not available (Why is that?)

Publication date: 21 June 2022

Abstract: 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, some 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 $mathcalO(1/sqrtK)$ and $mathcalO(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 zigzag when near a constraint, ACVI efficiently handles the constraints.

Has companion code repository: https://github.com/chavdarova/acvi

This page was built for publication: Solving Constrained Variational Inequalities via a First-order Interior Point-based Method

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6402778)