| Математические заметки |
|
|
|
|
|
Эта публикация цитируется в 3 научных статьях (всего в 3 статьях) Достаточные условия линейной сходимости одного алгоритма для нахождения метрической проекции точки на выпуклый компакт М. В. Балашов Институт проблем управления им. В. А. Трапезникова РАН, г. Москва
Англоязычная версия:
Mathematical Notes, 2023, Volume 113, Issue 5, Pages DOI: https://doi.org/10.1134/S0001434623050036 
Реферативные базы данных:
  1. ВведениеРассмотрим $n$-мерное вещественное евклидово пространство $\mathbb R^n$ со скалярным произведением $(\,{\cdot}\,,\,{\cdot}\,)$ и нормой $\| \cdot\| =\sqrt{(\,{\cdot}\,,\,{\cdot}\,)}$. Определим шар $\mathcal B_r(0)$ радиуса $r>0$ с центром в нуле. Для множества $\mathcal Z\subset\mathbb R^n$ определим границу $\partial \mathcal Z$ и внутренность $\operatorname{int} \mathcal Z$. Пусть $\mathcal Z\subset\mathbb R^n\setminus\{ 0\}$ – выпуклое компактное подмножество, для которого известна опорная функция $f(p)=s(p,\mathcal Z)=\max_{z\in \mathcal Z}(p,z)$, $p\in\mathbb R^n$. Рассмотрим задачу нахождения метрической проекции точки $0\in\mathbb R^n$ на $\mathcal Z$. На языке опорной функции $f(p)$ эту задачу можно переформулировать в виде Пусть $z_0\in\mathcal Z$ – метрическая проекция нуля на $\mathcal Z$. Легко видеть, что решение задачи (1.1) есть $p_0=-z_0/\| z_0\|$. При этом $J=(p_0,z_0)$ и $\| z_0\|=-J$.Обозначим для $p\in\mathbb R^n$ через $\partial f(p)$ субдифференциал функции $f$ в смысле выпуклого анализа, т.е. множество всех субградиентов $z\in\mathcal Z$
$$
\begin{equation*}
\partial f(p)=\bigl\{ z\in \mathcal Z\colon (p,z)=f(p)\bigr\}.
\end{equation*}
\notag
$$
Заметим, что субдифференциал $\partial f(p)$ является опорным подмножеством $\mathcal Z (p)$ множества $\mathcal Z$ в направлении $p$, т.е. $\mathcal Z (p)=\partial f(p)$. Нормальный конус $\mathcal N (\mathcal Z, z)$ в точке $z\in\partial\mathcal Z$ определяется как
$$
\begin{equation*}
\mathcal N (\mathcal Z, z)=\bigl\{ p\in\mathbb R^n\colon (p,z)=f(p)\bigr\}.
\end{equation*}
\notag
$$
Пусть $\mathcal S_1=\partial \mathcal B_1(0)$ евклидова сфера радиуса 1 с центром в нуле. Через $P_{\mathcal S_1}$ обозначим метрический проектор на сферу $\mathcal S_1$. В работе обсуждается следующий вопрос: при каких минимальных условиях на множество $\mathcal Z$ итерации проекционного алгоритма
$$
\begin{equation}
p_1\in\mathcal S_1, \qquad p_{k+1}=P_{\mathcal S_1}(p_k-tz_k), \quad z_k\in\partial f(p_k), \quad t>0, \quad k=1,2,\dots,
\end{equation}
\tag{1.2}
$$
сходятся к решению $p_0$ с линейной скоростью, т.е. со скоростью геометрической прогрессии? Шаг $t>0$ здесь один для всех $k$, выбор субградиента $z_k\in \partial f(p_k)$ произволен. Напомним [1], [2], что в общей ситуации для линейной сходимости метода проекции градиента нужна липшицева дифференцируемость целевой функции. В нашей задаче это означает липшицеву дифференцируемость $f$ в окрестности $\mathcal S_1$. Известно, что условие Липшица градиента $f'(p)$ на единичной сфере $\mathcal S_1$ с константой Липшица $R>0$ эквивалентно сильной выпуклости множества $\mathcal Z$ с радиусом $R>0$, т.е. $\mathcal Z=\bigcap_{x\in \mathcal N}\mathcal B_R(x)$ для некоторого подмножества центров $\mathcal N\subset\mathbb R^n$ [3; теорема 4.3.2]. Последнее эквивалентно опорному принципу для сильно выпуклых множеств: для всякого $p\in\mathcal S_1$ выполнено $\mathcal Z\subset B_R(\mathcal Z(p)-Rp)$. Таким образом, сильная выпуклость множества $\mathcal Z$ необходима и достаточна для липшицевости градиента $f'(p)$. При этом, сильная выпуклость $\mathcal Z$ также дает линейную сходимость итераций (1.2) при произвольном выборе $p_1\in\mathcal S_1$, $f(p_1)\leqslant 0$ [4]. При негладкости и выпуклости целевой функции имеются результаты о сублинейной скорости сходимости метода проекции градиента. Однако, она может быть линейной в случае т. н. условия острого минимума (sharpness condition), см. детали в [5; теорема 2, гл. 5, § 3]. Условие острого минимума в задаче (1.1) означает существование такого числа $\alpha>0$, что для всех $p\in\mathcal S_1$ (может быть из окрестности решения $p_0$) выполнено неравенство $f(p)-f(p_0)\geqslant \alpha \| p-p_0\|$. Последнее время условие острого минимума позволило доказать линейную скорость сходимости метода проекции градиента для некоторых классов задач минимизации невыпуклых функций при выпуклых и невыпуклых ограничениях [6], [7]. Задача (1.1) имеет самостоятельное значение в вычислительной геометрии и возникает в различных приложениях. Одно из приложений – это различные задачи о поведении множества достижимости $\mathcal R(\tau)$ линейной управляемой системы где $x(\tau)\in\mathbb R^n$, $A\in\mathbb R^{n\times n}$, $\mathcal U\subset\mathbb R^n$ – компактное подмножество, содержащее ноль, и $\mathcal R(\tau)=\int_{0}^{\tau}e^{As}\mathcal U\, ds$. Последний интеграл понимается в смысле Аумана [8].При решении для данного $\tau>0$ задачи о непустоте пересечения $\mathcal R(\tau)\cap\mathcal M$, где $\mathcal M\subset\mathbb R^n$ – выпуклое компактное подмножество, вопрос может быть переформулирован так: выяснить, верно ли, что
$$
\begin{equation*}
0\notin \mathcal Z(\tau)=\mathcal R(\tau)+ (-\mathcal M) \qquad\text{или}\qquad \min_{\| p\|=1}s(p,\mathcal Z(\tau))< 0?
\end{equation*}
\notag
$$
В работе [9; пример 2] была доказана сходимость итераций (1.2) для сильно выпуклых множеств $\mathcal R(\tau)$ и $\mathcal M$, т.е. каждое из множеств можно представить в виде пересечения замкнутых шаров одного радиуса (для каждого множества свой радиус). При этом $\mathcal M$ дополнительно должно иметь в определенном смысле гладкую границу, а именно $\mathcal M=\mathcal M_0+\mathcal B_r(0)$, где $\mathcal M_0$ – выпуклый компакт. Начальное приближение $p_1\in\mathcal S_1$ должно выбираться достаточно близко к решению $p_0$. Приведем другой пример. Пусть $\mathcal M$, $\mathcal M_0$ и $\mathcal R$ из $\mathbb R^n$ – выпуклые компакты, такие, что $\mathcal R\not\subset \mathcal M$ и 1) $\mathcal M=\mathcal M_0+\mathcal B_r(0)$, 2) $\mathcal R$ сильно выпукло с радиусом $R>0$, 3) $r>R$. Мы хотим найти
$$
\begin{equation}
J=\max_{x\in \mathcal R} \varrho (x,\mathcal M), \qquad \varrho (x,\mathcal M)=\inf_{y\in \mathcal M}\| x-y\|.
\end{equation}
\tag{1.4}
$$
Величина $J$ называется полурасстоянием по Хаусдорфу от $\mathcal R$ до $\mathcal M$. Задача (1.4) и способы ее решения обсуждались в [10]. Пусть $\mathcal M\,\frac{\,*}{}\ \mathcal R =\bigcap_{x\in\mathcal R}(\mathcal M-x)$ – геометрическая разность $\mathcal M$ и $\mathcal R$. Легко видеть, что
$$
\begin{equation*}
J=\max_{x\in \mathcal R} \varrho (0,\mathcal M-x)\leqslant \varrho \biggl (0,\bigcap_{x\in\mathcal R}(\mathcal M-x)\biggr) =\varrho (0,\mathcal M\,\frac{\,*}{}\ \mathcal R).
\end{equation*}
\notag
$$
С другой стороны, из свойства полного выметания для сильно выпуклых множеств, см. [3; теорема 3.1.2], $\mathcal R+(B_r(0)\,\frac{\,*}{}\ \mathcal R)=B_r(0)$. Добавляя к обеим частям $\mathcal M_0$, получаем $\mathcal R + (\mathcal M\,\frac{\,*}{}\ \mathcal R)=\mathcal M$. Отсюда и из включения $\mathcal R\subset \mathcal M+B_J(0)$, вытекающего из (1.4), получаем $0\in (\mathcal M\,\frac{\,*}{}\ \mathcal R)+B_J(0)$, т.е. $J\geqslant \varrho (0,\mathcal M\,\frac{\,*}{}\ \mathcal R)$. Таким образом, $J=\varrho (0,\mathcal M\,\frac{\,*}{}\ \mathcal R)$. Легко видеть, что из $\mathcal R + (\mathcal M\,\frac{\,*}{}\ \mathcal R)=\mathcal M$ для всякого $p\in\mathbb R^n$ вытекает равенство $s(p,\mathcal M\,\frac{\,*}{}\ \mathcal R)=s(p,\mathcal M)-s(p,\mathcal R)$ и В настоящей работе мы хотим по возможности ослабить условия на множество $\mathcal Z$, и в первую очередь условие сильной выпуклости. Условие сильной выпуклости $\mathcal Z$ мы заменим на некоторое локальное опорное условие шаром для множества $\mathcal Z$ в точке $z_0$. Введем определения. Определение 1. Будем говорить, что выпуклый компакт $\mathcal Z\subset\mathbb R^n$ удовлетворяет внешнему опорному условию в точке $z_0\in\partial\mathcal Z$ для единичного нормального вектора $p_0\in\mathcal N (\mathcal Z,z_0)$ и константы $R>0$, если Заметим, что само множество $\mathcal Z$ может не быть даже строго выпуклым. Мы докажем, что при выполнении этого локального опорного условия в точке $z_0\in\mathcal Z$ и для вектора $p_0=-z_0/\| z_0\|$, где $p_0$ – решение задачи (1.1), метод проекции градиента (1.2) сходится с линейной скоростью. При этом, отсутствие локального опорного условия в точке $z_0\in\mathcal Z$ может влечь расходимость метода (1.2), например его зацикливание. Соответствующий пример 2 приведен в конце статьи. Пример 1. Отметим, что если множество $\mathcal Z$ удовлетворяет определению 1 для каждой граничной точки $z_0\in\partial\mathcal Z$ и каждого единичного вектора $p_0\in\mathcal N(\mathcal Z,z_0)$ с константой $R=R(z_0,p_0)$, зависящей от $z_0$ и $p_0$, то множество $\mathcal Z$ не обязательно сильно выпукло с некоторым радиусом. Рассмотрим пример на плоскости. Пусть выпуклый компакт $\mathcal Z$ имеет границу $\partial B_1(0)$ во 2–4 четвертях. Пусть
$$
\begin{equation*}
\varphi_0=0, \qquad \varphi _{k+1}=\varphi_k+\frac{1}{2^{k+1}}\,\frac{\pi}{2}, \quad a_k=(\cos\varphi_k,\sin\varphi_k), \quad k=0,1,\dotsc\,.
\end{equation*}
\notag
$$
При $k=0,1,\dots$ зададим дугу $D_k$ окружности радиуса $k+1$ с концами $a_k$ и $a_{k+1}$, радианной мерой меньше $\pi$ и лежащую выше отрезка $[a_k,a_{k+1}]$. В первой четверти определим границу $\partial \mathcal Z$ как $\bigcup_{k\geqslant 0}D_k$. Легко видеть, что для каждой точки $z_0\in \partial \mathcal Z$ и любого единичного вектора $p_0\in \mathcal N(\mathcal Z,z_0)$ выполнено определение 1. Однако множество $\mathcal Z$ не сильно выпукло, поскольку $\sup_{z_0,p_0}R(z_0,p_0)=+\infty$. Определение 2. Будем говорить, что выпуклый компакт $\mathcal Z\subset\mathbb R^n$ удовлетворяет внутреннему опорному условию в точке $z_0\in\partial\mathcal Z$ для единичного нормального вектора $p_0\in\mathcal N (\mathcal Z,z_0)$ и константы $r>0$, если Определение 2 и его обобщения рассматривались ранее в работе [11]. Для множества $\mathcal N\subset\mathbb R^n$ через $\operatorname{aff}\mathcal N$ обозначим аффинную оболочку множества $\mathcal N$, через $\operatorname{cone}\mathcal N$ обозначим коническую оболочку множества $\mathcal N$. Здесь и ниже мы используем обозначение $f(p)=s(p,\mathcal Z)$. Определим подмножество $\mathcal S=\bigl\{ p\in\mathcal S_1\colon f(p)\leqslant 0\bigr\}$. Пусть
$$
\begin{equation*}
\mathcal K=\operatorname{cone}\mathcal Z=\bigl\{ \lambda z\colon z\in\mathcal Z,\, \lambda\geqslant 0\bigr\}
\end{equation*}
\notag
$$
есть коническая оболочка множества $\mathcal Z$. Множество $\mathcal K$ есть выпуклый замкнутый конус. Определим полярный конус
$$
\begin{equation*}
\mathcal K^-=\bigl\{ p\in\mathbb R^n\colon (p,q)\leqslant 0\ \forall q\in\mathcal K\bigr\}.
\end{equation*}
\notag
$$
Лемма 1. В рассматриваемых обозначениях выполнено равенство $\mathcal S=\mathcal K^-\cap \mathcal S_1$. Доказательство. Пусть $p\in \mathcal S$. Тогда для любого $z\in\mathcal Z$ т.е. для любых $z\in\mathcal Z$ и $q\in\operatorname{cone} \{z\}\subset\mathcal K$ выполнено $(p,q)\leqslant 0$ и $p\in \mathcal K^-$.
Допустим, $p\notin \mathcal S$. Для любого $z\in \partial f(p)$ имеем $(p,z)=f(p)>0$. Зафиксируем $z\in \partial f(p)$ и $q\in \operatorname{cone}\{z\}\subset \mathcal K$, $q\ne 0$. Тогда $(p,q)>0$ и $p\notin \mathcal K^-$. Лемма доказана. Доказательство. Для доказательства надо умножить обе части доказываемого неравенства на $\sqrt{\| u\|\cdot \| v\|}$ и возвести в квадрат. Пусть $\mathcal K$ – выпуклый замкнутый конус и $p_0\in\mathcal S_1\cap\operatorname{int} \mathcal K$. Через $\mathcal K_0(p_0)$ будем обозначать максимальный по включению конус вращения с осью $\operatorname{cone}p_0$, вписанный в $\mathcal K$. Конусом вращения называется конус, у которого угол между осью и любой прямолинейной образующей один и тот же. 2. Леммы об опорных шарахЛемма 3. Пусть $\mathcal Z\subset\mathbb R^n$ – выпуклый компакт, $0\notin \mathcal Z$, $f(p)=s(p,\mathcal Z)$. Положим $z_0=P_{\mathcal Z}0$, $p_0=-z_0/\| z_0\|$, $\mathcal K=\operatorname{cone}\mathcal Z$ и $\mathcal K_0^-=\mathcal K_0^-(p_0)$ – максимальный конус вращения с осью $\operatorname{cone}p_0$, вписанный в $\mathcal K^-$. Допустим, что $\mathcal Z$ удовлетворяет определению 1 в точке $z_0\in\partial\mathcal Z$ для единичного нормального вектора $p_0$ и константы $R>0$. Тогда итерации $\{p_k\}$ алгоритма (1.2) при $k=1,2,\dots$, произвольном выборе $p_1\in \mathcal S_1\cap \mathcal K_0^-$, $t\in (0,1/R)$ и $z_k\in\partial f(p_k)$ удовлетворяют условию Перед доказательством отметим, что из включения $\mathcal Z\subset \mathcal B_{R}(z_0-Rp_0)$ следует $\mathcal K\subset \mathcal N=\operatorname{cone}\mathcal B_{R}(z_0-Rp_0)$, и отсюда $\mathcal N^-\subset \mathcal K^-$. Легко видеть, что $\mathcal N$ – конус вращения с осью $\operatorname{cone}z_0= \operatorname{cone}(-p_0)$ и углом между осью и образующей $\arcsin(R/(R+\|z_0\|))$. Значит, конус $\mathcal N^-$ также есть конус вращения с осью $\operatorname{cone}p_0$ и углом между осью и образующей
$$
\begin{equation}
\varphi=\varphi (z_0,R)=\frac{\pi}{2}-\arcsin\frac{R}{R+\|z_0\|}.
\end{equation}
\tag{2.2}
$$
Поэтому в лемме 3 конус $\mathcal K_0^-$ имеет непустую внутренность, так как $\mathcal K_0^-\supset \mathcal N^-$. Доказательство. В силу леммы 1 $p_1\in\mathcal S$ и $f(p_1)\leqslant 0$.
Допустим, на $k$-м шаге получена точка $p_k\in \mathcal S_1\cap \mathcal K_0^-\subset\mathcal S$. Тогда $f(p_k)\leqslant 0$,
$$
\begin{equation*}
\begin{gathered} \, \| p_k - tz_k\|\geqslant (p_k,p_k-tz_k)=1-tf(p_k)\geqslant 1, \\ \| p_0 - tz_0\|\geqslant (p_0,p_0-tz_0)=1-tf(p_0)=1+t\| z_0\| \end{gathered}
\end{equation*}
\notag
$$
и поэтому
$$
\begin{equation*}
\| P_{\mathcal S_1}(p_k-tz_k)-P_{\mathcal S_1}(p_0-tz_0)\|\leqslant \lambda\| (p_k-tz_k)-(p_0-tz_0)\|,
\end{equation*}
\notag
$$
где в силу леммы 2 имеем $\lambda=1/\sqrt{1+t\| z_0\|}$. Отсюда
$$
\begin{equation*}
\begin{aligned} \, \| p_{k+1}-p_0\|^2 &=\| P_{\mathcal S_1}(p_k-tz_k)-P_{\mathcal S_1}(p_0-tz_0)\|^2 \leqslant \lambda^2\| (p_k-tz_k)-(p_0-tz_0)\|^2 \\ &\leqslant\lambda^2 \bigl(\| p_k-p_0\|^2-2t(p_k-p_0,z_k-z_0)+t^2\| z_k-z_0\|^2\bigr). \end{aligned}
\end{equation*}
\notag
$$
Из включение $\mathcal Z\subset \mathcal B_{R}(z_0-Rp_0)$ вытекает неравенство
$$
\begin{equation*}
\|z_0-Rp_0 -z_k \|\leqslant R \qquad\text{или}\qquad \| z_k-z_0\|^2\leqslant 2R (p_0,z_0-z_k).
\end{equation*}
\notag
$$
Последнее эквивалентно С учетом этой оценки и неравенства $(p_k,z_k-z_0)\geqslant 0$ имеем
$$
\begin{equation*}
\begin{gathered} \, -2t(p_k-p_0,z_k-z_0)= -2t(p_k,z_k-z_0) -2t(p_0,z_0-z_k) \leqslant -\frac{t}{R}\| z_k-z_0\|^2, \\ \begin{split} \| p_{k+1}-p_0\|^2 &\leqslant\lambda^2\biggl(\| p_{k}-p_0\|^2-\frac{t}{R}\| z_k-z_0\|^2+t^2\| z_k-z_0\|^2 \biggr) \\ &=\lambda^2\biggl(\| p_{k}-p_0\|^2-t\biggl(\frac1R-t\biggr)\|z_k-z_0\|^2\biggr). \end{split} \end{gathered}
\end{equation*}
\notag
$$
Из полученной оценки $\| p_{k+1}-p_0\|\leqslant \| p_k-p_0\|$ и поэтому $p_{k+1}\in \mathcal S_1\cap\mathcal K_0^-\subset\mathcal S$. Лемма доказана. Лемма 4. Пусть $\mathcal Z\subset\mathbb R^n$ – выпуклый компакт, $0\notin \mathcal Z$, $f(p)=s(p,\mathcal Z)$. Положим $z_0=P_{\mathcal Z}0$, $p_0=-z_0/\| z_0\|$. Допустим, что $\mathcal Z$ удовлетворяет определению 2 в точке $z_0\in\partial\mathcal Z$ для единичного нормального вектора $p_0$ и константы $r>0$. Тогда для любого единичного вектора $p$ и точки $z_p\in\partial f(p)$ выполняется неравенство Доказательство. Определим для $q\in\mathcal S_1$ множества
Зафиксируем $p\in\mathcal S_1\setminus\{ p_0\}$ и $z_p\in\partial f(p)$. В силу определения 2 точка $z_p$ содержится в пересечении полупространств $\mathcal N=\mathcal H_{p_0}^-\cap \mathcal H_p^+$. Положим
$$
\begin{equation*}
w=P_{\partial\mathcal H_{p_0}^-\cap\partial \mathcal H_p^+}z_0
\end{equation*}
\notag
$$
и определим двумерную плоскость $\mathcal L=\operatorname{aff} \bigl\{ z_0,w,z_0-rp_0+rp\bigr\}$.
Пусть $\alpha$ – угол
$$
\begin{equation*}
\angle (z_0,z_0-rp_0,w)=\angle (z_0-rp_0+rp,z_0-rp_0,w).
\end{equation*}
\notag
$$
Заметим, что $\sin\alpha=\| p-p_0\|/2$, см. рис. 1. Серым цветом показано множество $\mathcal N\cap\mathcal L$.
Если угол $\alpha\leqslant {\pi}/{4}$, то расстояние $\| z_0-z_p\|$ не менее $\| z_0-w\|$. Последняя величина есть расстояние от $z_0$ до $\mathcal N\ni z_p$. Поскольку $\angle (w,z_0,z_0-rp_0)={\pi}/{2}$, то
$$
\begin{equation*}
\| z_p-z_0\|\geqslant \| z_0-w\|=r \operatorname{tg} \alpha\geqslant r \sin\alpha=\frac{r}{2}\| p-p_0\|.
\end{equation*}
\notag
$$
Если угол ${\pi}/{4}<\alpha<{\pi}/{2} $, то расстояние $\| z_0-z_p\|$ не менее расстояния от точки $z_0$ до стороны угла $\mathcal N\cap \mathcal L$, продолжение которой не содержит $z_0$. Пусть $u$ – проекция точки $z_0$ на соответствующую сторону угла $\mathcal N\cap \mathcal L$. Тогда вектор $z_0-u$ параллелен вектору $z_0-rp_0+rp$ и тем самым вектор $z_0-u$ перпендикулярен плоскости $\partial \mathcal H_p^+$. Из треугольника $wz_0u$
$$
\begin{equation*}
\| z_p-z_0\|\geqslant \| z_0-u\|=r \operatorname{tg} \alpha\sin (\pi-2\alpha) =r \operatorname{tg} \alpha\sin 2\alpha= 2\sin\alpha\frac{r}{2}\| p-p_0\|\geqslant \frac{r}{2}\| p-p_0\|.
\end{equation*}
\notag
$$
В случае $p=-p_0$ получаем
$$
\begin{equation*}
\| z_p-z_0\|\geqslant r\|p-p_0\|\geqslant \frac{r}{2}\|p-p_0\|.
\end{equation*}
\notag
$$
Таким образом, в любом случае выполнено утверждение леммы. Лемма доказана. 3. Сходимость итераций: скорость сходимости и выбор начального приближенияТеорема 1. Пусть $\mathcal Z\subset\mathbb R^n$ – выпуклый компакт, $0\notin \mathcal Z$. Положим $z_0=P_{\mathcal Z}0$, $p_0=-z_0/\| z_0\|$, $\mathcal K=\operatorname{cone}\mathcal Z$ и $\mathcal K_0^-=\mathcal K_0^-(p_0)$ – максимальный конус вращения с осью $\operatorname{cone}p_0$, вписанный в $\mathcal K^-$. Допустим, что $\mathcal Z$ удовлетворяет определению 1 в точке $z_0\in\partial\mathcal Z$ для единичного нормального вектора $p_0$ и константы $R>0$. Тогда итерации $\{p_k\}$ алгоритма (1.2) при $k=1,2,\dots$, произвольном выборе $p_1\in \mathcal S_1\cap \mathcal K_0^-$, $t\in (0,1/R)$ и $z_k\in\partial f(p_k)$ удовлетворяют условию и тем самым $\{p_k\}$ сходится к решению $p_0$ с линейной скоростью. Доказательство. Доказательство состоит в применении леммы 3.
Заметим, что скорость сходимости зависит от величины $\| z_0\|$ и мала при малом $\| z_0\|$. В случае выполнения внутреннего опорного условия, скорость сходимости равномерно оценивается по $z_0$. Теорема 2. Пусть выполнено условие теоремы 1. Допустим, что $\mathcal Z$ удовлетворяет определению 2 в точке $z_0\in\partial\mathcal Z$ для единичного нормального вектора $p_0$ и константы $r>0$. Тогда и тем самым $\{p_k\}_{k=1}^{\infty}$ сходится к решению $p_0$ с линейной скоростью. Доказательство. Доказательство сводится к применению оценки (2.3) в формуле (2.1).
Таким образом, при выполнении определений 1 и 2 сходимость в теореме 2 равномерна по $\| z_0\|=\| P_{\mathcal Z}0\|$ и оценивается по формуле
$$
\begin{equation}
\| p_{k+1}-p_0\|\leqslant \sqrt{1-\frac{r^2}{4}t\biggl(\frac1R-t\biggr)}\| p_{k}-p_0\|.
\end{equation}
\tag{3.1}
$$
Выбор начальной точки итераций $p_1\in\mathcal S_1\cap \mathcal K_0^-$ также зависит от величины $\| z_0\|$. В частности, конус $\mathcal K_0^-$ может иметь малый угловой размер, например, если величина $\| z_0\|$ мала, а множество $\mathcal Z$ имеет гладкую границу. Это может составить проблему при поиске начальной точки итераций $p_1$. Покажем, что в некоторых случаях выбор $p_1$ можно осуществлять независимо от значения $\| z_0\|$. Теорема 3. Пусть выполнено условие теоремы 2 и $C=1+\max_{z\in\mathcal Z}\| z\|$. Тогда при произвольном выборе $0<t < \min\{1/R,1/C\}$ такого, что при любом начальном условии $p_1\in\mathcal S_1$, $\| p_1-p_0\|\leqslant L$, итерации $\{p_k\}_{k=1}^{\infty}$ сходятся к $p_0$ с линейной скоростью: Доказательство. Пусть построено $p_k\in\mathcal S_1$ такое, что $\| p_k-p_0\|\leqslant L$. Повторяя доказательство леммы 3, получаем
$$
\begin{equation}
\| p_{k+1}-p_0\|\leqslant \sqrt{\frac{1-r^2t(1/R-t)/4}{(1-t\| z_k\|)(1+t\| z_0\|)}}\| p_{k}-p_0\|.
\end{equation}
\tag{3.2}
$$
Член $1-t\| z_k\|$ возникает в знаменателе в силу оценки $\| p_k-tz_k\|\geqslant 1-t\|z_k\|$ и леммы 2, в силу которой в доказательстве леммы 3 надо взять
$$
\begin{equation*}
\lambda=\frac{1}{\sqrt{1-t\| z_k\|}\sqrt{1+t\| z_0\|}}.
\end{equation*}
\notag
$$
Из леммы 3 также получаем, что
$$
\begin{equation*}
\| z_k-z_0\|\leqslant \frac{1}{\sqrt{t(1/R-t)}}\| p_k-p_0\|.
\end{equation*}
\notag
$$
Отсюда следует оценка
$$
\begin{equation*}
\| z_k\|-\|z_0\|\leqslant \| z_k-z_0\|\leqslant \frac{1}{\sqrt{t(1/R-t)}}\| p_k-p_0\|\leqslant \frac{1}{\sqrt{t(1/R-t)}}L.
\end{equation*}
\notag
$$
Из определения $L$ вытекает неравенство
$$
\begin{equation*}
\begin{gathered} \, 1-\frac{r^2}{4}t\biggl(\frac1R-t\biggr)\leqslant 1-t(\|z_k\|-\|z_0\|)-t^2\|z_k\|\cdot\|z_0\|- t^2(C^2-\|z_k\|\cdot\|z_0\|), \\ 1-\frac{r^2}{4}t\biggl(\frac1R-t\biggr)\leqslant (1-t\|z_k\|)(1+t\|z_0\|)-t^2(C^2-\|z_k\|\cdot\|z_0\|). \end{gathered}
\end{equation*}
\notag
$$
Из последнего неравенства с учетом $\|z_k\|\leqslant C-1$, $\|z_0\|\leqslant C-1$, $t\|z_0\|< 1$ получаем оценку Таким образом, $\| p_{k+1}-p_0\|\leqslant L$. Теорема доказана. Отметим еще один важный случай гладкого множества $\mathcal Z$: $\mathcal Z=\mathcal Z_0+ \mathcal B_r(0)$, где $\mathcal Z_0$ – выпуклый компакт. В этом случае можно рассмотреть множество $\mathcal Z_1=\mathcal Z_0+\mathcal B_{r/2}(0)$, для которого расстояние от нуля до $\mathcal Z_1$ будет не менее $r/2$. Решив задачу (1.1) для множества $\mathcal Z_1$, мы очевидно получаем и решение для $\mathcal Z$. Приведем способ выбора $p_1$ из лебегова множества функции $f$. Это имеет практический смысл при условии, что имеется информация о радиусе $R$ из определения 1 для множества $\mathcal Z$ и оптимальном значении $J$. Лемма 5. Пусть в условиях леммы 3 $p_1\in\mathcal S_1$ выбрано так, что Доказательство. Из неравенства
$$
\begin{equation*}
f(p_1)\leqslant \frac{RJ}{R+|J|}=J+\frac{|J|^2}{R+|J|}=f(p_0)+\frac{|J|^2}{R+|J|},
\end{equation*}
\notag
$$
где $f(p_1)=(p_1,z_{p_1})$, $z_{p_1}\in\mathcal Z(p_1)$, вытекает
$$
\begin{equation*}
(p_1,z_{p_1})\leqslant (p_0,z_0)+\frac{|J|^2}{R+|J|}.
\end{equation*}
\notag
$$
Отсюда
$$
\begin{equation*}
0\leqslant (p_1,z_{p_1})- (p_1,z_0)\leqslant (p_0-p_1,z_0)+\frac{|J|^2}{R+|J|} =-|J|+|J|(p_1,p_0)+|J|\biggl(1-\frac{R}{R+|J|}\biggr),
\end{equation*}
\notag
$$
т.е. Таким образом, угол между $p_1$ и $p_0$ не более $\operatorname{arccos}(R/(R+|J|))$, т.е. $p_1\in \mathcal K_0^{-}$, см. (2.2). Лемма доказана. Покажем, что в задаче (1.1) выполнено условие квадратичного роста. Для функции $f(p)=s(p,\mathcal Z)$ имеем для решения $p_0\in\mathcal S_1$, произвольной точки $p\in\mathcal S_1$ и произвольной точки $z_p\in\partial f(p)$
$$
\begin{equation*}
f(p)-f(p_0)=(p,z_p)-(p_0,z_0)=(p,z_p-z_0)+(p-p_0,z_0).
\end{equation*}
\notag
$$
Первое слагаемое $(p,z_p-z_0)\geqslant 0$. Для второго слагаемого из $z_0=-|J|p_0$, где $J$ – оптимальное значение функционала в (1.1), получаем
$$
\begin{equation*}
f(p)-f(p_0)\geqslant (p-p_0,-|J|p_0)=|J|(1-(p,p_0))=\frac{|J|}{2}\| p-p_0\|^2.
\end{equation*}
\notag
$$
Пусть $0<r<L$, $\| p_0\|=1$ и $\mathcal Z=B_r(-Lp_0)$. Для произвольного $p\in\mathcal S_1$
$$
\begin{equation*}
f(p)-f(p_0)=(r-L(p,p_0))-(r-L)=L(1-(p,p_0))=\frac{L}{2}\| p-p_0\|^2.
\end{equation*}
\notag
$$
Последнее означает, что условие острого минимума в задаче (1.1) может не выполняться. В заключение приведем пример, который показывает важность опорного условия из определения 1 для сходимости алгоритма (1.2). Пример 2. Пусть множество $\mathcal Z\subset\mathbb R^2$ локально устроено как надграфик функции $y=x^4+1$ в окрестности точки $(0,1)$. Допустим, для любого единичного вектора $p=(\mathrm p_1,\mathrm p_2)\in\mathcal K$, где $\mathcal K$ – выпуклый конус с непустой внутренностью и осью симметрии $\operatorname{cone}(0,-1)$, опорный элемент $\mathcal Z$ есть опорный элемент надграфика $y=x^4+1$, т.е. где $f(p)=s(p,\mathcal Z)=(p,z(p))$, Отметим, что радиус кривизны графика $y=x^4+1$ в точке $(0,1)$ равен $+\infty$ и поэтому определение 1 не выполняется для точки $(0,1)$ и вектора $(0,-1)$. Выберем единичный вектор $p=(\mathrm p_1,\mathrm p_2)$ из условия $p\in\mathcal K$,
$$
\begin{equation}
\mathrm p_2<0, \qquad \frac13 |\mathrm p_2|>4^{1/3} \mathrm p_1^{2/3}|\mathrm p_2|^{1/3} +\frac{\mathrm p_1^2}{4|\mathrm p_2|}.
\end{equation}
\tag{$*$}
$$
Условие ($*$) выполняется для всех единичных векторов $p$, достаточно близких к вектору $(0,-1)$. Пусть также $\mathrm p_1>0$. Рассмотрим один шаг алгоритма (1.2): $\overline p(t)=p- t z(p)= (\overline{\mathrm p}_1(t),\overline{\mathrm p}_2(t))$. Здесь
$$
\begin{equation*}
\begin{gathered} \, \overline{\mathrm p}_1(t)=\frac{\mathrm p_1-({\mathrm p_1}/({4|\mathrm p_2|}))^{1/3}t} {\sqrt{\bigl(\mathrm p_1-(\mathrm p_1/(4|\mathrm p_2|))^{1/3}t\bigr)^2 +\bigl( \mathrm p_2-t-(\mathrm p_1/(4|\mathrm p_2|))^{4/3}t\bigr)^2}}, \\ \overline{\mathrm p}_2(t)=-\sqrt{1 -\overline{\mathrm p}^2_1(t)}. \end{gathered}
\end{equation*}
\notag
$$
При $t=0$ имеем $\overline{\mathrm p}_1(0)=\mathrm p_1$. Пусть $t_0=3\cdot 4^{1/3}\mathrm p_1^{2/3}| \mathrm p_2|^{1/3}$. Тогда
$$
\begin{equation*}
\mathrm p_1-\biggl(\frac{\mathrm p_1}{4|\mathrm p_2|}\biggr)^{1/3}t_0=-2\mathrm p_1, \qquad \mathrm p_2-t_0-\biggl(\frac{\mathrm p_1}{4|\mathrm p_2|}\biggr)^{4/3}t_0=-|\mathrm p_2|-t_0- \biggl(\frac{\mathrm p_1}{4|\mathrm p_2|}\biggr)^{4/3}t_0.
\end{equation*}
\notag
$$
С учетом условия ($*$) получаем, что
$$
\begin{equation*}
c=t_0+ \biggl(\frac{\mathrm p_1}{4|\mathrm p_2|}\biggr)^{4/3}t_0= 3\biggl(4^{1/3} \mathrm p_1^{2/3}|\mathrm p_2|^{1/3}+\frac{\mathrm p_1^2}{4|p_2|}\biggr) \leqslant 3\frac13 |\mathrm p_2|=|\mathrm p_2|
\end{equation*}
\notag
$$
и значение квадрата знаменателя в определении $\overline{\mathrm p}_1 (t_0)$ есть
$$
\begin{equation*}
(-2\mathrm p_1)^2+(-|\mathrm p_2|-c)^2\leqslant4 (\mathrm p_1^2+\mathrm p_2^2)=4.
\end{equation*}
\notag
$$
Таким образом, $\overline{\mathrm p}_1(t_0)\leqslant -\mathrm p_1$. Поэтому найдется такое число $t(p)\in (0,t_0]$, что
$$
\begin{equation*}
\overline{\mathrm p}_1(t(p))=-\mathrm p_1, \qquad \overline{\mathrm p}_2(t(p))=-\sqrt{1-\overline{\mathrm p}_1^2(t(p))}=\mathrm p_2.
\end{equation*}
\notag
$$
В силу симметрии графика $y=x^4+1$ относительно оси ординат, для указанных выше начального условия $p=(\mathrm p_1,\mathrm p_2)$ и числа $t(p)>0$ метод проекции градиента зацикливается: при итерациях последовательно получаются точки $(\mathrm p_1,\mathrm p_2)$ и $(-\mathrm p_1,\mathrm p_2)$. Заметим также, что $t(p)\to 0$ при $p\to (0,-1)$. ЗаключениеПолученные в работе результаты доказаны в предположении, что опорные условия из определений 1 или 2 выполнены в точке $z_0\in\mathcal Z$ для нормального вектора $p_0=-z_0/\| z_0\|$, где $p_0$ – решении задачи (1.1). Такие априорно непроверяемые в общей ситуации условия иногда возникают в задачах оптимизации. Например, аналогичные предположения делаются о выполнении в задачах условия острого минимума, условия квадратичного роста и ряда других условий. В то же время доказанные результаты показывают, что для линейной сходимости метода (1.2) достаточно выполнения определения 1 для решения $p_0\in\mathcal N(\mathcal Z,z_0)$. Больше от выпуклого компактного множества $\mathcal Z$ требовать ничего не нужно. В частности, не нужна даже локальная в том или ином смысле сильная выпуклость множества $\mathcal Z$ в окрестности $z_0$, что раньше было не очевидно. Важным примером множеств, для которых определение 1 типично, являются множества достижимости линейной управляемой системы (1.3) когда множество управлений $\mathcal U$ есть многогранник. В теореме 3.1 и замечании 3.2 [12] доказано, что при достаточно общих условиях для почти всех в некотором смысле точек $z_0$ границы такого множества достижимости $\mathcal R (t)$ выполнено условие локальной сильной выпуклости через модуль выпуклости: существует $c=c(z_0)>0$ такое, что для любой точки $z\in \mathcal R (t)$ выполнено включение
$$
\begin{equation}
\frac{z+z_0}{2}+c\| z-z_0\|^2B_1(0)\subset \mathcal R (t).
\end{equation}
\tag{3.3}
$$
Из этого условия вытекает включение из определения 1 для любого единичного $p_0\in\mathcal N (\mathcal R (t),z_0)$ и некоторого $R_0>0$. Покажем это от противного. Пусть для последовательности $\delta_k\to 0$ найдутся точки $z_k\in B_{\delta_k}(z_0) \cap \mathcal R (t)$ такие, что $z_k\notin B_k (z_0-kp_0)$. Пусть
$$
\begin{equation*}
\mathcal H^-_{p_0}=\bigl\{ x\in\mathbb R^n\colon (p_0,x)\leqslant (p_0,z_0)\bigr\}\supset \mathcal R (t).
\end{equation*}
\notag
$$
Тогда точка $z_k$ содержится во множестве $\mathcal H^-_{p_0}\setminus B_k (z_0-kp_0)$. Поэтому при малых значениях $\| z_k-z_0\|$ расстояние от точки $(z_k+z_0)/2$ до $\partial\mathcal H_{p_0}^-$ имеет порядок $(\| z_k-z_0\|^2)/k$, что противоречит включению (3.3) для $z=z_k$. Следовательно, найдутся такие $\delta>0$ и $R>0$, что
$$
\begin{equation}
B_{\delta}(z_0)\cap \mathcal R (t)\subset B_{\delta}(z_0)\cap B_R(z_0-Rp_0).
\end{equation}
\tag{3.4}
$$
Пусть
$$
\begin{equation*}
\mathcal H=\operatorname{aff} ( \partial B_{\delta}(z_0)\cap \partial B_R(z_0-Rp_0)).
\end{equation*}
\notag
$$
Легко видеть, что $\mathcal H=\partial\mathcal H^-_{p_0}-\varrho (z_0,\mathcal H)p_0$ есть сдвиг $\partial\mathcal H^-_{p_0}$ на ненулевое расстояние вдоль вектора $-p_0$. Между плоскостями $\mathcal H$ и $\partial \mathcal H_{p_0}^-$ и вне шара $B_R(z_0-Rp_0)$ нет точек $z\in\mathcal R (t)$. Если бы такая точка существовала, то в силу (3.4) $z\notin B_{\delta}(z_0)$, поэтому отрезок $[z,z_0]\subset\mathcal R(t)$ пересекал бы границу шара $\partial B_{\delta}(z_0)$ в точке $x\in\mathcal R (t)$. В силу включения $x\notin B_R(z_0-Rp_0)$ получаем противоречие с (3.4). Из включения
$$
\begin{equation*}
\mathcal R(t)\subset (\mathcal H^-_{p_0}-\varrho (z_0,\mathcal H)p_0)\cup B_R(z_0-Rp_0)
\end{equation*}
\notag
$$
в силу компактности $\mathcal R (t)$ можно подобрать число $R_0\geqslant R$ такое, что
Цитирование в формате AMSBIB
\RBibitem{Bal23} |
|
||||||||||
|
Обратная связь: |
Пользовательское соглашение
|
Регистрация посетителей портала |
Логотипы |
|