1.3.3.5 Метод нелинейной оптимизации Левенберга-Марквардта

Алгоритм Левенберга-Марквардта (Levenberg-Marquardt Algorithm, LMA) является наиболее распространенным алгоритмом оптимизации. Он превосходит по производительности метод наискорейшего спуска и другие методы сопряженных градиентов в различных задачах. Изначально считалось, что LMA - это комбинация простейшего градиентного метода и метода Гаусса-Ньютона, однако впоследствии выяснилось, что данный алгоритм можно также рассматривать как метод доверительных интервалов.

LMA как комбинация простейшего градиентного метода и метода Гаусса-Ньютона

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

. (12)

Однако при таком подходе имеют место различные проблемы сходимости. Логично предположить, что желательно было бы осуществлять большие шаги по направлению градиента там, где градиент мал (т.е. наклон пологий), и, наоборот, маленькие шаги там, где градиент большой, чтобы не пропустить минимум. Вместе с тем, в формуле (12) выполняются прямо противоположные действия. Другая проблема заключается в том, что кривизна поверхности невязки может быть не одинаковой по всем направлениям. К примеру, если есть длинная и узкая впадина на поверхности невязки, компонент градиента в направлении, указывающем вдоль основания впадины, очень мал, а компонент градиента вдоль стенок впадины, наоборот, велик. Это приводит к движению по направлению к стенкам впадины, тогда как необходимо перемещаться на большие расстояния вдоль основания впадины и на малые - вдоль ее стенок.

Ситуацию можно улучшить, если учитывать информацию о кривизне и градиенте, то есть вторые производные. Один из способов сделать это - использовать метод Ньютона для решения уравнения f(x)=0. Раскладывая градиент f в ряд Тейлора вокруг текущего состояния , получим:

. (13)

Пренебрегая членами более высокого порядка (считая f квадратичной вокруг x0 ) и решая задачу минимума, приравняв левую часть уравнения (13) к нулю, получим правило вычисления параметра на очередном шаге по методу Ньютона:

(14)

Главное достоинство такого подхода - быстрая сходимость. Однако скорость сходимости зависит от начального положения (если быть более точным, от линейности вокруг начального положения).

Легко заметить, что простейший градиентный метод и метод Гаусса-Ньютона дополняют друг друга с точки зрения предоставляемых преимуществ. Основываясь на этом наблюдении, Левенберг предложил алгоритм, в котором правило вычисления параметра есть комбинация правил (12) и (14):

, (15)

где H- матрица Гессе, вычисленная в точке xi.

Данное правило используется следующим образом: если на очередной итерации невязка сокращается, это значит, что предположение о квадратичности f(x) работает, и мы уменьшаем л (обычно в 10 раз), чтобы понизить влияние градиентного спуска. С другой стороны, если невязка увеличивается, необходимо следовать направлению градиента, и мы увеличиваем л (во столько же раз).

Таким образом, алгоритм Левенберга представляется в виде следующей последовательности действий:

1 Вычислить параметр на очередной итерации по правилу (15).

2 Оценить невязку в новом векторе параметров.

3 Если в результате вычисления параметра невязка увеличилась, вернуть-ся на шаг назад (т.е. восстановить прежние значения весов) и увеличить в 10 раз. Затем повторить выполнение, начиная с шага 1. л

4 Если в результате вычисления параметра невязка уменьшилась, принять текущий шаг (т.е. оставить новые значения весов) и уменьшить л в 10 раз.

Стоит отметить, что хотя LMA является не оптимальным, а лишь эвристическим методом, он очень хорошо работает на практике. Единственный его недостаток заключается в необходимости обращения матрицы на каждом шаге. Даже не смотря на то, что нахождение обратной матрицы обычно выполняется с использованием быстрых методов псевдообращения (таких как разложение по сингулярным числам матрицы), время одной итерации становится неприемлемым для нескольких тысяч параметров. Для моделей же средних размеров (с несколькими сотнями параметров) LMA работает даже быстрее, чем простейший градиентный метод[41, 42].