Метод переменного направления множителей — ADMM

Материал из MachineLearning.

(Различия между версиями)

Mariia Shubina (Обсуждение | вклад)
(Новая: {{well|Статья написана с использованием LLM Qwen3.7-Plus и проверена участником Mariia Shubina 23:17,...)
К следующему изменению →

Версия 20:30, 18 июля 2026

Статья написана с использованием LLM Qwen3.7-Plus и проверена участником Mariia Shubina 23:17, 18 июля 2026 (MSD)

Содержание

1 Введение
2 Формальная постановка задачи
- 2.1 Расширенный лагранжиан
3 Алгоритм ADMM
- 3.1 Псевдокод
- 3.2 Интуиция и отличие от классических методов
4 Теоретические результаты
- 4.1 Условия сходимости
- 4.2 Скорость сходимости
5 Роль параметров и остатков (Residuals)
6 Варианты и обобщения метода
7 Применения в машинном обучении
8 Сравнение с другими методами оптимизации
9 Ограничения и типичные ошибки
10 Литература

Введение

Метод переменного направления множителей (англ. Alternating Direction Method of Multipliers, ADMM) — это мощный алгоритм выпуклой оптимизации, предназначенный для решения задач, которые можно декомпозировать на более мелкие и простые подзадачи. Алгоритм сочетает в себе декомпозируемость и масштабируемость метода двойственного подъема (dual ascent) с превосходными свойствами сходимости метода множителей Лагранжа. В последние годы ADMM стал стандартом де-факто для решения задач с негладкими целевыми функциями (например, содержащими L1-норму или ядерную норму) и является фундаментальным инструментом в распределенных вычислениях и машинном обучении, где данные физически разделены между множеством вычислительных узлов.

Формальная постановка задачи

Классическая задача, решаемая методом ADMM, имеет следующий вид:

$\min_{x, z} f(x) + g(z)$

$\text{при условии } Ax + Bz = c$

где $x \in \mathbb{R}^n$ и $z \in \mathbb{R}^m$ — векторы переменных, $A \in \mathbb{R}^{p \times n}$ , $B \in \mathbb{R}^{p \times m}$ , $c \in \mathbb{R}^p$ . Функции $f: \mathbb{R}^n \to \mathbb{R} \cup {+\infty}$ и $g: \mathbb{R}^m \to \mathbb{R} \cup {+\infty}$ предполагаются собственными, замкнутыми и выпуклыми, но не обязательно гладкими.

Расширенный лагранжиан

В основе метода лежит функция расширенного лагранжиана (Augmented Lagrangian), которая добавляет квадратичный штраф за нарушение линейных ограничений к классическому лагранжиану:

$L_\rho(x, z, y) = f(x) + g(z) + y^T(Ax + Bz - c) + \frac{\rho}{2} |Ax + Bz - c|_2^2$

где $y \in \mathbb{R}^p$ — вектор двойственных переменных (множителей Лагранжа), а $\rho > 0$ — скалярный параметр штрафа (penalty parameter).

Алгоритм ADMM

Алгоритм итеративно обновляет переменные $x$ , $z$ и $y$ , чередуя (alternating) минимизацию по каждой из них при фиксированных остальных.

Псевдокод

Инициализировать $x^0, z^0, y^0$ и выбрать параметр $\rho > 0$ Для $k = 0, 1, 2, \dots$ до сходимости: $x^{k+1} := \arg\min_x L_\rho(x, z^k, y^k)$ $z^{k+1} := \arg\min_z L_\rho(x^{k+1}, z, y^k)$ $y^{k+1} := y^k + \rho(Ax^{k+1} + Bz^{k+1} - c)$

Интуиция и отличие от классических методов

Классический метод множителей минимизирует $L_\rho(x, z, y^k)$ по $x$ и $z$ совместно (jointly), что часто вычислительно сложно. ADMM минимизирует их поочередно (alternatingly). Это позволяет разделить задачу на две независимые подзадачи. Если матрицы $A$ и $B$ имеют блочно-диагональную структуру, x-шаг и z-шаг могут выполняться полностью параллельно, что является ключевым преимуществом метода.

Теоретические результаты

Условия сходимости

Если функции $f$ и $g$ выпуклы, и нестрогий лагранжиан $L_0(x, z, y)$ имеет седловую точку, то при любом $\rho > 0$ последовательность, генерируемая ADMM, сходится: Ограничения выполняются асимптотически: $Ax^k + Bz^k - c \to 0$ . Целевая функция сходится к оптимуму: $f(x^k) + g(z^k) \to f(x^) + g(z^)$ . Двойственные переменные сходятся: $y^k \to y^$ , где $y^$ — оптимальный множитель Лагранжа.

Скорость сходимости

Для общих выпуклых задач ADMM гарантирует скорость сходимости $O(1/k)$ как по значению целевой функции, так и по нарушению ограничений (в смысле средних значений итераций). При дополнительных предположениях (сильная выпуклость и гладкость $f$ или $g$ ) может быть достигнута линейная скорость сходимости $O(c^k)$ для некоторого $c \in (0, 1)$ .

Роль параметров и остатков (Residuals)

Параметр $\rho$ не влияет на конечную точку сходимости, но критически важен для скорости сходимости. Контроль сходимости осуществляется через два типа остатков: Прямой остаток (Primal residual): $r^k = Ax^k + Bz^k - c$ . Он измеряет допустимость текущего решения. Двойственный остаток (Dual residual): $s^k = \rho A^T B (z^k - z^{k-1})$ . Он измеряет оптимальность условий Каруша — Куна — Таккера. На практике часто используют адаптивные схемы обновления $\rho$ : если $|r^k|_2 \gg |s^k|_2$ , параметр $\rho$ увеличивают (чтобы усилить штраф за нарушение ограничений); если $|s^k|_2 \gg |r^k|_2$ , параметр $\rho$ уменьшают.

Варианты и обобщения метода

Consensus ADMM (Распределенный консенсус)

Для задач вида $\min_x \sum_{i=1}^N f_i(x)$ вводится локальная переменная $x_i$ для каждого узла и глобальная переменная $z$ с ограничением $x_i = z$ . Это позволяет каждому узлу решать свою подзадачу независимо, обмениваясь с центральным сервером только усредненными значениями, что минимизирует передачу данных в распределенном машинном обучении.

Стохастический ADMM

В задачах, где вычисление точного градиента или проксимального оператора на x-шаге слишком дорого, используется стохастическая аппроксимация. Это позволяет применять метод к огромным наборам данных, обрабатывая мини-батчи, аналогично стохастическому градиентному спуску.

Невыпуклый ADMM

Хотя строгие гарантии сходимости отсутствуют, модификации ADMM успешно применяются к невыпуклым задачам (например, обучение глубоких нейронных сетей с ограничениями или задачи фазовой реконструкции), часто с добавлением проксимальных членов для стабилизации итераций.

Применения в машинном обучении

Регуляризация и разреженные модели: Задача Lasso ( $\min_x \frac{1}{2}|Ax - b|_2^2 + \lambda |x|_1$ ) идеально ложится на ADMM. x-шаг сводится к решению системы линейных уравнений, а z-шаг имеет аналитическое решение через оператор мягкого порога (soft-thresholding). Матричное пополнение (Matrix completion): Восстановление матриц с низкой ранговой структурой путем минимизации ядерной нормы (nuclear norm), которая является негладкой, но имеет простой проксимальный оператор (сингулярное пороговое сжатие). Метод опорных векторов (SVM): ADMM позволяет эффективно обучать SVM на распределенных данных, избегая передачи сырых данных между узлами. Обучение нейронных сетей: Разделение слоев сети на разные блоки переменных для распараллеливания обучения или наложения жестких структурных ограничений на веса.

Сравнение с другими методами оптимизации

Градиентный спуск и его варианты: Требуют гладкости функции. ADMM превосходит их в задачах с негладкими регуляризаторами, так как инкапсулирует негладкость в проксимальный оператор. Метод внутренней точки: Обладает квадратичной скоростью сходимости и идеален для задач малой и средней размерности. Однако он плохо масштабируется на высокие размерности и распределенные системы из-за необходимости решения плотных систем линейных уравнений на каждой итерации. Координатный спуск: Обновляет одну скалярную переменную за раз. ADMM обновляет целые блоки переменных, что лучше использует векторные инструкции процессора и позволяет достичь высокого уровня параллелизма. Метод двойственного подъема (Dual Ascent): Не требует квадратичного штрафа, но сходится только при строгих предположениях (например, сильная выпуклость). ADMM сходится в гораздо более широком классе задач благодаря члену $\rho$ .

Ограничения и типичные ошибки

Чувствительность к выбору $\rho$ : Неудачный выбор параметра штрафа может замедлить сходимость на порядки. Использование фиксированного $\rho$ без адаптации является частой ошибкой новичков. Неэффективность для гладких задач малой размерности: Если $f$ и $g$ гладкие, а размерность пространства невелика, методы квазиньютоновские (например, L-BFGS) или методы внутренней точки будут значительно быстрее. Проблемы с невыпуклостью: Применение классического ADMM к невыпуклым задачам без модификаций (например, без проксимальных добавок) может привести к осцилляциям или расходимости. Масштабирование матриц: Если матрицы $A$ и $B$ плохо обусловлены, сходимость ADMM может резко ухудшиться; в таких случаях требуется предварительное масштабирование (preconditioning) переменных.

Литература

Boyd S., Parikh N., Chu E., Peleato B., Eckstein J. Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers. — Foundations and Trends in Machine Learning. — 2011 T. 3. — С. 1—122. Glowinski R., Marroco A. Sur l'approximation, par éléments finis d'ordre un, et la résolution, par pénalisation-dualité d'une classe de problèmes de Dirichlet non linéaires // Revue française d'automatique, informatique, recherche opérationnelle: Журнал. — 1975. — Т. 9. — № 2. — С. 41—76. Gabay D., Mercier B. A dual algorithm for the solution of nonlinear variational problems via finite element approximation // Computers & Mathematics with Applications: Журнал. — 1976. — Т. 2. — № 1. — С. 17—40. Hong M., Luo Z. Q. On the Linear Convergence of the Alternating Direction Method of Multipliers // Mathematical Programming: Журнал. — 2017. — Т. 162. — № 1. — С. 165—199.

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%BF%D0%B5%D1%80%D0%B5%D0%BC%D0%B5%D0%BD%D0%BD%D0%BE%D0%B3%D0%BE_%D0%BD%D0%B0%D0%BF%D1%80%D0%B0%D0%B2%D0%BB%D0%B5%D0%BD%D0%B8%D1%8F_%D0%BC%D0%BD%D0%BE%D0%B6%D0%B8%D1%82%D0%B5%D0%BB%D0%B5%D0%B9_%E2%80%94_ADMM»

Категории: Методы оптимизации | Машинное обучение | Энциклопедия анализа данных | Распределенные вычисления | Выпуклая оптимизация