Abstract
In this paper we consider iterative methods for stochastic variational inequalities (s.v.i.) with monotone operators. Our basic assumption is that the operator possesses both smooth and nonsmooth components. Further, only noisy observations of the problem data are available. We develop a novel Stochastic Mirror-Prox (SMP) algorithm for solving s.v.i. and show that with the convenient stepsize strategy it attains the optimal rates of convergence with respect to the problem parameters. We apply the SMP algorithm to Stochastic composite minimization and describe particular applications to Stochastic Semidefinite Feasibility problem and deterministic Eigenvalue minimization.
Keywords
Variational inequalityMonotone polygonConvergence (economics)MinificationOperator (biology)MathematicsEigenvalues and eigenvectorsMathematical optimizationAlgorithmApplied mathematicsComputer science
Affiliated Institutions
Related Publications
Splitting Algorithms for the Sum of Two Nonlinear Operators
Splitting algorithms for the sum of two monotone operators. We study two splitting algorithms for (stationary and evolution) problems involving the sum of two monotone operators...
Interior-Point Polynomial Algorithms in Convex Programming
Written for specialists working in optimization, mathematical programming, or control theory. The general theory of path-following and potential reduction interior point polynom...
Interior-Point Method for Nuclear Norm Approximation with Application to System Identification
The nuclear norm (sum of singular values) of a matrix is often used in convex heuristics for rank minimization problems in control, signal processing, and statistics. Such heuri...
A Direct Formulation for Sparse PCA Using Semidefinite Programming
Given a covariance matrix, we consider the problem of maximizing the variance explained by a particular linear combination of the input variables while constraining the number o...
Applying the genetic approach to simulated annealing in solving some NP-hard problems
A stochastic approach called the annealing-genetic algorithm is presented for solving some well-known combinatorial optimization problems. This approach incorporates genetic alg...
Publication Info
- Year
- 2011
- Type
- article
- Volume
- 1
- Issue
- 1
- Pages
- 17-58
- Citations
- 173
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
173
OpenAlex
Cite This
Anatoli Juditsky,
Arkadi Nemirovski,
Claire Tauvel
(2011).
Solving Variational Inequalities with Stochastic Mirror-Prox Algorithm.
Stochastic Systems
, 1
(1)
, 17-58.
https://doi.org/10.1287/10-ssy011
Identifiers
- DOI
- 10.1287/10-ssy011