Метод Левенберга — Марквардта

Метод Левенберга — Марквардта (также известный как метод демпфированных наименьших квадратов) — это численный метод оптимизации, предназначенный для решения задач нелинейного метода наименьших квадратов. Он сочетает в себе свойства градиентного спуска (метода наискорейшего спуска) и метода Гаусса — Ньютона, что позволяет ему эффективно находить локальный минимум функции суммы квадратов невязок. Метод широко применяется в задачах аппроксимации данных (подгонки кривых), регрессионного анализа, машинного обучения, компьютерного зрения и робототехники.

История

Метод был независимо разработан двумя математиками: Кеннетом Левенбергом, который опубликовал свою работу в 1944 году в журнале Quarterly of Applied Mathematics, и Дональдом Марквардтом, который представил усовершенствованную версию алгоритма в 1963 году в Journal of the Society for Industrial and Applied Mathematics. Левенберг предложил алгоритм для решения задач, возникающих при аппроксимации кривых, введя параметр регуляризации (демпфирования), который стабилизирует сходимость. Марквардт независимо переоткрыл метод, добавив к нему стратегию автоматической регулировки этого параметра, что сделало алгоритм более практичным и надёжным. С тех пор метод Левенберга — Марквардта стал стандартным инструментом в численной оптимизации, особенно в областях, где требуется подгонка моделей к экспериментальным данным.

Основная идея

Метод Левенберга — Марквардта решает задачу минимизации функции стоимости, представляющей собой сумму квадратов невязок:

\[ S(\boldsymbol{\beta}) = \sum_{i=1}^{m} r_i(\boldsymbol{\beta})^2, \]

где \(\boldsymbol{\beta} \in \mathbb{R}^n\) — вектор параметров модели, а \(r_i(\boldsymbol{\beta})\) — невязка между наблюдаемым значением и предсказанием модели для \(i\)-го наблюдения. Цель — найти \(\boldsymbol{\beta}^*\), минимизирующее \(S\).

Алгоритм является итерационным. На каждой итерации он вычисляет вектор приращений \(\boldsymbol{\delta}\), который добавляется к текущей оценке параметров: \(\boldsymbol{\beta}_{k+1} = \boldsymbol{\beta}_k + \boldsymbol{\delta}_k\). Вектор \(\boldsymbol{\delta}_k\) находится как решение системы линейных уравнений:

\[ (\mathbf{J}_k^T \mathbf{J}_k + \lambda_k \mathbf{I}) \boldsymbol{\delta}_k = -\mathbf{J}_k^T \mathbf{r}_k, \]

где:

\(\mathbf{J}_k\) — матрица Якоби (размером \(m \times n\)), элементы которой \(\frac{\partial r_i}{\partial \beta_j}\) вычислены в точке \(\boldsymbol{\beta}_k\);
\(\mathbf{r}_k\) — вектор невязок \((r_1, r_2, \dots, r_m)^T\);
\(\mathbf{I}\) — единичная матрица размером \(n \times n\);
\(\lambda_k \geq 0\) — параметр демпфирования (регуляризации).

Ключевая особенность метода — использование параметра \(\lambda_k\). Когда \(\lambda_k\) велико, член \(\lambda_k \mathbf{I}\) доминирует, и метод ведёт себя как градиентный спуск (с малым шагом в направлении антиградиента). Когда \(\lambda_k\) мало, метод приближается к методу Гаусса — Ньютона, который обеспечивает быструю сходимость вблизи минимума. Стратегия Марквардта заключается в адаптивном изменении \(\lambda_k\): если после шага функция стоимости уменьшается, \(\lambda_k\) уменьшают (чтобы ускорить сходимость); если шаг приводит к увеличению \(S\), \(\lambda_k\) увеличивают (чтобы сгладить ландшафт и избежать расходимости).

Алгоритм

Типичная реализация метода Левенберга — Марквардта включает следующие шаги:

Инициализация: задать начальное приближение \(\boldsymbol{\beta}_0\) и начальное значение параметра демпфирования \(\lambda_0\) (обычно \(\lambda_0 = 0.01\) или \(\lambda_0 = \max(\text{diag}(\mathbf{J}_0^T \mathbf{J}_0))\)). Установить порог сходимости \(\epsilon > 0\) и максимальное число итераций \(N\).
Вычисление: на \(k\)-й итерации вычислить матрицу Якоби \(\mathbf{J}_k\) и вектор невязок \(\mathbf{r}_k\).
Решение системы: найти \(\boldsymbol{\delta}_k\) из уравнения \((\mathbf{J}_k^T \mathbf{J}_k + \lambda_k \mathbf{I}) \boldsymbol{\delta}_k = -\mathbf{J}_k^T \mathbf{r}_k\).
Проверка уменьшения: вычислить \(S(\boldsymbol{\beta}_k + \boldsymbol{\delta}_k)\).

Если \(S(\boldsymbol{\beta}_k + \boldsymbol{\delta}_k) < S(\boldsymbol{\beta}_k)\): принять шаг, \(\boldsymbol{\beta}_{k+1} = \boldsymbol{\beta}_k + \boldsymbol{\delta}_k\), уменьшить \(\lambda_k\) (например, \(\lambda_{k+1} = \lambda_k / 10\)).
Иначе: отклонить шаг, увеличить \(\lambda_k\) (например, \(\lambda_{k+1} = \lambda_k \cdot 10\)), и повторить шаг 3 с новым \(\lambda_k\).

Проверка сходимости: если \(\|\boldsymbol{\delta}_k\| < \epsilon\) или \(S(\boldsymbol{\beta}_k) < \epsilon\), или превышено \(N\), остановиться. Иначе перейти к шагу 2.

На практике часто используют более сложные критерии сходимости, например, по норме градиента \(\|\mathbf{J}_k^T \mathbf{r}_k\|\) или по относительному изменению функции стоимости.

Свойства и особенности

Скорость сходимости: вблизи минимума метод демонстрирует квадратичную сходимость, как и метод Гаусса — Ньютона, при условии, что невязки малы. Вдали от минимума он ведёт себя как градиентный спуск с линейной сходимостью.
Устойчивость: благодаря демпфированию метод менее чувствителен к начальному приближению, чем чистый метод Гаусса — Ньютона, и может сходиться даже в случае вырожденной или плохо обусловленной матрицы \(\mathbf{J}_k^T \mathbf{J}_k\).
Вычислительная сложность: на каждой итерации требуется вычисление матрицы Якоби (что может быть дорого для больших \(m\) и \(n\)) и решение системы линейных уравнений размером \(n \times n\), что имеет сложность \(O(n^3)\).
Локальный оптимум: метод находит только локальный минимум. Для задач с несколькими локальными минимумами требуется выбор хорошего начального приближения или использование методов глобальной оптимизации.
Параметр демпфирования: стратегия изменения \(\lambda_k\) (например, по правилу Марквардта или с использованием коэффициента усиления) существенно влияет на сходимость. Слишком быстрое уменьшение \(\lambda_k\) может привести к расходимости, слишком медленное — к медленной сходимости.

Применение

Метод Левенберга — Марквардта является одним из наиболее популярных алгоритмов для решения задач нелинейного метода наименьших квадратов. Основные области применения включают:

Аппроксимация данных: подгонка параметров нелинейных моделей (экспоненциальных, логарифмических, синусоидальных) к экспериментальным данным в физике, химии, биологии, экономике.
Компьютерное зрение: калибровка камер (оценка внутренних и внешних параметров), реконструкция трёхмерных сцен по двумерным изображениям (структура из движения, bundle adjustment).
Робототехника: одновременная локализация и построение карты (SLAM), калибровка датчиков, оптимизация траекторий.
Машинное обучение: обучение нейронных сетей с малым числом параметров (например, в задачах регрессии), оценка параметров вероятностных моделей.
Обработка сигналов: оценка параметров сигналов (частоты, фазы, амплитуды) в спектральном анализе.

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

Градиентный спуск: метод Левенберга — Марквардта обычно сходится быстрее, особенно вблизи минимума, но требует вычисления матрицы Якоби и решения системы уравнений, что вычислительно дороже.
Метод Гаусса — Ньютона: метод Левенберга — Марквардта более устойчив к плохой обусловленности и плохим начальным приближениям, но может быть медленнее вдали от минимума из-за демпфирования.
Метод Бройдена — Флетчера — Гольдфарба — Шанно (BFGS): квазиньютоновские методы, такие как BFGS, не требуют вычисления матрицы Якоби (используют приближение гессиана), что может быть эффективнее для задач с большим числом параметров. Однако метод Левенберга — Марквардта часто оказывается более эффективным для задач с малым числом параметров и большим числом наблюдений.

Ограничения

Метод не гарантирует нахождение глобального минимума; для многоэкстремальных функций требуется комбинация с глобальными стратегиями (например, мультистарт).
Вычислительные затраты растут с увеличением числа параметров \(n\) из-за необходимости решения системы \(n \times n\) на каждой итерации.
При наличии большого числа наблюдений \(m\) вычисление полной матрицы Якоби может быть ресурсоёмким. В таких случаях применяют разреженные версии метода или стохастические приближения.
Метод чувствителен к выбросам в данных, так как использует квадратичную функцию стоимости. Для устойчивости к выбросам применяют робастные версии (например, с M-оценками).

Реализации

Метод Левенберга — Марквардта реализован во многих библиотеках численного анализа и математического программного обеспечения:

MATLAB: функция lsqnonlin (в составе Optimization Toolbox) использует метод Левенберга — Марквардта.
Python: реализован в библиотеках scipy.optimize.least_squares (с опцией method='lm') и lmfit.
C++: библиотеки Eigen (модуль NonLinearOptimization), Ceres Solver, GSL (GNU Scientific Library).
R: функция nls.lm из пакета minpack.lm.
Julia: пакет LsqFit.jl.

Источники

Левенберг, К. (1944). "A method for the solution of certain non-linear problems in least squares". Quarterly of Applied Mathematics, 2(2), 164–168.
Марквардт, Д. (1963). "An algorithm for least-squares estimation of nonlinear parameters". Journal of the Society for Industrial and Applied Mathematics, 11(2), 431–441.
Нокедал, Ж., Райт, С. (2006). Numerical Optimization. Springer.
Бейтс, Д., Уоттс, Д. (1988). Nonlinear Regression Analysis and Its Applications. Wiley.

BFOmetr — база данных и аналитика по компаниям России.

На главную BFOmetr →