Convergence of the Bregman extragradient method

Vedel, YI
Denisov, SV
1Semenov, VV
1V.М. Glushkov Institute of Cybernetics of the NAS of Ukraine, Kyiv
Dopov. Nac. akad. nauk Ukr. 2019, 5:18-23
https://doi.org/10.15407/dopovidi2019.05.018
Section: Information Science and Cybernetics
Language: Russian
Abstract: 

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.

Keywords: Bregman divergence, convergence, extragradient method, variational inequality
References: 

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: https://doi.org/10.1137/S0363012998338806
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: https://doi.org/10.1615/JAutomatInfScien.v46.i5.40
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: https://doi.org/10.1007/s10559-014-9664-y
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: https://doi.org/10.1007/s10559-015-9768-z
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: https://doi.org/10.1615/JAutomatInfScien.v47.i7.40
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: https://doi.org/10.1137/S1052623403425629
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: https://doi.org/10.1007/s10107-006-0034-z
9. Semenov, V. V. (2017). A version of the mirror descent method to solve variational inequalities. Cybern. Syst. Anal., 53, pp. 234-243. doi: https://doi.org/10.1007/s10559-017-9923-9
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: https://doi.org/10.1615/JAutomatInfScien.v50.i8.30
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: https://doi.org/10.1007/978-3-319-42056-1_10
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: https://doi.org/10.1016/0041-5553(87)90058-9
13. Beck, A. (2017). First-order methods in optimization. Philadelphia: Society for Industrial and Applied Mathematics. doi: https://doi.org/10.1137/1.9781611974997