The Lezanski – Polyak – Lojasiewicz inequality and the convergence of the gradient projection algorithm

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