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

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

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

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

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

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

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

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

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

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

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

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

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

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

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