Известия Саратовского университета. Новая серия.

Серия Математика. Механика. Информатика

ISSN 1816-9791 (Print)
ISSN 2541-9005 (Online)


Для цитирования:

Balashov M. V. The Lezanski – Polyak – Lojasiewicz inequality and the convergence of the gradient projection algorithm [Балашов М. В. Неравенство Лежанского – Поляка – Лоясевича и сходимость метода проекции градиента] // Известия Саратовского университета. Новая серия. Серия : Математика. Механика. Информатика. 2023. Т. 23, вып. 1. С. 4-10. DOI: 10.18500/1816-9791-2023-23-1-4-10, EDN: ZSKZLA


Статья опубликована на условиях лицензии Creative Commons Attribution 4.0 International (CC-BY 4.0).
Опубликована онлайн: 
01.03.2023
Полный текст:
(downloads: 903)
Язык публикации: 
английский
Рубрика: 
Тип статьи: 
Научная статья
УДК: 
519.853.4
EDN: 
ZSKZLA

The Lezanski – Polyak – Lojasiewicz inequality and the convergence of the gradient projection algorithm
[Неравенство Лежанского – Поляка – Лоясевича и сходимость метода проекции градиента]

Авторы: 
Балашов Максим Викторович, Институт проблем управления РАН им. В. А. Трапезникова
Аннотация: 

Рассматривается неравенство Лежанского – Поляка – Лоясевича для вещественно-аналитической функции на вещественно-аналитическом компактном многообразии без края в конечномерном евклидовом пространстве. Это неравенство возникло независимо в 1963 г. в работах трех авторов: Лежанского и Лоясевича из Польши и Поляка из СССР. Неравенство оказалось очень полезным инструментом для исследования сходимости градиентных методов, первоначально в безусловной оптимизации, а в течение последних нескольких десятилетий и в задачах условной оптимизации. Оно применяется, главным образом,  для гладких в определенном смысле функций на гладких в определенном смысле многообразиях. Мы предлагаем вывод неравенства из условия ограничения ошибки степенного типа на компактном вещественно-аналитическом многообразии. В качестве приложения мы доказываем сходимость метода проекции градиента вещественно-аналитической функции на вещественно аналитическом многообразии без края. В отличие от известных результатов, наше доказательство дает явную зависимость погрешности через параметры задачи:  в первую очередь, через показатель в условии ограничения ошибки и константу проксимальной гладкости.  При этом мы существенно используем технический факт, что гладкое компактное многообразие без края есть проксимально гладкое множество.

Благодарности: 
Работа выполнена при поддержке Российского научного фонда (проект № 22-11-00042).
Список источников: 
  1. Lee J. M. Manifolds and differential geometry. Graduate Studies in Mathematics. Rhode Island, AMS Providence, 2009. Vol. 107. 671 p. https://doi.org/10.1090/gsm/107
  2. Lojasiewicz S. Sur le probleme de la division. Studia Mathematica, 1959, vol. 18, pp. 87–136. https://doi.org/10.4064/sm-18-1-87-136
  3. Balashov M. V., Polyak B. T., Tremba A. A. Gradient projection and conditional gradient methods for constrained nonconvex minimization. Numerical Functional Analysis and Optimization, 2020, vol. 41, iss. 7, pp. 822–849. https://doi.org/10.1080/01630563.2019.1704780
  4. Karimi H., Nutini J., Schmidt M. Linear convergence of gradient and proximal-gradient methods under the Polyak – Lojasiewicz condition. In: Frasconi P., Landwehr N., Manco G., Vreeken J. (eds.) Machine Learning and Knowledge Discovery in Databases. ECML PKDD 2016. Lecture Notes in Computer Science, vol. 9851. Cham, Springer, 2016, pp. 795–811. https://doi.org/10.1007/978-3-319-46128-1_50
  5. Schneider R., Uschmajew A. Convergence results for projected line-search methods on varieties of low-rank matricies via Lojasiewicz inequality. SIAM Journal on Optimization, 2015, vol. 25, iss. 1, pp. 622–646. https://doi.org/10.1137/140957822
  6. Merlet B., Nguyen T. N. Convergence to equilibrium for discretizations of gradient-like flows on Riemannian manifolds. Differential Integral Equations, 2013, vol. 26, iss. 5/6, pp. 571–602. https://doi.org/10.57262/die/1363266079
  7. Vial J.-Ph. Strong and weak convexity of sets and functions. Mathematics of Operations Research, 1983, vol. 8, iss. 2, pp. 231–259. https://doi.org/10.1287/moor.8.2.231
  8. Balashov M. V. The gradient projection algorithm for smooth sets and functions in nonconvex case. Set-Valued and Variational Analysis, 2021, vol. 29, pp. 341–360. https://doi.org/10.1007/s11228-020-00550-4
  9. Balashov M. V. Stability of minimization problems and the error bound condition. Set-Valued and Variational Analysis, 2022, vol. 30, pp. 1061–1076. https://doi.org/10.1007/s11228-022-00634-3
  10. Ivanov G. E. Slabo vypuklye mnozhestva i funktsii: teoriya i prilozhenie [Weakly Convex Sets and Functions: Theory and Application]. Moscow, Fizmatlit, 2006. 351 p. (in Russian).
  11. Balashov M. V., Kamalov R. A. The gradient projection method with Armijo’s step size on manifolds. Computational Mathematics and Mathematical Physics, 2021, vol. 61, iss. 1, pp. 1776–1786. https://doi.org/10.1134/S0965542521110038
  12. Adly S., Nacry F., Thibault L. Preservation of prox-regularity of sets with applications to constrained optimization. SIAM Journal on Optimization, 2016, vol. 26, iss. 1, pp. 448–473. https://doi.org/10.1137/15M1032739
  13. Polyak B. T. Introduction to Optimization. New York, Optimization Software, 1987. 464 p.
  14. Balashov M. V., Tremba A. A. Error bound conditions and convergence of optimization methods on smooth and proximally smooth manifolds. Optimization: A Journal of Mathematical Programming and Operations Research, 2020, vol. 71, iss. 3, pp. 711–735. https://doi.org/10.1080/02331934.2020.1812066
Поступила в редакцию: 
20.08.2022
Принята к публикации: 
27.10.2022
Опубликована: 
01.03.2023