Метод Левенберга—Марквардта

квадратах. Является альтернативой методу Гаусса — Ньютона. Может рассматриваться как комбинация последнего

с методом градиентного спуска или как метод доверительных интервалов. Алгоритм был сформулирован независимо Левенбергом (1944) и Марквардтом (1963).

Kenneth Levenberg (1944). "A Method for the Solution of Certain Non-Linear Problems in Least Squares". The Quarterly of Applied Mathematics 2: 164–168.
Donald Marquardt (1963). "An Algorithm for Least-Squares Estimation of Nonlinear Parameters". SIAM Journal on Applied Mathematics 11(2): 431–441. doi:10.1137/0111030.
Philip E. Gill and Walter Murray (1978). "Algorithms for the solution of the nonlinear least-squares problem". SIAM Journal on Numerical Analysis 15 (5): 977–992. doi:10.1137/0715063.

07.11.2012

Метод Левенберга—Марквардта

The algorithm was first published by Kenneth Levenberg, while working at the Frankford Army Arsenal. It was rediscovered by Donald Marquardt who worked as a statistician at DuPont and independently by Girard, Wynn and Morrison.

Он превосходит по производительности метод наискорейшего спуска и другие методы

сопряженных градиентов в различных задачах. Изначально считалось, что LMA – это комбинация простейшего градиентного метода и метода Гаусса-Ньютона, однако впоследствии выяснилось, что данный алгоритм можно также рассматривать как метод доверительных интервалов.

Метод Левенберга—Марквардта

07.11.2012

.
LMA решает

задачу нелинейной минимизации методом наименьших квадратов. Это означает, что функция, которую необходимо минимизировать, выглядит следующим образом:

07.11.2012

Метод Левенберга—Марквардта

где - вектор, а - функция отображения из в .

Для простоты функция представляется вектором невязки вида:

производные представить с помощью матрицы Якоби

Рассмотрим линейный случай, когда

каждая функция линейна. Здесь якобиан равен константе, можно представить как гиперплоскость в пространстве, а

и . Решая задачу минимума , получим

то есть - решение системы нормальных уравнений

Возвращаясь к общему (нелинейному) случаю, получим:

Якоби ,
легко получить гессиан

, если функции можно
аппроксимировать линейными приближениями
(т.е. малы) или если малы сами по себе. Тогда гессиан, как и в линейном случае, будет равен:


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

07.11.2012

Метод Левенберга—Марквардта

градиентный метод – это наиболее интуитивно
понятный способ нахождения минимума

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

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

07.11.2012

Метод Левенберга—Марквардта

Однако в формуле выполняются прямо противоположные действия.

не одинаковой по всем направлениям. К примеру, если
есть длинная

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

Метод Левенберга—Марквардта

07.11.2012

) и решая задачу минимума, приравняв левую часть
уравнения

к нулю,

получим правило вычисления параметра на очередном шаге по
методу Ньютона:

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

07.11.2012

Метод Левенберга—Марквардта

друг друга с точки зрения
предоставляемых преимуществ. Основываясь на этом

наблюдении,
Левенберг предложил алгоритм, в котором правило вычисления
параметра

есть комбинация правил:


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

Метод Левенберга—Марквардта

07.11.2012

это
значит, что предположение о квадратичности
работает, и мы уменьшаем

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

Метод Левенберга—Марквардта

07.11.2012

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

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

Метод Левенберга—Марквардта

07.11.2012

Гессе никак не используется.
Однако можно извлечь некоторую выгоду из второй

производной
даже в этом случае, масштабируя каждый компонент градиента
согласно кривизне. Это должно привести к увеличению шага вдоль
направлений, где градиент мал, так что классическая проблема
впадины больше не возникнет. Этот ключевой момент был
замечен Марквардтом. Он заменил единичную матрицу в формуле
на диагональ гессиана, получив таким образом следующее
правило:


(Тихоновская регуляризация)

Метод Левенберга—Марквардта

07.11.2012

при малой кривизне (т.е. для почти плоской поверхности) и к

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

Метод Левенберга—Марквардта

07.11.2012

as given in the previous section where the parameter,

, was manipulated directly to find the minimum. Subsequently, a trust-region approach to the algorithm has gained ground.
Trust-region algorithms work in a fundamentally different manner than those presented in the previous section, which are called line-search methods. In a line search method, we decide on a direction in which to descend the gradient and are then concerned about the step size, i.e. if is the direction of descent, and the stepsize, then our step is given by and the stepsize is obtained by solving the sub-problem

Метод Левенберга—Марквардта

07.11.2012

a model m(k) that approximates the function f in a

finite region near x(k). This region, Δ, where the model is a good approximation of f , is called the trust-region. Trust-region algorithms maintain Δ and update it at each iteration using heuristics.
The model m(k) is most often a quadratic obtained by a Taylor series expansion of f around x(k), i.e.


where H is the Hessian (or an approximation of the Hessian) matrix. The sub-problem to be solved to find the step to take during the iteration is

Метод Левенберга—Марквардта

07.11.2012

. A trust-region algorithm can thus be conceived of as a sequence of iterations, in each of which we model the function f by a quadratic and then jump to the minimum of that quadratic.
The solution of problem is given by a theorem which is as follows

Метод Левенберга—Марквардта

07.11.2012

basically states that if then
but not otherwise. Hence, we reach the same parameter update equation for the LM algorithm using a trust-region framework as we obtained using the line-search method. The heuristic to update the size of the trust-region usually depends on the ratio of the expected change in f to the predicted change, i.e.



If there is a good agreement between predicted and actual values , then Δ is increased; if the agreement is poor ( is small), then is decreased. If is smaller than a threshold value ( ), the step is rejected and the value of is retained but Δ is decreased as before. Thus, the algorithm is similar to the previous one but the value that is changed with each iteration is Δ and not .

Метод Левенберга—Марквардта

07.11.2012

in C, Chapter 15.5: Nonlinear models
C. T. Kelley, Iterative Methods for

Optimization, SIAM Frontiers in Applied Mathematics, no 18, 1999, ISBN 0-89871-433-8. Online copy
History of the algorithm in SIAM news
A tutorial by Ananth Ranganathan
Methods for Non-Linear Least Squares Problems by K. Madsen, H.B. Nielsen, O. Tingleff is a tutorial discussing non-linear least-squares in general and the Levenberg-Marquardt method in particular
T. Strutz: Data Fitting and Uncertainty (A practical introduction to weighted least squares and beyond). Vieweg+Teubner, ISBN 978-3-8348-1022-9.

Метод Левенберга—Марквардта

07.11.2012

the public domain. See also:
lmfit, a translation of lmdif into C/C++ with an

easy-to-use wrapper for curve fitting, public domain.
The GNU Scientific Library library has a C interface to MINPACK.
C/C++ Minpack includes the Levenberg–Marquardt algorithm.
Several high-level languages and mathematical packages have wrappers for the MINPACK routines, among them:
Python library scipy, module scipy.optimize.leastsq,
IDL, add-on MPFIT.
R (programming language) has the minpack.lm package.
levmar is an implementation in C/C++ with support for constraints, distributed under the GNU General Public License.
levmar includes a MEX file interface for MATLAB
Perl (PDL), python and Haskell interfaces to levmar are available: see PDL::Fit::Levmar, PyLevmar and HackageDB levmar.
sparseLM is a C implementation aimed at minimizing functions with large, arbitrarily sparse Jacobians. Includes a MATLAB MEX interface.
InMin library contains a C++ implementation of the algorithm based on the eigen C++ linear algebra library. It has a pure C-language API as well as a Python binding
ALGLIB has implementations of improved LMA in C# / C++ / Delphi / Visual Basic. Improved algorithm takes less time to converge and can use either Jacobian or exact Hessian.

Метод Левенберга—Марквардта

07.11.2012

+ b sin(aX) 
using the Levenberg–Marquardt algorithm
implemented in GNU Octave as the leasqr  function. The

3 graphs Fig 1,2,3 show progressively better
fitting for the parameters a=100, b=102 used in the
initial curve. Only when the parameters in Fig 3 are
chosen closest to the original, are the curves fitting
exactly. This equation is an example of very sensitive
initial conditions for the Levenberg–Marquardt
algorithm. One reason for this sensitivity is the
existence of multiple minima — the function
cos(βx) has minima at parameter value b* and b*+2pi.

Example

07.11.2012