Журнал вычислительной математики и математической физики, 2021, T. 61, № 11, стр. 1814-1824

1.1. Введение

Рассмотрим в ${{\mathbb{R}}^{n}}$ задачу

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

Мы предполагаем, что $S$ – гладкое многообразие без края, а $f$ – функция с непрерывным по Липшицу градиентом, которая необязательно выпуклая. Пусть ${{T}_{x}}$ – касательное подпространство к $S$ в точке $x \in S$ и $T_{x}^{ \bot }$ – его ортогональное дополнение. Мы рассматриваем МПГ вида ${{x}_{0}} \in S$, $k = 0$,

Здесь ${{P}_{A}}$ – оператор метрического проектирования на замкнутое множество $A \subset {{\mathbb{R}}^{n}}$, а ${{R}_{S}}{{z}_{k}}$ – некоторая ретракция (см. подробности в [3]) точки ${{z}_{k}}$ на множество $S$, ${{R}_{S}}{{z}_{k}} \in S$. Часто используется ${{R}_{S}} = {{P}_{S}}$. Другой вид ретракции мы обсудим ниже.

Примером актуальной задачи (1) является задача минимизации гладкой функции $f$ на некотором матричном многообразии $S$ без края (см. [4], [5]).

Традиционно в задаче (1) используются варианты метода проекции градиента с шагами, связанными с локальными геодезическими на многообразии (см. [5]–[9]), а также метод Ньютона (см. [4], [7]).

В последнее время появилось много работ, где используется идеология (2). Основными трудностями являются выбор шага ${{t}_{k}}$ и доказательство сходимости алгоритма при разумных предположениях.

В [10] рассмотрен МПГ в задаче (1) с шагом ${{t}_{k}}$ Армихо (см. определение A1). Однако по сути доказана лишь асимптотика последовательности ${\text{\{ }}{{x}_{k}}{\text{\} }}$, но не явные оценки сходимости (см. [10, Theorem 2.3]). Аналогичный результат при некотором фиксированном ${{t}_{k}} = t > 0$ для всех $k$ получен и в [11, Corollary 4.2] при условии, что кривизны многообразия $S$ ограничены. В обоих работах для линейной сходимости принципиально условие Лежанского–Поляка–Лоясевича (условие ЛПЛ) функции $f$ на поверхности $S$ (см. ниже определение 1). Близкий к алгоритму из [10] алгоритм с шагом Армихо рассмотрен в [12, Algorithm 2.1]. Однако в [12] исследовался только факт сходимости алгоритма без оценки скорости сходимости. Кроме того, множество $S$ предполагалось выпуклым, а функция $f$ невыпуклой.

Обозначим через ${{B}_{R}}(x)$ замкнутый шар с центром $x$ радиуса $R$. В [13, Theorems 2, 3] получен следующий результат.

Теорема A. Пусть многообразие $S$ гладкое и проксимально гладкое с константой $\tfrac{\pi }{2}R$ многообразие без края, ${{x}_{0}} \in S$. Предположим, что $f:{{\mathbb{R}}^{n}} \to \mathbb{R}$ функция обладает следующими свойствами:

1) $f$ липшицево дифференцируема с константой ${{L}_{1}}$,

2) $L = \mathop {sup}\limits_{x\,:\,\varrho (x,S) < R} \left\| {f{\kern 1pt} {\text{'}}{\kern 1pt} (x)} \right\| < + \infty $, где $\varrho (x,S) = in{{f}_{{s \in S}}}\left\| {x - s} \right\|$,

3) выполнено условие ЛПЛ для функции $f$ на $S \cap {{\mathcal{L}}_{f}}(f({{x}_{0}}))$, ${{\mathcal{L}}_{f}}(f({{x}_{0}})) = \{ x \in {{\mathbb{R}}^{n}}\,|\,f(x) \leqslant f({{x}_{0}})\} $, c константой $\mu > 0$, т.е. для всех $x \in S \cap {{\mathcal{L}}_{f}}(f({{x}_{0}}))$

Пусть ${{t}_{0}} = \frac{1}{{\tfrac{{2L}}{R} + {{L}_{1}}}}$ и $t \in (0,{{t}_{0}}]$. Положим $q(t) = t - {{t}^{2}}\tfrac{L}{R} - {{t}^{2}}\tfrac{{{{L}_{1}}}}{2}$. Тогда итерации ${{x}_{0}} \in S$,

илисходятся с линейной скоростью по функцииПри этомКроме того, для случая 1) имеет место следующая линейная скорость сходимости по точкеОтметим, что $1 - \mu q(t) \in (0,\;1)$.

В случае итераций 1) пересечение $S \cap ({{z}_{k}} + T_{{{{x}_{k}}}}^{ \bot }) \cap {{B}_{R}}({{x}_{k}})$ одноточечно для всякого $k$ (см. [13, Lemma 5]).

Покажем, что условие (5) действительно означает линейную сходимость к решению (1). Положим

$\theta = \sqrt {1 - \mu q(t)} \in (0,\;1)$, $C = \tfrac{{{{t}^{2}} + {{t}^{4}}\tfrac{{{{L}^{2}}}}{{{{R}^{2}}}}}}{{q(t)}}(f({{x}_{0}}) - {{f}_{ * }})$

Для $M \geqslant N$

Значит, ${{x}_{N}} \to {{x}_{ * }} \in S$. Очевидно, что $\left\| {{{x}_{N}} - {{x}_{ * }}} \right\| \leqslant \tfrac{{C{{\theta }^{N}}}}{{1 - \theta }}$, т.е. сходимость ${\text{\{ }}{{x}_{k}}{\text{\} }}$ линейная. В силу [13, Theorem 2] $f({{x}_{k}}) - f({{x}_{{k + 1}}}) \geqslant q(t){{\left\| {{{P}_{{{{T}_{{{{x}_{k}}}}}}}}f{\kern 1pt} {\text{'}}{\kern 1pt} ({{x}_{k}})} \right\|}^{2}}$ для всех $k$ и в силу условия ЛПЛ Отсюда $f({{x}_{ * }}) = {{f}_{ * }}$.

Условие ЛПЛ с показателем 2 является одним из наиболее общих условий на гладкую функцию на многообразии, которое обеспечивает линейную сходимость градиентных методов (см. [10]). В частности, сильно выпуклая функция на многообразии при определенном соотношении константы сильной выпуклости и других параметров удовлетворяет условию ЛПЛ, а также некоторые функции с условием квадратичного роста на множестве (см. [13, Theorem 1]). Также условию ЛПЛ удовлетворяет квадратичная форма на сфере или, более общо, квадратичная форма на многообразии Штифеля (см. [14]).

Теорема A решает вопрос об оценке скорости сходимости алгоритма и выборе шага ${{t}_{k}} = t$ через константы Липшица $L$, ${{L}_{1}}$ и константу проксимальной гладкости $R$ многообразия. Константа $\mu $ из условия ЛПЛ возникает в оценке (5), она не нужна для выбора шага $t$. Ключевое отличие в доказательстве теоремы A от приведенных выше результатов состоит в использовании проксимальной гладкости множества $S$, что позволяет получить оценку сходимости (5) в явном виде.

Тем не менее на практике константы $L$, ${{L}_{1}}$ и $R$ могут быть неизвестны. В этой ситуации становится актуальным выбор шага ${{t}_{k}}$ в (2) по некоторому правилу, которое не требует знания упомянутых констант. Правило Армихо как раз и является одним из таких способов выбора шага ${{t}_{k}}$.

В работе рассмотрены два способа выбора шага ${{t}_{k}}$ по правилу Армихо. Это правило A1, заимствованное в [10], а также правило A2, сформулированное нами.

В обоих случаях мы получаем явную оценку скорости сходимости метода (2) для правил выбора шага A1 и A2.

При правиле A1 нам не нужно знать никаких констант.

В случае, когда константа проксимальной гладкости известна и известна оценка сверху для константы $L$, можно применять правило A2. Правило A2 имеет техническое преимущество: в отличие от правила A1 при подсчете шага ${{t}_{k}}$ ретракцию точки на множество нужно вычислять 1 раз.

В Приложении мы приводим точные константы проксимальной гладкости $R$ для основных матричных многообразий.

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

Через ${{\mathbb{R}}^{n}}$ будем обозначать вещественное евклидово пространство $n$ измерений со скалярным произведением $(x,y)$ $\forall x,y \in {{\mathbb{R}}^{n}}$. Обозначим через ${{B}_{R}}(x)$ замкнутый шар с центром $x$ радиуса $R$. Далее по тексту для задачи (1) ${{T}_{x}}$ – касательное подпространство к многообразию $S$ в точке $x \in S$, $f{\kern 1pt} {\text{'}}{\kern 1pt} (x)$ – градиент Фреше функции $f$ в точке $x$. Для точки ${{x}_{k}} \in S$ для краткости обозначим ${{\xi }_{k}} = {{P}_{{{{T}_{{{{x}_{k}}}}}}}}f{\kern 1pt} {\text{'}}{\kern 1pt} ({{x}_{k}})$. Отметим, что $(f{\kern 1pt} {\text{'}}{\kern 1pt} ({{x}_{k}}),{{\xi }_{k}}) = {{\left\| {{{\xi }_{k}}} \right\|}^{2}}$.

Если $f{\kern 1pt} {\text{'}}$ – липшицева функция с константой ${{L}_{1}}$, то для любых $x,y \in {{\mathbb{R}}^{n}}$ верны оценки (см. [15, Лемма 1.2.3])

Лебеговым множеством функции $f$ для $\beta \in \mathbb{R}$ называют множество ${{\mathcal{L}}_{f}}(\beta ) = {\text{\{ }}x \in {{R}^{n}}\,|\,f(x) \leqslant \beta {\text{\} }}$.

Определение 1 (см. [10], [16, Definition 1]). Пусть $S$ является ${{C}^{1}}$ многообразием, функция $f:{{\mathbb{R}}^{n}} \to \mathbb{R}$ дифференцируема. Пусть $\mu > 0$, $\beta \in \mathbb{R}$, ${{f}_{ * }} = in{{f}_{{x \in S}}}f(x)$. Будем говорить, что функция $f$ удовлетворяет условию ЛПЛ на множестве $S \cap {{\mathcal{L}}_{f}}(\beta )$, если ${{\left\| {{{P}_{{{{T}_{x}}}}}f{\kern 1pt} {\text{'}}{\kern 1pt} (x)} \right\|}^{2}} \geqslant \mu (f(x) - {{f}_{ * }})$ $\forall x \in S \cap {{\mathcal{L}}_{f}}(\beta )$.

Определим $O(n)$ – ортогональные матрицы размера $n \times n$. Для матриц $X \in {{\mathbb{R}}^{{n \times k}}}$ и $Y \in {{\mathbb{R}}^{{n \times k}}}$ определим скалярное произведение $\left( {X,Y} \right) = \operatorname{tr} {{X}^{{{\text{T}}Y}}}$ и норму Фробениуса $\left\| X \right\| = \sqrt {\operatorname{tr} {{X}^{{\text{т}}}}X} $. Напомним (см. [17, Theorem 7.3.2]), что для каждой матрицы $X \in {{\mathbb{R}}^{{n \times k}}}$ ранга $r$ существует сингулярное разложение вида $X = U\Sigma {{V}^{{\text{т}}}}$, где

$U \in O(n)$, $V \in O(k)$, $\Sigma = \left( {\begin{array}{*{20}{c}} {{{\sigma }_{1}}}& \ldots & \ldots & \ldots & \ldots & \ldots &0 \\ 0&{{{\sigma }_{2}}}& \ldots & \ldots & \ldots & \ldots &0 \\ \vdots & \vdots & \ddots & \vdots & \vdots & \vdots & \vdots \\ 0&0& \ldots &{{{\sigma }_{r}}}& \ldots & \ldots &0 \\ 0&0& \ldots & \ldots &0& \ldots &0 \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\ 0&0& \ldots & \ldots & \ldots & \ldots &0 \end{array}} \right) \in {{\mathbb{R}}^{{n \times k}}}$.

Числа ${{\sigma }_{1}} \geqslant \ldots \geqslant {{\sigma }_{r}} > 0$ называются сингулярными числами матрицы $X$. Для случая $k \leqslant n$ договоримся обозначать оставшиеся $k - r$ нулей на главной диагонали матрицы $\Sigma $ через ${{\sigma }_{{r + 1}}},\; \ldots ,\;{{\sigma }_{k}}$.

Мы будем пользоваться следующей формулой (см. [17, Corollary 7.3.5]) для $X,Y \in {{\mathbb{R}}^{{n \times k}}}$:

Через ${{I}_{k}}$ обозначим единичную матрицу размера $k \times k$.

Множество $A \subset {{\mathbb{R}}^{n}}$ называется проксимально гладким (прокс-регулярным, слабо выпуклым) с константой $R > 0$ (см. [18], [19]), если функция расстояния $\varrho (x,A) = \mathop {inf}\limits_{a \in A} \left\| {x - a} \right\|$ непрерывно дифференцируема на множестве ${{U}_{A}}(R) = \{ x \in {{\mathbb{R}}^{n}}\,|\,0 < \varrho (x,A) < R\} $. Эквивалентным условием проксимальной гладкости множества $A \subset {{\mathbb{R}}^{n}}$ является условие, что для всякой точки $x \in {{U}_{A}}(R)$ метрическая проекция ${{P}_{A}}(x)$ является одноточечным множеством.

Напомним определения основных матричных многообразий и множеств (далее $k \leqslant n$):

(i) многообразие Штифеля ${{\mathcal{S}}_{{n,k}}} = \{ X \in {{\mathbb{R}}^{{n \times k}}}\,|\,{{X}^{{\text{т}}}}X = {{I}_{k}}\} $;

(ii) многообразие Грассмана ${{\mathcal{G}}_{{n,k}}}$ – множество всех $k$-мерных подпространств в ${{\mathbb{R}}^{n}}$. Мы рассматриваем реализацию ${{\mathcal{G}}_{{n,k}}}$ вида ${{\mathcal{G}}_{{n,k}}} = \{ X{{X}^{{\text{T}}}}\,|\,X \in {{\mathcal{S}}_{{n,k}}}\} $ (см. [20]), т.е. подмножество во множестве симметричных матриц $n \times n$;

(iii) многообразие ${{\mathfrak{M}}_{r}} = \{ X \in {{\mathbb{R}}^{{n \times k}}}\,|\,\operatorname{rank} X = r,\;{{\sigma }_{i}}(X) \geqslant {{\sigma }_{0}} > 0\;\;\forall i = \overline {1,r} \} $ – матрицы ранга $r$ с сингулярными числами $ \geqslant {{\sigma }_{0}} > 0$;

(iv) множество ${{\mathfrak{L}}_{r}} = \{ X \in {{\mathbb{R}}^{{n \times k}}}\,|\,0 < \operatorname{rank} X \leqslant r,\;{{\sigma }_{i}}(X) \geqslant {{\sigma }_{0}} > 0\;\;\forall i = \overline {1,{\text{rank}}(X)} \} $ – матрицы ранга $ > 0$, $ \leqslant r$ с сингулярными числами $ \geqslant {{\sigma }_{0}} > 0$.

В [21] было показано, что ${{\mathcal{S}}_{{n,k}}}$ – проксимально гладкое множество с $R = 1$, а ${{\mathcal{G}}_{{n,k}}}$ (в указанной реализации) – проксимально гладкое множество с $R = \tfrac{1}{{\sqrt 2 }}$. Там же приводятся формулы для метрической проекции матрицы на многообразие Штифеля или Грассмана. Точные значения констант проксимальной гладкости для множеств ${{\mathfrak{M}}_{r}}$, ${{\mathfrak{L}}_{r}}$ и метрические проекции на них найдены нами в Приложении.

3.1. Шаг Армихо А1

Теорема 1. Предположим, что в задаче (1) функция $f$ липшицева с константой $L$, функция $f{\kern 1pt} {\text{'}}$ липшицева с константой ${{L}_{1}}$, $S$ – проксимально гладкое множество с константой $\tfrac{\pi }{2}R$. Числа $L$, ${{L}_{1}}$, $R$ неизвестны. Пусть выполнено условие ЛПЛ для функции $f$ на $S \cap {{\mathcal{L}}_{f}}(f({{x}_{0}}))$.

Определим $B = min\left\{ {d;\tfrac{{\beta (1 - \alpha )}}{C}} \right\}$, где $C = \tfrac{{{{L}_{1}}}}{2} + \tfrac{L}{R}$. Тогда алгоритм (2) с выбором шага $A1$ сходится с линейной скоростью по функции (8) и по точке (9).

Доказательство. Рассмотрим алгоритм с шагом A1 и случаи а и б:

$(a)$ Если $\alpha {{t}_{k}} > {{t}_{k}} - Ct_{k}^{2}$, т.е. ${{t}_{k}} > \tfrac{{1 - \alpha }}{C}$, то на $k$-м шаге имеем

(б) Пусть ${{t}_{k}} - Ct_{k}^{2} \geqslant \alpha {{t}_{k}}$, т.е. ${{t}_{k}} \leqslant \tfrac{{1 - \alpha }}{C} < \tfrac{1}{C}$.

Если $d > \tfrac{{1 - \alpha }}{C}$, то ${{t}_{k}} \geqslant \tfrac{{(1 - \alpha )\beta }}{C}$ в силу определения шага Армихо A1.

Если $d \leqslant \tfrac{{1 - \alpha }}{C}$, то ${{t}_{k}} = d$ (и $m = 0$). Покажем это. По теореме A (4) при ${{t}_{k}} < \tfrac{1}{C}$ (оценка (4) верна для всех ${{t}_{k}}$)

Максимальное ${{t}_{k}}$, удовлетворяющее предыдущей формуле, равно $d$.

Таким образом, в случаях (а) и (б), которые исчерпывают весь диапазон ${{t}_{k}} > 0$,

В силу неравенства ЛПЛ получаем, что Для функции $\varphi (x) = f(x) - {{f}_{ * }}$ имеем

Для сходимости по точке с учетом формулы

и неравенства $\left\| {{{\xi }_{k}}} \right\| \leqslant L$ имеем Теорема доказана.

3.2. Шаг Армихо А2

Теорема 2. Пусть в задаче (1) известна константа $\tfrac{\pi }{2}R$ проксимальной гладкости множества $S$ (или ее оценка снизу), а также известна оценка сверху $L$ константы Липшица $f$. Пусть $f{\kern 1pt} {\text{'}}$ – липшицева функция с неизвестной константой ${{L}_{1}}$. Предположим, что выполнено условие ЛПЛ для функции $f$ на $S \cap {{\mathcal{L}}_{f}}(f({{x}_{0}}))$.

Пусть ${{\alpha }_{1}} \in (0,\;1)$, $\alpha > {{\alpha }_{1}}$ и $d \leqslant {{\alpha }_{1}}\tfrac{{\sqrt 3 R}}{{2L}}$. Тогда алгоритм (2) с выбором шага A2 сходится с линейной скоростью по функции (14) и по точке (15) (для ${{R}_{S}}$) или $($16) (для P$_{S}$).

Доказательство. Рассмотрим ретракцию ${{R}_{S}}$. Для ${{z}_{k}} = {{x}_{k}} - {{t}_{k}}{{\xi }_{k}}$ имеем

Рассмотрим альтернативы (а) и (б):

${\text{(a)}}$ $\alpha {{t}_{k}} > {{t}_{k}} - \tfrac{{{{L}_{1}}}}{2}t_{k}^{2}$, т.е. ${{t}_{k}} > \tfrac{{2(1 - \alpha )}}{{{{L}_{1}}}}$,

(б) $\alpha {{t}_{k}} \leqslant {{t}_{k}} - \tfrac{{{{L}_{1}}}}{2}t_{k}^{2}$, т.е. ${{t}_{k}} \leqslant \tfrac{{2(1 - \alpha )}}{{{{L}_{1}}}}$.

Аналогично п. (б) теоремы $1$, ${{t}_{k}} \geqslant \tfrac{{2\beta (1 - \alpha )}}{{{{L}_{1}}}}$ в случае (б) при условии $d \geqslant \tfrac{{2(1 - \alpha )}}{{{{L}_{1}}}}$. Если $d < \tfrac{{2(1 - \alpha )}}{{{{L}_{1}}}}$, то, опять же аналогично доказательству теоремы $1$, ${{t}_{k}} = d$ и $m = 0$.

Итак, в любом случае ${{t}_{k}} \geqslant E: = min\left\{ {d;\tfrac{{2\beta (1 - \alpha )}}{{{{L}_{1}}}}} \right\}$.

Имеем

По теореме Пифагора ${{\left\| {{{x}_{{k + 1}}} - {{x}_{k}}} \right\|}^{2}} = {{\left\| {{{x}_{k}} - {{z}_{k}}} \right\|}^{2}} + {{\left\| {{{z}_{k}} - {{x}_{{k + 1}}}} \right\|}^{2}}$. При этом при условии ${{t}_{k}}\left\| {{{\xi }_{k}}} \right\| < \tfrac{{\sqrt 3 }}{2}R$ (см. [13, Theorem 2 (20)]) В силу (11) Из (10) и (12) получаем В силу условий $d \leqslant {{\alpha }_{1}}\tfrac{{\sqrt 3 R}}{{2L}}$, $\alpha > {{\alpha }_{1}}$ имеем Вспоминая, что ${{t}_{k}} \geqslant E$, окончательно получаем По условию ЛПЛ ${{\left\| {{{\xi }_{k}}} \right\|}^{2}} \geqslant \mu (f({{x}_{k}}) - {{f}_{ * }})$ и для $\varphi (x) = f(x) - {{f}_{ * }}$ имеем С учетом формулы (11)Применяя (13), получаем

Заметим, что для ретракции ${{P}_{S}}$ оценка (14) также остается верной в силу теоремы A.

Для сходимости по точке с учетом формулы (11) и неравенства $\left\| {{{\xi }_{k}}} \right\| \leqslant L$

Отсюда с учетом формулы (13) получаем

Теорема доказана.