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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Алгоритм Левенберга — Марквардта — метод оптимизации, направленный на решение задач о наименьших квадратах. Является альтернативой методу Ньютона. Может рассматриваться как комбинация последнего с методом градиентного спуска или как метод доверительных интервалов. Алгоритм был сформулирован независимо Левенбергом (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})=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})\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}\,^TH\vec{p}.

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

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

Литература[править | править исходный текст]

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