Parameter-Free First-Order Method for Constrained Variational Inequalities
math.OC
Submitted: 2026-10-30
Updated: 2026-10-30
Code: https://github.com/qluorocky/CVI_IJOC
License: http://creativecommons.org/licenses/by/4.0/
The gist: Constrained variational inequalities (VIs) provide a general framework for modeling and solving complementarity and equilibrium problems with functional constraints.
Terminology
Abstract
Constrained variational inequalities (VIs) provide a general framework for modeling and solving complementarity and equilibrium problems with functional constraints. In this paper, we propose a parameter-free accelerated operator sliding (PFAOS) method for solving monotone VIs with convex smooth constraints. For a single constraint, PFAOS achieves an operator evaluation complexity of O(1/epsilon) and a constraint gradient evaluation complexity of O(1/sqrt epsilon), without requiring prior knowledge of the Lipschitz constant of the VI operator or the smoothness constant of the constraint function. We further extend PFAOS to multiple constraints by incorporating a primal-dual hybrid gradient update, yielding a multi-constrained PFAOS (MC-PFAOS) method that preserves the same evaluation complexities. Finally, numerical experiments are conducted on large-scale games with coupling constraints to validate the efficiency and effectiveness of the proposed algorithms.
Sources
- Simple and optimal methods for stochastic variational inequalities, I: operator extrapolation
- Mirror-prox sliding methods for solving a class of monotone variational inequalities
- Universal and Parameter-free Gradient Sliding for Composite Optimization
- Solving Convex Smooth Function Constrained Optimization Is Almost As Easy As Unconstrained Optimization
Related papers
- An Accelerated Proximal Gradient Method for Bures-Wasserstein Space
- FOMTools: Development and AI-Assisted Code Generation for First-Order Methods
- Lions and Muons: Optimization via Stochastic Frank-Wolfe under Heavy-Tailed Noise
- Dynamic Service Recommendation with Congestion-Dependent Joining: Near-Optimal and Constant-Factor Approximation Algorithms
- Integrating Learning and Optimization for Open Transport Capacity Pooling under Disruption
- Zeroth-Order Gradient Estimators under Decision-Dependent Noise