麦夸特法

Levenberg-Marquardt(LM)算法是一种迭代技术,其定位表示为非线性函数的平方和的函数的最小值。它已经成为非线性最小二乘问题的标准技术,可以被认为是最快下降与高斯牛顿法的组合。主要就是用来求解非线性最小二乘问题。

在了解麦夸特法的过程中,发现还有一些与它相关的其他算法,为了说明我画了下图进行说明算法间的关系

这些算法都在求解非线性问题的优化中常用的算法。

牛顿法,一般用在解决非线性中的求零点和求极值,(求极值其实也是优化问题,求出最为合适的解),并且适用的范围是在变量较少的情况下。为了解决高维非线方程中的最小二乘问题,在牛顿法的基础进行了修改,有了高斯牛顿法,但是却有缺陷,另外梯度下降法在用在这里的最小二乘法也有自己的缺陷。为此,就有了在高斯牛顿法的基础上修改的麦夸特法。下面关于具体原理,我会一一说明。

算法原理

非线性问题的处理思路都是将非线性的转化成线性的,主要有两类算法,一类是搜索算法,一类是这里的迭代算法。(算法的分类是有些模糊的,这个大家不必在意)另外关于各类概念的说明,防止大家搞得太乱,我会详细说明的。

大家可以先看一下一些博客:

谈谈自己对线性最小二乘和非线性最小二乘之间关系的理解~

Jacobian矩阵和Hessian矩阵

最小二乘法:一般是在进行数据拟合,对结果进行评估的一种方式,一般是通过将测量值与实际值作差求平方再求和。

雅克比矩阵(Jacobian矩阵):类似于多元函数的一阶导组成的矩阵。

海森矩阵(Hessian矩阵) :类似于多元函数的二阶导组成的矩阵。

 

先看一下

1.牛顿法

主要用于解决的问题有低维非线性函数的求零点和求极值的问题。

1.求零点

主要是先将目标函数在某一可可微点处x0进行一阶泰勒展开,忽略高阶,令展开式=0,求解出x1,此时得到的x1并不是目标函数的零点,但是确实一个比x0更加接近零点的点,因此就不免想到多次迭代从而达到零点处。

2.求极值点

求目标函数的极值点,其实就是对目标函数的一阶导求零点。这里可以通过对目标函数的二阶泰勒展开式求值,来实现原理同上,不断迭代从而找到满足条件的点。

Jacobian矩阵和Hessian矩阵中有关于牛顿法更为详细的说明。

2.高斯牛顿法

高斯牛顿法正是用于解决非线性最小二乘问题,达到数据拟合、参数估计和函数估计的目的。

主要的在牛顿的法上的改变是将迭代公式,也就是求解下个点的公式的处理,由于在高维的情况下,迭代公式中的海森矩阵是极其复杂的,因此高斯牛顿法中舍弃黑森矩阵的二阶偏导数,将海森矩阵用雅克比矩阵进行表示。

具体的表达式可以看

Gauss-Newton算法学习

【math】梯度下降法(梯度下降法,牛顿法,高斯牛顿法,Levenberg-Marquardt算法)

高斯牛顿法

3.麦夸特法

麦夸特法又称为阻尼因子法,是在高斯牛顿法的基础上进行的,对迭代式的调整,主要就是添加了阻尼因子,从而对高斯牛顿法进行完善。

Levenberg-Marquardt方法的好处在于可以调节:

如果下降太快,使用较小的λ,使之更接近高斯牛顿法

如果下降太慢,使用较大的λ,使之更接近梯度下降法

这里有一篇英文的文档是对麦夸特法的具体阐述,有能力的可以看看

麦夸特法.pdf

以上是对原理的大概讲解

接下来就是代码工具:

代码工具:

麦夸特法:
  1. %% 函数功能:利用Levenberg_Marquardt算法求解无约束的非线性最小二乘问题
  2. function [x_curr, iter] = Levenberg_Marquardt(Diff, f, var, x0, lamda, beita, eps)
  3.     % 相关参数
  4.     max_iter    = 100;
  5.     flag        = 1;
  6.     x_curr      = x0;
  7.     for iter = 1 : max_iter
  8.         if flag
  9.             J   = double(subs(jacobian(Diff, var), var, x_curr));      % 雅可比矩阵
  10.             H   = transpose(J) * J;                                    % 赫森矩阵
  11.             if iter == 1
  12.                 f_curr = double(subs(f, var, x_curr));
  13.             end
  14.         end
  15.         % 计算新Hessen矩阵
  16.         H_new = H + (lamda * eye(2, 2));
  17.         % 计算步长d
  18.         diff = double(subs(Diff, var, x_curr));
  19.         d    = inv(H_new) * (J’ * diff);
  20.         % 更新参数
  21.         x_new = x_curr – d;
  22.         % 计算新函数值
  23.         f_new = double(subs(f, var, x_new));
  24.         if f_new < f_curr
  25.             % 收敛条件(左侧分支)
  26.             x_curr = x_new;
  27.             if (norm(d) < eps)
  28.                 disp(‘收敛条件1’)
  29.                 break;
  30.             end
  31.             f_curr = f_new;
  32.             flag = 1;
  33.             lamda = lamda / beita;
  34.         else
  35.             % 收敛条件(右侧分支)
  36.             if (norm(d) < eps)
  37.                 disp(‘收敛条件2’)
  38.                 break;
  39.             end
  40.             flag = 0;
  41.             lamda = lamda * beita;
  42.         end
  43.     end
  44. end

其他的代码以后再积累补充

 

接下来就是最关键的部分了

算法的应用

 

 

《麦夸特法》有2个想法

发表评论

电子邮件地址不会被公开。 必填项已用*标注