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

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

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

Перейти к: навигация, поиск

Версия 20:34, 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)$

при условии

$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://www.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»

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

@@ Строка 1: / Строка 1: @@
 {{well|Статья написана с использованием LLM Qwen3.7-Plus и проверена участником [[Участник:Mariia Shubina|Mariia Shubina]] 23:17, 18 июля 2026 (MSD)}}
 {{TOCright}}
 == Введение ==
 [[Метод переменного направления множителей]] (англ. Alternating Direction Method of Multipliers, ADMM) — это мощный алгоритм [[Выпуклая оптимизация|выпуклой оптимизации]], предназначенный для решения задач, которые можно декомпозировать на более мелкие и простые подзадачи. Алгоритм сочетает в себе декомпозируемость и масштабируемость метода двойственного подъема (dual ascent) с превосходными свойствами сходимости метода множителей Лагранжа.
 В последние годы ADMM стал стандартом де-факто для решения задач с негладкими целевыми функциями (например, содержащими [[L1-регуляризация|L1-норму]] или ядерную норму) и является фундаментальным инструментом в [[Распределенные вычисления|распределенных вычислениях]] и [[Машинное обучение|машинном обучении]], где данные физически разделены между множеством вычислительных узлов.
 == Формальная постановка задачи ==
 Классическая задача, решаемая методом ADMM, имеет следующий вид:
-<tex>\min_{x, z} f(x) + g(z)</tex>
+:: <tex>\min_{x, z} f(x) + g(z)</tex>
 при условии
+:: <tex>Ax + Bz = c</tex>
+где <tex>x \in \mathbb{R}^n</tex> и <tex>z \in \mathbb{R}^m</tex> — векторы переменных, <tex>A \in \mathbb{R}^{p \times n}</tex>, <tex>B \in \mathbb{R}^{p \times m}</tex>, <tex>c \in \mathbb{R}^p</tex>. Функции <tex>f: \mathbb{R}^n \to \mathbb{R} \cup \{+\infty\}</tex> и <tex>g: \mathbb{R}^m \to \mathbb{R} \cup \{+\infty\}</tex> предполагаются собственными, замкнутыми и выпуклыми, но не обязательно гладкими.
-<tex>Ax + Bz = c</tex>
-где <tex>x \in \mathbb{R}^n</tex> и <tex>z \in \mathbb{R}^m</tex> — векторы переменных, <tex>A \in \mathbb{R}^{p \times n}</tex>, <tex>B \in \mathbb{R}^{p \times m}</tex>, <tex>c \in \mathbb{R}^p</tex>. Функции <tex>f: \mathbb{R}^n \to \mathbb{R} \cup {+\infty}</tex> и <tex>g: \mathbb{R}^m \to \mathbb{R} \cup {+\infty}</tex> предполагаются собственными, замкнутыми и выпуклыми, но не обязательно гладкими.
 === Расширенный лагранжиан ===
 В основе метода лежит функция расширенного лагранжиана (Augmented Lagrangian), которая добавляет квадратичный штраф за нарушение линейных ограничений к классическому лагранжиану:
-:: <tex>L_\rho(x, z, y) = f(x) + g(z) + y^T(Ax + Bz - c) + \frac{\rho}{2} |Ax + Bz - c|_2^2</tex>
+:: <tex>L_\rho(x, z, y) = f(x) + g(z) + y^T(Ax + Bz - c) + \frac{\rho}{2} \|Ax + Bz - c\|_2^2</tex>
 где <tex>y \in \mathbb{R}^p</tex> — вектор двойственных переменных (множителей Лагранжа), а <tex>\rho > 0</tex> — скалярный параметр штрафа (penalty parameter).
 == Алгоритм ADMM ==
 Алгоритм итеративно обновляет переменные <tex>x</tex>, <tex>z</tex> и <tex>y</tex>, чередуя (alternating) минимизацию по каждой из них при фиксированных остальных.
 === Псевдокод ===
-Инициализировать <tex>x^0, z^0, y^0</tex> и выбрать параметр <tex>\rho > 0</tex>
+# Инициализировать <tex>x^0, z^0, y^0</tex> и выбрать параметр <tex>\rho > 0</tex>
-Для <tex>k = 0, 1, 2, \dots</tex> до сходимости:
+# Для <tex>k = 0, 1, 2, \dots</tex> до сходимости:
-<tex>x^{k+1} := \arg\min_x L_\rho(x, z^k, y^k)</tex>
+#     <tex>x^{k+1} := \arg\min_x L_\rho(x, z^k, y^k)</tex>
-<tex>z^{k+1} := \arg\min_z L_\rho(x^{k+1}, z, y^k)</tex>
+#     <tex>z^{k+1} := \arg\min_z L_\rho(x^{k+1}, z, y^k)</tex>
-<tex>y^{k+1} := y^k + \rho(Ax^{k+1} + Bz^{k+1} - c)</tex>
+#     <tex>y^{k+1} := y^k + \rho(Ax^{k+1} + Bz^{k+1} - c)</tex>
 === Интуиция и отличие от классических методов ===
 Классический метод множителей минимизирует <tex>L_\rho(x, z, y^k)</tex> по <tex>x</tex> и <tex>z</tex> совместно (jointly), что часто вычислительно сложно. ADMM минимизирует их поочередно (alternatingly). Это позволяет разделить задачу на две независимые подзадачи. Если матрицы <tex>A</tex> и <tex>B</tex> имеют блочно-диагональную структуру, x-шаг и z-шаг могут выполняться полностью параллельно, что является ключевым преимуществом метода.
 == Теоретические результаты ==
 === Условия сходимости ===
 Если функции <tex>f</tex> и <tex>g</tex> выпуклы, и нестрогий лагранжиан <tex>L_0(x, z, y)</tex> имеет седловую точку, то при любом <tex>\rho > 0</tex> последовательность, генерируемая ADMM, сходится:
-Ограничения выполняются асимптотически: <tex>Ax^k + Bz^k - c \to 0</tex>.
+* Ограничения выполняются асимптотически: <tex>Ax^k + Bz^k - c \to 0</tex>.
-Целевая функция сходится к оптимуму: <tex>f(x^k) + g(z^k) \to f(x^) + g(z^)</tex>.
+* Целевая функция сходится к оптимуму: <tex>f(x^k) + g(z^k) \to f(x^*) + g(z^*)</tex>.
-Двойственные переменные сходятся: <tex>y^k \to y^</tex>, где <tex>y^</tex> — оптимальный множитель Лагранжа.
+* Двойственные переменные сходятся: <tex>y^k \to y^*</tex>, где <tex>y^*</tex> — оптимальный множитель Лагранжа.
 === Скорость сходимости ===
 Для общих выпуклых задач ADMM гарантирует скорость сходимости <tex>O(1/k)</tex> как по значению целевой функции, так и по нарушению ограничений (в смысле средних значений итераций). При дополнительных предположениях (сильная выпуклость и гладкость <tex>f</tex> или <tex>g</tex>) может быть достигнута линейная скорость сходимости <tex>O(c^k)</tex> для некоторого <tex>c \in (0, 1)</tex>.
 == Роль параметров и остатков (Residuals) ==
 Параметр <tex>\rho</tex> не влияет на конечную точку сходимости, но критически важен для скорости сходимости. Контроль сходимости осуществляется через два типа остатков:
-Прямой остаток (Primal residual): <tex>r^k = Ax^k + Bz^k - c</tex>. Он измеряет допустимость текущего решения.
+* Прямой остаток (Primal residual): <tex>r^k = Ax^k + Bz^k - c</tex>. Он измеряет допустимость текущего решения.
-Двойственный остаток (Dual residual): <tex>s^k = \rho A^T B (z^k - z^{k-1})</tex>. Он измеряет оптимальность условий Каруша — Куна — Таккера.
+* Двойственный остаток (Dual residual): <tex>s^k = \rho A^T B (z^k - z^{k-1})</tex>. Он измеряет оптимальность условий Каруша — Куна — Таккера.
-На практике часто используют адаптивные схемы обновления <tex>\rho</tex>: если <tex>|r^k|_2 \gg |s^k|_2</tex>, параметр <tex>\rho</tex> увеличивают (чтобы усилить штраф за нарушение ограничений); если <tex>|s^k|_2 \gg |r^k|_2</tex>, параметр <tex>\rho</tex> уменьшают.
+На практике часто используют адаптивные схемы обновления <tex>\rho</tex>: если <tex>\|r^k\|_2 \gg \|s^k\|_2</tex>, параметр <tex>\rho</tex> увеличивают (чтобы усилить штраф за нарушение ограничений); если <tex>\|s^k\|_2 \gg \|r^k\|_2</tex>, параметр <tex>\rho</tex> уменьшают.
 == Варианты и обобщения метода ==
 === Consensus ADMM (Распределенный консенсус) ===
 Для задач вида <tex>\min_x \sum_{i=1}^N f_i(x)</tex> вводится локальная переменная <tex>x_i</tex> для каждого узла и глобальная переменная <tex>z</tex> с ограничением <tex>x_i = z</tex>. Это позволяет каждому узлу решать свою подзадачу независимо, обмениваясь с центральным сервером только усредненными значениями, что минимизирует передачу данных в [[Распределенное машинное обучение|распределенном машинном обучении]].
 === Стохастический ADMM ===
 В задачах, где вычисление точного градиента или проксимального оператора на x-шаге слишком дорого, используется стохастическая аппроксимация. Это позволяет применять метод к огромным наборам данных, обрабатывая мини-батчи, аналогично [[Стохастический градиентный спуск|стохастическому градиентному спуску]].
 === Невыпуклый ADMM ===
 Хотя строгие гарантии сходимости отсутствуют, модификации ADMM успешно применяются к невыпуклым задачам (например, обучение глубоких [[Нейронная сеть|нейронных сетей]] с ограничениями или задачи фазовой реконструкции), часто с добавлением проксимальных членов для стабилизации итераций.
 == Применения в машинном обучении ==
-[[Регуляризация]] и разреженные модели: Задача Lasso (<tex>\min_x \frac{1}{2}|Ax - b|_2^2 + \lambda |x|_1</tex>) идеально ложится на ADMM. x-шаг сводится к решению системы линейных уравнений, а z-шаг имеет аналитическое решение через оператор мягкого порога (soft-thresholding).
+* [[Регуляризация]] и разреженные модели: Задача Lasso (<tex>\min_x \frac{1}{2}\|Ax - b\|_2^2 + \lambda \|x\|_1</tex>) идеально ложится на ADMM. x-шаг сводится к решению системы линейных уравнений, а z-шаг имеет аналитическое решение через оператор мягкого порога (soft-thresholding).
-[[Матричное пополнение]] (Matrix completion): Восстановление матриц с низкой ранговой структурой путем минимизации ядерной нормы (nuclear norm), которая является негладкой, но имеет простой проксимальный оператор (сингулярное пороговое сжатие).
+* [[Матричное пополнение]] (Matrix completion): Восстановление матриц с низкой ранговой структурой путем минимизации ядерной нормы (nuclear norm), которая является негладкой, но имеет простой проксимальный оператор (сингулярное пороговое сжатие).
-[[Метод опорных векторов]] (SVM): ADMM позволяет эффективно обучать SVM на распределенных данных, избегая передачи сырых данных между узлами.
+* [[Метод опорных векторов]] (SVM): ADMM позволяет эффективно обучать SVM на распределенных данных, избегая передачи сырых данных между узлами.
-[[Обучение нейронных сетей]]: Разделение слоев сети на разные блоки переменных для распараллеливания обучения или наложения жестких структурных ограничений на веса.
+* [[Обучение нейронных сетей]]: Разделение слоев сети на разные блоки переменных для распараллеливания обучения или наложения жестких структурных ограничений на веса.
 == Сравнение с другими методами оптимизации ==
-[[Градиентный спуск]] и его варианты: Требуют гладкости функции. ADMM превосходит их в задачах с негладкими регуляризаторами, так как инкапсулирует негладкость в проксимальный оператор.
+* [[Градиентный спуск]] и его варианты: Требуют гладкости функции. ADMM превосходит их в задачах с негладкими регуляризаторами, так как инкапсулирует негладкость в проксимальный оператор.
-[[Метод внутренней точки]]: Обладает квадратичной скоростью сходимости и идеален для задач малой и средней размерности. Однако он плохо масштабируется на высокие размерности и распределенные системы из-за необходимости решения плотных систем линейных уравнений на каждой итерации.
+* [[Метод внутренней точки]]: Обладает квадратичной скоростью сходимости и идеален для задач малой и средней размерности. Однако он плохо масштабируется на высокие размерности и распределенные системы из-за необходимости решения плотных систем линейных уравнений на каждой итерации.
-[[Координатный спуск]]: Обновляет одну скалярную переменную за раз. ADMM обновляет целые блоки переменных, что лучше использует векторные инструкции процессора и позволяет достичь высокого уровня параллелизма.
+* [[Координатный спуск]]: Обновляет одну скалярную переменную за раз. ADMM обновляет целые блоки переменных, что лучше использует векторные инструкции процессора и позволяет достичь высокого уровня параллелизма.
-Метод двойственного подъема (Dual Ascent): Не требует квадратичного штрафа, но сходится только при строгих предположениях (например, сильная выпуклость). ADMM сходится в гораздо более широком классе задач благодаря члену <tex>\rho</tex>.
+* Метод двойственного подъема (Dual Ascent): Не требует квадратичного штрафа, но сходится только при строгих предположениях (например, сильная выпуклость). ADMM сходится в гораздо более широком классе задач благодаря члену <tex>\rho</tex>.
 == Ограничения и типичные ошибки ==
-Чувствительность к выбору <tex>\rho</tex>: Неудачный выбор параметра штрафа может замедлить сходимость на порядки. Использование фиксированного <tex>\rho</tex> без адаптации является частой ошибкой новичков.
+* Чувствительность к выбору <tex>\rho</tex>: Неудачный выбор параметра штрафа может замедлить сходимость на порядки. Использование фиксированного <tex>\rho</tex> без адаптации является частой ошибкой новичков.
-Неэффективность для гладких задач малой размерности: Если <tex>f</tex> и <tex>g</tex> гладкие, а размерность пространства невелика, методы квазиньютоновские (например, [[L-BFGS]]) или методы внутренней точки будут значительно быстрее.
+* Неэффективность для гладких задач малой размерности: Если <tex>f</tex> и <tex>g</tex> гладкие, а размерность пространства невелика, методы квазиньютоновские (например, [[L-BFGS]]) или методы внутренней точки будут значительно быстрее.
-Проблемы с невыпуклостью: Применение классического ADMM к невыпуклым задачам без модификаций (например, без проксимальных добавок) может привести к осцилляциям или расходимости.
+* Проблемы с невыпуклостью: Применение классического ADMM к невыпуклым задачам без модификаций (например, без проксимальных добавок) может привести к осцилляциям или расходимости.
-Масштабирование матриц: Если матрицы <tex>A</tex> и <tex>B</tex> плохо обусловлены, сходимость ADMM может резко ухудшиться; в таких случаях требуется предварительное масштабирование (preconditioning) переменных.
+* Масштабирование матриц: Если матрицы <tex>A</tex> и <tex>B</tex> плохо обусловлены, сходимость 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 |том = 3 |номер = 1 |страницы = 1—122 }}
+* {{книга |автор = 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 |том = 3 |номер = 1 |страницы = 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 }}
+* {{статья |автор = 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 }}
+* {{статья |автор = 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 }}
+* {{статья |автор = Hong M., Luo Z. Q. |заглавие = On the Linear Convergence of the Alternating Direction Method of Multipliers |издание = Mathematical Programming |тип = Журнал |год = 2017 |том = 162 |номер = 1 |страницы = 165—199 }}
 <references/>