The gradient projection algorithm for a proximally smooth set and a function with Lipschitz continuous gradient

Capa

Citar

Texto integral

Acesso aberto Acesso aberto
Acesso é fechado Acesso está concedido
Acesso é fechado Somente assinantes

Resumo

We consider the minimization problem for a nonconvex function with Lipschitz continuous gradient on a proximally smooth (possibly nonconvex) subset of a finite-dimensional Euclidean space. We introduce the error bound condition with exponent $\alpha\in(0,1]$ for the gradient mapping. Under this condition, it is shown that the standard gradient projection algorithm converges to a solution of the problem linearly or sublinearly, depending on the value of the exponent $\alpha$. This paper is theoretical. Bibliography: 23 titles.

Sobre autores

Maxim Balashov

V. A. Trapeznikov Institute of Control Sciences of Russian Academy of Sciences

Email: balashov73@mail.ru
Doctor of physico-mathematical sciences, Associate professor

Bibliografia

  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 с.

Arquivos suplementares

Arquivos suplementares
Ação
1. JATS XML
Baixar

Declaração de direitos autorais © Balashov M.V., 2020

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

 

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