Generalized Mirror Prox for Monotone Variational Inequalities: Universality and Inexact Oracle
Preprint
Abstract
We introduce an inexact oracle model for variational inequalities (VI) with monotone operator, propose a numerical method which solves such VI's and analyze its convergence rate. As a particular case, we consider VI's with H\"older-continuous operator and show that our algorithm is universal. This means that without knowing the H\"older parameter $\nu$ and H\"older constant $L_{\nu}$ it has the best possible complexity for this class of VI's, namely our algorithm has complexity $O\left( \inf_{\nu\in[0,1]}\left(\frac{L_{\nu}}{\varepsilon} \right)^{\frac{2}{1+\nu}}R^2 \right)$, where $R$ is the size of the feasible set and $\varepsilon$ is the desired accuracy of the solution. We also consider the case of VI's with strongly monotone operator and generalize our method for VI's with inexact oracle and our universal method for this class of problems. Finally, we show, how our method can be applied to convex-concave saddle point problems with H\"older-continuous partial subgradients.
Keywords
All Related Versions
This publication has 38 references indexed in Scilit:
- Implementable tensor methods in unconstrained convex optimizationMathematical Programming, 2019
- Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problemsMathematical Programming, 2019
- Generalized Uniformly Optimal Methods for Nonlinear ProgrammingJournal of Scientific Computing, 2019
- Primal-Dual Methods for Solving Infinite-Dimensional GamesJournal of Optimization Theory and Applications, 2015
- On the convergence properties of non-Euclidean extragradient methods for variational inequalities with generalized monotone operatorsComputational Optimization and Applications, 2014
- Universal gradient methods for convex optimization problemsMathematical Programming, 2014
- First-order methods of smooth convex optimization with inexact oracleMathematical Programming, 2013
- Modified projection method for strongly pseudomonotone variational inequalitiesJournal of Global Optimization, 2013
- Dual extrapolation and its applications to solving variational inequalities and related problemsMathematical Programming, 2006
- Finite-dimensional variational inequality and nonlinear complementarity problems: A survey of theory, algorithms and applicationsMathematical Programming, 1990