Loading [MathJax]/jax/element/mml/optable/BasicLatin.js
Математические заметки
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Скоро в журнале
Архив
Импакт-фактор
Правила для авторов
Лицензионный договор
Загрузить рукопись

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Матем. заметки:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Математические заметки, 2023, том 113, выпуск 5, страницы 655–666
DOI: https://doi.org/10.4213/mzm13745
(Mi mzm13745)
 

Эта публикация цитируется в 3 научных статьях (всего в 3 статьях)

Достаточные условия линейной сходимости одного алгоритма для нахождения метрической проекции точки на выпуклый компакт

М. В. Балашов

Институт проблем управления им. В. А. Трапезникова РАН, г. Москва
Список литературы:
Аннотация: Многие задачи, например, задачи о свойствах множества достижимости линейной управляемой системы, сводятся к нахождению проекции нуля на некоторое выпуклое компактное подмножество в конечномерном евклидовом пространстве. Последнее множество задано своей опорной функцией. В настоящей работе обсуждаются некоторые минимальные достаточные условия, которые надо наложить на выпуклое компактное множество для того, чтобы метод проекции градиента для решения задачи о нахождении проекции нуля на это множество сходился с линейной скоростью. На примере показана существенность указанных условий.
Библиография: 12 названий.
Ключевые слова: метод проекции градиента, опорный шар, условия роста функции, негладкий анализ.
Финансовая поддержка Номер гранта
Российский научный фонд 22-11-00042
Исследование выполнено за счет гранта Российского научного фонда № 22-11-00042, https://rscf.ru/project/22-11-00042/ в ИПУ РАН.
Поступило: 26.09.2022
Исправленный вариант: 16.12.2022
Англоязычная версия:
Mathematical Notes, 2023, Volume 113, Issue 5, Pages 632–641
DOI: https://doi.org/10.1134/S0001434623050036
Реферативные базы данных:
Тип публикации: Статья
УДК: 517.98
MSC: 49J52, 90C26, 52A05

1. Введение

Рассмотрим n-мерное вещественное евклидово пространство Rn со скалярным произведением (,) и нормой =(,). Определим шар Br(0) радиуса r>0 с центром в нуле. Для множества ZRn определим границу Z и внутренность intZ.

Пусть ZRn{0} – выпуклое компактное подмножество, для которого известна опорная функция f(p)=s(p,Z)=max, p\in\mathbb R^n. Рассмотрим задачу нахождения метрической проекции точки 0\in\mathbb R^n на \mathcal Z. На языке опорной функции f(p) эту задачу можно переформулировать в виде

\begin{equation} \min_{\| p\|=1}f(p)=J. \end{equation} \tag{1.1}
Пусть 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) линейной управляемой системы

\begin{equation} x'(\tau)\in Ax(\tau)+\mathcal U, \end{equation} \tag{1.3}
где 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) и

\begin{equation*} -J=\min_{\| p\|=1}(s(p,\mathcal M)-s(p,\mathcal R)). \end{equation*} \notag

В настоящей работе мы хотим по возможности ослабить условия на множество \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, если

\begin{equation*} \mathcal Z\subset \mathcal B_{R}(z_0-Rp_0). \end{equation*} \notag

Заметим, что само множество \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, если

\begin{equation*} \mathcal B_{r}(z_0-rp_0)\subset\mathcal Z. \end{equation*} \notag

Определение 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
\begin{equation*} (p,z)\leqslant f(p)\leqslant 0, \end{equation*} \notag
т.е. для любых 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^-. Лемма доказана.

Лемма 2. Пусть u,v\in\mathbb R^n\setminus\{ 0\}. Тогда

\begin{equation*} \| P_{\mathcal S_1}u - P_{\mathcal S_1}v\|=\biggl\| \frac{u}{\| u\|}-\frac{v}{\| v\|}\biggr\|\leqslant \frac{\| u-v\|}{\sqrt{\| u\|\cdot \| v\|}}. \end{equation*} \notag

Доказательство. Для доказательства надо умножить обе части доказываемого неравенства на \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) удовлетворяют условию

\begin{equation} \| p_{k+1}-p_0\|^2\leqslant \frac{1}{1+t\| z_0\|} \biggl(\| p_{k}-p_0\|^2-t\biggl(\frac1R-t\biggr) \| z_k-z_0\|^2\biggr). \end{equation} \tag{2.1}

Перед доказательством отметим, что из включения \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
Последнее эквивалентно
\begin{equation*} -(p_0,z_0-z_k)\leqslant -\frac{1}{2R}\| z_k-z_0\|^2. \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) выполняется неравенство

\begin{equation} \| z_p-z_0\|\geqslant \frac{r}{2}\| p-p_0\|. \end{equation} \tag{2.3}

Доказательство. Определим для q\in\mathcal S_1 множества
\begin{equation*} \begin{gathered} \, \mathcal H_q^+=\bigl\{ x\in\mathbb R^n\colon (q,x)\geqslant s(q,\mathcal B_r(z_0-rp_0))\bigr\}, \\ \mathcal H_q^-=\bigl\{ x\in\mathbb R^n\colon (q,x)\leqslant s(q,\mathcal B_r(z_0-rp_0))\bigr\}. \end{gathered} \end{equation*} \notag

Зафиксируем 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) удовлетворяют условию

\begin{equation*} \| p_{k+1}-p_0\|\leqslant \frac{1}{\sqrt{1+t\| z_0\|}}\| p_{k}-p_0\| \end{equation*} \notag
и тем самым \{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. Тогда

\begin{equation*} \| p_{k+1}-p_0\|\leqslant \sqrt{\frac{1-r^2t(1/R-t)/4}{1+t\| z_0\|}}\| p_{k}-p_0\| \end{equation*} \notag
и тем самым \{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\} такого, что

\begin{equation*} L=L(t,r,R,C)=\sqrt{t\biggl(\frac1R-t\biggr)}\biggl( \frac{r^2}{4R}-t\biggl( \frac{r^2}{4}+C^2\biggr) \biggr)>0, \end{equation*} \notag
при любом начальном условии p_1\in\mathcal S_1, \| p_1-p_0\|\leqslant L, итерации \{p_k\}_{k=1}^{\infty} сходятся к p_0 с линейной скоростью:
\begin{equation*} \| p_{k+1}-p_0\|\leqslant q\cdot \| p_k-p_0\|, \qquad q=\sqrt{1-\frac{t^2}{2}(2C-1)}. \end{equation*} \notag

Доказательство. Пусть построено 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 получаем оценку
\begin{equation*} \frac{1-r^2t(1/R-t)/4}{(1-t\| z_k\|)(1+t\| z_0\|)}\leqslant 1-\frac{t^2(C^2-\|z_k\|\cdot\|z_0\|)}{(1-t\| z_k\|)(1+t\| z_0\|)}\leqslant 1-\frac{t^2(2C-1)}{1+t\| z_0\|}\leqslant q^2. \end{equation*} \notag
Таким образом, \| 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|}, \qquad J=-\| z_0\|. \end{equation*} \notag
Тогда p_1\in\mathcal K_0^{-}. Тем самым, итерации (1.2) с начальной точкой p_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
т.е.
\begin{equation*} \frac{R}{R+|J|}\leqslant (p_1,p_0). \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, т.е.

\begin{equation*} z(p)=\biggl( \biggl( \frac{\mathrm p_1}{4|\mathrm p_2|}\biggr)^{1/3}, \biggl(\frac{\mathrm p_1}{4|\mathrm p_2|} \biggr)^{4/3}+1\biggr)=f'(p), \end{equation*} \notag
где f(p)=s(p,\mathcal Z)=(p,z(p)),
\begin{equation*} f(p)=\frac34 \,\frac{\mathrm p_1^{4/3}}{(4|\mathrm p_2|)^{1/3}}+\mathrm p_2. \end{equation*} \notag

Отметим, что радиус кривизны графика 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 такое, что
\begin{equation*} \mathcal R (t)\subset B_{R_0}(z_0-R_0p_0). \end{equation*} \notag

СПИСОК ЦИТИРОВАННОЙ ЛИТЕРАТУРЫ

1. Б. Т. Поляк, “Градиентные методы минимизации функционалов”, Ж. вычисл. матем. и матем. физ., 3:4 (1963), 643–653  mathnet  mathscinet  zmath
2. Е. С. Левитин, Б. Т. Поляк, “Методы минимизации при наличии ограничений”, Ж. вычисл. матем. и матем. физ., 6:5 (1966), 787–823  mathnet  mathscinet  zmath
3. Е. С. Половинкин, М. В. Балашов, Элементы выпуклого и сильно выпуклого анализа, Физматлит, М., 2007
4. М. В. Балашов, “Некоторые оптимизационные задачи с множеством достижимости линейной управляемой системы”, Современные проблемы теории функций и их приложения (Материалы 21-й международной Саратовской зимней школы), Саратовсий ун-т, Саратов, 2022, 40–43
5. Б. Т. Поляк, Введение в оптимизацию, Наука, М., 1983  mathscinet
6. D. Davis, D. Drusvyatskiy, K. J. MacPhee, C. Paquette, “Subgradient methods for sharp weakly convex functions.”, J. Optim. Theory Appl., 179:3 (2018), 962–982  crossref  mathscinet
7. М. В. Балашов, “О методе проекции градиента для слабо выпуклой функции на проксимально гладком множестве”, Матем. заметки, 108:5 (2020), 657–668  mathnet  crossref  mathscinet
8. R. J. Aumann, “Integrals of set-valued functions”, J. Math. Anal. Appl., 12 (1) (1965), 1–12  crossref  mathscinet
9. М. В. Балашов, “Сильная выпуклость множеств достижимости линейных систем”, Матем. сб., 213:5 (2022), 30–49  mathnet
10. М. В. Балашов, “Вложение гомотета в выпуклый компакт: алгоритм и его сходимость”, Вестник российских университетов. Математика, 27:138 (2022), 143–149  mathnet  crossref
11. P. Cannarsa, H. Frankowska, “Interior sphere property of attainable sets and time optimal control problems”, ESAIM Control Optim. Calc. Var., 12:2 (2006), 350–370  crossref  mathscinet
12. V. M. Veliov, “On the convexity of integrals of multivalued mappings: applications in control theory”, J. Optim. Theory Appl., 54:3 (1987), 541–563  crossref  mathscinet

Образец цитирования: М. В. Балашов, “Достаточные условия линейной сходимости одного алгоритма для нахождения метрической проекции точки на выпуклый компакт”, Матем. заметки, 113:5 (2023), 655–666; Math. Notes, 113:5 (2023), 632–641
Цитирование в формате AMSBIB
\RBibitem{Bal23}
\by М.~В.~Балашов
\paper Достаточные условия линейной сходимости одного алгоритма для нахождения метрической проекции точки на выпуклый компакт
\jour Матем. заметки
\yr 2023
\vol 113
\issue 5
\pages 655--666
\mathnet{http://mi.mathnet.ru/mzm13745}
\crossref{https://doi.org/10.4213/mzm13745}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=4602425}
\transl
\jour Math. Notes
\yr 2023
\vol 113
\issue 5
\pages 632--641
\crossref{https://doi.org/10.1134/S0001434623050036}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85162665651}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/mzm13745
  • https://doi.org/10.4213/mzm13745
  • https://www.mathnet.ru/rus/mzm/v113/i5/p655
  • Эта публикация цитируется в следующих 3 статьяx:
    1. М. В. Балашов, К. З. Биглов, “Опорное условие сильной выпуклости и условие Липшица для метрической проекции”, Матем. заметки, 115:2 (2024), 197–207  mathnet  crossref  mathscinet; M. V. Balashov, K. Z. Biglov, “The Strong Convexity Supporting Condition and the Lipschitz Condition for the Metric Projection”, Math. Notes, 115:2 (2024), 164–172  crossref
    2. М. В. Балашов, “Условие Липшица метрической проекции и сходимость градиентных методов”, Матем. сб., 215:4 (2024), 62–80  mathnet  crossref  mathscinet  zmath  adsnasa; M. V. Balashov, “Lipschitz continuity of the metric projection operator and convergence of gradient methods”, Sb. Math., 215:4 (2024), 494–510  crossref  isi
    3. M. V. Balashov, A. A. Tremba, “The Gradient Projection Method for a Supporting Function on the Unit Sphere and Its Applications”, Comput. Math. and Math. Phys., 64:4 (2024), 676  crossref
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Математические заметки Mathematical Notes
    Статистика просмотров:
    Страница аннотации:199
    PDF полного текста:18
    HTML русской версии:119
    Список литературы:35
    Первая страница:16
     
      Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2025