FINITE CONVERGENCE OF TWO-STAGE ALGORITHMS FOR SOLVING OF EQUILIBRIUM PROBLEMS

  • Ya. I. Vedel Faculty of Computer Science and Cybernetics, Taras Shevchenko Kiev National University, Kiev, Ukraine
  • E. N. Golubeva Faculty of Computer Science and Cybernetics, Taras Shevchenko Kiev National University, Kiev, Ukraine
  • V. V. Semenov Faculty of Computer Science and Cybernetics, Taras Shevchenko Kiev National University, Kiev, Ukraine
Keywords: equilibrium problem, bifunction, pseudo-monotonicity, sharpness, two-stage proximal algorithm, Hilbert space, finite convergence

Abstract

A two iterative two-stage proximal algorithms for the approximate solution of the equilibrium problem in a Hilbert space is considered. In this article we proved the convergence of algorithms in a finite number of iterations when the condition of sharpness is fulfilled.

References

Antipin A. S. Equilibrium programming: Proximal methods. Comput. Math. Math. Phys. 1997. Vol. 37. P. 1285–1296.

Mastroeni G. On auxiliary principle for equilibrium problems. In: Daniele, P. et al. (eds.) Equilibrium Problems and Variational Models. Kluwer Academic Publishers, Dordrecht, 2003. P. 289-298.

Combettes P. L., Hirstoaga S. A. Equilibrium Programming in Hilbert Spaces. J. Nonlinear Convex Anal. 2005. Vol. 6. P. 117–136.

Korpelevich G. M. The extragradient method for finding saddle points and other problems. Ekonomika i Matematicheskie Metody. 1976. Vol. 12. P. 747–756.

Lyashko S. I., Semenov V. V., Voitova T. A. Low-cost modification of Korpelevich’s methods for monotone equilibrium problems. Cybernetics and Systems Analysis. 2011. Vol. 47. P. 631–639.

Quoc T. D., Muu L. D., Hien N. V. Extragradient algorithms extended to equilibrium problems. Optimization. 2008. Vol. 57. P. 749–776.

Popov L. D. A modification of the Arrow-Hurwicz method for search of saddle points. Mathematical notes of the Academy of Sciences of the USSR. 1980. Vol. 28. Issue 5. P. 845–848.

Vedel Y. I., Semenov V. V. A new two-phase proximal method of solving the problem of equilibrium programming. Journal of Computational and Applied Mathematics. 2015. No. 1 (118). P. 15–23. (in Russian)

Lyashko S. I., Semenov V. V. 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, vol. 115. Springer, Cham, 2016. P. 315–325.

Chabak L., Semenov V., Vedel Y. A New Non-Euclidean Proximal Method for Equilibrium Problems. In: Chertov O., Mylovanov T., Kondratenko Y., Kacprzyk J., Kreinovich V., Stefanuk V. (eds.) Recent Developments in Data Science and Intelligent Analysis of Information. ICDSIAI 2018. Advances in Intelligent Systems and Computing, vol. 836. Springer, Cham, 2019. P. 50–58.

Vedel Y. I., Semenov V. V., Chabak L. M. About the two-stage proximal method for solving of equilibrium problems. Journal of Numerical and Applied Mathematics. 2019. No. 2 (131). P. 23–31. (in Russian)

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

Zykina A. V., Melenchuk N. V. Finite number of iterations in the two-step extragradient method. Russian Mathematics. 2014. Volume 58. Issue 9. P. 62–65.

Ferris M. C. Finite convergence of the proximal point algorithm. Math. Programming. 1991. Vol. 50. P. 359–366.

Burke J. V., Ferris M. C. Weak sharp minima in mathematical programming. SIAM J. Control Optim. 1993. Vol. 31. P. 1340–1359.

Antipin A. S. On the finite convergence of processes to a sharp minimum and a smooth minimum with a sharp derivative. Differ. Equ. 1994. Vol. 30. No. 11. P.1703–1713.

Marcotte P., Zhu D. L. Weak sharp solutions of variational inequalities. SIAM J. Optim. 1999. Vol. 9. P. 179–189.

Xiu N. H., Zhang J. Z. Local convergence analysis of projection-type algorithms: a unified approach. J. Optim. Theory Appl. 2002. Vol. 115. P. 211–230.

Wu Z. L., Wu S. Y. Weak sharp solutions of variational inequalities in Hilbert spaces. SIAM J. Optim. 2004. Vol. 14. P. 1011–1027.

Xiu N., Zhang J. On finite convergence of proximal point algorithms for variational inequalities. J. Math. Anal. Appl. 2005. Vol. 312. P. 148–158.

Matsushita S., Xu L. Finite Convergence of the Proximal Point Algorithm for Variational Inequality Problems. Set-Valued Variational Analysis. 2013. Vol. 21. P. 297–309.

Zhou J., Wang C. A note on finite termination of iterative algorithms in mathematical programming. Oper. Res. Lett. 2008. Vol. 36. P. 715–717.

Chabak L. M., Vedel Ya. I., Dudar V. V., Semenov V. V. Finite convergence of two-stage algorithms for solving variational inequalities. Journal of Numerical and Applied Mathematics. 2017. No. 2 (125). P. 91–99. (in Russian)

Konnov I. V. Application of the proximal point method to nonmonotone equilibrium problems. J. Optim. Theory Appl. 2003. Vol. 119. P. 317–333.

Polyak B. T. Introduction in Optimization. Moscow: Nauka, 1983. 384 p. (in Russian)

Bauschke H. H., Combettes P. L. Convex Analysis and Monotone Operator Theory in Hilbert Spaces. Berlin, Heidelberg, New York: Springer, 2011. 408 p.

Malitsky Yu. V., Semenov V. V. An extragradient algorithm for monotone variational inequalities. Cybernetics and Systems Analysis. 2014. Vol. 50. P. 271–277.

Semenov V. V. A Version of the Mirror descent Method to Solve Variational Inequalities. Cybernetics and Systems Analysis. 2017. Vol. 53. P. 234–243.

Nomirovskii D. A., Rublyov V. V., Semenov V. V. Convergence of Two-Stage Method with Bregman Divergence for Solving Variational Inequalities. Cybernetics and Systems Analysis. 2019. Vol. 55. P. 359–368.

Gidel G., Berard H., Vincent P., Lacoste-Julien S. A Variational Inequality Perspective on Generative Adversarial Networks. arXiv:1802.10551. 2018.

Published
2019-12-25