Email this article The Lipschitz condition of the metric projection and the convergence of gradient methods
- Authors: Balashov M.V.1
-
Affiliations:
- V. A. Trapeznikov Institute of Control Sciences of Russian Academy of Sciences
- Issue: Vol 215, No 4 (2024)
- Pages: 62-80
- Section: Articles
- URL: https://journals.rcsi.science/0368-8666/article/view/255289
- DOI: https://doi.org/10.4213/sm9982
- ID: 255289
Cite item
Open Access
Access granted
Subscription Access
Abstract
Рассмотрены разные опорные условия для замкнутого множества из вещественного гильбертова пространства $\mathcal H$ в точке границы множества. Указанные условия обеспечивают некоторое локальное условие Липшица метрического проектора точки на множество по точке. Также имеет место локальная липшицевость проектора в метрике Хаусдорфа как функции множества. Полученное условие Липшица применено для доказательства линейной сходимости ряда градиентных методов (метода проекции градиента, метода условного градиента) без предположения сильной выпуклости или даже выпуклости функции и без выпуклости множества. Функция при этом предполагается дифференцируемой с непрерывным по Липшицу градиентом.Библиография: 29 названий.
About the authors
Maxim Viktorovich Balashov
V. A. Trapeznikov Institute of Control Sciences of Russian Academy of Sciences
Email: balashov73@mail.ru
Scopus Author ID: 55947326500
ResearcherId: L-2315-2013
Doctor of physico-mathematical sciences, Associate professor
References
- R. R. Phelps, “Convex sets and nearest points”, Proc. Amer. Math. Soc., 8 (1957), 790–797
- T. Abatzoglou, “The metric projection on $C^2$ manifolds in Banach spaces”, J. Approx. Theory, 26:3 (1979), 204–211
- J.-Ph. Vial, “Strong and weak convexity of sets and functions”, Math. Oper. Res., 8:2 (1983), 231–259
- F. H. Clarke, R. J. Stern, P. R. Wolenski, “Proximal smoothness and the lower-$C^2$ property”, J. Convex Anal., 2:1-2 (1995), 117–144
- B. O. Björnestål, “Local Lipschitz continuity of the metric projection operator”, Approximation theory, Papers, VIth semester, Stefan Banach Internat. Math. Center, Warsaw, 1975, Banach Center Publ., 4, PWN–Polish Sci. Publ., Warsaw, 1979, 43–53
- J. W. Daniel, “The continuity of metric projections as functions of the data”, J. Approx. Theory, 12:3 (1974), 234–239
- Е. С. Половинкин, М. В. Балашов, Элементы выпуклого и сильно выпуклого анализа, 2-е изд., Физматлит, М., 2007, 438 с.
- В. И. Бердышев, “Непрерывность многозначного отображения, связанного с задачей минимизации функционала”, Изв. АН СССР. Сер. матем., 44:3 (1980), 483–509
- Г. Е. Иванов, “Точные оценки модулей непрерывности метрической проекции на слабо выпуклые множества”, Изв. РАН. Сер. матем., 79:4 (2015), 27–56
- Е. С. Левитин, Б. Т. Поляк, “Методы минимизации при наличии ограничений”, Ж. вычисл. матем. и матем. физ., 6:5 (1966), 787–823
- V. M. Veliov, “On the convexity of integrals of multivalued mappings: applications in control theory”, J. Optim. Theory Appl., 54:3 (1987), 541–563
- G. Braun, A. Carderera, C. W. Combettes, H. Hassani, A. Karbasi, A. Mokhtari, S. Pokutta, Conditional gradient methods
- М. В. Балашов, “Максимизации функции с непрерывным по Липшицу градиентом”, Фундамент. и прикл. матем., 18:5 (2013), 17–25
- M. V. Balashov, B. T. Polyak, A. A. Tremba, “Gradient projection and conditional gradient methods for constrained nonconvex minimization”, Numer. Funct. Anal. Optim., 41:7 (2020), 822–849
- А. В. Маринов, “О равномерных константах сильной единственности в чебышевских приближениях и основополагающих результатах Н. Г. Чеботарева”, Изв. РАН. Сер. матем., 75:3 (2011), 161–188
- Б. Т. Поляк, “Минимизация негладких функционалов”, Ж. вычисл. матем. и матем. физ., 9:3 (1969), 509–521
- D. Davis, D. Drusvyatskiy, K. J. MacPhee, C. Paquette, Subgradient methods for sharp weakly convex functions
- Xiao Li, Zhihui Zhu, A. Man-Cho So, J. D. Lee, Incremental methods for weakly convex optimization
- R. Schneider, A. Uschmajew, “Convergence results for projected line-search methods on varieties of low-rank matrices via Łojasiewicz inequality”, SIAM J. Optim., 25:1 (2015), 622–646
- P.-A. Absil, R. Mahony, R. Sepulchre, Optimization algorithms on matrix manifolds, Princeton Univ. Press, Princeton, NJ, 2008, xvi+224 pp.
- М. В. Балашов, “Метод проекции градиента для проксимально гладкого множества и функции с непрерывным по Липшицу градиентом”, Матем. сб., 211:4 (2020), 3–26
- М. В. Балашов, “Метод проекции градиента на матричных многообразиях”, Ж. вычисл. матем. и матем. физ., 60:9 (2020), 1453–1461
- 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
- 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
- М. В. Балашов, “Достаточные условия линейной сходимости одного алгоритма для нахождения метрической проекции точки на выпуклый компакт”, Матем. заметки, 113:5 (2023), 655–666
- Н. В. Ефимов, С. Б. Стечкин, “Аппроксимативные свойства множеств в линейных нормированных пространствах”: С. Б. Стечкин, Избранные труды, Физматлит, М., 1998, 270–281
- М. В. Балашов, К. З. Биглов, “Опорное условие сильной выпуклости и условие Липшица для метрической проекции”, Матем. заметки, 115:2 (2024), 197–207
- I. Necoara, Yu. Nesterov, F. Glineur, “Linear convergence of first order methods for non-strongly convex optimization”, Math. Program., 175:1-2(A) (2019), 69–107
- Y. Bello-Cruz, Guoyin Li, T. T. A. Nghia, “On the linear convergence of forward-backward splitting method: Part I – Convergence analysis”, J. Optim. Theory Appl., 188:2 (2021), 378–401
Supplementary files
