Алгоритм Левенберга — Марквардта

Алгоритм Левенберга — Марквардта

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

Постановка задачи

Пусть имеется задача о наименьших квадратах вида:

$F(\vec{x})=\|\vec{f}(\vec{x})\|=\sum_{i=1}^m f_i^2(\vec{x})=\sum_{i=1}^m(\varphi_i(\vec{x})-\mathcal{F}_i)^2\to\min\!.$

Эта задача отличается особым видом градиента и матрицы Гессе:

$\nabla F(\vec{x})=J^T(\vec{x})f(\vec{x}),$

$H(\vec{x})=J^T(\vec{x})J(\vec{x})+Q(\vec{x}),\qquad Q(\vec{x})=\sum_{i=1}^m f_i(\vec{x})H_i(\vec{x}),$

где $J(\vec{x})$ — матрица Якоби вектор-функции $\vec{f}(\vec{x})$, $H_i(\vec{x})$ — матрица Гессе для её компоненты $f_i(\vec{x})$.

Тогда согласно методу Гаусса — Ньютона в предположении доминирующей роли слагаемого $J^T(\vec{x})J(\vec{x})$ над $Q(\vec{x})$ (то есть если норма $\|\vec{f}(\vec{x})\|$ значительно меньше максимального собственного значения матрицы $J^T(\vec{x})J(\vec{x})$) очередное направление $\vec{p}$ определяется из системы:

$J^T(\vec{x})J(\vec{x})\vec{p}=-J^T(\vec{x})f(\vec{x}).$

Алгоритм

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

$[J^T(\vec{x}_k)J(\vec{x}_k)+\lambda_k I]\vec{p}_k=-J^T(\vec{x}_k)f(\vec{x}_k),$

где λ_k — некоторая неотрицательная константа, своя для каждого шага, I — единичная матрица.

$\vec{x}_{k+1}=\vec{x}_k+\vec{p}_k.$

Выбор λ_k можно осуществлять, делая его достаточным для монотонного спуска по функции невязки $F(\vec{x})$, то есть увеличивать параметр до тех пор, пока не будет достигнуто условие $F(\vec{x}_{k+1})<F(\vec{x}_k)$. Также параметр λ_k можно устанавливать исходя из отношения между фактическими изменениями функции $\vec{f}(\vec{x})$, достигнутыми в результате пробных шагов, и ожидаемыми величинами этих изменений при интерполяции. Подобную процедуру построил Флетчер.

Также можно показать, что $\vec{p}_k$ удовлетворяет условию:

$\vec{p}_k=\mathrm{arg}\min_{\|p\|\leqslant\Delta}\|J(\vec{x}_k)\vec{p}+\vec{f}(\vec{x}_k)\|,$

где Δ — параметр, связанный с λ_k.

Комбинация градиентного спуска и метода Гаусса — Ньютона

Нетрудно заметить, что при λ_k = 0 алгоритм вырождается в метод Гаусса — Ньютона, а при достаточно большом λ_k направление $\vec{p}_k$ незначительно отличается от направления наискорейшего спуска. Таким образом, при правильном подборе параметра λ_k добиваются монотонного убывания минимизируемой функции. Неравенство $F(\vec{x}_{k+1})<F(\vec{x}_k)$ всегда можно обеспечить, выбрав λ_k достаточно большим. Однако при этом теряется информация о кривизне, заключённая в первом слагаемом, и проявляются все недостатки метода градиентного спуска: в местах пологого наклона антиградиент мал, а в местах с крутым наклоном — велик, в то время как в первом случае желательно делать большие шаги, а во втором — маленькие. Так, с одной стороны, если есть длинная и узкая впадина на поверхности, определяемой функцией невязки $F(\vec{x})$, то компоненты градиента вдоль основания впадины — малы, а в направлении к стенкам — велики, в то время как идти желательно по основанию оврага. Способ учёта информации о кривизне предложил Марквардт. Он заметил, что если заменить единичную матрицу на диагональ матрицы Гессе, то можно достичь увеличения шага вдоль пологих участков и уменьшения вдоль крутых спусков:

$\left\{J^T(\vec{x}_k)J(\vec{x}_k)+\lambda_k\mathrm{diag}\,[J^T(\vec{x}_k)J(\vec{x}_k)]\right\}\vec{p}_k=-J^T(\vec{x}_k)f(\vec{x}_k).$

Метод доверительных интервалов

При рассмотрении алгоритма Левенберга — Марквардта как метода доверительных интервалов с помощью эвристик выбирается интервал Δ, на котором строится приближение функции $\vec{f}(\vec{x})$:

$m(\vec{p})=\vec{f}(\vec{x}_k)+J(\vec{x}_k)\vec{p}+\frac{1}{2}\vec{p}\,^TH\vec{p}.$

При этом шаг $\vec{p}_k$ определяется исходя из задачи минимизации:

$\|m(\vec{p})\|\to\min_{\|p\|\leqslant\Delta}\!.$

Литература

• Гилл Ф., Мюррей У., Райт М. Практическая оптимизация = Practical optimization.