| Математический сборник |
|
|
|
|
|
Эта публикация цитируется в 3 научных статьях (всего в 3 статьях) Условие Липшица метрической проекции и сходимость градиентных методов М. В. Балашов Институт проблем управления им. В. А. Трапезникова Российской академии наук, г. Москва
Англоязычная версия:
Sbornik: Mathematics, 2024, Volume 215, Issue 4, Pages DOI: https://doi.org/10.4213/sm9982e 
Реферативные базы данных:
     § 1. Введение1.1.Пусть $\mathcal Q\subset\mathcal H$ – выпуклое замкнутое подмножество в вещественном гильбертовом пространстве $\mathcal H$. Тогда для любой точки $x\in\mathcal H$ метрическая проекция $P_{\mathcal Q}x$ точки $x$ на $\mathcal Q$ одноточечна и для любых точек $x,x_0\in\mathcal H$ выполнено условие Липшица вида
$$
\begin{equation*}
\|P_{\mathcal Q}x-P_{\mathcal Q}x_0\|\leqslant 1\cdot\|x-x_0\|.
\end{equation*}
\notag
$$
В гильбертовом пространстве $\mathcal H$ на указанное условие Липшица, по-видимому, впервые обратил внимание Р. Р. Фелпс (см. [1]). В дальнейшем метрический проектор $P_{\mathcal Q}$ исследовался в разных классах пространств и для разных множеств $\mathcal Q$. Для гладких многообразий из $\mathcal H$ константа Липшица оператора метрического проектирования (в случае, когда она $<1$) оценивалась в [2; следствие 4.2]. В дальнейшем возникли обобщения выпуклых множеств, например, проксимально гладкие множества. Условие Липшица метрического проектора по точке для таких множеств в $\mathbb R^n$ и в $\mathcal H$ рассматривалось в работах [3], [4]. Для равномерно выпуклых и равномерно гладких банаховых пространств локальное условие Гёльдера метрического проектора на замкнутые подпространства по точке получено в работе Б. О. Бьёрнесталя [5]. Была также исследована устойчивость метрического проектора по множеству. В работе Дж. Даниеля [6] показано, что для выпуклых замкнутых ограниченных подмножеств $\mathcal Q,\mathcal Q_0\subset\mathcal H$ расстояние между метрическими проекциями $P_{\mathcal Q}0$ и $P_{\mathcal Q_0}0$ имеет порядок $(h(\mathcal Q,\mathcal Q_0))^{1/2}$ относительно расстояния в метрике Хаусдорфа $h(\mathcal Q,\mathcal Q_0)$. При этом на элементарных примерах в $\mathbb R^2$ легко убедиться, что порядок $1/2$ по $h(\mathcal Q,\mathcal Q_0)$ является точным. Можно рассмотреть пример множеств $A_1,A_2\subset\mathbb R^2$ из [7; с. 190]. На случай равномерно выпуклых банаховых пространств результат [6] был обобщен в работе В. И. Бердышева [8]. Результат Бердышева, в частности, объяснял корень в оценке Даниеля: это обратная функция к модулю выпуклости гильбертова пространства. Условия Гёльдера для модуля непрерывности метрического проектора на проксимально гладкие множества по точке и по множеству в классе равномерно выпуклых и равномерно гладких банаховых пространств в зависимости от модулей выпуклости и гладкости были установлены в [9]. Нерастягиваемость и, если есть, сжимаемость оператора $\mathcal H\ni x\mapsto P_{\mathcal Q}x$ имеет большое количество приложений. Рассмотрим одно из важнейших приложений – градиентные методы минимизации функции на множестве и условия их сходимости. Пусть $\mathcal Q\subset\mathbb R^n$ – замкнутое подмножество и $f\colon \mathbb R^n\to\mathbb R$ – функция с непрерывным по Липшицу градиентом. Градиентные методы такие, как метод проекции градиента:
$$
\begin{equation}
x_1\in\mathcal Q, \qquad x_{k+1}\in P_{\mathcal Q}(x_k-\alpha_k f'(x_k)), \quad k\geqslant 1, \quad \alpha_k>0,
\end{equation}
\tag{1.1}
$$
или метод условного градиента:
$$
\begin{equation}
\begin{gathered} \, x_1\in\mathcal Q,\qquad z_k\in\operatorname{Arg}\max_{x\in\mathcal Q}(-f'(x_k),x), \\ x_{k+1}\in\operatorname{Arg}\min_{x\in [x_k,z_k]}f(x),\qquad k\geqslant 1, \end{gathered}
\end{equation}
\tag{1.2}
$$
являются важными алгоритмами минимизации первого порядка. Оба метода применяются главным образом к выпуклым множествам и функциям, хотя последнее время происходит отказ от выпуклости функции, а в методе (1.1) и от выпуклости множества. Важно, что для достаточно широких классов задач указанные методы имеют линейную скорость сходимости к решению, т.е. сходимость со скоростью геометрической прогрессии со знаменателем $<1$. Первой работой, где даны линейные оценки скорости сходимости методов (1.1) и (1.2) для широкого класса выпуклых множеств и функций, является работа [10]. Для метода проекции градиента (1.1) была доказана линейная сходимость в случае сильно выпуклой функции1 $f$ и выпуклого множества $\mathcal Q$. Для метода условного градиента (1.2) линейная сходимость была доказана для сильно выпуклого множества2 $\mathcal Q$ и выпуклой функции $f$. В обоих случаях градиент $f'$ предполагался непрерывным по Липшицу. В дальнейшем результаты работы [10] обобщались. Для метода условного градиента (1.2) была доказана линейная сходимость при условии локальной сильной выпуклости множества $\mathcal Q$ в точке $x_0\in\mathcal Q$, которая является решением задачи (1.2). Локальная сильная выпуклость определялась через локальный модуль выпуклости (см. [11]) и означает, что существует такая константа $c>0$, что для любой точки $x\in\mathcal Q$ выполнено включение $(x_0+x)/2+\mathcal B_{c\|x_0-x\|^2}(0)\subset\mathcal Q$, $\mathcal B_r(0)$ – замкнутый евклидов шар радиуса $r$ с центром в нуле. В дальнейшем этот результат также обобщался и уточнялся (см. [12; п. 2.2.3]). Кроме того, была доказана линейная сходимость метода (1.2) для многогранников при условии сильной выпуклости и гладкости $f$ (см. [12; теорема 2.29]). В работах [13], [14] была доказана линейная сходимость модификации алгоритма (1.2) для сильно выпуклого множества $\mathcal Q$ и невыпуклой, но имеющей липшицев градиент функции $f$. При этом метод не содержал минимизации по отрезку, т.е. полагалось $x_{k+1}=z_k$. Для линейной сходимости такого алгоритма требовалось некоторое соотношение между константами сильной выпуклости, Липшица и др. В работах по методу проекции градиента получила развитие идея острого минимума, c историей возникновения которой в геометрической теории приближений можно ознакомиться в работе [15]. В работе [16; формула (4)] условие острого минимума использовалось в линейных оценках скорости сходимости субградиентных методов для негладкой выпуклой функции. В дальнейшем условие острого минимума позволило доказать результаты о линейной сходимости градиентных методов для слабо выпуклых, т.е. не выпуклых, функций (см. [17], [18]). Важным направлением исследования алгоритма (1.1) являются результаты о линейной сходимости метода проекции градиента при условии Поляка–Лоясевича и других условий в духе метрической регулярности, в частности на гладких многообразиях (см. [19]–[22]). В работе [23] было доказано, что для проксимально гладкого с константой $K>0$ множества3 $\mathcal Q\subset \mathcal H$ и сильно выпуклой с константой $\varkappa>0$ функции $f$ со свойством ${L}/{\varkappa}<K$, где $L=\sup_{x\in\mathcal L}\|f'(x)\|$ на некотором нижнем лебеговом множестве $\mathcal L$ функции $f$ уровня $>\inf_{x\in\mathcal Q}f(x)$, метод проекции градиента (1.1) при выборе $x_1\in\mathcal L$ сходится с линейной скоростью при достаточно малом $\alpha_k=\alpha>0$. Таким образом, отказ от выпуклости множества $\mathcal Q$ компенсируется в приведенном результате сильной выпуклостью $f$ и “более сильной” выпуклостью лебеговых множеств $f$, нежели “невыпуклость” множества $\mathcal Q$. В частности можно показать, что лебеговы множества $f$, которые содержатся в $\mathcal L$, сильно выпуклы с радиусом ${L}/{\varkappa}$. Отметим, что в работе [23] существенно использовалось условие Липшица метрического проектора на $\mathcal Q$: для точек $x_0,x_1{\notin}\,\mathcal Q$ и на расстоянии не более $\rho\in(0,K)$ от $\mathcal Q$ имеет место условие Липшица $\|P_{\mathcal Q}x_0-P_{\mathcal Q}x_1\|\leqslant ({K}/(K- \rho))\|x_0- x_1\|$. Поскольку константа ${K}/(K-\rho)$ близка к 1 при малых $\rho>0$, то сжимаемость в методе (1.1) удается получить стандартными рассуждениями за счет сильной выпуклости функции $f$. С другой стороны, известно, что сильная выпуклость множества $\mathcal Q$ (см. [24]) или даже ее ослабление в виде некоторого опорного условия (см. [25]) делают оператор $P_{\mathcal Q}$ сжимающим на множестве достаточно удаленных от множества $\mathcal Q$ точек. Это, в частности, может обеспечивать линейную сходимость градиентных методов. Настоящая работа мотивирована в первую очередь следующим вопросом: какие минимальные геометрические свойства множества $\mathcal Q$ позволяют доказать сжимаемость в некотором смысле проектора $P_{\mathcal Q}$? Параллельно с этим решается вопрос о сходимости градиентных методов (1.1) или (1.2). От функции $f$ мы требуем условие Липшица для градиента. В частности, функция $f$ может быть не выпуклой. В настоящей работе мы дадим два определения. Первое уже появлялось в работах автора ранее (см. [25]) и является некоторым существенным ослаблением условия сильной выпуклости. Второе определение является некоторым ослаблением условия проксимальной гладкости. В § 2 мы уточним условие Липшица для оператора $P_{\mathcal Q}$ в случае, когда множество удовлетворяет одному из определений. Мы, в частности, покажем, что для первого определения выполняется некоторое локальное условие Липшица с константой $<1$. Полученные константы Липшица для $P_{\mathcal Q}$ неулучшаемы, что показано на примерах. Мы также докажем некоторое обобщение результата Даниеля из [6] о непрерывности в метрике Хаусдорфа метрического проектора как функции выпуклых ограниченных замкнутых множеств в гильбертовом пространстве $\mathcal H$ на случай невыпуклых подмножеств $\mathcal H$ достаточно общей природы. Наличие сжимаемости $P_{\mathcal Q}$ позволяет получить достаточные условия сходимости градиентных методов для невыпуклых функций и множеств в § 3 и в § 4. Предельным переходом отсюда получаются и соответствующие результаты для выпуклых множеств. В заключении (§ 6) мы кратко сравним упомянутое выше условие локальной сильной выпуклости из [11] с определением 1 и покажем, что условие квадратичного роста функции позволяет доказать ряд полученных оценок в выпуклом случае. 1.2. Некоторые определения и обозначенияВ вещественном евклидовом пространстве $\mathbb R^n$ обозначим через $(x,y)$ скалярное произведение векторов $x$, $y$, $\|x\|=\sqrt{(x,x)}$. Положим $\mathcal B_R(a)=\{ x\in\mathbb R^n\mid \|x-a\|\leqslant R\}$. Через $\mathcal H$ обозначим вещественное гильбертово пространство с теми же обозначениями для скалярного произведения, нормы и шара, что и в $\mathbb R^n$. Будем обозначать через $e_1,\dots,e_n$ стандартный ортонормированный базис в $\mathbb R^n$. Для множества $\mathcal P\subset\mathcal H$ и точки $x\in\mathcal H$ определим $\varrho(x,\mathcal P)=\inf_{z\in \mathcal P}\|x-z\|$. Обозначим через $\operatorname{co} \mathcal P$ выпуклую оболочку множества $\mathcal P$. Пусть $\partial \mathcal P$ – граница множества $\mathcal P$, а $\operatorname{int}\mathcal P$ – внутренность. Расстоянием по Хаусдорфу между замкнутыми множествами $\mathcal P$ и $\mathcal Q$ из $\mathcal H$ называется число
$$
\begin{equation*}
\begin{aligned} \, h(\mathcal P,\mathcal Q) &=\inf\bigl\{ \varepsilon>0\mid \mathcal P\subset \mathcal Q+\mathcal B_{\varepsilon}(0),\, \mathcal Q\subset \mathcal P+\mathcal B_{\varepsilon}(0)\bigr\} \\ &=\max\Bigl\{ \max_{x\in \mathcal P}\varrho(x,\mathcal Q),\, \max_{x\in \mathcal Q}\varrho(x,\mathcal P)\Bigr\}. \end{aligned}
\end{equation*}
\notag
$$
Опорной функцией множества $\mathcal Q\subset\mathbb R^n$ называется функция
$$
\begin{equation*}
s(p,\mathcal Q)=\sup_{x\in \mathcal Q}(p,x),\qquad p\in\mathbb R^n.
\end{equation*}
\notag
$$
Для выпуклого замкнутого множества $\mathcal Q\subset\mathbb R^n$ определим нормальный конус в точке $x\in \mathcal Q$, т.е.
$$
\begin{equation*}
N(\mathcal Q,x)=\{ p\in\mathbb R^n\mid (p,x)=s(p,\mathcal Q)\}.
\end{equation*}
\notag
$$
Для компактного и не обязательно выпуклого множества $\mathcal Q\subset\mathbb R^n$ и вектора $p\ne 0$ определим
$$
\begin{equation*}
\mathcal Q (p)=\{ x\in \mathcal Q\mid (p,x)=s(p,\mathcal Q)\}
\end{equation*}
\notag
$$
– опорное множество множества $\mathcal Q$ в направлении $p$. Заметим, что в силу леммы 1.18.1 и теоремы 1.18.3 из [7] для произвольного компактного подмножества $\mathcal Q\subset\mathbb R^n$ и вектора $ p\ne 0$ выполнено включение $\mathcal Q (p) \subset (\operatorname{co}\mathcal Q)(p)$. Отметим, что в случае выпуклого замкнутого множества $\mathcal Q$ множество $\mathcal Q(p)$ есть субдифференциал $s(\cdot,\mathcal Q)$ в точке $p$. Напомним, что субдифференциалом выпуклой функции $f\colon \mathbb R^n\supset D\to\mathbb R$ в точке $x_0\in\mathbb R^n$ называется (возможно пустое) множество
$$
\begin{equation*}
\partial f(x_0)=\{ p\in\mathbb R^n\mid f(x)\geqslant f(x_0)+(p,x-x_0)\ \forall\, x\in D\}.
\end{equation*}
\notag
$$
Договоримся обозначать элемент множества $\mathcal Q(p)$ в случае неодноточечности последнего также через $\mathcal Q(p)$. Непустое множество $Q\subset\mathcal H$ называется сильно выпуклым с радиусом $R$, если $Q=\bigcap_{x\in \mathcal X}\mathcal B_R(x)$ для некоторого множества центров $\mathcal X\subset\mathcal H$. Для выпуклого замкнутого ограниченного множества $Q\subset\mathcal H$ следующие условия эквивалентны (см. [7; теоремы 4.2.7, 4.3.3], [3]). 1) Множество $Q$ сильно выпукло с радиусом $R$. 2) Опорный принцип: для любого $\|p\|=1$ выполнено $\mathcal Q\subset \mathcal B_R(Q(p)-Rp)$. 3) $\|Q(p)-Q(q)\|\leqslant R\|p-q\|$ для всех $\|p\|=\|q\|=1$. Замкнутое множество $\mathcal Q\subset\mathcal H$ называется проксимально гладким с константой $K>0$, если функция расстояния $\varrho (x,\mathcal Q)$ непрерывно дифференцируема на множестве $\mathcal U_{\mathcal Q}(K)=\{ x\in\mathcal H\colon 0<\varrho (x,\mathcal Q)<K\}$. Эквивалентными проксимальной гладкости множества $\mathcal Q\subset\mathcal H$ с константой $K$ являются следующие условия (см. [3], [4]): 1) для любой точки $x\in \mathcal U_{\mathcal Q}(K)$ значение $P_{\mathcal Q}x\in\mathcal Q$ одноточечно и непрерывно4 зависит от $x$; 2) для $x \notin \mathcal Q$ и $a = P_{\mathcal Q}x$ выполнено равенство
$$
\begin{equation*}
\mathcal Q\cap\operatorname{int} \mathcal B_K \biggl(a+K\frac{(x-a)}{\|x-a\|}\biggr)=\varnothing;
\end{equation*}
\notag
$$
3) для любого $r\in (0,K)$, точек $x_0,x_1\in \mathcal U_{\mathcal Q}(r)$ и для проекций $a_i=P_{\mathcal Q}x_i$, $i=0,1$, выполнено условие Липшица $\|a_0-a_1\|\leqslant ({K}/(K-r))\|x_0-x_1\|$. Вектор $\mathcal H\ni p\ne 0$ будем называть проксимальной нормалью замкнутого множества $\mathcal Q\subset\mathcal H$ в точке $x\in\mathcal Q$, если для некоторого $t>0$ выполнено равенство $P_{\mathcal Q}(x+tp)=x$. Множество проксимальных нормалей вместе с точкой $0\in\mathcal H$ в любой точке $x\in\mathcal Q$ образует конус (может быть, вырожденный $\{0\}$). Будем обозначать этот конус через $N_P(\mathcal Q,x)$. Определение 1 (см. [25]). Будем говорить, что замкнутое множество $\mathcal Q\,{\subset}\,\mathcal H$ удовлетворяет опорному условию сильной выпуклости для вектора $p_0\ne 0$, $p_0\,{\in}\, \mathcal H$, с радиусом $R>0$, если множество $\mathcal Q(p_0)=\operatorname{Arg}\max_{x\in\mathcal Q}(p_0,x)$ одноточечно и Будем для краткости обозначать это условие для замкнутого множества $Q$ через $\operatorname{sc}$ или, если надо конкретизировать $p_0$ и $R$, через $\operatorname{sc}(p_0,R)$. Определение 2. Будем говорить, что замкнутое множество $\mathcal Q\subset\mathcal H$ удовлетворяет опорному условию слабой выпуклости для точки $x_0\in\mathcal Q$ и вектора $p_0\ne 0$, $p_0\in N_P(\mathcal Q,x_0)$, с константой $K>0$, если Будем для краткости обозначать это условие для замкнутого множества $Q$ через $\operatorname{wc}$ или, если надо конкретизировать $x_0$, $p_0$ и $K$, через $\operatorname{wc}(x_0,p_0,K)$. § 2. Локальное условие Липшица метрической проекцииТеорема 1. Пусть замкнутое множество $\mathcal Q\subset\mathcal H$ удовлетворяет опорному условию $\operatorname{sc}(p_0,R)$ и $\|p_0\|=1$. Допустим, что $r>0$, $x_0=\mathcal Q(p_0)+rp_0$ и $x\in\mathcal H$ – такая точка, что $\varrho (x,\mathcal Q)=\rho \geqslant 0$ и $P_{\mathcal Q}x\ne\varnothing$. Определим проекцию $a_0=P_{\mathcal Q}x_0=\mathcal Q(p_0)$ и зафиксируем произвольную точку $a\in P_{\mathcal Q}x$. Пусть в точке $a\in\mathcal Q$ выполнено опорное условие $\operatorname{wc}(a,x-a,K)$. Тогда Доказательство. Пусть $\rho>0$. Запишем опорное условие $\operatorname{sc}$ Возводя неравенство в квадрат, получаем Отсюда следует, что Запишем теперь опорное условие $\operatorname{wc}$ Возводя в квадрат, получаем откуда
Из неравенства (2.2) следует, что
$$
\begin{equation*}
\begin{aligned} \, (2R+r)\|a_0-a\|^2 &\leqslant 2R (x_0-a,a_0-a) \\ &\leqslant 2R (x_0-x,a_0-a)+2R (x-a,a_0-a), \end{aligned}
\end{equation*}
\notag
$$
а с учетом формулы (2.3) приходим к неравенству
$$
\begin{equation*}
\begin{aligned} \, (2R+r)\|a_0-a\|^2 &\leqslant 2R (x_0-a,a_0-a) \\ &\leqslant 2R (x_0-x,a_0-a)+\frac{R\rho}{K}\|a_0-a\|^2, \end{aligned}
\end{equation*}
\notag
$$
откуда
$$
\begin{equation*}
\begin{aligned} \, \biggl(2R+r-\frac{R\rho}{K}\biggr)\|a_0-a\|^2 &\leqslant 2R (x_0-x,a_0-a) \\ &\leqslant 2R \|x_0-x\|\,\| a_0-a\|. \end{aligned}
\end{equation*}
\notag
$$
Если в условии теоремы $\rho=0$, то $x=a$ и из формулы (2.2) следует, что
$$
\begin{equation*}
\begin{aligned} \, (2R+r)\|a_0-a\|^2 &\leqslant 2R (x_0-a,a_0-a) \\ &=2R (x_0-x,a_0-a)\leqslant 2R\|x_0-x\|\,\|a_0-a\|. \end{aligned}
\end{equation*}
\notag
$$
Таким образом, при $\rho=0$ оценка (2.1) также верна.
Теорема доказана. Замечание 1. Если в теореме 1 множество $\mathcal Q$ дополнительно выпукло, то $K=+\infty$ и оценка приобретает вид Замечание 2. Результат теоремы 1 не изменится, если считать, что $\|x_0- a_0\|\geqslant r$ (и $(x_0-a_0)/(\|x_0-a_0\|)=p_0$) и $\varrho (x,\mathcal Q)\leqslant \rho$. Это непосредственно вытекает из формулы (2.1). Замечание 3. Отметим, что для любого замкнутого подмножества $\mathcal Q\subset\mathcal H$ из теоремы 1 без выполнения опорного условия $\operatorname{wc}$ в точке $a\in\mathcal Q$ мы имеем $K=\rho$, и тем самым выполнена оценка Пусть при выполнении условия теоремы 1 множество $\mathcal Q=\mathcal Q_0$. Пусть $\mathcal Q_1$ – другое замкнутое подмножество. Допустим, что $\mathcal Q_0$ и $\mathcal Q_1$ выпуклые. Пусть $a=P_{\mathcal Q_1}x$ и $b=P_{\mathcal Q_0}x$. Тогда В силу теоремы 1, где $r=\|x_0-a_0\|$, $\rho=\|x-b\|$, и в силу результата работы [6] $\|a-b\|$ имеет порядок $\sqrt{h(Q_0,Q_1)}$. Например, из [7; формула (2.1.1)] $\|a-b\|\leqslant 2\sqrt{2Rh(Q_0,Q_1)}$, где $R>0$ – такое число, что $Q_0\cup\mathcal Q_1\subset \mathcal B_R(x)$ для некоторого центра $x$. Оказывается, что аналогичные оценки имеют место для метрической проекции на произвольное замкнутое подмножество из $\mathcal H$ при выполнении условия $\operatorname{wc}$.Теорема 2. Пусть замкнутое множество $\mathcal Q_0\subset\mathcal H$ удовлетворяет опорному условию слабой выпуклости $\operatorname{wc}(a_0,p_0,K)$ и $\|p_0\|=1$. Допустим, что $r\in (0,K)$, $t\in (0,r]$, $x_0=a_0+tp_0$, при этом $a_0=P_{\mathcal Q_0}x_0 $. Пусть $\mathcal Q\subset \mathcal H$ – такое замкнутое множество, что $h(\mathcal Q_0,\mathcal Q)<r$ и $x\in\mathcal H$ – такая точка, что $\varrho (x,\mathcal Q)\leqslant r$ и $P_{\mathcal Q}x\ne\varnothing$. Пусть точка $a\in P_{\mathcal Q}x$ выбрана произвольно. Тогда Доказательство. Пусть $r>h_1>h=h(\mathcal Q_0,\mathcal Q)$ и $b\in\mathcal Q_0$ – такая точка, что $\|a-b\|\leqslant h_1$. Запишем условие $\operatorname{wc}$
$$
\begin{equation*}
\biggl\|a_0+\frac{x_0-a_0}{\|x_0-a_0\|}K-b\biggr\|\geqslant K.
\end{equation*}
\notag
$$
Отсюда
$$
\begin{equation*}
\biggl\|a_0+\frac{x_0-a_0}{\|x_0-a_0\|}K-a\biggr\|\geqslant K-h_1.
\end{equation*}
\notag
$$
Возводя в квадрат и обозначая $\rho_0=\|x_0-a_0\|\leqslant r$, получаем
$$
\begin{equation*}
\begin{gathered} \, \|a_0-a\|^2+\frac{2K}{\rho_0}(a_0-a,x_0-a_0)+K^2\geqslant (K-h_1)^2, \\ \|a_0-a\|^2+\frac{2K}{\rho_0}(a_0-a,x_0-a_0+a-a)+K^2\geqslant (K-h_1)^2, \\ \|a_0-a\|^2-\frac{2K}{\rho_0}\|a_0-a\|^2+\frac{2K}{\rho_0}(a_0-a,x_0-a)+K^2\geqslant (K-h_1)^2, \end{gathered}
\end{equation*}
\notag
$$
и с учетом $\rho_0\leqslant r$ получаем
Уточним выбор $h_1\in (h,r)$ в двух следующих случаях. Случай 1: $\rho=\varrho (x,\mathcal Q) >0$, $\rho > h$. Выберем $h_1\in (h,\rho)$, тогда аналогично рассмотренному выше
$$
\begin{equation}
\begin{gathered} \, \notag \biggl\|a+\frac{x-a}{\|x-a\|}\rho-a_0\biggr\|\geqslant \rho-h_1, \\ \notag -\|a_0-a\|^2+2(a-a_0,x-a_0)+2\rho h_1\geqslant 0, \end{gathered}
\end{equation}
\notag
$$
Складывая (2.7) и (2.8), получаем
$$
\begin{equation*}
\begin{gathered} \, (3K-r)\|a_0-a\|^2\leqslant 2K(x_0-x+a_0-a,a_0-a)+4Krh_1, \\ \begin{aligned} \, \|a_0-a\|^2 &\leqslant \frac{2K}{K-r}(x_0-x,a_0-a)+\frac{4Krh_1}{K-r} \\ &\leqslant \frac{2K}{K-r}\|x_0-x\|\, \|a_0-a\|+ \frac{4Kr}{K-r}h_1. \end{aligned} \end{gathered}
\end{equation*}
\notag
$$
Из оценки
$$
\begin{equation*}
\begin{aligned} \, \biggl( \|a_0-a\|-\frac{2K}{2(K-r)}\|x_0-x\|\biggr)^2 &\leqslant \biggl( \frac{2K}{2(K-r)}\| x_0-x\|\biggr)^2+\frac{4Kr}{K-r}h_1 \\ & \leqslant \biggl(\frac{2K}{2(K-r)}\|x_0-x\|+\sqrt{\frac{4Kr}{K-r}h_1}\,\biggr)^2 \end{aligned}
\end{equation*}
\notag
$$
предельным переходом $h_1\to h$ получаем утверждение леммы для случая 1.
Случай 2: $0<\rho=\varrho (x,\mathcal Q)\leqslant h$. Зафиксируем $h_1\in (h,r)$. Пусть $z=a+((x-a)/\|x-a\|)\rho=x$ и точка $b\in \mathcal Q$: $\|a_0-b\|\leqslant h_1$. С учетом оценок $\|z-b\|\geqslant \rho$ и $\|a_0-b\|\leqslant h_1$ имеем
$$
\begin{equation*}
\|z-a_0+a_0-b\|\geqslant \rho, \qquad \|z-a_0\|^2+\|a_0-b\|^2\geqslant \frac{\rho^2}{2},
\end{equation*}
\notag
$$
откуда, подставляя $z=x$, получаем
$$
\begin{equation*}
\|a-a_0\|^2+2(a-a_0,x-a)+\rho^2+h_1^2\geqslant \frac{\rho^2}{2}.
\end{equation*}
\notag
$$
С учетом условия $\rho<h_1$ перепишем неравенство в виде
$$
\begin{equation*}
\|a-a_0\|^2+2(a-a_0,x-a_0)-2\|a_0-a\|^2+2h_1^2\geqslant \frac{\rho^2}{2},
\end{equation*}
\notag
$$
и окончательно имеем
$$
\begin{equation*}
\begin{gathered} \, \|a_0-a\|^2\leqslant 2(a-a_0,x-a_0)+2h_1^2, \\ K\|a_0-a\|^2\leqslant 2K(a-a_0,x-a_0)+2Kh_1^2. \end{gathered}
\end{equation*}
\notag
$$
Поскольку по условию теоремы $h_1<r$, то Складывая последнее неравенство с (2.7), получаем
$$
\begin{equation*}
(3K-r)\|a_0-a\|^2\leqslant 2K(a_0-a,x_0-x+a_0-a)+4Krh_1.
\end{equation*}
\notag
$$
Из этого неравенства, повторяя рассуждение случая 1, получаем результат (2.6) теоремы. Случай $\varrho (x,\mathcal Q)=0$ с помощью формулы (2.7) и с учетом равенства $x=a$ также приводит к оценке (2.6).
Теорема доказана. Следующее следствие теоремы 2 обобщает результат Даниеля (см. [6]) на невыпуклый случай. Следствие 1. Пусть замкнутое множество $\mathcal Q_0\,{\subset}\,\mathcal H$ удовлетворяет опорному условию слабой выпуклости $\operatorname{wc}(a_0,p_0,K)$ и $\|p_0\|=1$. Допустим, что $r\in (0,K)$, $t\in (0,r]$, $x_0=a_0+tp_0$, при этом $a_0=P_{\mathcal Q}x_0 $. Пусть $\mathcal Q\subset \mathcal H$ – такое замкнутое подмножество, что $h(\mathcal Q_0,\mathcal Q)<r$, $\varrho (x_0,\mathcal Q)\leqslant r$ и $P_{\mathcal Q_0}x_0\ne \varnothing$. Тогда имеет место оценка для метрической проекции Лемма 1. Пусть выпуклое замкнутое множество $\mathcal Q\subset\mathcal H$ удовлетворяет условию $\operatorname{sc}(p,R)$ и $\|p\|=1$. Тогда для всякого единичного вектора $q\in\mathcal H$ и произвольного элемента опорного множеств $\mathcal Q(q)$ (который мы также обозначим $\mathcal Q(q)$) выполнено неравенство Доказательство. Зафиксируем единичный вектор $q$ и элемент $\mathcal Q(q)$. Положим без ограничения общности $\mathcal Q (p)-Rp=0$.
Пусть $(p,q)\geqslant 0$. Точка $\mathcal Q(q)$ содержится во множестве $\mathcal S=\mathcal B_R(0)\cap H_q^+$ (где $H_q^+= \{x\in\mathcal H\colon (q,x)\geqslant (q,\mathcal Q(p))\}$), которое является сферическим сегментом. Пусть $\xi=[0,Rq]\cap\partial H_q^+$. Тогда $\|\xi-Rp\|\leqslant R\|q-p\|$ (так как $\xi$ – метрическая проекция $Rq$ на $\partial H_q^+$) и $\|\mathcal Q(q)-\mathcal Q(p)\|\leqslant \operatorname{diam}\mathcal S=2\|\xi-Rp\|$ (так как $(p,q)\geqslant 0$ и диаметр $\mathcal S$ реализуется на основании сегмента). Если $(p,q)<0$, то $\|p-q\|^2=2-2(p,q)>2$, $\|p-q\|>\sqrt{2}$ и
$$
\begin{equation*}
\frac{\|\mathcal Q(p)-\mathcal Q(q)\|}{\|p-q\|}\leqslant \frac{2R}{\sqrt{2}}=\sqrt{2}\, R.
\end{equation*}
\notag
$$
Лемма доказана. Покажем, что полученные константы Липшица точны. Покажем точность константы Липшица $2R$ в лемме 1. Пусть $R>0$ и в $\mathbb R^2$ $p=(0,1)=e_2$, $q=(\sin\varphi,\cos\varphi)$ для малого $\varphi>0$. Рассмотрим множество $\mathcal Q=\mathcal B_R(0)\cap \{ x\in\mathbb R^2\colon (q,x)\leqslant R(q,e_2)\}$, т.е. круг без кругового сегмента. Из элементарной планиметрии легко видеть, что длина основания удаленного сегмента есть $2R\sin\varphi$. При этом $\mathcal Q(p)=Re_2$. Добавим к $\mathcal Q$ точку, которая лежит в удаленном сегменте строго выше прямой $\{ x\in\mathbb R^2\colon (q,x)= R(q,e_2)\}$ близко к точке $R(\sin 2\varphi,\cos 2\varphi)$ в том смысле, что расстояние между этими точками имеет по $\varphi$ порядок $\varphi^2$. Обозначим выпуклую оболочку множества $\mathcal Q$ и добавленной точки через $\widetilde{\mathcal Q}$, при этом $\widetilde{\mathcal Q}(q)$ по построению есть добавленная точка. Тогда $\|p-q\|\sim \varphi$, а $\|\widetilde{\mathcal Q}(p)-\widetilde{\mathcal Q}(q)\|\sim 2R\varphi$ при $\varphi\to +0$. Покажем, что оценка теоремы 1 точна для выпуклого множества $\mathcal Q$, см. замечание 1. Рассмотрим множество $\mathcal Q$ из приведенного выше примера. Зафиксируем $r>0$. Пусть $x_0=(R+r)e_2$, $a_0=Re_2=P_{\mathcal Q}x_0$, $a=R(\sin 2\varphi,\cos 2\varphi)$, $x=a+rq\sim ((2R+r)\varphi, (R+r))$ при $\varphi\to +0$. При этом $a=P_{\mathcal Q}x$. Тогда $\|a-a_0\|\sim 2R\varphi$, а $\|x-x_0\|\sim (2R+r)\varphi$ при $\varphi \to +0$. Покажем точность константы Липшица $2R/(R+r)$ в формуле (2.5). Зададим числа $R>\varepsilon>0$ и $r>0$. В $\mathbb R^2$ рассмотрим множество $\mathcal Q=\{ a_0,a\}$, где $a_0=Re_2$, $a=-Re_2$, и точки $x_0=(R+r)e_2$, $x=-\varepsilon e_2$. Тогда $P_{\mathcal Q}x_0=a_0$, $P_{\mathcal Q}x=a$, $\|a_0-a\|=2R$, $\| x_0-x\|=R+r+\varepsilon$. При этом выполнено условие $\operatorname{sc}(x_0-a_0,R)$. Покажем наконец точность теоремы 2. Поскольку в выпуклом случае порядок $\|a_0-a\|$ по $h=h(\mathcal Q_0,\mathcal Q)$ есть $\sqrt{h}$, то в теореме 2 он точный. Пусть $K>r>0$ и $\varepsilon>0$. Рассмотрим в $\mathbb R^2$ множество $\mathcal Q=\{ a_0,a\}$, где $a_0=-e_2K$, $a=e_2(K+\varepsilon)$. Пусть $x_0=-e_2(K-r)$, $x=\varepsilon e_2$. При этом $a_0=P_{\mathcal Q}x_0$, $a=P_{\mathcal Q}x$. Тогда $\|a_0-a\|=2K+\varepsilon$, $\| x_0-x\|=K-r+\varepsilon$, что и показывает точность константы Липшица. Отметим, что выполнено условие $\operatorname{wc}(a_0,x_0-a_0,K)$. Замечание 4. Если в теореме 1 или 2 $P_{\mathcal Q}x=\varnothing$, то найдется последовательность $\{ a_k\}\subset\mathcal Q$ такая, что предел $\lim_{k\to\infty}\|x-a_k\|=\varrho (x,\mathcal Q)$ и предел $\limsup_{k\to\infty}\|a_0-a_k\|$ оценивается правой частью формулы (2.5) в теореме 1 либо правой частью формулы (2.6) в теореме 2. Рассмотрим в теореме 1 точку $x$, для которой $P_{\mathcal Q}x=\varnothing$. Поскольку для любого замкнутого подмножества из $\mathcal H$ множество точек, для которых существует единстенная метрическая проекция на это подмножество всюду плотно (см. [26]), то найдется последовательность $\{ x_k\}$, $x_k\to x$, $k\to\infty$, и $P_{\mathcal Q}x_k=a_k$. Пусть $C=2R/(R+r)$. Тогда в общей ситуации мы можем утверждать, что для каждой точки $x_k$ силу замечания 3 выполнена оценка $\|a_0-a_k\|\leqslant C\|x_0-x_k\|$ и
$$
\begin{equation*}
\limsup_{k\to\infty}\|a_0-a_k\|\leqslant C\limsup_{k\to\infty}\|x_0-x_k\|=C\|x_0-x\|.
\end{equation*}
\notag
$$
Аналогично рассматривается случай теоремы 2. § 3. Приложение к методу условного градиентаРассмотрим в $\mathbb R^n$ задачу с компактным множеством $\mathcal Q$ и липшицево дифференцируемой функцией $f$.Теорема 3. Пусть в задаче (3.1) $\mathcal Q\subset\mathbb R^n$ – замкнутое множество и точка $x_0\in \partial \mathcal Q$ – решение. Предположим, что функция $f\colon \mathbb R^n\to\mathbb R$ такая, что $\|f'(x)\|\geqslant m>0$ для всех $x\in\mathcal Q$, градиент $f'$ удовлетворяет условию Липшица с константой $L_1>0$ и множество $\mathcal Q$ удовлетворяет условию $\operatorname{sc}(-f'(x_0),R)$. Пусть $2RL_1/{m}<1$. Тогда итерации $x_1\in\mathcal Q$, $x_{k+1}\in \operatorname{Arg}\max_{x\in\mathcal Q}(-f'(x_k),x)$ сходятся к $x_0$ с линейной скоростью: Доказательство. Заметим, что выпуклый компакт $\operatorname{co}\mathcal Q$ также удовлетворяет условию $\operatorname{sc}(-f'(x_0),R)$. Из равенства
$$
\begin{equation*}
\|x_0-x_{k+1}\|=\|\mathcal Q(-f'(x_0))-\mathcal Q(-f'(x_k))\|,
\end{equation*}
\notag
$$
соотношений $\mathcal Q(-f'(x_k))\in (\operatorname{co}\mathcal Q)(-f'(x_k))$, $\mathcal Q(-f'(x_0))\,{=}\, (\operatorname{co}\mathcal Q)(-f'(x_0))$ и леммы 1 имеем
Теорема доказана. Заметим, что в отличие от известных ранее результатов, в теореме 2 ни функция, ни множество не предполагаются выпуклыми. § 4. Приложение к методу проекции градиентаСнова рассмотрим задачу (3.1) в $\mathbb R^n$. Приведем ряд теорем о сходимости метода проекции градиента (1.1) для разных типов функций и множеств. Всюду будет доказана линейная скорость сходимости алгоритма. В следующей теореме функция $f$ с непрерывным по Липшицу градиентом либо выпуклая, либо нет, а множество $\mathcal Q$ проксимально гладкое с константой $K>0$. Заметим, что устремляя $K\to +\infty$, мы получаем результат для выпуклого множества $\mathcal Q$. Теорема 4. Пусть в задаче (3.1) $\mathcal Q\subset\mathbb R^n$ и точка $x_0\in \partial \mathcal Q$ – решение. Пусть функция $f\colon \mathbb R^n\to\mathbb R$ выпуклая с липшицевым градиентом $f'$ с константой Липшица $L_1>0$ и $f'(x_0)\ne 0$, а компактное множество $\mathcal Q$ удовлетворяет условию $\operatorname{sc}(-f'(x_0),R)$. Кроме того, пусть множество $\mathcal Q$ проксимально гладкое с константой $K>0$. Пусть $L=\max_{x\in\mathcal Q}\|f'(x)\|$ и $\| f'(x_0)\|>{RL}/{K}$. Тогда алгоритм (1.1) с $\alpha_k=\alpha\in ( 0,2/{L_1})$ сходится с линейной скоростью: Если функция $f$ не выпуклая, то при условии $2RL_1+{RL}/{K}<\|f'(x_0)\|$ и $\alpha_k=\alpha>0$ имеет место линейная сходимость: Доказательство. Обозначим
$$
\begin{equation*}
\beta_k=\frac{2R}{2R+\alpha\|f'(x_0)\|-({R}/{K})\varrho (x_k-\alpha f'(x_k),\mathcal Q)}.
\end{equation*}
\notag
$$
Тогда с учетом формулы (2.1)
$$
\begin{equation}
\begin{aligned} \, \notag \|x_{k+1}-x_0\|^2 &=\|P_{\mathcal Q}(x_k-\alpha f'(x_k))-P_{\mathcal Q}(x_0-\alpha f'(x_0))\|^2 \\ \notag &\leqslant \beta_k^2\|(x_k-x_0)-\alpha (f'(x_k)-f'(x_0))\|^2 \\ &=\beta_k^2\bigl( \|x_k-x_0\|^2- 2\alpha (f'(x_k)-f'(x_0),x_k-x_0) \notag \\ &\qquad+\alpha^2\|f'(x_k)-f'(x_0)\|^2\bigr). \end{aligned}
\end{equation}
\tag{4.3}
$$
В силу выпуклости $f$ и условия Липшица с константой $L_1$ на градиент $f'$ получаем оценку (см. [7; лемма 1.19.5, (iii)])
$$
\begin{equation*}
L_1 (f'(x_k)-f'(x_0),x_k-x_0)\geqslant \|f'(x_k)-f'(x_0)\|^2.
\end{equation*}
\notag
$$
Отсюда следует оценка Из монотонности субдифференциала выпуклой функции и условия $0<\alpha<{2}/{L_1}$ вытекает неравенство $\alpha(2-\alpha L_1) (f'(x_k)-f'(x_0),x_k-x_0)\geqslant 0$, откуда
Пусть функция $f$ не выпуклая. Из оценки (4.3) в обозначениях теоремы вытекает неравенство
$$
\begin{equation*}
\|x_{k+1}-x_0\|^2\leqslant \beta_k^2 (1+\alpha L_1)^2\|x_k-x_0\|^2\leqslant \beta^2 (1+\alpha L_1)^2\|x_k-x_0\|^2,
\end{equation*}
\notag
$$
где
$$
\begin{equation*}
\beta=\frac{2R}{2R+\alpha\|f'(x_0)\|-\alpha L({R}/{K})}.
\end{equation*}
\notag
$$
Из условия получаем $\beta (1+\alpha L_1)<1$.
Теорема доказана. В следующей теореме компактное множество $\mathcal Q\subset\mathbb R^n$ произвольно. Теорема 5. Пусть в задаче (3.1) $\mathcal Q\subset\mathbb R^n$ и точка $x_0\in \partial \mathcal Q$ – решение. Пусть функция $f\colon \mathbb R^n\to\mathbb R$ выпуклая с липшицевым градиентом $f'$ с константой Липшица $L_1>0$ и $f'(x_0)\ne 0$, а компактное множество $\mathcal Q$ удовлетворяет условию $\operatorname{sc}(-f'(x_0),R)$. Пусть $2\|f'(x_0)\|>RL_1$. Тогда алгоритм (1.1) с Доказательство повторяет доказательство теоремы 4 с использованием вместо формулы (2.1) оценки (2.5) замечания 3. Теорема 6. Пусть выполнены условия теоремы 4, функция $f$ не выпуклая и константа $L$ неизвестна. Тогда при выборе первой точки $x_1\in\mathcal Q$ алгоритма (1.1) так, что выполнено условие при произвольном выборе $\alpha_k=\alpha>0$ имеет место линейная сходимость алгоритма: Доказательство. Из теоремы 1, формула (2.1), получаем
$$
\begin{equation*}
\begin{aligned} \, &\|x_{k+1}- x_0\| \\ &\ \leqslant\frac{2R}{2R+\alpha \|f'(x_0)\|-({R}/{K})\varrho(x_k-\alpha f'(x_k),\mathcal Q)}\|(x_k-\alpha f'(x_k))- (x_0-\alpha f'(x_0))\| \\ &\ \leqslant\frac{2R(1+\alpha L_1)}{2R+\alpha \|f'(x_0)\|-({R}/{K})\varrho(x_k-\alpha f'(x_k),\mathcal Q)}\|x_k-x_0\|. \end{aligned}
\end{equation*}
\notag
$$
Из оценки следует, что Из последней формулы по индукции получаем монотонное убывание последовательности $\{\|x_k{-}\,x_0\|\}$, откуда вытекает утверждение теоремы.
Теорема доказана. Приведем в заключение табл. 1 о свойствах линейной сходимости метода (1.1) для функции $f$ с непрерывным по Липшицу градиентом с константой Липшица $L_1$, и проксимально гладкого с константой $K>0$/произвольного компактного множества $\mathcal Q$. При этом предполагается, что множество $\mathcal Q$ удовлетворяет условию $\operatorname{sc}(-f'(x_0),R)$, $f'(x_0)\ne 0$, где $x_0$ – точка минимума и $L=\max_{x\in\mathcal Q}\|f'(x)\|$. Столбец “$P_{\mathcal Q}$” отсылает к соответствующему варианту условия Липшица для метрического проектора, который требуется для доказательства линейной сходимости. Таблица 1
Заметим, что во второй или четвертой строках таблицы выпуклость функции $f$ не исключается. Отметим также, что предельным переходом $K\to +\infty$ мы получаем соответствующий результат для выпуклого множества $\mathcal Q$. При невыполнения условия линейной сходимости в соответствующем столбце таблицы алгоритм может не сойтись. Приведем пример для первой строки: функция $f$ выпуклая и множество $\mathcal Q$ проксимально гладкое. В $\mathbb R^2$ рассмотрим функцию $f(\mathrm{x}_1,\mathrm{x}_2)=(\mathrm{x}_1^2+\mathrm{x}_2^2)/2$ и множество
$$
\begin{equation*}
\mathcal Q=\biggr\{ (\mathrm{x}_1,\mathrm{x}_2)\in\mathbb R^2\colon \mathrm{x}_1\leqslant 0,\, x_1^2+\biggl(x_2-\frac32\biggr)^2=\frac14\biggr\}.
\end{equation*}
\notag
$$
Минимум $f$ на $\mathcal Q$ достигается в точке $x_0=(0,1)$. Для множества $\mathcal Q$ выполнено опорное условие сильной выпуклости $\operatorname{sc}(-f'(x_0),R)$ для $f'(x_0)\,{=}\,(0,1)$ и $R=1/2$, множество $\mathcal Q$ проксимально гладкое с константой $K=1/2$ и $L=\max_{x\in\mathcal Q}\|f'(x)\|=2$. Имеем $\|f'(x_0)\|\,{=}\,1$ и условие не выполнено. Если взять начальную точку итераций $x_1=(0,2)$, то для всех $\alpha\in (0,1/4)$ получаем, что
$$
\begin{equation*}
x_2=P_{\mathcal Q}(x_1-\alpha f'(x_1))=P_{\mathcal Q}(0, 2-2\alpha)=x_1.
\end{equation*}
\notag
$$
Итак, при $\alpha\in (0,1/4)$ алгоритм зацикливается.
§ 5. Случай неограниченного множества $\mathcal Q$Рассмотрим для простоты случай выпуклых множества $\mathcal Q$ и функции $f$. Пусть в задаче (3.1) множество $\mathcal Q$ неограничено и $x_0$ – решение задачи, $f'(x_0)\ne 0$. Отметим, что в выпуклом случае минимум $x_0$ глобальный. Для $d> 0$ определим $\mathcal Q_d=\mathcal Q\cap\mathcal B_d(x_0)$. Предположим, что множество $\mathcal Q_d$ удовлетворяет условию $\operatorname{sc}(-f'(x_0),R)$. Пусть $L=\max_{x\in\mathcal Q_d}\|f'(x)\|$ и $\alpha>0$ выбрано так, что $d>2\alpha L$. Выберем $x_1\in \mathcal Q_{d-2\alpha L}$. Тогда для точки $x_2\in P_{\mathcal Q}(x_1-\alpha f'(x_1))$ имеем
$$
\begin{equation*}
\|x_2-x_1\|\leqslant 2\alpha \|f'(x_1)\|\leqslant 2\alpha L.
\end{equation*}
\notag
$$
Поэтому $x_2\in\mathcal Q_d$ и из теоремы 4 для $K=+\infty$ имеем
$$
\begin{equation*}
\| x_2-x_0\|\leqslant\frac{2R}{2R+\alpha\|f'(x_0)\|} \|x_1-x_0\|< d-2\alpha L.
\end{equation*}
\notag
$$
Продолжая рассуждения, получаем, что $x_k\in\mathcal Q_d$ для всех $k$ и имеет место линейная сходимость $x_k$ к $x_0$. В невыпуклом случае можно привести достаточные условия сходимости итераций к локальному экстремуму. § 6. ЗаключениеПриведенные условия сходимости градиентных методов имеют в первую очередь теоретическое значение. Заметим, что условие $\operatorname{sc}$ является типичным и для произвольного выпуклого компакта оно выполняется для почти всех в смысле меры Лебега векторов $p\in\partial \mathcal B_1(0)\subset\mathbb R^n$ с некоторым радиусом $R(p)>0$ (см. [27; теорема 4]). Кроме того, для выпуклого множества $\mathcal Q$ условие $\operatorname{sc}$ более общее, чем условие локальной сильной выпуклости из [11], см. [25; заключение]. Для невыпуклого множества $\mathcal Q$ условие локальной сильной выпуклости, определенное через модуль выпуклости, теряет смысл, в отличие от условия $\operatorname{sc}$. Поэтому изучение условия $\operatorname{sc}$ имеет потенциальный интерес. Этот интерес также мотивирован приложениями к градиентным методам, приведенными в настоящей работе. Заметим, что в случае липшицево дифференцируемой выпуклой функции $f\colon \mathbb R^n\to\mathbb R$ и выпуклого компактного множества $\mathcal Q\subset \mathbb R^n$ аналог теоремы 4 можно получить из условия квадратичного роста. Из условия $\operatorname{sc}(-f'(x_0),R)$ имеем
$$
\begin{equation*}
\biggl\|x_0+\frac{f'(x_0)}{\|f'(x_0)\|}R-x\biggr\|\leqslant R
\end{equation*}
\notag
$$
для всякого $x\in\mathcal Q$. Возводя в квадрат, получаем
$$
\begin{equation*}
\frac{\|f'(x_0)\|}{2R}\|x_0-x\|^2\leqslant (f'(x_0),x-x_0)
\end{equation*}
\notag
$$
и из выпуклости $f$ для всех $x\in\mathcal Q$ следует
$$
\begin{equation*}
f(x)-f(x_0)\geqslant (f'(x_0),x-x_0)\geqslant \frac{\|f'(x_0)\|}{2R}\|x_0-x\|^2.
\end{equation*}
\notag
$$
Последнее условие называется условием квадратичного роста. Отметим что для выпуклого множества $\mathcal Q$ и выпуклой липшицево дифференцируемой функции $f$, удовлетворяющей условию квадратичного роста на $\mathcal Q$, линейная сходимость метода проекции градиента с определенным постоянным шагом $\alpha_k=\alpha\,{>}\,0$ доказана в [28; теорема 13]. Некоторые уточнения этих результатов можно найти в [29].
Цитирование в формате AMSBIB
\RBibitem{Bal24} |
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Обратная связь: |
Пользовательское соглашение
|
Регистрация посетителей портала |
Логотипы |
|