Convergence of the Bregman extragradient method
DOI:
https://doi.org/10.15407/dopovidi2019.05.018Keywords:
Bregman divergence, convergence, extragradient method, variational inequalityAbstract
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.
Downloads
References
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).
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
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
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
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
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
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
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
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
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
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
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
Beck, A. (2017). First-order methods in optimization. Philadelphia: Society for Industrial and Applied Mathematics. doi: https://doi.org/10.1137/1.9781611974997
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2024 Reports of the National Academy of Sciences of Ukraine
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
