F.S. Stonyakin. On the adaptive proximal method for a class of variational inequalities and related problems ... P. 185-197

For problems of unconstrained optimization, the concept of inexact oracle proposed by O. Devolder, F. Gleener and Yu. E. Nesterov is well known. We introduce an analog of the notion 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 proximal method for variational inequalities with an adaptive adjustment to the level of smoothness for a fairly wide class of problems. It is also possible to inexactly solve auxiliary problems at the iterations of the method. 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 bounds 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.

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

Received February 8, 2019

Revised May 7, 2019

Accepted May 13, 2019

Funding Agency: The theoretical research (the concept of a model of a function for variational inequalities and saddle point problems) was supported by the Russian Foundation for Basic Research (project no. 18-31-20005 mol-a-ved). The research of Remark 5 (numerical experiments for one variational inequality) was supported by the Russian Science Foundation (project no. 18-71-00048).

Fedor Sergeevich Stonyakin, Cand. Sci. (Phys.-Math.), V.I. Vernadsky Crimean Federal University, Simferopol, Republic of Crimea, 295007 Russia, e-mail: fedyor@mail.ru

REFERENCES

1.   Facchinei F., Pang J. S. Finite-dimensional variational inequality and complementarity problems, vols. 1 and 2. N Y, Springer-Verlag, 2003, vol. 1. 693 p. doi: 10.1007/b97543 ; vol. 2. 704 p. doi: 10.1007/b97544 

2.   Antipin A. S. Solution methods for variational inequalities with coupled constraints. Comput. Math. Math. Phys., 2000, vol. 40, no. 9, pp. 1239–1254.

3.   Antipin A. S., Jacimovic V., Jacimovic M. Dynamics and variational inequalities. Comput. Math. Math. Phys., 2017, vol. 57, no. 5, pp. 784–801. doi: 10.1134/S0965542517050013 

4.   Konnov I. V., Salahuddin R. A. Two-level iterative method for non-stationary mixed variational inequalities. Russian Math. (Iz. VUZ), 2017, vol. 61, no. 10, pp. 44–53. doi: 10.3103/S1066369X17100061 

5.   Bao T. Q., Khanh P. Q. Some algorithms for solving mixed variational inequalities. Acta Math. Vietnamica, 2006, vol. 31, no. 1, pp. 77–98.

6.   Chambolle A., Pock T. A first-order primal-dual algorithm for convex problems with applications to imaging. J. Math. Imag. Vis., 2011, vol. 40, no. 1, pp. 120–145. doi: 10.1007/s10851-010-0251-1 

7.   Guzman C., Nemirovski A. On lower complexity bounds for large-scale smooth convex optimization. J. Complexity, 2015, vol. 31, no. 1, pp. 1–14. doi: 10.1016/j.jco.2014.08.003 

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., 2004, vol. 15, no. 1, pp. 229–251. doi: 10.1137/S1052623403425629

9.   Melenchuk N. V. Metody i algoritmy dlya resheniya zadach matematicheskogo modelirovaniya na osnove variatsionnykh neravenstv [Methods and algorithms for solving problems of mathematical modeling based on variational inequalities]. Candidate Sci. (Phys.-Math.) Dissertation: 05.13.18, Omsk, 2011, 123 p.

10.   Nesterov Yu. Dual extrapolation and its application for solving variational inequalities and related problems. Math. Program., Ser. B., 2007, vol. 109, no. 2-3, pp. 319–344. doi: 10.1007/s10107-006-0034-z 

11.   Nesterov Yu., Scrimali L. Solving strongly monotone variational and quasi-variational inequalities. Discrete and Continuous Dynamical Systems. Ser. A., 2011, vol. 31, no. 4, pp. 1383–1396. doi: 10.3934/dcds.2011.31.1383 

12.   Nesterov Yu. E. Algoritmicheskaya vypuklaya optimizatsiya [Algorithmic convex optimization]. Doctor Sci. (Phys.-Math.) Dissertation. Moscow: Mosk. Phys.-Tech. Inst. (State University), 2013. 367 p.

13.   Korpelevich G. M. Extragradient method for finding saddle points and other problems. Ekonom. Mat. Metody, 1976, vol. 12, no. 4, pp. 747–756 (in Russian).

14.   Nesterov Yu. Universal gradient methods for convex optimization problems. Math. Program. Ser. A, 2015, vol. 152, no. 1-2, pp. 381–404. doi: 10.1007/s10107-014-0790-0 .

15.   Gasnikov A. V. Sovremennye chislennye metody optimizatsii. Metod universal’nogo gradientnogo spuska [Modern numerical optimization methods. The universal gradient descent method]. Moscow: MIPT Publ., 2018, 160 p.

16.   Gasnikov A. V., Dvurechensky P. E., Stonyakin F. S., Titov A. A. Adaptive proximal method for variational inequalities. Zh. Vychisl. Mat. Mat. Fiz., 2019, vol. 59, no. 5, pp. 889 – 894 (in Russian).

17.   Nemirovskii A. S., Yudin D. B. Problem complexity and method efficiency in optimization. Chichester etc.: John Wiley & Sons., 1983, 388 p. ISBN: 9780471103455 . Original Russian text published in Nemirovskii A.S., Yudin D.B. Slozhnost’ zadach i effektivnost’ metodov optimizatsii. Moscow: Nauka Publ., 1979, 384 p.

18.   Nemirovski A. Information-based complexity of convex programming [e-resource]. Technion, Fall Semester 1994/95 / The Israel Institute of Technology Faculty of Industrial Engineering & Management. 268 p. Available at: 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., 2014, vol. 146, no. 1-2, pp. 37–75. doi: 10.1007/s10107-013-0677-5 

20.   Antipin A. S. Equilibrium programming: Proximal methods. Comput. Math. Math. Phys., 1997, vol. 37, no. 11, pp. 1285–1296.

21.   Vedel’ Ya. I., Semenov V. V. New two-stage proximal algorithm for solving the problem of equilibrium. Zh. Vychisl. Mat. Mat. Fiz., 2015, no. 1 (118), pp. 15–23 (in Russian).

22.   Ben-Tal A., Nemirovski A. Lectures on modern convex optimization. Philadelphia, SIAM, 2001. 500 p.

23.   Mastroeni G. On auxiliary principle for equilibrium problems. In: Daniele P., Giannessi F., Maugeri A. (eds) Equilibrium Problems and Variational Models, Ser. Nonconvex Optim. Its Appl., vol. 68, Boston: Springer, 2003, pp. 289–298. doi: 10.1007/978-1-4613-0239-1_15 

Cite this article as: F.S.Stonyakin. On the adaptive proximal method for a class of variational inequalities and related problems, Trudy Instituta Matematiki i Mekhaniki URO RAN, 2019, vol. 25, no. 2, pp. 185–197.