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

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

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

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

$F(\overrightarrow{x})=\Vert \overrightarrow{f}(\overrightarrow{x}){\Vert }^2=\sum _{i=1}^m{f}_i^2(\overrightarrow{x})=\sum _{i=1}^m({\phi }_i(\overrightarrow{x})-{ℱ}_i{)}^2\to \min .$

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

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

$H(\overrightarrow{x})=2J^T(\overrightarrow{x})J(\overrightarrow{x})+2Q(\overrightarrow{x}),Q(\overrightarrow{x})=\sum _{i=1}^m{f}_i(\overrightarrow{x})H_i(\overrightarrow{x}),$

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

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

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

Алгоритм

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

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

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

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

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

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

${\overrightarrow{p}}_k=\mathrm{a}\mathrm{r}\mathrm{g}\underset{\Vert \overrightarrow{p}\Vert ⩽\mathrm{\Delta }}{\min }\Vert J({\overrightarrow{x}}_k)\overrightarrow{p}+\overrightarrow{f}({\overrightarrow{x}}_k)\Vert ,$

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

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

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

$\{J^T({\overrightarrow{x}}_k)J({\overrightarrow{x}}_k)+{\lambda }_k\mathrm{d}\mathrm{i}\mathrm{a}\mathrm{g}[J^T({\overrightarrow{x}}_k)J({\overrightarrow{x}}_k)]\}{\overrightarrow{p}}_k=-J^T({\overrightarrow{x}}_k)f({\overrightarrow{x}}_k).$

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

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

$m(\overrightarrow{p})=\overrightarrow{f}({\overrightarrow{x}}_k)+J({\overrightarrow{x}}_k)\overrightarrow{p}+\frac{1}{2}\overrightarrow{p}{}^{T}H\overrightarrow{p}.$

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

$\Vert m(\overrightarrow{p})\Vert \to \underset{\Vert \overrightarrow{p}\Vert ⩽\mathrm{\Delta }}{\min }.$

Литература

• Шаблон:Книга

Ссылки

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