Convergence of the Bregman extragradient method

TitleConvergence of the Bregman extragradient method
Publication TypeJournal Article
Year of Publication2019
AuthorsVedel, YI, Denisov, SV, Semenov, VV
Abbreviated Key TitleDopov. Nac. akad. nauk Ukr.
SectionInformation Science and Cybernetics
Date Published05/2019

The convergence of a new extragradient-type method for the approximate solution of variational inequalities with pseudomonotonіс and Lipschitz-continuous operators acting in a finite-dimensional linear normed space is proved. The method uses the Bregman divergence instead of the Euclidean distance and the new adjustment of the step size, which does not require knowledge of the Lipschitz constant of an operator. In contrast to the previously used rules for choosing the step size, the proposed method does not perform additional calculations for the operator values and prox-map.

KeywordsBregman divergence, convergence, extragradient method, variational inequality

1. Korpelevich, G. M. (1976). The extragradient method for finding saddle points and other problems. Ekonomika i Matematicheskie Metody, 12, No. 4, pp. 747-756 (in Russian).
2. Tseng, P. (2000). A modified forward-backward splitting method for maximal monotone mappings. SIAM J. Control Optim., 38, pp. 431-446. doi:
3. Semenov, V. V. (2014). A strongly convergent splitting method for systems of operator inclusions with monotone operators. J. Autom. Inform. Sci., 46, No. 5, pp. 45-56. doi:
4. Semenov, V. V. (2014). Hybrid splitting methods for the system of operator inclusions with monotone operators. Cybern. Syst. Anal., 50, pp. 741-749. doi:
5. Denisov, S. V., Semenov, V. V. & Chabak, L. M. (2015). Convergence of the modified extragradient method for variational inequalities with non-Lipschitz operators. Cybern. Syst. Anal., 51, pp. 757-765. doi:
6. Verlan, D. A., Semenov, V. V. & Chabak, L. M. (2015). A strongly convergent modified extragradient method for variational inequalities with non-Lipschitz operators. J. Autom. Inform. Sci., 47, No. 7, pp. 31-46. doi:
7. Nemirovski, A. (2004). Prox-method with rate of convergence O(1/t) for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM J. Optim., 15, pp. 229-251. doi:
8. Nesterov, Yu. (2007). Dual extrapolation and its applications to solving variational inequalities and related problems. Math. Program., 109, Iss. 2-3, pp. 319–344. doi:
9. Semenov, V. V. (2017). A version of the mirror descent method to solve variational inequalities. Cybern. Syst. Anal., 53, pp. 234-243. doi:
10. Semenov, V. V. (2018). Modified extragradient method with bregman divergence for variational inequalities. J. Autom. Inform. Sci., 50, Iss. 8, pp. 26-37. doi:
11. Lyashko, S. I. & Semenov, V. V. (2016). A new two-step proximal algorithm of solving the problem of equilibrium programming. In Goldengorin, B. (Ed.). Optimization and its applications in control and data sciences (pp. 315-325). Optimization and Its Applications, Vol. 115. Cham: Springer. doi:
12. Khobotov, E. N. (1987). Modification of the extra-gradient method for solving variational inequalities and certain optimization problems. USSR Comput. Math. Math. Phys., 27, Iss. 5, pp. 120-127. doi:
13. Beck, A. (2017). First-order methods in optimization. Philadelphia: Society for Industrial and Applied Mathematics. doi: