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

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

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

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

$F({\vec {x}})=\|{\vec {f}}({\vec {x}})\|^{2}=\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}})=2J^{T}({\vec {x}}){\vec {f}}({\vec {x}}),$

$H({\vec {x}})=2J^{T}({\vec {x}})J({\vec {x}})+2Q({\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}}){\vec {f}}({\vec {x}}).$

Алгоритм

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

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

где $\lambda _{k}$ — некоторая неотрицательная константа, своя для каждого шага, $I$ — единичная матрица.

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

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

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

${\vec {p}}_{k}=\mathrm {arg} \min _{\|{\vec {p}}\|\leqslant \Delta }\|J({\vec {x}}_{k}){\vec {p}}+{\vec {f}}({\vec {x}}_{k})\|,$

где $\Delta$ — параметр, связанный с $\lambda _{k}$.

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

Нетрудно заметить, что при $\lambda _{k}=0$ алгоритм вырождается в метод Гаусса — Ньютона, а при достаточно большом $\lambda _{k}$ направление ${\vec {p}}_{k}$ незначительно отличается от направления наискорейшего спуска. Таким образом, при правильном подборе параметра $\lambda _{k}$ добиваются монотонного убывания минимизируемой функции. Неравенство $F({\vec {x}}_{k+1})<F({\vec {x}}_{k})$ всегда можно обеспечить, выбрав $\lambda _{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}).$

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

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

$m({\vec {p}})={\vec {f}}({\vec {x}}_{k})+J({\vec {x}}_{k}){\vec {p}}+{\frac {1}{2}}{\vec {p}}\,^{T}H{\vec {p}}.$

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

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

Литература

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

Ссылки

• Метод Левенберга-Марквардта библиотека ALGLIB - реализация метода в OpenSource библиотеке ALGLIB. Несколько языков программирования.