Primal Methods for Variational Inequality Problems with Functional
  Constraints
Liang Zhang Niao He Michael Muehlebach
Constrained variational inequality problems are recognized for their broad
applications across various fields including machine learning and operations
research. First-order methods have emerged as the standard approach for solving
these problems due to their simplicity and scalability. However, they typically
rely on projection or linear minimization oracles to navigate the feasible set,
which becomes computationally expensive in practical scenarios featuring
multiple functional constraints. Existing efforts to tackle such functional
constrained variational inequality problems have centered on primal-dual
algorithms grounded in the Lagrangian function. These algorithms along with
their theoretical analysis often require the existence and prior knowledge of
the optimal Lagrange multipliers. In this work, we propose a simple primal
method, termed Constrained Gradient Method (CGM), for addressing functional
constrained variational inequality problems, without necessitating any
information on the optimal Lagrange multipliers. We establish a non-asymptotic
convergence analysis of the algorithm for variational inequality problems with
monotone operators under smooth constraints. Remarkably, our algorithms match
the complexity of projection-based methods in terms of operator queries for
both monotone and strongly monotone settings, while utilizing significantly
cheaper oracles based on quadratic programming. Furthermore, we provide several
numerical examples to evaluate the efficacy of our algorithms.