Алгоритм Левенберга — Марквардта | это... Что такое Алгоритм Левенберга — Марквардта? (original) (raw)

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

Содержание

• 1 Постановка задачи
• 2 Алгоритм
• 3 Комбинация градиентного спуска и метода Гаусса — Ньютона
• 4 Метод доверительных интервалов
• 5 Литература

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

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

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

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

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

Алгоритм

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

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

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

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

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

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

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

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

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

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

Литература

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