Журнал вычислительной математики и математической физики, 2020, T. 60, № 9, стр. 1453-1461

1.1. Введение

Метод проекции градиента (МПГ) (известный также как проекционно-проксимальный метод и др.) для решения задачи

был предложен в [1], [2]. Если функция в (1) сильно выпуклая с непрерывным по Липшицу градиентом и множество выпукло и замкнуто, то МПГ сходится со скоростью геометрической прогрессии (или линейной скоростью). МПГ доказал свою эффективность для решения различных экстремальных задач [2], [3].

Примером актуальной невыпуклой задачи (1) является задача минимизации гладкой функции $f$ на некотором матричном многообразии $A$ без края. Например, $A$ может быть многообразием Штифеля или Грассмана [4].

В случае, если множество $A$ в задаче (1) является гладким многообразием, традиционно используются варианты метода проекции градиента с шагами, связанными с локальными геодезическими на многообразии [5]–[9]. Метод Ньютона также находит применение [4], [6] для решения упомянутой задачи, главным образом с квадратичными функциями или ограничениями. Однако метод Ньютона сходится в общем случае локально и существует очень немного работ с явными оценками для его области сходимости в случае невыпуклой задачи (1). Последнее верно и для МПГ.

В данной статье мы планируем сформулировать МПГ для задачи минимизации гладкой невыпуклой в общем случае функции на вещественном многообразии Штифеля или Грассмана. Ключевым в работе является тот факт, что вещественное многобразие Штифеля есть проксимально гладкое множество с константой проксимальной гладкости 1, а вещественное многообразие Грассмана также проксимально гладкое множество с константой $1{\text{/}}\sqrt 2 $. Заметим, что в силу соображений компактности любое компактное гладкое многообразие без края является проксимально гладким. Таким образом, речь идет о нахождении наилучшей (т.е. наибольшей) константы.

Кроме того, в теоремах 2 и 4 работы сформулированы достаточные условия сходимости МПГ с линейной скоростью на многообразиях Штифеля и Грассмана соответственно.

В отличие от упомянутых выше работ, свойства проксимально гладких множеств позволяют предъявить некоторый вариант МПГ с простой и явной оценкой скорости сходимости. Кроме того, наши результаты не зависят от геодезических на многообразиях. Это является еще одним преимуществом предложенного подхода. За это мы платим погружением задачи (1) в евклидово пространство большей (по сравнению с размерностью многообразия) размерности.

1.2. Основные обозначения

Обозначим евклидово пространство размерности $n$ через ${{\mathbb{R}}^{n}}$ и скалярное произведение $( \cdot , \cdot )$. Определим ${{B}_{R}}(a) = \{ x \in {{\mathbb{R}}^{n}}\,|\,\left\| {x - a} \right\| \leqslant R\} $, $a \in {{\mathbb{R}}^{n}}$, $R > 0$. Функция $f:{{\mathbb{R}}^{n}} \to \mathbb{R}$ называется сильно выпуклой с константой $\varkappa > 0$, если функция $f(x) - \tfrac{\varkappa }{2}{{\left\| x \right\|}^{2}}$ выпуклая. Мы будем говорить, что функция $f$ гладкая, если ее градиент Фреше $f{\kern 1pt} {\text{'}}$ непрерывен по Липшицу с константой ${{L}_{1}}$. Для функции $f:{{\mathbb{R}}^{n}} \to \mathbb{R}$ и $\beta \in \mathbb{R}$ определим нижнее множество уровня ${{\mathcal{L}}_{f}}(\beta ) = \{ x \in {{\mathbb{R}}^{n}}\,|\,f(x) \leqslant \beta \} $. Определим функцию расстояния ${{\varrho }_{A}}(x) = \mathop {inf}\limits_{a \in A} \left\| {x - a} \right\|$. Метрическая проекция точки $x \in {{\mathbb{R}}^{n}}$ на множество $A \subset {{\mathbb{R}}^{n}}$ есть

Замкнутое множество $A \subset {{\mathbb{R}}^{n}}$ называется проксимально гладким (или прокс-регулярным, слабо выпуклым) с константой $R$, если функция расстояния ${{\varrho }_{A}}(x)$ непрерывно дифференцируема на множестве ${{U}_{A}}(R) = \{ x \in {{\mathbb{R}}^{n}}\,|\,0 < {{\varrho }_{A}}(x) < R\} $. Свойства таких множеств рассматривались разными авторами [10], [11]. Мы хотим подчеркнуть, что в нашей работе проксимально гладкие множества по определению замкнуты. Для проксимально гладкого множества $A$ и точки $x \in A$ обозначим через $N(A,x)$ конус проксимальных нормалей Эквивалентным свойством для проксимальной гладкости замкнутого множества $A$ с константой $R$ является опорный принцип [10], [11]: для любой точки $x \in \partial A$ и всякого единичного вектора нормали $p(x) \in N(A,x)$ мы имеем $A \cap {\text{int}}\;{{B}_{R}}(x + Rp(x)) = \not {0}$. В конечномерном пространстве ${{\mathbb{R}}^{n}}$ последнее эквивалентно единственности метрической проекции ${{P}_{A}}x$ для каждой точки $x \in {{U}_{A}}(R)$, так как одноточечная метрическая проекция в конечномерном пространстве непрерывна [12, Ch. 3, § 1, Proposition 23].

Для проксимально гладкого множества $A \subset {{\mathbb{R}}^{n}}$ с константой $R$ и любых точек ${{x}_{1}},{{x}_{2}} \in A \cup {{U}_{A}}(r)$, $r < R$, для проекций ${{a}_{i}} = {{P}_{A}}{{x}_{i}}$ мы имеем оценку (см. [11])

Скажем, что $x \in A$ является стационарной точкой функции $f$ на проксимально гладком множестве $A \subset {{\mathbb{R}}^{n}}$, если существует число $t > 0$ со свойством ${{P}_{A}}(x - tf{\kern 1pt} {\text{'}}(x)) = x$. Последнее эквивалентно включению $f{\kern 1pt} {\text{'}}(x) \in - N(A,x)$. Данное условие является необходимым условием экстремума с проксимально гладким множеством [13, Appendix 5.1].

Пусть ${{I}_{k}} \in {{\mathbb{R}}^{{k \times k}}}$ – единичная матрица и $O(k)$ есть множество ортогональных матриц размера $k \times k$. Определим скалярное произведение $(X,Y) = {\text{tr}}{{X}^{{\text{т}}}}Y$ для матриц $X,Y \in {{\mathbb{R}}^{{n \times k}}}$. Нормой Фробениуса матрицы $X \in {{\mathbb{R}}^{{n \times k}}}$ называется ${{\left\| X \right\|}_{F}} = \sqrt {\operatorname{tr} {{X}^{{\text{т}}}}X} $. Далее мы будем считать, что $\left\| X \right\| = {{\left\| X \right\|}_{F}}$ для всякой матрицы $X$. Обозначим через ${{S}_{{n,k}}}$ вещественное многообразие Штифеля с натуральными параметрами $n \geqslant k$, т.е. ${{S}_{{n,k}}} = \{ X \in {{\mathbb{R}}^{{n \times k}}}\,|\,{{X}^{{\text{т}}}}X = {{I}_{k}}\} $. Очевидно, что ${{S}_{{n,k}}}$ вложено в пространство ${{\mathbb{R}}^{{n \times k}}}$ матриц с фробениусовой нормой. Обозначим через ${{G}_{{n,k}}}$ вещественное многообразие Грассмана с натуральными параметрами $n \geqslant k$, т.е. множество всех $k$-мерных линейных подпространств в ${{\mathbb{R}}^{n}}$. Известно [14], что ${{G}_{{n,k}}}$ может быть вложено (в определенном смысле изометрично) в евклидово пространство симметричных $n \times n$ матриц ${\text{Sym}}(n)$ размерности $\tfrac{1}{2}n(n + 1)$ с нормой $\tfrac{1}{{\sqrt 2 }}{{\left\| {\, \cdot \,} \right\|}_{F}}$. Следуя [14], мы будем рассматривать указанную реализацию ${{G}_{{n,k}}}$ вида $\{ X{{X}^{{\text{т}}}}\,|\,X \in {{S}_{{n,k}}}\} $ с нормой ${{\left\| {\, \cdot \,} \right\|}_{F}}$. Заметим, что $X{{X}^{{\text{т}}}}$ есть метрический проектор на подпространство ${\text{lin}}\left\{ {{{X}_{1}},\; \ldots ,\;{{X}_{k}}} \right\}$, где ${{X}_{i}}$ есть $i$-й столбец матрицы $X \in {{S}_{{n,k}}}$.

Легко видеть, что для всякой матрицы $X \in {{S}_{{n,k}}}$ имеем

$\left\| {X{{X}^{{\text{т}}}} - \tfrac{k}{n}{{I}_{n}}} \right\| = \sqrt {\tfrac{{k(n - k)}}{n}} $.

Таким образом, константа проксимальной гладкости для ${{G}_{{n,k}}}$ не более чем $\sqrt {\tfrac{{k(n - k)}}{n}} $.

Предложение 1. Для всякой матрицы $X \in {{\mathbb{R}}^{{n \times k}}}$ и $Q \in O(n)$ ($Q \in O(k)$) имеем $\left\| {QX} \right\| = \left\| X \right\|$ ($\left\| {XQ} \right\| = \left\| X \right\|$).

2.1. Основная теорема о сходимости МПГ в невыпуклом случае

Определение 1. Предположим, что $f:{{\mathbb{R}}^{n}} \to \mathbb{R}$ – дифференцируемая функция, $A \subset {{\mathbb{R}}^{n}}$ – замкнутое подмножество и $\Omega \subset A$, $\Omega \ne \not {0}$, есть множество решений для (1). Будем говорить, что условие Restricted Secant Inequality (RSI) выполняется для функции $f$ на множестве $A$, если существует такое число $\mu > 0$, что для любого $x \in A$ и любого ${{x}_{0}} \in {{P}_{\Omega }}x$ выполняется неравенство

Условие RSI хорошо известно в безусловной оптимизации [15]. Отметим, что указанное свойство выполнено для всякой сильно выпуклой функции с константой сильной выпуклости $\mu $ [15].

Теорема 1. Пусть $A \subset {{\mathbb{R}}^{n}}$ – проксимально гладкое с константой $R > 0$ множество. Предположим, что функция $f:{{\mathbb{R}}^{n}} \to \mathbb{R}$ удовлетворяет условию RSI на множестве $A$ с константой $\mu > 0$, и $f$ — гладкая функция с константой ${{L}_{1}} > 0$. Положим $L = \mathop {sup}\limits_{x \in A \cap {{\mathcal{L}}_{f}}(\beta )} \left\| {f{\kern 1pt} {\text{'}}(x)} \right\|$ для некоторого $\beta \in \mathbb{R}$. Допустим, что $\tfrac{L}{\mu } < R$ и множество решений $\Omega $ в (1) непусто. Определим

${{t}_{0}} = \frac{{\mu - \tfrac{L}{R}}}{{L_{1}^{2} - \tfrac{{\mu L}}{R}}}$.

Тогда для любой начальной точки ${{x}_{0}} \in A \cap {{\mathcal{L}}_{f}}(\beta )$ и всякого $t \in (0,{{t}_{0}}]$ итерационный процесс ${{x}_{{k + 1}}} = {{P}_{A}}\left( {{{x}_{k}} - tf{\kern 1pt} {\text{'}}({{x}_{k}})} \right)$ сходится к решению задачи (1) с линейной скоростью ${{\varrho }_{\Omega }}({{x}_{k}}) \leqslant {{q}^{k}}(t){{\varrho }_{\Omega }}({{x}_{0}})$, причем $\left\| {{{x}_{{k + 1}}} - {{x}_{k}}} \right\| \leqslant {{q}^{k}}(t)(1 + q(t)){{\varrho }_{\Omega }}({{x}_{0}})$,

Последовательность ${\text{\{ }}f({{x}_{k}}){\text{\} }}$ нестрого монотонно убывает.

Доказательство. Пусть $x_{k}^{0} \in \Omega $ такая точка, что $\left\| {{{x}_{k}} - x_{k}^{0}} \right\| = {{\varrho }_{\Omega }}({{x}_{k}})$. Используя включения ${{x}_{k}} - tf{\kern 1pt} {\text{'}}({{x}_{k}}) \in {{U}_{A}}(R)$, $x_{k}^{0} - tf{\kern 1pt} {\text{'}}(x_{k}^{0}) \in {{U}_{A}}(R)$ (заметим, что $t < \tfrac{R}{L}$) имеем в силу условия Липшица для метрической проекции (2)

и в силу условия (RSI) находим Таким образом, мы получаем оценку Используя неравенство треугольника и формулу (3), $\left\| {{{x}_{{k + 1}}} - x_{k}^{0}} \right\| \leqslant q(t)\left\| {{{x}_{k}} - x_{k}^{0}} \right\|$, мы получаем, что Следовательно, ${\text{\{ }}{{x}_{k}}{\text{\} }}$ есть последовательность Коши, которая сходится к некоторой точке ${{x}_{ * }} \in \Omega $.

Из равенства $\left\| {{{x}_{{k + 1}}} - {{x}_{k}} + tf{\kern 1pt} {\text{'}}({{x}_{k}})} \right\| = {{\varrho }_{A}}({{x}_{k}} - tf{\kern 1pt} {\text{'}}({{x}_{k}}))$ и оценки $t \leqslant \tfrac{1}{{{{L}_{1}}}}$ находим

Используя условие Липшица для $f{\kern 1pt} '$, получаем, что и ${{x}_{{k + 1}}} \in A \cap {{\mathcal{L}}_{f}}(\beta )$. Таким образом, по индукции, ${\text{\{ }}f({{x}_{k}}){\text{\} }}$ монотонно не возрастает и ${{x}_{k}} \in A \cap {{\mathcal{L}}_{f}}(\beta )$ для всех $k$. Теорема доказана.

Теорема 1 была доказана для случая сильно выпуклой функции в [16]. Включение $q(t) \in (0,1)$ для всех $t \in (0,{{t}_{0}}]$ также обосновано в указанной статье.

Если функция $f$ непрерывна по Липшицу на множестве $A$ с константой Липшица $L$, то

Пусть $A$ – гладкое многообразие без края и ${{T}_{x}}$ – касательное подпространство к $A$ в точке $x \in A$. В этом случае МПГ с промежуточной фазой проектирования на касательное подпространство ${{T}_{{{{x}_{k}}}}}$: ${{x}_{0}} \in A$, ${{z}_{k}} = {{P}_{{{{T}_{{{{x}_{k}}}}}}}}({{x}_{k}} - {{t}_{k}}f{\kern 1pt} {\text{'}}({{x}_{k}}))$, ${{t}_{k}} > 0$, ${{x}_{{k + 1}}} = {{P}_{A}}{{z}_{k}}$, см. [13], в некоторых случаях может быть вычислительно экономичнее, чем алгоритм с прямым проектированием на множество $A$. Например, это выгоднее для матриц малого ранга [17, § 2.3]. С другой стороны, в этом случае мы должны вычислять проекцию ${{z}_{k}}$ точки на подпространство ${{T}_{{{{x}_{k}}}}}$, и это должно приниматься во внимание.

Пример 1. Рассмотрим дифференцируемую функцию $f$ с не равным нулю градиентом $\left\| {f{\kern 1pt} {\text{'}}(x)} \right\|$ на множестве $A$: существует $l > 0$ такое, что $\left\| {f{\kern 1pt} {\text{'}}(x)} \right\| \geqslant l$ для всех $x \in A$. Пусть $\beta \in \mathbb{R}$. Предположим также, что $f$ сильно квазивыпукла с константой $r > 0$ на множестве ${{\mathcal{L}}_{f}}(\beta )$, т.е. для всякого $\alpha \leqslant \beta $ множество уровня ${{\mathcal{L}}_{f}}(\alpha )$ может быть представлено как пересечение замкнутых шаров радиуса $r$ (либо пусто). Допустим также, что множество $A$ есть гладкое и проксимально гладкое с константой $R$ многообразие и $R > \tfrac{{rL}}{l}$. Тогда функция $f$ удовлетворяет условию RSI на множестве $A \cap {{\mathcal{L}}_{f}}(\beta )$ с константой $\mu = \tfrac{1}{2}\left( {\tfrac{l}{r} - \tfrac{L}{R}} \right)$.

Рассмотрим точку $x \in A \cap {{\mathcal{L}}_{f}}(\beta )$ и ${{x}_{0}} \in {{P}_{\Omega }}x$. Тогда в силу опорного принципа для сильно выпуклых множеств [10] имеем

и Из включения $ \pm f{\kern 1pt} {\text{'}}({{x}_{0}}) \in N(A,{{x}_{0}})$ ($A$ – гладкое многообразие) мы имеем в силу опорного принципа для проксимально гладких множеств, что и, следовательно, Таким образом, для всякой точки $x \in A \cap {{\mathcal{L}}_{f}}(\beta )$ имеем

Условие $\tfrac{L}{\mu } < R$ существенно в теореме 1.

Пример 2. Рассмотрим в евклидовой плоскости ${{\mathbb{R}}^{2}}$ функцию $f(x,y) = {{x}^{2}} + {{\left( {y - \tfrac{1}{2}} \right)}^{2}}$ и множество $S = {\text{\{ }}{{x}^{2}} - y = 0{\text{\} }}$. Функция $f$ сильно выпукла с константой $\mu = 2$ и непрерывна по Липшицу в окрестности начала координат с константой $L \geqslant 1$. Минимальный радиус кривизны параболы $S$ равен $\tfrac{1}{2}$ в точке $(0,0)$. Следовательно, $S$ проксимально гладкое множество с константой $R = \tfrac{1}{2}$. Таким образом, условие $\tfrac{L}{\mu } < R$ нарушено.

Выберем начальную точку МПГ ${{a}_{0}} = (\tau ,{{\tau }^{2}})$, где $\tau > 0$. Рассмотрим две функции: ${{y}_{1}} = {{x}^{2}}$ и ${{x}^{2}} + {{\left( {{{y}_{2}} - \tfrac{1}{2}} \right)}^{2}} = {{\tau }^{2}} + {{\left( {{{\tau }^{2}} - \tfrac{1}{2}} \right)}^{2}}$. Тогда $y_{1}^{'} = y_{1}^{'}(\tau ) = 2\tau $,

Имеем $y_{2}^{'} - y_{1}^{'} \sim 4{{\tau }^{3}}$, $\tau \to + 0$. Последнее означает, что угол $\varphi $ между касательными к графикам $y = {{y}_{1}}$ и $y = {{y}_{2}}$ в точке $(\tau ,{{\tau }^{2}})$ равен $\varphi \sim 4{{\tau }^{3}}$, $\tau \to + 0$. Пусть ${{n}_{0}}$ – единичная нормаль к параболе $y = {{x}^{2}}$ в точке ${{a}_{0}}$ с условием $({{n}_{0}},{{e}_{2}}) > 0$, ${{e}_{2}} = (0,1)$. Для достаточно малых чисел $t > 0$ и для точки ${{a}_{1}} = {{P}_{S}}({{a}_{0}} - tf{\kern 1pt} {\text{'}}({{a}_{0}}))$ получаем, что ${{\varrho }_{S}}({{a}_{1}}) \leqslant t\left\| {f{\kern 1pt} {\text{'}}({{a}_{0}})} \right\| < \tfrac{1}{4}$. Используя (2), получаем Таким образом, на $k$-м шаге точка ${{a}_{k}}$ имеет абсциссу больше ${{\tau }_{k}}$, где ${{\tau }_{0}} = \tau $, ${{\tau }_{k}} = {{\tau }_{{k - 1}}} - 8t\tau _{{k - 1}}^{3}$. Последовательность ${\text{\{ }}{{\tau }_{k}}{\text{\} }}$ имеет асимптотику ${{\tau }_{k}} \asymp \tfrac{1}{{\sqrt k }}$. Линейная скорость сходимости отсутствует.

2.2. Сравнение теоремы 1 с известными результатами

Наиболее сильные результаты для линейной скорости сходимости МПГ на гладких многообразиях, известные автору, содержатся в [18, Theorem 2.3]. Однако указанный результат дает только асимптотику для скорости сходимости, но не точную оценку. При этом существенным для сходимости является условие Лежанского–Поляка–Лоясевича [13, § 3.2, Definition 1], которое достаточно трудно проверить.

Сходимость МПГ в теореме 1 локальна. Однако указанная теорема верна не только для гладкого многообразия, но для любого проксимально гладкого множества. Кроме того, в теореме получена гарантированная оценка скорости сходимости, а не асимптотика.

Автору известно крайне мало работ, в которых МПГ рассматривается на произвольном невыпуклом замкнутом множестве, которое не является гладким многообразием.

В работе [19, Theorem 3.3] доказана линейная сходимость МПГ для произвольного замкнутого множества $A$, но с очень сильными ограничениями на функцию $f$, определенную на множестве $A$. Большинство функций не удовлетворяют таким ограничениям.

Наиболее сильные известные автору результаты о МПГ (для множеств, не являющихся обязательно многообразиями) содержатся в работе [20]. Работа [20] изобилует разными результатами, но мы сосредоточимся на основной теоерме 3 из [20] о сходимости МПГ для случая евклидова пространства.

Если переписать для случая евклидова пространства формулу (14) работы [20] в наших обозначениях, то получится, что на множестве $A$ для сходимости алгоритма должно выполняться условие $\tfrac{L}{\mu } < R(1 - {{c}_{0}}) < R$, т.е. в точности условие теоремы 1. Более того, множества из работы [20] являются проксимально гладкими (см. [20, п. 2.3]).

Однако от функции в работе [20] требуется так называемое условие ограниченной сильной выпуклости (RSC), т.е. для некоторого $\alpha > 0$ и любых точек $x,y \in A$ должно выполняться неравенство

Легко видеть, что из условия RSC вытекает условие RSI. Обратное очевидно неверно. Более того, легко привести примеры задач, где теорема 1 работает, а [20, Theorem 3] нет.

Рассмотрим пример в ${{\mathbb{R}}^{2}}$. Пусть $a \in \left( {0,\tfrac{1}{4}} \right)$ и $A = \{ (x,y)\,|\,x \in [0,a],\;0 \leqslant y \leqslant {{x}^{2}} + 1\} $. Множество $A$ проксимально гладкое с константой $R = \tfrac{1}{2}$ (это минимальный радиус кривизны параболы $y = {{x}^{2}} + 1$ при $x \in [0,a]$). Рассмотрим $f(x,y) = {{x}^{2}}$. Очевидно, множество решений задачи (1) есть $\Omega = \left\{ {(0,y)\,|\,y \in [0,1]} \right\}$. Функция $f$ не удовлетворяет на множестве $A$ условию RSC, так как она постоянна на вертикальных отрезках. Для точки $(x,y) \in A$ имеем при $y \in [0,\;1]$ ${{P}_{\Omega }}(x,y) = {\text{\{ }}(0,y){\text{\} }}$, при $y > 1$ ${{P}_{\Omega }}(x,y) = {\text{\{ }}(0,\;1){\text{\} }}$. Из соотношений $f{\kern 1pt} {\text{'}}(x,y) = (2x,0)$, $f{\kern 1pt} {\text{'}}(0,y) = (0,0)$ и с учетом неравенства $\left| x \right| \geqslant \left| {y - 1} \right|$ для всех $(x,y) \in A$, $y \geqslant 1$, получаем, что

т.е. функция удовлетворяет условию RSI с константой $\mu = 1$. В силу выбора $a$ условие $\tfrac{L}{\mu } < R$ также выполнено для функции $f$ и множества $A$.