A Hybrid Algorithm for Monotone Variational Inequalities
Reza Rahimi Baghbadorani, Peyman Mohajerin Esfahani, Sergio Grammatico · 2026
Read A Hybrid Algorithm for Monotone Variational Inequalities by Reza Rahimi Baghbadorani, Peyman Mohajerin Esfahani, Sergio Grammatico (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-03658.txt.
Introduction
Reza Rahimi Baghbadorani and colleagues proposed two solvers for a broad class of math problems in which the goal is a point where no move can improve the result. Such problems show up when players seek a stable outcome, when choices unfold over time, and when competing aims must be balanced. Building on the adaptive Golden Ratio Algorithm, the team pushed its momentum past the golden ratio and switched between small and large momentum to reach the answer faster. Tests across several problem classes showed gains over existing methods.
Catalog record
| CREATOR | Reza Rahimi Baghbadorani, Peyman Mohajerin Esfahani, Sergio Grammatico |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 43375 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.03658
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A Hybrid Algorithm for Monotone Variational Inequalities Reza Rahimi Baghbadorani, Peyman Mohajerin Esfahani, Sergio Grammatico Abstract Inspired by the adaptive Golden Ratio Algorithm (aGRAAL), we propose two new methods for solving monotone variational inequalities. We show that by selecting the momentum parameter beyond the golden ratio in aGRAAL, the convergence speed can be improved, which motivates us to study the switching between small and large momentum parameters to accelerate convergence. We validate the performance of our proposed algorithms on several classes of variational inequality problems studied in the machine learning and control literature, including Nash equilibrium seeking, composite minimization, Markov decision processes, and zero-sum games, and compare them to that of existing methods. I Introduction The variational inequality (VI) problem has recently emerged from several multi-agent control and machine learning problems [ 5 ] , e.g., in generative adversarial networks, robust optimization, and optimal control [ 8 ] . Motivating example (Linear-Quadratic Dynamic Game [ 5 ] ). Consider a finite-horizon open-loop linear–quadratic (LQ) dynamic game with N agents and shared system state x_{t}\in\mathbb{R}^{n} evolving as \displaystyle x_{t+1}=A_{t}x_{t}+\sum_{i=1}^{N}B_{t}^{(i)}u_{t}^{i},\quad t\in\{0,\dots,T-1\}, where u_{t}^{i}\in\mathbb{R}^{m_{i}} is the control input of agent i at time t . Each agent i seeks to minimize the quadratic cost \displaystyle J_{i}(u^{1},\dots,u^{N}) \displaystyle=\ \frac{1}{2}\sum_{t=0}^{T-1}\Big(x_{t}^{\top}Q_{t}^{(i)}x_{t}+u_{t}^{i\top}R_{t}^{(i)}u_{t}^{i} \displaystyle+\sum_{j\neq i}u_{t}^{j\top}S_{t}^{(i,j)}u_{t}^{i}\Big)+\frac{1}{2}x_{T}^{\top}Q_{T}^{(i)}x_{T}, with Q_{t}^{(i)},Q_{T}^{(i)}\succeq 0 weighting the state deviation, R_{t}^{(i)}\succ 0 penalizing the individual control effort, and S_{t}^{(i,j)} capturing the interaction or coupling between the control actions of agents i and j . We impose local constraints on each agent’s control input u^{i}\in\mathcal{V}^{i} and global constraints on the state trajectory x_{t}\in\mathcal{X} . By recursively substituting the dynamics, the state trajectory can be expressed as an affine function of the stacked control vector u=\mathrm{col}(u^{1},\dots,u^{N}) . The resulting Nash equilibrium conditions can then be formulated as an affine variational inequality: \displaystyle\text{find }u^{*}\in\mathcal{V} \displaystyle:=\mathcal{V}^{1}\times\dots\times\mathcal{V}^{N}\text{ such that } \displaystyle\langle F(u^{*}), \displaystyle v-u^{*}\rangle\geq 0,\quad\forall v\in\mathcal{V}, where F is the pseudogradient operator of cost J_{i} defined as \displaystyle F(u)=\begin{bmatrix}\nabla_{u^{1}}J_{1}(u)\\ \vdots\\ \nabla_{u^{N}}J_{N}(u)\end{bmatrix}. This framework illustrates how shared dynamics and interactions among agents naturally lead to a VI problem, providing a tractable benchmark for developing fast and scalable algorithms for constrained multi-agent dynamic games in various applications, such as distributed automatic generation control, vehicle platooning, and the control of autonomous vehicles navigating a crossroad [ 5 , 2 ] . This motivates fast algorithms for the following VI problem: \text{find}\,\,x^{*}\in\mathcal{V}\,\text{s.t.}\,\inf\limits_{x\in\mathcal{V}}\langle F(x^{*}),x-x^{*}\rangle+g(x)-g(x^{*})\geq 0, (1) where \mathcal{V} is a finite-dimensional vector space. We assume that the operator F is continuous, monotone, Lipschitz continuous, the solution set of ( 1 ) is nonempty, and g(x) is a proper lower semicontinuous (lsc) convex function. Problem ( 1 ) can be written more traditionally as follows: \text{find}\,\,x^{*}\in\mathcal{A}\quad\text{s.t.}\quad\inf\limits_{x\in\mathcal{A}}\langle F(x^{*}),x-x^{*}\rangle\geq 0, (2) where g in ( 1 ) would be the indicator function of the set \mathcal{A} in ( 2 ). Note that VI problem in ( 1 ) can be considered as a general form of problems in convex optimization. As an example, consider the composite minimization problem \min_{x\in\mathbb{R}^{n}}f(x)+g(x) , where f is a convex and smooth function and g is a proper lsc convex (and possibly nonsmooth) function. Via the KKT conditions, this problem can be written as ( 1 ) with F=\nabla f and the same g in ( 1 ) [ 9 ] . Another common problem in optimization and control theory is the min-max problem. For example, consider the convex-concave saddle point problem \min_{y\in\mathbb{R}^{n}}\max_{z\in\mathbb{R}^{m}}g_{1}(y)+f(y,z)-g_{2}(z) , where g_{1} and g_{2} are proper lsc convex functions and f(y,z) is a smooth convex-concave function in y and z , respectively. By using first-order optimality conditions, we can rewrite this problem as in ( 1 ) with the following variables: \displaystyle x=\begin{pmatrix}y\\ z\end{pmatrix},\quad F=\begin{pmatrix}\nabla_{y}f(y,z)\\ -\nabla_{z}f(y,z)\end{pmatrix},\quad g(x)=g_{1}(y)+g_{2}(z). Furthermore, in many applications of reinforcement learning and game theory, we need to solve a fixed-point problem. For instance, Markov decision processes (MDPs) are a powerful modeling framework in reinforcement learning, where we should solve a fixed point problem, Tx=x , for some finite dimensional operator T , that is ( 1 ) with F=\mbox{Id}-T and g(x)=0 [ 6 ] . Several iterative algorithms have been introduced to address VI problems ( 1 ). For comparison purposes, let us review some recent and closely related existing methods used in system and control applications. For simplicity, let us consider the VI problem formulation in ( 2 ). Projected Gradient descent (PGD) [ 27 ] : \displaystyle x^{k+1}={\pi}_{\mathcal{A}}(x^{k}-\lambda F(x^{k})), where \lambda is the stepsize. The convergence of this method is guaranteed for strongly monotone (with a strongly monotone constant \mu ) and Lipschitz (with a Lipschitz constant L ) operator with \lambda\in\left(0,2\mu/L^{2}\right) . This algorithm is used for equilibrium seeking in aggregative games [ 4 ] (IEEE TAC, 2021), optimal consensus and resource allocation [ 17 ] (IEEE TAC, 2023), open-loop Nash equilibrium in linear quadratic dynamic games [ 5 ] , and game theoretical approach for generative adversarial network [ 11 ] (IEEE CDC, 2020). Extragradient descent [ 19 ] : \displaystyle y^{k}={\pi}_{\mathcal{A}}(x^{k}-\lambda F(x^{k})), \displaystyle x^{k+1}={\pi}_{\mathcal{A}}(x^{k}-\lambda F(y^{k})), where \lambda is the stepsize, and unlike the previous method, the convergence is guaranteed for a Lipschitz and monotone operator (with a Lipschitz constant L ) with \lambda\in\left(0,1/L\right) . The authors in [ 32 ] (IEEE CDC, 2014) implement this method to design robust stochastic extragradient algorithms for solving monotone VIs. Similarly, [ 17 ] (IEEE TAC, 2023) uses the extra-gradient method to solve the variational inequality problem in optimal consensus and resource allocation problems. The same algorithm is adopted in [ 31 ] (IEEE TPS, 2022) to design an algorithm for the variational inequality problem associated with a collaborative pricing scheme for a power-transportation coupled network. Projected Reflected Gradient descent (PrjRef) [ 23 ] : \displaystyle x^{k+1}={\pi}_{\mathcal{A}}(x^{k}-\lambda F(2x^{k}-x^{k-1})), where \lambda is the stepsize, and the convergence of this method is guaranteed for Lipschitz and monotone operator (with a Lipschitz constant L ) with \lambda\in\left(0,(\sqrt{2}-1)/L\right) . Unlike the extragradient method, PrjRef needs only one projection per iteration. The authors in [ 7 ] (IEEE CDC, 2016) implement this method to design a stochastic monotone VI algorithm under some weak sharpness assumptions. Likewise, this method is adopted in [ 16 ] (IEEE CDC, 2021) to design an algorithm for solving Bayesian regression game, which is a special class of two-player general-sum Bayesian game. The authors in [ 12 ] (ECC, 2021) also use the projected-reflected method to design an algorithm for stochastic generalized Nash equilibrium problems. Golden RAtio ALgorithm (GRAAL) [ 24 ] : \displaystyle y^{k}=(1-\beta)x^{k}+\beta y^{k-1}, \displaystyle x^{k+1}={\pi}_{\mathcal{A}}(y^{k}-\lambda F(x^{k})), where \lambda is the stepsize and \beta\in\left(0,{(\sqrt{5}-1)/2}\right] . The convergence of this method is guaranteed for Lipschitz and monotone operator (with a Lipschitz constant L ) with \lambda\in\left(0,1/{(2\beta L)}\right) , and it requires one projection per iteration. The stepsize in this method can be chosen adaptively as follows, leading to the Adaptive Golden RAtio ALgorithm (aGRAAL) [ 24 ] : \displaystyle\lambda_{k} \displaystyle= \displaystyle\min\left\{(\beta+\beta^{2})\lambda_{k-1},\frac{\|x^{k}-x^{k-1}\|^{2}}{4\beta^{2}\lambda_{k-2}\|F(x^{k})-F(x^{k-1})\|^{2}},\bar{\lambda}\right\}. This algorithm is applied in [ 13 ] (IEEE TAC, 2021) and [ 20 ] (IEEE CDC, 2021) to design a method for (stochastic) generalized Nash equilibrium in monotone games. The authors in [ 28 ] also use this method in a stochastic portfolio allocation game as a case study for Nash equilibrium seeking in quadratic-bilinear Wasserstein distributionally robust games. We also refer interested readers