Adaptive algorithms for equilibrium problems in Hadamard spaces

Vedel, YI
1Semenov, VV
1V.М. Glushkov Institute of Cybernetics of the NAS of Ukraine, Kyiv
Dopov. Nac. akad. nauk Ukr. 2020, 8:26-34
https://doi.org/10.15407/dopovidi2020.08.026
Section: Information Science and Cybernetics
Language: Ukrainian
Abstract: 

One of the most popular areas of modern applied nonlinear analysis is the study of equilibrium problems (Ky Fan inequalities, equilibrium programming problems). In the form of an equilibrium problem, one can formulate mathematical programming problems, vector optimization problems, variational inequalities, and many game theory problems. The classical formulation of the equilibrium problem first appeared in the works by H. Nikaido and K. Isoda, and the first general proximal algorithms for solving the equilibrium problems were proposed by A.S. Antipin. Recently, the interest has arisen in the problems of mathematical biology and machine learning to construct the theory and algorithms for solving mathematical programming problems in Hadamard metric spaces. Another strong motivation for studying these problems is the ability to write down some non-convex problems in the form of convex ones in a space with specially selected metric. In this paper, we consider general equilibrium problems in Hadamard metric spaces. For an approximate solution of problems, new iterative adaptive two-stage proximal algorithms are proposed and studied. At each step of the algorithms, the sequential minimization of two special strongly convex functions should be done. In contrast to the previously used rules for choosing the step size, the proposed algorithms do not calculate bifunction values at additional points and do not require knowledge of the information on of bifunction’s Lipschitz constants. For pseudo-monotone bifunctions of the Lipschitz type, weakly upper semicontinuous in the first variable, convex and lower semicontinuous in the second variable, the theorems on weak convergence of sequences generated by the algorithms are proved. The proof is based on the use of the Fejer property of the algorithms with respect to the set of solutions of equilibrium problem. It is shown that the proposed algorithms are applicable to variational inequalities with Lipschitz-continuous, sequentially weakly continuous and pseudomonotone operators acting in Hilbert spaces.

Keywords: adaptivity, convergence, equilibrium problem, Hadamard space, pseudo-monotonicity, two-stage proximal algorithms
References: 

1. Kassay, G. & Radulescu, V. D. (2019). Equilibrium problems and applications. London: Academic Press.
2. Antipin, A. S. (1997). Equilibrium programming: Proximal methods. Comput. Math. Math. Phys., 37, pp. 1285-1296. https://doi.org/10.1134/S0965542507120044
3. Mastroeni, G. (2003). On auxiliary principle for equilibrium problems. In Daniele, P., Giannessi, F. & Maugeri, A. (Eds.). Equilibrium problems and variational models (pp. 289-298). Dordrecht: Kluwer. https://doi.org/10.1007/978-1-4613-0239-1
4. Combettes, P. L. & Hirstoaga, S. A. (2005). Equilibrium programming in Hilbert spaces. J. Nonlinear Convex Anal., 6, pp. 117-136.
5. Lyashko, S. I. & Semenov, V. V. (2016). 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 (pp. 315-325). Springer optimization and its applications (vol. 115). Cham: Springer. https://doi.org/10.1007/978-3-319-42056-1_10
6. Korpelevich, G. M. (1976). An extragradient method for finding saddle points and for other problems. Matecon, 12, No. 4, pp. 747-756.
7. Quoc, T. D., Muu, L. D. & Hien, N. V. (2008). Extragradient algorithms extended to equilibrium problems. Optimization, 57, pp. 749-776. https://doi.org/10.1080/02331930601122876
8. Popov, L. D. (1980). A modification of the Arrow-Hurwicz method for search of saddle points. Math. Notes of the Academy of Sciences of the USSR, 28, Iss. 5, pp. 845-848. https://doi.org/10.1007/BF01141092
9. Chabak, L., Semenov, V. & Vedel, Y. (2019). A new non-euclidean proximal method for equilibrium problems. In Chertov, O., Mylovanov, T., Kondratenko, Y., Kacprzyk, J., Kreinovich, V. & Stefanuk, V. (Eds.). Recent de ve lopments in data science and intelligent analysis of information. Proceedings of the XVIII International Conference on Data Science and Intelligent Analysis of Information (pp. 50-58). Advances in Intelligent Systems and Computing (vol. 836). Cham: Springer. https://doi.org/10.1007/978-3-319-97885-7_6
10. Colao, V., Lopez, G., Marino, G. & Martin-Marquez, V. (2012). Equilibrium problems in Hadamard manifolds. J. Math. Anal. Appl., 388, pp. 61-77. https://doi.org/10.1016/j.jmaa.2011.11.001
11. Khatibzadeh, H. & Mohebbi, V. (2019). Monotone and pseudo-monotone equilibrium problems in Hadamard spaces. J. Aust. Math. Soc., pp. 1-23. https://doi.org/10.1017/S1446788719000041
12. Khatibzadeh, H. & Mohebbi, V. (2019). Approximating solutions of equilibrium problems in Hadamard spaces. Miskolc Math. Notes, 20, No. 1, pp. 281-297. https://doi.org/10.18514/MMN.2019.2361
13. Vedel, Ya. I., Semenov, V. V. & Chabak, L. M. (2020). A two-stage proximal algorithm for equilibrium problems in Hadamard spaces. Dopov. Nac. akad. nauk Ukr., No. 2, pp. 7-14. https://doi.org/10.15407/dopovidi2020.02.007
14. Denisov, S. V., Semenov, V. V. & Stetsyuk, P. I. (2019). Bregman extragradient method with monotone rule of step adjustment. Cybern. Syst. Anal., 55, Iss. 3, pp. 377-383. https://doi.org/10.1007/s10559-019-00144-5
15. Bacak, M. (2014). Convex analysis and optimization in Hadamard spaces. Berlin, Boston: De Gruyter