A new modified extragradient method with Bregman divergence

TitleA new modified extragradient method with Bregman divergence
Publication TypeJournal Article
Year of Publication2018
AuthorsSemenov, VV
Abbreviated Key TitleDopov. Nac. akad. nauk Ukr.
DOI10.15407/dopovidi2018.08.018
Issue8
SectionInformation Science and Cybernetics
Pagination18-24
Date Published8/2018
LanguageRussian
Abstract

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.
KeywordsBregman divergence, convergence, extragradient method, Lipschitz condition, monotonicity, pseudomonotonicity, 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 and Optimization, 38, pp. 431-446. doi: https://doi.org/10.1137/S0363012998338806
  3. 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
  4. 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
  5. 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
  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. Automation and Information Sciences, 47, No. 7, pp. 31-46. doi: https://doi.org/10.1615/JAutomatInfScien.v47.i7.40
  7. 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
  8. 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
  9. 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
  10. 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
  11. 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
  12. 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
  13. 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