Метод проекции градиента для проксимально гладкого множества и функции с непрерывным по Липшицу градиентом

Обложка

Цитировать

Полный текст

Открытый доступ Открытый доступ
Доступ закрыт Доступ предоставлен
Доступ закрыт Только для подписчиков

Аннотация

Рассматривается задача минимизации невыпуклой функции с непрерывным по Липшицу градиентом на проксимально гладком подмножестве (которое может быть невыпуклым) в конечномерном евклидовом пространстве. Для градиентного отображения вводится условие ограничения ошибки (error bound condition) с показателем $\alpha\in (0,1]$. В случае выполнения этого условия доказывается, что стандартный метод проекции градиента сходится к решению задачи с линейной или сублинейной скоростью в зависимости от показателя $\alpha$. Работа носит теоретический характер. Библиография: 23 названия.

Об авторах

Максим Викторович Балашов

Институт проблем управления им. В. А. Трапезникова РАН

Email: balashov73@mail.ru
доктор физико-математических наук, доцент

Список литературы

  1. A. A. Goldstein, “Convex programming in Hilbert space”, Bull. Amer. Math. Soc., 70:5 (1964), 709–710
  2. Е. С. Левитин, Б. Т. Поляк, “Методы минимизации при наличии ограничений”, Ж. вычисл. матем. и матем. физ., 6:5 (1966), 787–823
  3. Б. Т. Поляк, “Градиентные методы минимизации функционалов”, Ж. вычисл. матем. и матем. физ., 3:4 (1963), 643–653
  4. Б. Т. Поляк, Введение в оптимизацию, Наука, М., 1983, 384 с.
  5. Yu. Nesterov, Introductory lectures on convex optimization. A basic course, Appl. Optim., 87, Kluwer Acad. Publ., Boston, MA, 2004, xviii+236 pp.
  6. H. Karimi, J. Nutini, M. Schmidt, “Linear convergence of gradient and proximal-gradient methods under the Polyak–Łojasiewicz condition”, Machine learning and knowledge discovery in databases. ECML PKDD 2016, Lecture Notes in Comput. Sci., 9851, Springer, Cham, 2016, 795–811
  7. Б. Т. Поляк, “Градиентные методы минимизации функционалов”, Ж. вычисл. матем. и матем. физ., 3:4 (1963), 643–653
  8. S. Lojasiewicz, “Une propriete topologique des sous-ensembles analitiques reels”, Les equations aux derivees partielles (Paris, 1962), Ed. du CNRS, Paris, 1963, 87–89
  9. Zhi-Quan Luo, “New error bounds and their applications to convergence analysis of iterative algorithms”, Error bounds in mathematical programming (Kowloon, 1998), Math. Program., 88:2, Ser. B (2000), 341–355
  10. J. Bolte, Trong Phong Nguyen, J. Peypouquet, B. W. Suter, “From error bounds to the complexity of first-order descent methods for convex functions”, Math. Program., 165:2, Ser. A (2017), 471–507
  11. D. Drusvyatskiy, A. S. Lewis, “Error bounds, quadratic growth, and linear convergence of proximal methods”, Math. Oper. Res., 43:3 (2018), 919–948
  12. Tianbao Yang, Qihang Lin, “RSG: Beating Subgradient Method without Smoothness and Strong Convexity”, J. Mach. Learn. Res., 19 (2018), 6, 33 pp.
  13. M. V. Balashov, M. O. Golubev, “About the Lipschitz property of the metric projection in the Hilbert space”, J. Math. Anal. Appl., 394:2 (2012), 545–551
  14. М. В. Балашов, “Максимизации функции с непрерывным по Липшицу градиентом”, Фундамент. и прикл. матем., 18:5 (2013), 17–25
  15. M. V. Balashov, B. T. Polyak, A. A. Tremba, “Gradient projection and conditional gradient methods for constrained nonconvex minimization”, Numer. Funct. Anal. Optim., Publ. online: 2020
  16. J.-Ph. Vial, “Strong and weak convexity of sets and functions”, Math. Oper. Res., 8:2 (1983), 231–259
  17. F. H. Clarke, R. J. Stern, P. R. Wolenski, “Proximal smoothness and lower-$C^{2}$ property”, J. Convex Anal., 2:1-2 (1995), 117–144
  18. М. В. Балашов, Г. Е. Иванов, “Слабо выпуклые и проксимально гладкие множества в банаховых пространствах”, Изв. РАН. Сер. матем., 73:3 (2009), 23–66
  19. R. A. Poliquin, R. T. Rockafellar, L. Thibault, “Local differentiability of distance functions”, Trans. Amer. Math. Soc., 352:11 (2000), 5231–5249
  20. M. V. Balashov, “About the gradient projection algorithm for a strongly convex function and a proximally smooth set”, J. Convex Anal., 24:2 (2017), 493–500
  21. A. D. Ioffe, “Metric regularity – a survey. Part 1. Theory”, J. Aust. Math. Soc., 101:2 (2016), 188–243
  22. M. Bounkhel, L. Thibault, “On various notions of regularity of sets in nonsmooth analysis”, Nonlinear Anal., 48:2, Ser. A: Theory Methods (2002), 223–246
  23. Е. С. Половинкин, Многозначный анализ и дифференциальные включения, Физматлит, М., 2015, 524 с.

Дополнительные файлы

Доп. файлы
Действие
1. JATS XML
Скачать

© Балашов М.В., 2020

Согласие на обработку персональных данных

 

Используя сайт https://journals.rcsi.science, я (далее – «Пользователь» или «Субъект персональных данных») даю согласие на обработку персональных данных на этом сайте (текст Согласия) и на обработку персональных данных с помощью сервиса «Яндекс.Метрика» (текст Согласия).