Прокс-алгоритмы и расщепление операторов

Мотивация: как работать с недифференцируемыми членами?

Задача LASSO: min (1/2)‖Ax−b‖² + λ‖x‖₁. Первый член — гладкий (можно дифференцировать), второй — нет (|x|₁ недифференцируема в нуле). Применить градиентный спуск нельзя напрямую. Субградиентный метод — слишком медленный (O(1/√k)). Прокс-алгоритмы решают эту проблему элегантно: «расщепляют» функцию на гладкую и негладкую части и работают с каждой по-своему.

Прокс-оператор

Определение: prox_{τf}(x) = argmin_{y} {f(y) + (1/2τ)‖y − x‖²}

Смысл каждого символа:

τ > 0 — размер шага
f(y) — «минимизируем» f
(1/2τ)‖y − x‖² — «не уходим далеко от x»
argmin — возвращаем минимизирующую точку y

Это «мягкий шаг в сторону минимума f». При τ → 0: prox ≈ x (не двигаемся). При τ → ∞: prox → argmin f (идём в минимум).

Ключевые примеры:

f(x) = ‖x‖₁: prox_{τf}(x) = sign(x) · max(|x| − τ, 0) — мягкое пороговое (soft thresholding)

Смысл: компоненты |xᵢ| ≤ τ обнуляются, остальные сдвигаются к нулю на τ.
f(x) = δ_C(x) — индикатор выпуклого C: prox_{δ_C}(x) = P_C(x) — проекция на C
f(X) = ‖X‖* (ядерная норма = сумма сингулярных чисел): prox{τ‖·‖_*}(X) = UΣ̃Vᵀ, где X = UΣVᵀ (SVD), Σ̃ᵢᵢ = max(σᵢ − τ, 0) — мягкое пороговое для сингулярных чисел.

Проксимальный градиентный метод (ISTA/FISTA)

Для задачи min F(x) = f(x) + g(x), где f — гладкая (L-гладкая), g — выпуклая (проксируемая):

ISTA (Iterative Shrinkage-Thresholding Algorithm):

x^{k+1} = prox_{τg}(x^k − τ ∇f(x^k))

Шаги: 1) Градиентный шаг по f 2) Прокс-шаг по g. Сходимость: O(1/k).

FISTA = ISTA + момент Нестерова:

y^{k+1} = prox_{τg}(x^k − τ ∇f(x^k)) x^{k+1} = y^{k+1} + (k−1)/(k+2) · (y^{k+1} − y^k)

Сходимость: O(1/k²) — оптимально!

Полный разбор LASSO с FISTA

Задача: min F(x) = (1/2)‖Ax − b‖² + λ‖x‖₁

f(x) = (1/2)‖Ax−b‖², ∇f(x) = Aᵀ(Ax − b), L = λ_max(AᵀA) g(x) = λ‖x‖₁, prox_{τg}(z) = sign(z)·max(|z| − τλ, 0)

Итерация FISTA:

Вычислить r^k = Ax^k − b (невязка)
Градиент: ∇f(x^k) = Aᵀ r^k
Градиентный шаг: z^{k+1} = x^k − (1/L) Aᵀ r^k
Прокс: y^{k+1} = sign(z^{k+1}) · max(|z^{k+1}| − λ/L, 0)
Момент: x^{k+1} = y^{k+1} + βₖ(y^{k+1} − y^k)

Численный пример: A — матрица 50×100, x* разреженный (5 ненулевых компонент). FISTA с λ = 0.1 достигает точности 10⁻⁶ за ~200 итераций. Без ускорения (ISTA) — за ~2000 итераций.

ADMM (Alternating Direction Method of Multipliers)

ADMM решает задачи вида: min f(x) + g(z) при Ax + Bz = c

Алгоритм ADMM (итерация):

x-шаг: x^{k+1} = argmin_x {f(x) + (ρ/2)‖Ax + Bz^k − c + u^k‖²}
z-шаг: z^{k+1} = argmin_z {g(z) + (ρ/2)‖Ax^{k+1} + Bz − c + u^k‖²}
Двойной шаг: u^{k+1} = u^k + Ax^{k+1} + Bz^{k+1} − c

Здесь ρ > 0 — параметр штрафа, u — двойственная переменная (масштабированная).

Почему ADMM мощнее: расщепляет задачу на два подзадачи — по x и по z — решаемые по отдельности. Если обе подзадачи имеют удобные прокс-операторы, весь алгоритм очень эффективен.

Пример: Lasso через ADMM

x-шаг: обычный ridge-regression (закрытое решение через LDLT-разложение) z-шаг: soft thresholding

ADMM сходится за O(1/k) и хорошо параллелизируется по блокам данных.

Применения

Распределённая оптимизация: при n машинах каждая хранит свою часть данных. ADMM позволяет решать глобальную задачу, не собирая все данные в одном месте — только обмен «двойственными» переменными.

Обработка изображений: Total Variation (TV) деноизинг: min (1/2)‖u − f‖² + λTV(u). TV норма — негладкая, но имеет удобный прокс. FISTA и ADMM — стандартные методы.

Прокс-операторы для типичных регуляризаторов

Помимо мягкого порога для L1 и проекции для индикатора, важными прокс-операторами являются:

Для L2-регуляризации τ‖x‖²: prox(x) = x / (1 + 2τ) — простое масштабирование
Для группового LASSO τ‖x‖_{2,1}: групповой мягкий порог, обнуляющий целые группы координат
Для ядерной нормы ‖X‖_* (сумма сингулярных чисел матрицы): SVD-разложение X = UΣVᵀ, затем мягкий порог сингулярных чисел и обратная сборка
Для индикатора симплекса: проекция на симплекс через сортировку — O(n log n)

Применения расщепления операторов

Метод Дугласа-Рэчфорда (Douglas-Rachford splitting) и ADMM являются основой современных систем выпуклой оптимизации: TFOCS, CVXPY, COSMO. Они особенно эффективны для задач с разделимой структурой, где целевая функция распадается на простые слагаемые с легко вычислимыми прокс-операторами. ADMM активно используется в распределённой оптимизации: каждый узел вычислителя решает локальную подзадачу через прокс, а затем синхронизируется через двойственные переменные. Это позволяет масштабировать обучение на тысячи машин.