数学知识
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 影响 方向和 步长大小。这让我们拥有两种方法的优势。
问题：为什么通常牛顿法比梯度下降法能更快的收敛？
解答：牛顿法是二阶收敛，梯度下降是一阶收敛，所以牛顿法就更快。如果更通俗地说的话，比如你想找一条最短的路径走到一个盆地的最底部，梯度下降法每次只从你当前所处位置选一个坡度最大的方向走一步，牛顿法在选择方向时，不仅会考虑坡度是否够大，还会考虑你走了一步之后，坡度是否会变得更大。所以，可以说牛顿法比梯度下降法看得更远一点，能更快地走到最底部。
根据wiki上的解释，从几何上说，牛顿法就是用一个二次曲面去拟合你当前所处位置的局部曲面，而梯度下降法是用一个平面去拟合当前的局部曲面，通常情况下，二次曲面的拟合会比平面更好，所以牛顿法选择的下降路径会更符合真实的最优下降路径。
11
数学知识
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 影响 方向和 步长大小。这让我们拥有两种方法的优势。
问题：为什么通常牛顿法比梯度下降法能更快的收敛？
解答：牛顿法是二阶收敛，梯度下降是一阶收敛，所以牛顿法就更快。如果更通俗地说的话，比如你想找一条最短的路径走到一个盆地的最底部，梯度下降法每次只从你当前所处位置选一个坡度最大的方向走一步，牛顿法在选择方向时，不仅会考虑坡度是否够大，还会考虑你走了一步之后，坡度是否会变得更大。所以，可以说牛顿法比梯度下降法看得更远一点，能更快地走到最底部。
根据wiki上的解释，从几何上说，牛顿法就是用一个二次曲面去拟合你当前所处位置的局部曲面，而梯度下降法是用一个平面去拟合当前的局部曲面，通常情况下，二次曲面的拟合会比平面更好，所以牛顿法选择的下降路径会更符合真实的最优下降路径。
11