Ф.С. Стонякин. Об адаптивном проксимальном методе для некоторого класса вариационных неравенств и смежных задач ... C. 185-197

УДК 519.85

MSC: 90C33, 90С06, 65K15

DOI: 10.21538/0134-4889-2019-25-2-185-197

Полный текст статьи (Full text)

Теоретические исследования, связанные с концепцией модели функции для вариационных неравенств и седловых задач выполнены при поддержке Российского фонда фундаментальных исследований, грант 18-31-20005 мол-а-вед. Замечание 5 (численные эксперименты для одного вариационного неравенства) выполнены при поддержке Российского научного фонда, проект 18-71-00048.

Для задач безусловной оптимизации хорошо известна концепция неточного оракула, предложенная О. Деволдером, Ф. Глинером и Ю. Е. Нестеровым. В настоящей работе введен аналог понятия неточного оракула (модели функции) для абстрактных задач равновесия, вариационных неравенств и седловых задач. Это позволило предложить аналог известного проксимального метода А. С. Немировского для вариационных неравенств с адаптивной настройкой на уровень гладкости для достаточно широкого класса задач. При этом предусмотрена возможность неточного решения вспомогательных задач проектирования на итерациях метода. Показано, что возникающие погрешности не накапливаются в ходе работы метода. Получены оценки скорости сходимости предложенного метода. Обоснована оптимальность метода с точки зрения теории нижних оракульных оценок. Показано, что предложенный метод применим к смешанным вариационным неравенствам и композитным седловым задачам. Приведен пример, демонстрирующий возможность существенного ускорения метода по сравнению с теоретическими оценками за счет адаптивности критерия остановки.

Ключевые слова: неточная модель функции, вариационное неравенство, седловая задача, абстрактная задача равновесия, адаптивный критерий остановки

СПИСОК ЛИТЕРАТУРЫ

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.   Антипин А. С. Методы решения вариационных неравенств со связанными ограничениями // Журн. вычисл. математики и мат. физики. 2000. Т. 40, № 9. С. 1291–1307.

3.   Антипин А. С., Ячимович В., Ячимович М. Динамика и вариационные неравенства // Журн. вычисл. математики и мат. физики. 2017. Т. 57, № 5. С. 783–800. doi: 10.7868/S0044466917050015 

4.   Коннов И. В., Салахутдин Р. А. Двухуровневый итеративный метод для нестационарных смешанных вариационных неравенств // Изв. вузов. Математика. 2017. № 10. C. 50–61.

5.   Bao T. Q., Khanh P. Q. Some algorithms for solving mixed variational inequalities // Acta Mathem. Vietnamica. 2006. Vol. 31, no. 1. P. 77–98. doi: 10.1016/j.jco.2014.08.003 

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. 120. 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. P. 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. P. 229–251. doi: 10.1137/S1052623403425629

9.   Меленьчук Н. В. Методы и алгоритмы для решения задач математического моделирования на основе вариационных неравенств: дис. …канд. физ.-мат. наук. Омск, 2011. 123 c.

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

11.   Nesterov Yu., Scrimali L. Solving strongly monotone variational and quasi-variational inequalities // Discr. Contin. Dynam. Syst. Ser. A. 2011. Vol. 31, no. 4. P. 1383–1396. doi: 10.3934/dcds.2011.31.1383 

12.   Нестеров Ю. Е. Алгоритмическая выпуклая оптимизация: дис. …д-р физ.-мат. наук. М.: Моск. физ.-техн. ин-т. 2013. 367 с.

13.   Корпелевич Г. М. Экстраградиентный метод для отыскания седловых точек и других задач // Экономика и мат. методы. 1976. Т. 12, № 4. С. 747–756.

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

15.   Гасников А. В. Современные численные методы оптимизации. Метод универсального градиентного спуска: учеб. пособие. Москва: Изд-во МФТИ, 2018. 160 c.

16.   Гасников А. В., Двуреченcкий П. Е., Стонякин Ф. С., Титов А. А. Адаптивный проксимальный метод для вариационных неравенств // Журн. вычисл. математики и мат. физики. 2019. Т. 59, № 5. С. 889–894. doi: 10.1134/S0965542519050075 

17.   Немировский А. С., Юдин Д. Б. Сложность задач и эффективность методов оптимизации // Москва: Наука. 1979. 384 с.

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. URL: 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. P. 37–75. doi: 10.1007/s10107-013-0677-5 

20.   Антипин А. С. Равновесное программирование: проксимальные методы // Журн. вычисл. математики и мат. физики. 1997. Т. 37, № 11. C. 1327–1339.

21.   Ведель Я. И., Семенов В. В. Новый двухэтапный проксимальный алгоритм для решения задачи о равновесии // Журн. вычисл. и прикл. математики. 2015. Т. 118, № 1. С. 15–23.

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 // Publicatione del Departimento di Mathematica Dell’Universita di Pisa. 2000. Vol. 3. P. 1244–1258.

Поступила 8.02.2019

После доработки 7.05.2019

Принята к публикации 13.05.2019

Стонякин Федор Сергеевич
канд. физ.-мат. наук, доцент
Крымский федеральный университет им. В.И.Вернадского
г. Симферополь
e-mail: fedyor@mail.ru

Ссылка на статью: Ф.С. Стонякин. Об адаптивном проксимальном методе для некоторого класса вариационных неравенств и смежных задач // Тр. Ин-та математики и механики УрО РАН. 2019. Т. 25, № 2. С. 185-197.

English

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

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.

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.

[References -> on the "English" button bottom right]