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

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

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

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

${\displaystyle 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 \!.}$

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

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

${\displaystyle 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}}),}$

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

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

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

Алгоритм

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

${\displaystyle [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}),}$

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

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

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

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

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

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

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

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

${\displaystyle \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}).}$

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

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

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

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

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

Примечания

1. Б. Т. Поляк. Метод Ньютона и его роль в оптимизации и вычислительной математике // Труды Института Системного Анализа Российской Академии Наук. — 2006. — Т. 28. — С. 44–62. Архивировано 24 октября 2018 года.

Литература

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

Ссылки

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