Geodesic
Numerical Methods for Some Classes of Variational Inequalities with Relatively Strongly Monotone Operators
Matematičeskie zametki, Tome 112 (2022) no. 6, pp. 879-894.

Voir la notice de l'article provenant de la source Math-Net.Ru

The paper deals with a significant extension of the recently proposed class of relatively strongly convex optimization problems in spaces of large dimension. In the present paper, we introduce an analog of the concept of relative strong convexity for variational inequalities (relative strong monotonicity) and study estimates for the rate of convergence of some numerical first-order methods for problems of this type. The paper discusses two classes of variational inequalities depending on the conditions related to the smoothness of the operator. The first of these classes of problems contains relatively bounded operators, and the second, operators with an analog of the Lipschitz condition (known as relative smoothness). For variational inequalities with relatively bounded and relatively strongly monotone operators, a version of the subgradient method is studied and an optimal estimate for the rate of convergence is justified. For problems with relatively smooth and relatively strongly monotone operators, we prove the linear rate of convergence of an algorithm with a special organization of the restart procedure of a mirror prox method for variational inequalities with monotone operators.
Keywords: variational inequality, relatively strongly convex function, strongly monotone operator, relatively bounded operator, relative smoothness, subgradient method, mirror prox method, adaptive method, restart procedure, saddle point problem. 
@article{MZM_2022_112_6_a7,
     author = {F. S. Stonyakin and A. A. Titov and D. V. Makarenko and M. S. Alkousa},
     title = {Numerical {Methods} for {Some} {Classes} of {Variational} {Inequalities} with {Relatively} {Strongly} {Monotone} {Operators}},
     journal = {Matemati\v{c}eskie zametki},
     pages = {879--894},
     publisher = {mathdoc},
     volume = {112},
     number = {6},
     year = {2022},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MZM_2022_112_6_a7/}
}
TY  - JOUR
AU  - F. S. Stonyakin
AU  - A. A. Titov
AU  - D. V. Makarenko
AU  - M. S. Alkousa
TI  - Numerical Methods for Some Classes of Variational Inequalities with Relatively Strongly Monotone Operators
JO  - Matematičeskie zametki
PY  - 2022
SP  - 879
EP  - 894
VL  - 112
IS  - 6
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MZM_2022_112_6_a7/
LA  - ru
ID  - MZM_2022_112_6_a7
ER  - 
%0 Journal Article
%A F. S. Stonyakin
%A A. A. Titov
%A D. V. Makarenko
%A M. S. Alkousa
%T Numerical Methods for Some Classes of Variational Inequalities with Relatively Strongly Monotone Operators
%J Matematičeskie zametki
%D 2022
%P 879-894
%V 112
%N 6
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MZM_2022_112_6_a7/
%G ru
%F MZM_2022_112_6_a7
F. S. Stonyakin; A. A. Titov; D. V. Makarenko; M. S. Alkousa. Numerical Methods for Some Classes of Variational Inequalities with Relatively Strongly Monotone Operators. Matematičeskie zametki, Tome 112 (2022) no. 6, pp. 879-894. http://geodesic.mathdoc.fr/item/MZM_2022_112_6_a7/

[1] H. Bauschke, J. Bolte, M. Teboulle, “A descent lemma beyond Lipschitz gradient continuity: first-order methods revisited and applications”, Math. Oper. Res., 42:2 (2017), 330–348 | DOI | MR | Zbl

[2] R.-A. Dragomir, A. Taylor, A. d'Aspremont, J. Bolte, “Optimal complexity and certification of Bregman first-order methods”, Math. Program. Ser. A, 194:1-2 (2022), 41–83 | DOI | MR | Zbl

[3] H. Lu, R. Freund, Yu. Nesterov, “Relatively smooth convex optimization by first-order methods, and applications”, SIAM J. Optim., 28:1 (2018), 333–354 | DOI | MR | Zbl

[4] R.-A. Dragomir, Bregman Gradient Methods for Relatively-Smooth Optimization, Doctoral Dissertation, 2021 https://hal.inria.fr/tel-03389344/document

[5] S. Julien, M. Schmidt, F. Bach, A Simpler Approach to Obtaining an $O(1/t)$ Convergence Rate for the Projected Stochastic Subgradient Method, 2012, arXiv: 1212.2002

[6] K. Antonakopoulos, P. Mertikopoulos, “Adaptive first-order methods revisited: Convex optimization without Lipschitz requirements”, 35th Conference on Neural Information Processing Systems (NeurIPS 2021), 2021

[7] H. Lu, “Relative-continuity for non-Lipschitz nonsmooth convex optimization using stochastic (or deterministic) mirror descent”, INFORMS J. Optim., 1:4 (2018), 288–303 | MR | Zbl

[8] Y. Zhou, V. Portella, M. Schmidt, N. Harvey, “Regret bounds without Lipschitz continuity: Online learning with relative-Lipschitz losses”, 34th Conference on Neural Information Processing Systems (NeurIPS 2020), Springer, Vancouver, BC, 2020, 232–246

[9] H. Hendrikx, L. Xiao, S. Bubeck, F. Bach, L. Massoulie, “Statistically preconditioned accelerated gradient method for distributed optimization”, Proceedings of the 37th International Conference on Machine Learning, 2020 https://hal.archives-ouvertes.fr/hal-02974232

[10] F. Stonyakin, A. Tyurin, A. Gasnikov, P. Dvurechensky, A. Agafonov, D. Dvinskikh, M. Alkousa, D. Pasechnyuk, S. Artamonov, V. Piskunova, “Inexact relative smoothness and strong convexity for optimization and variational inequalities by inexact model”, Optim. Methods Softw., 36:6 (2021), 1155–1201 | DOI | MR | Zbl

[11] A. Gasnikov, P. Dvurechensky, F. Stonyakin, A. Titov, “An adaptive proximal method for variational inequalities”, Comput. Math. and Math. Phys., 59:5 (2018), 836–841 | DOI

[12] A. Titov, F. Stonyakin, M. Alkousa, A. Gasnikov, “Algorithms for solving variational inequalities and saddle point problems with some generalizations of Lipschitz property for operators”, Mathematical Optimization Theory and Operations Research – Recent Trends, Commun. Comput. Inf. Sci., 1476, Springer, Cham, 2021, 86–101 | MR

[13] A. S. Nemirovskii, Yu. E. Nesterov, “Optimalnye metody gladkoi vypukloi minimizatsii”, Zh. vychisl. matem. i matem. fiz., 25:3 (1985), 356–369 | MR | Zbl

[14] F. Stonyakin, A. Titov, M. Alkousa, O. Savchuk, D. Pasechnyuk, Gradient-Type Adaptive Methods for Relatively Lipschitz Convex Optimization Problems, , 2021 2107.05765 | Zbl