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

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

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

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

$F(\stackrel{\to <!--\; \to \; -->}{x})=\Vert <!--\; \Vert \; -->\stackrel{\to <!--\; \to \; -->}{f}(\stackrel{\to <!--\; \to \; -->}{x}){\Vert <!--\; \Vert \; -->}^2=\underset{i=1}{\overset{m}{\sum <!--\; \sum \; -->}}{f}_i^2(\stackrel{\to <!--\; \to \; -->}{x})=\underset{i=1}{\overset{m}{\sum <!--\; \sum \; -->}}({\mathrm{\phi <!--\; \phi \; -->}}_i(\stackrel{\to <!--\; \to \; -->}{x})-<!--\; -\; -->{\mathcal{F}}_i{)}^2\to <!--\; \to \; -->min.$$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 \!.$ 

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

$\mathrm{\nabla <!--\; \nabla \; -->}F(\stackrel{\to <!--\; \to \; -->}{x})=2J^T(\stackrel{\to <!--\; \to \; -->}{x})\stackrel{\to <!--\; \to \; -->}{f}(\stackrel{\to <!--\; \to \; -->}{x}),$$\nabla F({\vec {x}})=2J^{T}({\vec {x}}){\vec {f}}({\vec {x}}),$ 

$H(\stackrel{\to <!--\; \to \; -->}{x})=2J^T(\stackrel{\to <!--\; \to \; -->}{x})J(\stackrel{\to <!--\; \to \; -->}{x})+2Q(\stackrel{\to <!--\; \to \; -->}{x}),Q(\stackrel{\to <!--\; \to \; -->}{x})=\underset{i=1}{\overset{m}{\sum <!--\; \sum \; -->}}{f}_i(\stackrel{\to <!--\; \to \; -->}{x})H_i(\stackrel{\to <!--\; \to \; -->}{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(\stackrel{\to <!--\; \to \; -->}{x})$$J({\vec {x}})$  — матрица Якоби вектор-функции $\stackrel{\to <!--\; \to \; -->}{f}(\stackrel{\to <!--\; \to \; -->}{x})$${\vec {f}}({\vec {x}})$ , $H_i(\stackrel{\to <!--\; \to \; -->}{x})$$H_{i}({\vec {x}})$  — матрица Гессе для её компоненты $f_i(\stackrel{\to <!--\; \to \; -->}{x})$$f_{i}({\vec {x}})$ .

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

$J^T(\stackrel{\to <!--\; \to \; -->}{x})J(\stackrel{\to <!--\; \to \; -->}{x})\stackrel{\to <!--\; \to \; -->}{p}=-<!--\; -\; -->J^T(\stackrel{\to <!--\; \to \; -->}{x})\stackrel{\to <!--\; \to \; -->}{f}(\stackrel{\to <!--\; \to \; -->}{x}).$$J^{T}({\vec {x}})J({\vec {x}}){\vec {p}}=-J^{T}({\vec {x}}){\vec {f}}({\vec {x}}).$ 

АлгоритмПравить

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

$[J^T({\stackrel{\to <!--\; \to \; -->}{x}}_k)J({\stackrel{\to <!--\; \to \; -->}{x}}_k)+{\mathrm{\lambda <!--\; \lambda \; -->}}_{k}I]{\stackrel{\to <!--\; \to \; -->}{p}}_k=-<!--\; -\; -->J^T({\stackrel{\to <!--\; \to \; -->}{x}}_k)\stackrel{\to <!--\; \to \; -->}{f}({\stackrel{\to <!--\; \to \; -->}{x}}_k),$$[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}),$ 

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

${\stackrel{\to <!--\; \to \; -->}{x}}_{k+1}={\stackrel{\to <!--\; \to \; -->}{x}}_k+{\stackrel{\to <!--\; \to \; -->}{p}}_k.$${\vec {x}}_{{k+1}}={\vec {x}}_{k}+{\vec {p}}_{k}.$ 

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

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

${\stackrel{\to <!--\; \to \; -->}{p}}_k=\mathrm{a}\mathrm{r}\mathrm{g}\underset{\Vert <!--\; \Vert \; -->\stackrel{\to <!--\; \to \; -->}{p}\Vert <!--\; \Vert \; -->⩽<!--\; ⩽\; -->\mathrm{\Delta <!--\; \Delta \; -->}}{min}\Vert <!--\; \Vert \; -->J({\stackrel{\to <!--\; \to \; -->}{x}}_k)\stackrel{\to <!--\; \to \; -->}{p}+\stackrel{\to <!--\; \to \; -->}{f}({\stackrel{\to <!--\; \to \; -->}{x}}_k)\Vert <!--\; \Vert \; -->,$${\vec {p}}_{k}={\mathrm {arg}}\min _{{\|{\vec {p}}\|\leqslant \Delta }}\|J({\vec {x}}_{k}){\vec {p}}+{\vec {f}}({\vec {x}}_{k})\|,$ 

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

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

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

$\left\{J^T({\stackrel{\to <!--\; \to \; -->}{x}}_k)J({\stackrel{\to <!--\; \to \; -->}{x}}_k)+{\mathrm{\lambda <!--\; \lambda \; -->}}_k\mathrm{d}\mathrm{i}\mathrm{a}\mathrm{g}[J^T({\stackrel{\to <!--\; \to \; -->}{x}}_k)J({\stackrel{\to <!--\; \to \; -->}{x}}_k)]\right\}{\stackrel{\to <!--\; \to \; -->}{p}}_k=-<!--\; -\; -->J^T({\stackrel{\to <!--\; \to \; -->}{x}}_k)f({\stackrel{\to <!--\; \to \; -->}{x}}_k).$$\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}).$ 

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

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

$m(\stackrel{\to <!--\; \to \; -->}{p})=\stackrel{\to <!--\; \to \; -->}{f}({\stackrel{\to <!--\; \to \; -->}{x}}_k)+J({\stackrel{\to <!--\; \to \; -->}{x}}_k)\stackrel{\to <!--\; \to \; -->}{p}+\frac{1}{2}\stackrel{\to <!--\; \to \; -->}{p}{}^{T}H\stackrel{\to <!--\; \to \; -->}{p}.$$m({\vec {p}})={\vec {f}}({\vec {x}}_{k})+J({\vec {x}}_{k}){\vec {p}}+{\frac {1}{2}}{\vec {p}}\,^{T}H{\vec {p}}.$ 

При этом шаг ${\stackrel{\to <!--\; \to \; -->}{p}}_k$${\vec {p}}_{k}$  определяется исходя из задачи минимизации:

$\Vert <!--\; \Vert \; -->m(\stackrel{\to <!--\; \to \; -->}{p})\Vert <!--\; \Vert \; -->\to <!--\; \to \; -->\underset{\Vert <!--\; \Vert \; -->\stackrel{\to <!--\; \to \; -->}{p}\Vert <!--\; \Vert \; -->⩽<!--\; ⩽\; -->\mathrm{\Delta <!--\; \Delta \; -->}}{min}.$$\|m({\vec {p}})\|\to \min _{{\|{\vec {p}}\|\leqslant \Delta }}\!.$ 

ЛитератураПравить

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

СсылкиПравить

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