Abstract
A new two-stage method is proposed for the approximate solution of variational inequalities with pseudo-monotone and Lipschitz-continuous operators acting in a finite-dimensional linear normed space. This method is a modification of several well-known two-stage algorithms using the Bregman divergence instead of the Euclidean distance. Like other schemes using Bregman divergence, the proposed method can sometimes efficiently take into account the structure of the feasible set of the problem. A theorem on the convergence of the method is proved and, in the case of a monotone operator and convex compact feasible set, non-asymptotic estimates of the efficiency of the method are obtained.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
I. V. Konnov, Combined Relaxation Methods for Variational Inequalities, Springer-Verlag, Berlin–Heidelberg–New York (2001).
A. Nagurney, Network Economics: A Variational Inequality Approach, Kluwer Academic Publishers, Dordrecht (1999).
G. M. Korpelevich, “The extra-gradient method for finding saddle points and other problems,” Ekonomika i Mat. Metody, Vol. 12, No. 4, 747–756 (1976).
A. Nemirovski, “Prox-method with rate of convergence O t (1/ ) for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems,” SIAM J. on Optimization, Vol. 15, 229–251 (2004).
A. Auslender and M. Teboulle, “Interior projection-like methods for monotone variational inequalities,” Mathematical Programming, Vol. 104, Iss. 1, 39–68 (2005).
Yu. Nesterov, “Dual extrapolation and its applications to solving variational inequalities and related problems,” Mathematical Programming, Vol. 109, Iss. 2–3, 319–344 (2007).
E. A. Nurminski, “The use of additional diminishing disturbances in Fejer models of iterative algorithms,” J. Comp. Math. Math. Physics, Vol. 48, No. 12, 2154–2161 (2008).
V. V. Semenov, “On the parallel proximal decomposition method for solving the problems of convex optimization,” J. Autom. Inform. Sci., Vol. 42, Iss. 4, 13–18 (2010).
Y. Censor, A. Gibali, and S. Reich, “The subgradient extragradient method for solving variational inequalities in Hilbert space,” J. of Optimization Theory and Applications, Vol. 148, 318–335 (2011).
S. I. Lyashko, V. V. Semenov, and T. A. Voitova, “Low-cost modification of Korpelevich’s methods for monotone equilibrium problems,” Cybern. Syst. Analysis, Vol. 47, No. 4, 631–639 (2011).
V. V. Semenov, “A strongly convergent splitting method for the system of operator inclusions with monotone operators,” J. Autom. Inform. Sci., Vol. 46, Iss. 5, 45–56 (2014).
V. V. Semenov, “Hybrid splitting metods for the system of operator inclusions with monotone operators,” Cybern. Syst. Analysis, Vol. 50, No. 5, 741–749 (2014).
D. A. Verlan, V. V. Semenov, and L. M. Chabak, “A strongly convergent modified extragradient method for variational inequalities with non-Lipschitz operators,” J. Autom. Inform. Sci., Vol. 47, Iss. 7, 31–46 (2015).
S. V. Denisov, V. V. Semenov, and L. M. Chabak, “Convergence of the modified extragradient method for variational inequalities with non-Lipschitz operators,” Cybern. Syst. Analysis, Vol. 51, No. 5, 757–765 (2015).
L. D. Popov, “A modification of the of Arrow–Hurwitz method for finding saddle points,” Mat. Zametki, Vol. 28, No. 5, 777–784 (1980).
Yu. V. Malitsky and V. V. Semenov, “An extragradient algorithm for monotone variational inequalities,” Cybern. Syst. Analysis, Vol. 50, No. 2, 271–277 (2014).
V. V. Semenov, “A version of the mirror descent method to solve variational inequalities,” Cybern. Syst. Analysis, Vol. 53, No. 2, 234–243 (2017).
S. I. Lyashko and V. V. Semenov, “A new two-step proximal algorithm of solving the problem of equilibrium programming,” in: B. Goldengorin (ed.), Optimization and Its Applications in Control and Data Sciences, Springer Optimization and Its Applications, Springer, Cham, Vol. 115 (2016), 315–325.
L. M. Bregman, “A relaxation method to find a common point of convex sets and its application to solve convex programming problems,” Zhurn. Vych. Mat. Mat. Fiziki, Vol. 7, No. 3, 620–631 (1967).
A. S. Nemirovskii and D. B. Yudin, Problem Complexity and Efficiency of Optimization Methods [in Russian], Nauka, Moscow (1979).
A. Beck, First-Order Methods in Optimization, Society for Industrial and Applied Mathematics, Philadelphia (2017).
V. V. Semenov, “Modified extragradient method with Bregman divergence for variational inequalities,” J. Autom. Inform. Sci., Vol. 50, Iss. 8, 26–37 (2018).
D. A. Lorenz, F. Schopfer, and S. Wenger, “The linearized Bregman method via split feasibility problems,” Analysis and Generalizations. SIAM J. on Imaging Sciences, Vol. 7, Iss. 2, 1237–1262 (2014).
Author information
Authors and Affiliations
Corresponding author
Additional information
Translated from Kibernetika i Sistemnyi Analiz, No. 3, May–June, 2019, pp. 17–27.
Rights and permissions
About this article
Cite this article
Nomirovskii, D.A., Rublyov, B.V. & Semenov, V.V. Convergence of Two-Stage Method with Bregman Divergence for Solving Variational Inequalities*. Cybern Syst Anal 55, 359–368 (2019). https://doi.org/10.1007/s10559-019-00142-7
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10559-019-00142-7