Метод переменного направления множителей — ADMM
Материал из MachineLearning.
| Статья написана с использованием LLM Qwen3.7-Plus и проверена участником Mariia Shubina 23:17, 18 июля 2026 (MSD) |
|
Введение
Метод переменного направления множителей (англ. Alternating Direction Method of Multipliers, ADMM) — это мощный алгоритм выпуклой оптимизации, предназначенный для решения задач, которые можно декомпозировать на более мелкие и простые подзадачи. Алгоритм сочетает в себе декомпозируемость и масштабируемость метода двойственного подъема (dual ascent) с превосходными свойствами сходимости метода множителей Лагранжа. В последние годы ADMM стал стандартом де-факто для решения задач с негладкими целевыми функциями (например, содержащими L1-норму или ядерную норму) и является фундаментальным инструментом в распределенных вычислениях и машинном обучении, где данные физически разделены между множеством вычислительных узлов.
Формальная постановка задачи
Классическая задача, решаемая методом ADMM, имеет следующий вид:
при условии
где
и
— векторы переменных,
,
,
. Функции
и
предполагаются собственными, замкнутыми и выпуклыми, но не обязательно гладкими.
Расширенный лагранжиан
В основе метода лежит функция расширенного лагранжиана (Augmented Lagrangian), которая добавляет квадратичный штраф за нарушение линейных ограничений к классическому лагранжиану:
где — вектор двойственных переменных (множителей Лагранжа), а
— скалярный параметр штрафа (penalty parameter).
Алгоритм ADMM
Алгоритм итеративно обновляет переменные ,
и
, чередуя (alternating) минимизацию по каждой из них при фиксированных остальных.
Псевдокод
Инициализировать и выбрать параметр
Для
до сходимости:
Интуиция и отличие от классических методов
Классический метод множителей минимизирует по
и
совместно (jointly), что часто вычислительно сложно. ADMM минимизирует их поочередно (alternatingly). Это позволяет разделить задачу на две независимые подзадачи. Если матрицы
и
имеют блочно-диагональную структуру, x-шаг и z-шаг могут выполняться полностью параллельно, что является ключевым преимуществом метода.
Теоретические результаты
Условия сходимости
Если функции и
выпуклы, и нестрогий лагранжиан
имеет седловую точку, то при любом
последовательность, генерируемая ADMM, сходится:
Ограничения выполняются асимптотически:
.
Целевая функция сходится к оптимуму:
.
Двойственные переменные сходятся:
, где
— оптимальный множитель Лагранжа.
Скорость сходимости
Для общих выпуклых задач ADMM гарантирует скорость сходимости как по значению целевой функции, так и по нарушению ограничений (в смысле средних значений итераций). При дополнительных предположениях (сильная выпуклость и гладкость
или
) может быть достигнута линейная скорость сходимости
для некоторого
.
Роль параметров и остатков (Residuals)
Параметр не влияет на конечную точку сходимости, но критически важен для скорости сходимости. Контроль сходимости осуществляется через два типа остатков:
Прямой остаток (Primal residual):
. Он измеряет допустимость текущего решения.
Двойственный остаток (Dual residual):
. Он измеряет оптимальность условий Каруша — Куна — Таккера.
На практике часто используют адаптивные схемы обновления
: если
, параметр
увеличивают (чтобы усилить штраф за нарушение ограничений); если
, параметр
уменьшают.
Варианты и обобщения метода
Consensus ADMM (Распределенный консенсус)
Для задач вида вводится локальная переменная
для каждого узла и глобальная переменная
с ограничением
. Это позволяет каждому узлу решать свою подзадачу независимо, обмениваясь с центральным сервером только усредненными значениями, что минимизирует передачу данных в распределенном машинном обучении.
Стохастический ADMM
В задачах, где вычисление точного градиента или проксимального оператора на x-шаге слишком дорого, используется стохастическая аппроксимация. Это позволяет применять метод к огромным наборам данных, обрабатывая мини-батчи, аналогично стохастическому градиентному спуску.
Невыпуклый ADMM
Хотя строгие гарантии сходимости отсутствуют, модификации ADMM успешно применяются к невыпуклым задачам (например, обучение глубоких нейронных сетей с ограничениями или задачи фазовой реконструкции), часто с добавлением проксимальных членов для стабилизации итераций.
Применения в машинном обучении
Регуляризация и разреженные модели: Задача Lasso () идеально ложится на ADMM. x-шаг сводится к решению системы линейных уравнений, а z-шаг имеет аналитическое решение через оператор мягкого порога (soft-thresholding).
Матричное пополнение (Matrix completion): Восстановление матриц с низкой ранговой структурой путем минимизации ядерной нормы (nuclear norm), которая является негладкой, но имеет простой проксимальный оператор (сингулярное пороговое сжатие).
Метод опорных векторов (SVM): ADMM позволяет эффективно обучать SVM на распределенных данных, избегая передачи сырых данных между узлами.
Обучение нейронных сетей: Разделение слоев сети на разные блоки переменных для распараллеливания обучения или наложения жестких структурных ограничений на веса.
Сравнение с другими методами оптимизации
Градиентный спуск и его варианты: Требуют гладкости функции. ADMM превосходит их в задачах с негладкими регуляризаторами, так как инкапсулирует негладкость в проксимальный оператор.
Метод внутренней точки: Обладает квадратичной скоростью сходимости и идеален для задач малой и средней размерности. Однако он плохо масштабируется на высокие размерности и распределенные системы из-за необходимости решения плотных систем линейных уравнений на каждой итерации.
Координатный спуск: Обновляет одну скалярную переменную за раз. ADMM обновляет целые блоки переменных, что лучше использует векторные инструкции процессора и позволяет достичь высокого уровня параллелизма.
Метод двойственного подъема (Dual Ascent): Не требует квадратичного штрафа, но сходится только при строгих предположениях (например, сильная выпуклость). ADMM сходится в гораздо более широком классе задач благодаря члену .
Ограничения и типичные ошибки
Чувствительность к выбору : Неудачный выбор параметра штрафа может замедлить сходимость на порядки. Использование фиксированного
без адаптации является частой ошибкой новичков.
Неэффективность для гладких задач малой размерности: Если
и
гладкие, а размерность пространства невелика, методы квазиньютоновские (например, L-BFGS) или методы внутренней точки будут значительно быстрее.
Проблемы с невыпуклостью: Применение классического ADMM к невыпуклым задачам без модификаций (например, без проксимальных добавок) может привести к осцилляциям или расходимости.
Масштабирование матриц: Если матрицы
и
плохо обусловлены, сходимость 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.
