Коротко — алгоритм, условия сходимости, критерий оптимальности и практические тонкости.
1) Постановка и базовый шаг
- Пусть $f:{\mathbb{R}}^n\to \mathbb{R}$ — выпуклая (не обязательно гладкая) функция, $C\subset {\mathbb{R}}^n$ — выпуклое замкнутое множество. Цель: ${\min }_{x\in C}f(x)$.
- Проектированный субградиентный метод (PSM):
$$g_k\in \partial f(x_k),y_{k+1}=x_k-{\alpha }_k{g}_k,x_{k+1}=P_C(y_{k+1}),$$ где $P_C$ — ортопроекция на $C$, ${\alpha }_k>0$ — шаг.
2) Необходимые предпосылки для сходимости (стандартные)
- Существует оптимум $f^{\ast }={\min }_{x\in C}f(x)$.
- Субградиенты ограничены: существует $G<\infty$ такое, что для всех рассматриваемых итераций $\Vert g_k\Vert \le G$ (например, $f$ локально липшицева на $C$).
- Множество $C$ ограничено или расстояние до некоторого решения $x^{\ast }$ ограничено: $D=\Vert x_0-x^{\ast }\Vert <\infty$ или диаметр ${\max }_{x,y\in C}\Vert x-y\Vert <\infty$.
3) Условия на шаги и типы сходимости
- Диминирующие шаги (гарантия сходимости в значении функции):
$${\alpha }_k\ge 0,\sum _{k=0}^{\infty }{\alpha }_k=\infty ,\sum _{k=0}^{\infty }{\alpha }_k^2<\infty$$ (например ${\alpha }_k=\frac{a}{k+b}$ с $a>0,b\ge 1$). Тогда значения $f(x_k)$ сходятся к $f^{\ast }$ (обычно с медленным темпом).
- Фиксированный шаг $\alpha$: после $T$ итераций оценка для лучшей итерации (best iterate)
$$\underset{k\le T}{\min }(f(x_k)-f^{\ast })\le \frac{D^2}{2\alpha T}+\frac{\alpha G^2}{2}.$$ Оптимальный выбор $\alpha =\frac{D}{G\sqrt{T}}$ даёт скорость порядка
$$\underset{k\le T}{\min }(f(x_k)-f^{\ast })=O\left(\frac{GD}{\sqrt{T}}\right).$$ - Polyak‑шаг (требует известного $f^{\ast }$):
$${\alpha }_k=\frac{f(x_k)-f^{\ast }}{\Vert g_k{\Vert }^2}$$ даёт более быстрые гарантии (практически полезен, если $f^{\ast }$ известна или есть хороший нижний bound).
- Усреднение: усреднённые итераты ${\bar{x}}_T=\frac{1}{T}{\sum }_{k=1}^T{x}_k$ часто дают лучшие и более стабильные оценки по функции и достигают той же $O(1/\sqrt{T})$ скорости с лучшей практикой.
4) Критерий оптимальности через субградиент
- Необходимое и достаточное условие оптимальности (Ферма) для выпуклой задачи на $C$:
$$0\in \partial f(x^{\ast })+N_C(x^{\ast }),$$ где $N_C(x^{\ast })$ — нормальное множество к $C$ в $x^{\ast }$.
- Часто эквивалентно: существует $g\in \partial f(x)$ такой, что
$$x=P_C(x-g).$$ Практический остаток для проверки: для некоторого $g\in \partial f(x)$ вычислить
$$r(x,g)=\Vert x-P_C(x-g)\Vert .$$ Если $r(x,g)\le \epsilon$ (малое число), то $x$ считается $\epsilon$-станционарной/приближённо-оптимальной точкой.
- В неограниченном случае (без ограничений) оптимальность эквивалентна $0\in \partial f(x)$; практический критерий: найти $g\in \partial f(x)$ с $\Vert g\Vert \le \epsilon$.
5) Практические тонкости при негладких функциях
- Выбор конкретного субградиента. В точках неровности $\partial f(x)$ — многогранник; разные выборы дают разное поведение итераций. Рекомендуется:
- усреднять итераты или субградиенты для стабильности;
- использовать bundle‑методы или метод субградиента с адаптивным шагом, если нужна лучшая производительность.
- Проекция на $C$ может быть вычислительно дорогой; заменяют:
- приближенными проекциями (контролируя ошибку),
- проксимальными шагами, или
- зеркальными/prox‑алгоритмами (mirror descent) при удобной задаче геометрии.
- Отсутствие липшицевости. Если субградиенты неограничены, стандартные оценки ломаются — требуется локальная регуляризация/сглаживание (Moreau‑envelope, Nesterov smoothing).
- Падающая/осциллирующая динамика при больших шагах; при слишком маленьких шагах — крайне медленная сходимость. Практически выбирают схемы типа ${\alpha }_k=\frac{a}{k+b}$ с подбором $a$.
- Polyak‑шаг хорош, но требует $f^{\ast }$. Можно использовать оценку нижней грани вместо точного $f^{\ast }$.
- Для функций вида $f(x)={\max }_i⟨a_i,x⟩+b_i$ (макс-линейные) субградиенты — конвексная оболочка активных градиентов; на практике удобно выбирать любой активный индекс или их сочетание.
- Численные ошибки: при вычислении субградиента численные приближения могут нарушать критерий $0\in \partial f+N_C$; надо учитывать допуск при проверке остатка $r$.
6) Рекомендации для реализации
- Используйте проекции/проксиматоры, которые вы можете эффективно считать.
- Если $G$ или $D$ неизвестны, экспериментально подберите параметр $a$ в ${\alpha }_k=\frac{a}{k+b}$.
- Храните и возвращайте усреднённый iterate или лучшую по функции из просмотренных итератов.
- При жёстких негладкостях рассмотрите bundle‑метод или сглаживание (Moreau), если нужно ускорение.
- Останавливайте по комбинированному критерию: малое уменьшение значения функции, малый остаток $r(x,g)$ и/или ограничение числа итераций.
Кратко: стандартный проектированный субградиентный метод прост в реализации; при условии ограниченных субградиентов и правильно выбранных шагов (обычно диминирующих) значения функции сходятся к оптимуму с темпом примерно $O(1/\sqrt{T})$; оптимальность проверяется через условие $0\in \partial f(x)+N_C(x)$ (практически — через остаток $\Vert x-P_C(x-g)\Vert$). Для реальных негладких задач нужно заботиться о выборе субградиента, проекции, шагов и/или применять более сложные методы (bundle, прокс/сглаживание) для улучшения скорости и стабильности.