数学知识--Methods for Non-Linear Least Squares Problems（第三章）

版权声明：本文为博主原创文章，未经博主允许不得转载。 https://cloud.tencent.com/developer/article/1436942

Methods for Non-Linear Least Squares Problems 非线性最小二乘问题的方法

2nd Edition, April 2004

K. Madsen, H.B. Nielsen, O. Tingleff

3 Non-linear least squares problems 非线性最小二乘问题

接下来我们主要关注非线性最小二乘问题的讨论。给定一个向量函数 f: Rn --> Rm 其中 m>=n . 我们希望最小化 ||f(x)||

最小二乘问题可以通过普通优化算法来求解，但是这里我们介绍一类特别算法，其更加的高效。多数情况下，它们收敛的速度好于线性收敛，有时甚至达到二次收敛，但是它们不需要计算二阶导数。在算法的推导中我们需要 F 的导数计算公式，假定 f 的泰勒展开如下：

3.1. The Gauss–Newton Method

这个方法是下面我们将要介绍的方法的基础。它的实现依赖于向量函数的一阶导数。在特殊情况下，它能够给出二阶收敛，正如牛顿方法在广义优化问题中的表现。泰勒展开如下

将上式带入（3.1）得到

L’(0)=JTf=F’(x)

如果 J has full rank，那么 L(h) has a unique minimizer： L’(h_gn)=0

Newton’s method 和 Gauss-Newton method 的区别

两者的 search directions 分别如下所示：

区别在于：

所以当 f(x*)=0 则 对 离x* 很近的 x 来说 L’’(h) 约等于F’’(x)

we get quadratic convergence also with the Gauss-Newton method

3.2. The Levenberg–Marquardt Method

damping parameter µ 有几个效果：

a）对所有 µ>0 参数矩阵是正定的，所以这保证了 h_lm 是一个下降方向

b) 对于较大的 µ 值 我们得到

a short step in the steepest descent direction。 This is good if the current iterate is far from the solution

c) 当 µ 值 很小时， h_lm == h_gn, 在迭代的后期，这是一个很好的步长，当 x 离 x* 很近的时候

If F(x* )=0 (or very small), then we can get (almost) quadratic final convergence

所以 damping parameter 影响 方向和 步长大小。这让我们拥有两种方法的优势。

https://blog.csdn.net/pi9nc/article/details/11922835

问题：为什么通常牛顿法比梯度下降法能更快的收敛？

解答：牛顿法是二阶收敛，梯度下降是一阶收敛，所以牛顿法就更快。如果更通俗地说的话，比如你想找一条最短的路径走到一个盆地的最底部，梯度下降法每次只从你当前所处位置选一个坡度最大的方向走一步，牛顿法在选择方向时，不仅会考虑坡度是否够大，还会考虑你走了一步之后，坡度是否会变得更大。所以，可以说牛顿法比梯度下降法看得更远一点，能更快地走到最底部。

根据wiki上的解释，从几何上说，牛顿法就是用一个二次曲面去拟合你当前所处位置的局部曲面，而梯度下降法是用一个平面去拟合当前的局部曲面，通常情况下，二次曲面的拟合会比平面更好，所以牛顿法选择的下降路径会更符合真实的最优下降路径。

11