# An Augmented Lagrangian Approach to Conically Constrained Non-monotone Variational Inequality Problems

arXiv: https://arxiv.org/abs/2306.01214 · HTML: https://mlsanity.com/paper/2306.01214/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 51 references that are in the map.
- First posted on arXiv 2 Jun 2023.

## Builds on (most cited first, 9 of 9)

- [Golden Ratio Algorithms for Variational Inequalities](https://mlsanity.com/paper/1803.08832/) (2018)
- [Non-convex Min-Max Optimization: Applications, Challenges, and Recent Theoretical Advances](https://mlsanity.com/paper/2006.08141/) (2020)
- [A Forward-Backward Splitting Method for Monotone Inclusions Without Cocoercivity](https://mlsanity.com/paper/1808.04162/) (2018)
- [On Lower Iteration Complexity Bounds for the Saddle Point Problems](https://mlsanity.com/paper/1912.07481/) (2019)
- [A First-Order Primal-Dual Method for Nonconvex Constrained Optimization Based On the Augmented Lagrangian](https://mlsanity.com/paper/2007.12219/) (2020)
- [Perseus: A Simple and Optimal High-Order Method for Variational Inequalities](https://mlsanity.com/paper/2205.03202/) (2022)
- [A Unifying Framework of Accelerated First-Order Approach to Strongly Monotone Variational Inequalities](https://mlsanity.com/paper/2103.15270/) (2021)
- [On Error Bounds and Multiplier Methods for Variational Problems in Banach Spaces](https://mlsanity.com/paper/1807.04034/) (2018)
- [Primal-Dual First-Order Methods for Affinely Constrained Multi-Block Saddle Point Problems](https://mlsanity.com/paper/2109.14212/) (2021)

## Abstract (arXiv)

In this paper we consider a non-monotone (mixed) variational inequality model with (nonlinear) convex conic constraints. Through developing an equivalent Lagrangian function-like primal-dual saddle-point system for the VI model in question, we introduce an augmented Lagrangian primal-dual method, to be called ALAVI in the current paper, for solving a general constrained VI model. Under an assumption, to be called the primal-dual variational coherence condition in the paper, we prove the convergence of ALAVI. Next, we show that many existing generalized monotonicity properties are sufficient -- though by no means necessary -- to imply the above mentioned coherence condition, thus are sufficient to ensure convergence of ALAVI. Under that assumption, we further show that ALAVI has in fact an o(1/√k) global rate of convergence where k is the iteration count. By introducing a new gap function, this rate further improves to be O(1/k) if the mapping is monotone. Finally, we show that under a metric subregularity condition, even if the VI model may be non-monotone the local convergence rate of ALAVI improves to be linear. Numerical experiments on some randomly generated highly nonlinear and non-monotone VI problems show practical efficacy of the newly proposed method.