Cybernetics And Systems Analysis logo
Editorial Board Announcements Abstracts Authors Archive
Cybernetics And Systems Analysis
International Theoretical Science Journal
UDC 517.988
D.A. Nomirovskii1, B.V. Rublyov2, V.V. Semenov3


1 Taras Shevchenko National University of Kyiv, Kyiv, Ukraine

kashpir74@gmail.com

2 Taras Shevchenko National University of Kyiv, Kyiv, Ukraine

rublyovbv@gmail.com

3 Taras Shevchenko National University of Kyiv, Kyiv, Ukraine

semenov.volodya@gmail.com

CONVERGENCE OF TWO-STEP METHOD WITH BREGMAN DIVERGENCE
FOR SOLVING VARIATIONAL INEQUALITIES

Abstract. A new two-step method for the approximate solution of variational inequalities with pseudo-monotone and Lipschitz-continuous operators acting in a finite- dimensional linear normed space is proposed. This method is a modification of several previously studied 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.

Keywords: variational inequality, pseudo-monotonicity, monotonicity, Lipschitz condition, two-step method, Bregman divergence, convergence.



FULL TEXT

REFERENCES

  1. Konnov I.V. Combined relaxation methods for variational inequalities. Berlin; Heidelberg; New York: Springer-Verlag, 2001. 181 p.

  2. Nagurney A. Network economics: A variational inequality approach. Dordrecht: Kluwer Academic Publishers, 1999. 325 p.

  3. Korpelevich G.M. Extragradient method for finding saddle points and other tasks. Ekonomika i mat. metody. 1976. V. 12, No. 4. P. 747–756.

  4. Nemirovski A. Prox-method with rate of convergence for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM Journal on Optimization. 2004. Vol. 15. P. 229–251.

  5. Auslender A., Teboulle M. Interior projection-like methods for monotone variational inequalities. Mathematical Programming. 2005. Vol. 104, Iss. 1. P. 39–68.

  6. Nesterov Yu. Dual extrapolation and its applications to solving variational inequalities and related problems. Mathematical Programming. 2007. Vol. 109, Iss. 2–3. P. 319–344.

  7. Nurminski E.A. The use of additional small effects in the Fejer models of iterative algorithms. Zhurn. Vychisl. Mat. i Mat. Fiz. 2008. V. 48, No. 12. P. 2121–2128.

  8. Semenov V.V. On the method of parallel proximal decomposition for solving problems of convex optimization. Probl. upravleniya i informatiki. 2010. No. 2. P. 42–46.

  9. Censor Y., Gibali A., Reich S. The subgradient extragradient method for solving variational inequalities in Hilbert space. Journal of Optimization Theory and Applications. 2011. Vol. 148. P. 318–335.

  10. Lyashko S.I., Semenov V.V., Voitova T.A. Economical modification of the Korpelevich method for monotone equilibrium problems. Kibernetika i sistemnyj analiz. 2011. No. 4. P. 146–154.

  11. Semenov V.V. Strongly convergent splitting method for a system of operator inclusions with monotone operators. Probl. upravleniya i informatiki. 2014. No. 3. P. 22–32.

  12. Semenov V.V. Hybrid splitting methods for a system of operator inclusions with monotone operators. Kibernetika i sistemnyj analiz. 2014. Vol. 50, № 5. P. 104–112.

  13. Verlan D.A., Semenov V.V., Chabak L.M. A strongly convergent modified extragradient method for variational inequalities with non-Lipschitz operators. Probl. upravleniya i informatiki. 2015. No. 4. P. 37–50.

  14. Denisov S.V., Semenov V.V., Chabak L.M. Convergence of the modified extragradient method for variational inequalities with non-Lipschitz operators. Kibernetika i sistemnyj analiz. 2015. Vol. 51, No. 5. P. 102–110.

  15. Popov L.D. Modification of the Arrow–Hurwitz method of searching for saddle points. Mat. zametki. 1980. Vol. 28, No. 5. P. 777–784.

  16. Malitsky Yu.V., Semenov V.V. An extragradient algorithm for monotone variational inequalities. Kibernetika i sistemnyj analiz. 2014. Vol. 50, No. 2. P. 125–131.

  17. Semenov V.V. Variant of the method of mirror descent for variational inequalities. Kibernetika i sistemnyj analiz. 2017. Vol. 53, No. 2. P. 83–93.

  18. Lyashko S.I., Semenov V.V. 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. Springer Optimization and Its Applications. Cham: Springer, 2016. Vol. 115. P. 315–325.

  19. Bregman L.M. Relaxation method for finding a common point of convex sets and its application for solving convex programming problems. Zhurn. vychisl. matematiki i mat. fiziki. 1967. No. 3. P. 620–631.

  20. Nemirovsky A.S., Yudin D.B. The complexity of the problems and the efficiency of optimization methods (in Russian). Moscow: Nauka, 1979. 384 p.

  21. Beck A. First-order methods in optimization. Philadelphia: Society for Industrial and Applied Mathematics, 2017. 479 p.

  22. Semenov V.V. Modified extragradient method with Bregman divergence for variational inequalities. Probl. upravleniya i informatiki. 2018. No. 4. P. 43–53.

  23. Lorenz D.A., Schopfer F., Wenger S. The linearized Bregman method via split feasibility problems. Analysis and generalizations. SIAM Journal on Imaging Sciences. 2014. Vol. 7, Iss. 2. P. 1237–1262.
© 2019 Kibernetika.org. All rights reserved.