A new modified extragradient method with Bregman divergence
DOI:
https://doi.org/10.15407/dopovidi2018.08.018Keywords:
Bregman divergence, convergence, extragradient method, Lipschitz condition, monotonicity, pseudomonotonicity, variational inequalityAbstract
A new method of the extragradient type for the approximate solution of variational inequalities with pseu-domonotone and Lipschitz-continuous operators acting in a finite-dimensional linear normed space is proposed. This method is a modification of the subgradient extragradient algorithm using the Bregman divergence instead of the Euclidean distance. A theorem on the convergence of the method is proved, and, in the case of a monotone operator, non-asymptotic estimates of the effectiveness of the method are obtained.
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 and Optimization, 38, pp. 431-446. doi: https://doi.org/10.1137/S0363012998338806
Censor, Y., Gibali, A., & Reich, S. (2011). The subgradient extragradient method for solving variational inequalities in Hilbert space. J. Optimization Theory and Applications, 148, pp. 318-335. doi: https://doi.org/10.1007/s10957-010-9757-3
Lyashko, S. I., Semenov, V. V. & Voitova, T. A. (2011). Low-cost modification of Korpelevich's methods for monotone equilibrium problems. Cybernetics and Systems Analysis, 47, pp. 631-639. doi: https://doi.org/10.1007/s10559-011-9343-1
Semenov, V. V. (2011). A Strongly Convergent Splitting Method for Systems of Operator Inclusions with Monotone Operators. J. Automation and Information Sciences, 46, No. 5, pp. 45-56. doi: https://doi.org/ 10.1615/JAutomatInfScien.v46.i5.40
Verlan, D. A., Semenov, V. V. & Chabak, L. M. (2015). A Strongly Convergent Modified Extragradient Method for Variational Inequalities with Non-Lipschitz Operators. J. Automation and Information Sciences, 47, No. 7, pp. 31-46. doi: https://doi.org/10.1615/JAutomatInfScien.v47.i7.40
Denisov, S. V., Semenov, V. V. & Chabak, L. M. (2015). Convergence of the Modified Extragradient Method for Variational Inequalities with Non-Lipschitz Operators. Cybernetics and Systems Analysis, 51, pp. 757-765. doi: https://doi.org/10.1007/s10559-015-9768-z
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. Optimization, 15, pp. 229-251. doi: https://doi.org/10.1137/S1052623403425629
Auslender, A. & Teboulle, M. (2005). Interior projection-like methods for monotone variational inequalities. Mathematical Programming, 104, Iss. 1, pp. 39-68. doi: https://doi.org/10.1007/s10107-004-0568-x
Bregman, L. M. (1967). The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming. USSR Computational Mathematics and Mathematical Physics, 7, pp. 200-217. doi: https://doi.org/10.1016/0041-5553(67)90040-7
Lorenz, D. A., Schöpfer, F. & Wenger, S. (2014). The Linearized Bregman Method via Split Feasibility Problems: Analysis and Generalizations. SIAM J. Imaging Sciences, 7, pp. 1237-1262. doi: https://doi.org/10.1137/130936269
Semenov, V. V. (2017). A Version of the Mirror descent Method to Solve Variational Inequalities. Cybernetics and Systems Analysis, 53, p. 234-243. doi: https://doi.org/10.1007/s10559-017-9923-9
Semenov, V. V. (2017). A variant of mirror descent method for solving variational inequalities. Int. Conference "Constructive Nonsmooth Analysis and Related Topics (dedicated to the memory of V.F. Demyanov)". St. Petersburg. May 22—27, pp. 281-284. doi: https://doi.org/10.1109/CNSA.2017.7974011
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.
