TB-03: Solution Techniques for Variational Inequalities
Stream: Variational inequalities, Nash games, game theory, multilevel and dynamic optimization
Chair(s): Patrizia Daniele
Pseudo-monotone variational inequalities: Dynamics and numerical schemes of Tseng type
We associate to a pseudo-monotone variational inequality a Tseng-type dynamical system and carry out an asymptotic analysis for the generated trajectories. The explicit time discretization of this system results into Tseng’s forward-backward-forward algorithm with relaxation parameters, which we prove to convergence also when it is applied to the solving of pseudo-monotone variational inequalities. In addition, we show that linear convergence is guaranteed under strong pseudo-monotonicity. We close with numerical experiments which justify the theory presented.
Variance Reduction schemes for stochastic Variational inequalities
We develop a new stochastic algorithm with variance reduction for solving pseudo-monotone stochastic variational inequalities. Our method builds on Tseng’s forward-backward-forward algorithm, which is known in the deterministic literature to be a valuable alternative to Korpelevich’s extragradient method when solving variational inequalities over a convex and closed set governed by pseudo-monotone, Lipschitz continuous operators.
A second order dynamical system and its discretization for strongly pseudo-monotone variational inequalities
We consider a second order dynamical system for solving variational inequalities in Hilbert spaces. Under standard conditions, we prove the existence and uniqueness of strong global solution of the proposed dynamical system. The exponential convergence of trajectories is established under strong pseudo-monotonicity and Lipschitz continuity assumptions. A discrete version of the proposed dynamical system leads to a relaxed inertial projection algorithm whose the linear convergence is proved. We discuss the possibility of extension to general monotone inclusions.
Stochastic generalized Nash equilibrium seeking and Variational Inequalities
Barbara Franci, Sergio Grammatico
We consider the stochastic generalized Nash equilibrium problem (SGNEP) in merely monotone games with expected-value cost functions and shared constraints. Specifically, we present a distributed SGNE seeking algorithm with a single proximal computation (e.g. projection) and one single evaluation of the pseudogradient mapping. Our scheme is inspired by the relaxed forward-backward algorithm for variational inequalities by Malitsky (Mathematical programming, 2019) and convergence is proven under monotonicity of the pseudogradient, approximated with the average over a number of random samples.