On the Adaptive Proximal Method for a Class of Variational Inequalities and Related Problems

F. S. Stonyakin

Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 25 (2019) no. 2, pp. 185-197

Résumé

For problems of unconstrained optimization, the concept of inexact oracle proposed by O. Devolder, F. Glineur, and Yu.E. Nesterov is well known. We introduce an analog of the concept of inexact oracle (model of a function) for abstract equilibrium problems, variational inequalities, and saddle-point problems. This allows us to propose an analog of Nemirovskii's known mirror prox method for variational inequalities with an adaptive adjustment to the smoothness level for a fairly wide class of problems. The auxiliary problems at the iterations of the method can be solved with error. It is shown that the resulting errors do not accumulate during the operation of the method. Estimates of the convergence rate of the method are obtained, and its optimality from the viewpoint of the theory of lower oracle estimates is established. It is shown that the method is applicable to mixed variational inequalities and composite saddle-point problems. An example showing the possibility of an essential acceleration of the method as compared to the theoretical estimates due to the adaptivity of the stopping rule is given.

Détail

Keywords: inexact model of a function, variational inequality, saddle-point problem, abstract equilibrium problem, adaptive stopping rule.

Bibliographie

[1] Facchinei F., Pang J. S., Finite-dimensional variational inequality and complementarity problems, Vols 1 and 2, v. 1, Springer-Verlag, N Y, 2003, 693 pp. ; v. 2, 704 pp. | DOI | MR | DOI

[2] Antipin A. S., “Metody resheniya variatsionnykh neravenstv so svyazannymi ogranicheniyami”, Zhurn. vychisl. matematiki i mat. fiziki, 40:9 (2000), 1291–1307 | MR | Zbl

[3] Antipin A. S., Yachimovich V., Yachimovich M., “Dinamika i variatsionnye neravenstva”, Zhurn. vychisl. matematiki i mat. fiziki, 57:5 (2017), 783–800 | DOI | Zbl

[4] Konnov I. V., Salakhutdin R. A., “Dvukhurovnevyi iterativnyi metod dlya nestatsionarnykh smeshannykh variatsionnykh neravenstv”, Izv. vuzov. Matematika, 2017, no. 10, 50–61 | Zbl

[5] Bao T. Q., Khanh P. Q., “Some algorithms for solving mixed variational inequalities”, Acta Mathem. Vietnamica, 31:1 (2006), 77–98 | DOI | MR | Zbl

[6] Chambolle A., Pock T., “A first-order primal-dual algorithm for convex problems with applications to imaging”, J. Math. Imag. Vis., 40:120 (2011) | DOI | MR | Zbl

[7] Guzman C., Nemirovski A., “On lower complexity bounds for large-scale smooth convex optimization”, J. Complexity, 31:1 (2015), 1–14 | DOI | MR | Zbl

[8] Nemirovski A., “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. Optim., 15:1 (2004), 229–251 | DOI | MR | Zbl

[9] Melenchuk N. V., Metody i algoritmy dlya resheniya zadach matematicheskogo modelirovaniya na osnove variatsionnykh neravenstv, dis. $\dots$ kand. fiz.-mat. nauk, Omsk, 2011, 123 pp.

[10] Nesterov Yu., “Dual extrapolation and its application for solving variational inequalities and related problems”, Math. Program. Ser. B, 2007, 319–344 | DOI | MR | Zbl

[11] Nesterov Yu., Scrimali L., “Solving strongly monotone variational and quasi-variational inequalities”, Discr. Contin. Dynam. Syst. Ser. A., 31:4 (2011), 1383–1396 | DOI | MR | Zbl

[12] Nesterov Yu. E., Algoritmicheskaya vypuklaya optimizatsiya, dis. $\dots$ d-r fiz.-mat. nauk, Mosk. fiz.-tekhn. in-t, M., 2013, 367 pp.

[13] Korpelevich G. M., “Ekstragradientnyi metod dlya otyskaniya sedlovykh tochek i drugikh zadach”, Ekonomika i mat. metody, 12:4 (1976), 747–756 | MR | Zbl

[14] Nesterov Yu., “Universal gradient methods for convex optimization problems”, Math. Program. Ser. A, 152:1-2 (2015), 381–404 | DOI | MR | Zbl

[15] Gasnikov A. V., Sovremennye chislennye metody optimizatsii. Metod universalnogo gradientnogo spuska, ucheb. posobie, Izd-vo MFTI, Moskva, 2018, 160 pp.

[16] Gasnikov A. V., Dvurechenckii P. E., Stonyakin F. S., Titov A. A., “Adaptivnyi proksimalnyi metod dlya variatsionnykh neravenstv”, Zhurn. vychisl. matematiki i mat. fiziki, 59:5 (2019), 889–894 | DOI

[17] Nemirovskii A. S., Yudin D. B., Slozhnost zadach i effektivnost metodov optimizatsii, Nauka, Moskva, 1979, 384 pp.

[18] Nemirovski A., Information-based complexity of convex programming, Technion, Fall Semester 1994/95, The Israel institute of technology faculty of industrial engineering management, 268 pp. https://www2.isye.gatech.edu/nemirovs/Lect_EMCO.pdf

[19] Devolder O., Glineur F., Nesterov Yu., “First-order methods of smooth convex optimization with inexact oracle”, Math. Progr., 146:1-2 (2014), 37–75 | DOI | MR | Zbl

[20] Antipin A. S., “Ravnovesnoe programmirovanie: proksimalnye metody”, Zhurn. vychisl. matematiki i mat. fiziki, 37:11 (1997), 1327–1339 | MR | Zbl

[21] Vedel Ya. I., Semenov V. V., “Novyi dvukhetapnyi proksimalnyi algoritm dlya resheniya zadachi o ravnovesii”, Zhurn. vychisl. i prikl. matematiki, 118:1 (2015), 15–23 | MR

[22] Ben-Tal A., Nemirovski A., Lectures on modern convex optimization, SIAM, Philadelphia, 2001, 500 pp. | MR | Zbl

[23] Mastroeni G., “On auxiliary principle for equilibrium problems”, Publicatione del Departimento di Mathematica Dell'Universita di Pisa, 3 (2000), 1244–1258