Pseudomonotone Stochastic Variational Inequality Problems: Analysis and Stochastic Approximation Schemes

Aswin Kannan, Uday V. ShanbhagarXiv 2014 · arXiv

Abstract

The variational inequality problem represents an effective tool for capturing a range of phenomena arising in engineering, economics, and applied sciences. Prompted by the role of uncertainty, recent efforts have considered both the analysis as well as the solution of the associated stochastic variational inequality problem where the map is expectation-valued. Yet, a majority of the studies have been restricted to regimes where the map is monotone. This work is motivated by the growing interest in pseudomonotone stochastic variational inequality problems (PSVIs); such problems emerge from product pricing, fractional optimization problems, and subclasses of economic equilibrium problems arising in uncertain regimes. In this paper, we first develop integration-free sufficiency conditions for the existence and uniqueness of solutions to PSVIs. We consider the solution of PSVIs via stochastic approximation (SA) schemes, proving that the solution iterates produced by extragradient and mirror-prox SA schemes converge to the solution set in an almost sure sense. Under stronger conditions, we derive the optimal initial steplength and show that the mean-squared error in the solution iterates produced by the extragradient SA scheme converges at the optimal rate of $O(1/K)$.

Introduction

Variational Inequality (VI) problems serve as a fundamental framework for modeling complex systems, including traffic flow, power grids, and economic equilibria. When these systems are subject to uncertainty, they are modeled as Stochastic Variational Inequalities (SVIs), where the governing map is an expectation over random variables. Historically, the analysis of SVIs has been largely confined to the class of monotone maps—the VI counterpart to convex functions. However, many practical applications, such as fractional programming and product pricing, exhibit pseudomonotonicity rather than monotonicity. This work bridges the gap by providing a rigorous analysis and efficient solution schemes for pseudomonotone SVIs (PSVIs).

Theoretical Contributions: Integration-Free Analysis

A significant hurdle in SVI theory is the requirement for tractable expressions of integrals arising from expectations to prove the existence and uniqueness of solutions. This often necessitates precise knowledge of the underlying probability distributions. This paper introduces "integration-free" sufficiency conditions that are distribution-independent. By focusing on the properties of the sampled map rather than the expected map, the existence of solutions can be established even in "black-box" stochastic environments where the exact distribution is unknown.

Algorithmic Framework: ESA and MPSA

To solve PSVIs, the authors analyze two primary Stochastic Approximation (SA) schemes:

  1. Stochastic Extragradient (ESA): A two-step projection method that utilizes a "look-ahead" step. This additional step allows the algorithm to stabilize in pseudomonotone landscapes where standard projection methods might oscillate or fail to converge.
  2. Mirror-Prox Generalizations (MPSA): An extension to non-Euclidean geometries using prox-functions. This allows the algorithm to be tailored to the specific geometry of the constraint set, potentially improving efficiency in high-dimensional spaces.

Convergence and Performance

A key distinction of this work is the focus on iterate convergence. While much of the prior literature focuses on the convergence of a "gap function" (an average error metric), this paper proves the almost sure convergence of the solution iterates themselves, which is a significantly stronger guarantee for practitioners.

Comparison of the proposed SA schemes with existing literature on stochastic variational inequalities.

As shown in the table above, the proposed methods (detailed in Sections 3.3 and 3.4 of the paper) provide strong guarantees for almost sure (a.s.) convergence across various pseudomonotone regimes. Notably, for strongly pseudomonotone problems or monotone problems with weak-sharpness, the mean-squared error (MSE) of the iterates converges at the optimal rate of $O(1/K)$. The authors also derive a closed-form expression for the optimal initial steplength ($\gamma_0$), which is critical for achieving these theoretical rates in practice.

Empirical Validation

The schemes were tested on a suite of problems, including stochastic fractional convex quadratic problems and Nash-Cournot games. The results confirmed that:

  • Optimal Steplength: Using the derived optimal $\gamma_0$ significantly reduces MSE compared to heuristic choices, sometimes by several orders of magnitude.
  • Efficiency: While MPSA is theoretically elegant, ESA often proves more computationally efficient per iteration due to lower overhead, making it a preferred choice for many practical applications.
  • Robustness: The algorithms successfully navigated non-monotone benchmarks like Watson’s problem, demonstrating the practical utility of the pseudomonotone framework in "wilder" landscapes.

Conclusion

By relaxing the requirement of monotonicity to pseudomonotonicity, this work significantly expands the applicability of SVI theory. The combination of integration-free existence conditions and optimal $O(1/K)$ convergence rates for iterates provides a robust foundation for solving complex stochastic equilibrium problems in engineering and economics.

Reference: Kannan, A., & Shanbhag, U. V. (2014). Pseudomonotone Stochastic Variational Inequality Problems: Analysis and Optimal Stochastic Approximation Schemes. arXiv:1410.1628v1 [math.OC].

Summary updated

Abstract

The variational inequality problem represents an effective tool for capturing a range of phenomena arising in engineering, economics, and applied sciences. Prompted by the role of uncertainty, recent efforts have considered both the analysis as well as the solution of the associated stochastic variational inequality problem where the map is expectation-valued. Yet, a majority of the studies have been restricted to regimes where the map is monotone. This work is motivated by the growing interest in pseudomonotone stochastic variational inequality problems (PSVIs); such problems emerge from product pricing, fractional optimization problems, and subclasses of economic equilibrium problems arising in uncertain regimes. In this paper, we first observe that a direct application of standard existence/uniqueness theory requires a tractable expression for the integrals arising from the expectation. Instead, we develop integration- free sufficiency conditions for the existence and uniqueness of solutions to PSVIs. We consider the solution of PSVIs via stochastic approximation (SA) schemes, motivated by the observation that almost all of the prior SA schemes can accommodate monotone SVIs. Under various forms of pseudomonotonicity, we prove that the solution iterates produced by extragradient SA schemes converge to the solution set in an almost sure sense. This result is further extended to mirror-prox regimes and an analogous statement is also provided for monotone regimes under a weak-sharpness requirement. Under stronger conditions, we derive the optimal initial steplength and show that the mean-squared error in the solution iterates produced by the extragradient SA scheme converges at the optimal rate of O(1/K). Finally, both the asymptotics and the empirical rates of the schemes are studied on a set of pseudomonotone and non-monotone variational problems.
BibTeX
@misc{kannan2014pseudomonotone,
  author = {Aswin Kannan and Uday V. Shanbhag},
  title = {{Pseudomonotone Stochastic Variational Inequality Problems: Analysis and Stochastic Approximation Schemes}},
  year = {2014},
  eprint = {1410.1628},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1410.1628},
}
Figure