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

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

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

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

где  — матрица Якоби вектор-функции ,  — матрица Гессе для её компоненты .

Тогда согласно методу Гаусса — Ньютона в предположении доминирующей роли слагаемого над (то есть если норма значительно меньше максимального собственного значения матрицы ) очередное направление определяется из системы:

Алгоритм

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

где  — некоторая неотрицательная константа, своя для каждого шага,  — единичная матрица.

Выбор можно осуществлять, делая его достаточным для монотонного спуска по функции невязки , то есть увеличивать параметр до тех пор, пока не будет достигнуто условие . Также параметр можно устанавливать исходя из отношения между фактическими изменениями функции достигнутыми в результате пробных шагов, и ожидаемыми величинами этих изменений при интерполяции. Подобную процедуру построил Флетчер.

Также можно показать, что удовлетворяет условию:

где  — параметр, связанный с .

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

Нетрудно заметить, что при алгоритм вырождается в метод Гаусса — Ньютона, а при достаточно большом направление незначительно отличается от направления наискорейшего спуска. Таким образом, при правильном подборе параметра добиваются монотонного убывания минимизируемой функции. Неравенство всегда можно обеспечить, выбрав достаточно большим. Однако при этом теряется информация о кривизне, заключённая в первом слагаемом, и проявляются все недостатки метода градиентного спуска: в местах пологого наклона антиградиент мал, а в местах с крутым наклоном — велик, в то время как в первом случае желательно делать большие шаги, а во втором — маленькие. Так, с одной стороны, если есть длинная и узкая впадина на поверхности, определяемой функцией невязки , то компоненты градиента вдоль основания впадины — малы, а в направлении к стенкам — велики, в то время как идти желательно по основанию оврага. Способ учёта информации о кривизне предложил Марквардт. Он заметил, что если заменить единичную матрицу на диагональ матрицы Гессе, то можно достичь увеличения шага вдоль пологих участков и уменьшения вдоль крутых спусков:

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

При рассмотрении алгоритма Левенберга — Марквардта как метода доверительных интервалов с помощью эвристик выбирается интервал , на котором строится приближение функции :

При этом шаг определяется исходя из задачи минимизации:

Литература

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