Stonyakin, Fedor
[Verfasser:in];
Gasnikov, Alexander
[Verfasser:in];
Dvurechensky, Pavel
[Verfasser:in];
Alkousa, Mohammad
[Verfasser:in];
Titov, Alexander
[Verfasser:in]
Generalized Mirror Prox for Monotone Variational Inequalities: Universality and Inexact Oracle
Titel:
Generalized Mirror Prox for Monotone Variational Inequalities: Universality and Inexact Oracle
Beteiligte:
Stonyakin, Fedor
[Verfasser:in];
Gasnikov, Alexander
[Verfasser:in];
Dvurechensky, Pavel
[Verfasser:in];
Alkousa, Mohammad
[Verfasser:in];
Titov, Alexander
[Verfasser:in]
Anmerkungen:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Beschreibung:
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ölder-continuous operator and show that our algorithm is universal. This means that without knowing the Hölder parameter ν and Hölder constant Lν it has the best possible complexity for this class of VI's, namely our algorithm has complexity O(infν∈[0,1](Lνε)21+νR2), where R is the size of the feasible set and ε 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ölder-continuous partial subgradients.