Diagonal Levenberg-Marquardt method

 Метод Левенберга-Марквардта, как и  Quasi-Newton  метод,является модификацией классического метода Гаусса-Ньютона для минимизации суммы квадратов функций. Метод Левенберга-Марквардта использует корректирующий множитель, чтобы найти направление для следующего приближения. Направление находится по формуле:

где D — диагональная матрица, главная диагональ которой совпадает с главной диагональю матрицы JtJ.

Поправочный множитель λ (коэффициент Марквардта) пересчитывается на каждой итерации метода, при этом он уменьшается, если целевая функция уменьшается (направление приближается к направлению Гаусса-Ньютона), и увеличивается при недостаточном уменьшении или невозможности убывание целевой функции.Направление приближается к 

Пересчет длины шага α^s методом линейного перебора производится не на каждой итерации, а только при невозможности уменьшения целевой функции. Изменяется (увеличивается) и фактор Марквардта. Если пять последующих итераций не приводят к уменьшению целевой функции, алгоритм останавливается. Другие условия останова алгоритма Левенберга-Марквардта совпадают с условиями останова квазиньютоновского алгоритма.

Использование метода Левенберга-Марквардта в функции наименьших квадратов scipy. Пример кода:

(.env) [boris@fedora LEASTSQ]$ cat leastSquare.py

import numpy as np

from scipy.optimize import least_squares

a = 2

b = -1

def myfun(x,a,b):

    print(x[0],x[1])

    return [a*x[0]-x[1]-np.exp(-x[0]), b*x[0]+2*x[1]-np.exp(-x[1])]

x_start = [-5,-5]

sol = least_squares(myfun,x_start,method='lm',ftol=1e-9,xtol=1e-9, \

                    max_nfev=int(1e6),args=(a,b))

print(sol)

(.env) [boris@fedora LEASTSQ]$ python leastSquare.py

-5.0 -5.0

-5.0 -5.0

-5.0 -5.0

-4.999999925494194 -5.0

-5.0 -4.999999925494194

-3.9732285575084685 -3.9732285575084685

-3.9732284983027495 -3.9732285575084685

-3.9732285575084685 -3.9732284983027495

-2.9183272109899803 -2.91832721098998

-2.918327167503516 -2.91832721098998

-2.9183272109899803 -2.9183271675035156

-1.8200033530748914 -1.8200033530748914

-1.820003325954728 -1.8200033530748914

-1.8200033530748914 -1.820003325954728

-0.7056674257415931 -0.7056674257415929

-0.705667415226329 -0.7056674257415929

-0.7056674257415931 -0.7056674152263288

0.19703892123361877 0.19703891364708526

0.1970389241697275 0.19703891364708526

0.19703892123361877 0.19703891658319386

0.5397436852475499 0.5397436856175911

0.5397436932903575 0.5397436856175911

0.5397436852475499 0.5397436936603988

0.567006315748519 0.56700631576721

0.5670063241975715 0.56700631576721

0.567006315748519 0.5670063242162624

0.5671432870159018 0.5671432870154018

0.5671432954669953 0.5671432870154018

0.5671432870159018 0.5671432954664953

0.567143290409784 0.567143290409784

0.5671432988608776 0.567143290409784

0.567143290409784 0.5671432988608776

0.5671432904097838 0.5671432904097838

0.5671432904097838 0.5671432904097838

0.5671372349553314 0.5671432904097838

0.5671493458642363 0.5671432904097838

0.5671432904097838 0.5671372349553314

0.5671432904097838 0.5671493458642363

 active_mask: array([0, 0])

        cost: 0.0

         fun: array([0., 0.])

        grad: array([0., 0.])

         jac: array([[ 2.56714329, -1.        ],

       [-1.        ,  2.56714329]])

     message: '`xtol` termination condition is satisfied.'

        nfev: 31

        njev: None

  optimality: 0.0

      status: 3

     success: True

           x: array([0.56714329, 0.56714329])