牛顿法是什么？用二次近似一步跳到最低点附近的优化方法

牛顿法（Newton's Method），也叫牛顿-拉弗森方法，是一种经典的迭代求解方法。它最初用于求方程的根，后来被广泛地用于寻找函数的最小值或最大值，是数值优化中最重要的方法之一。它的特点是：在接近最优解时，收敛的速度非常快。

用来求方程的根

牛顿法最早是用来求解方程的。艾萨克·牛顿在 17 世纪 60 年代就提出了这一方法的思想，约瑟夫·拉弗森在 1690 年给出了更简洁通用的形式。要求一个方程等于零的解，可以从一个初始的猜测出发，在这一点上画出函数曲线的切线，切线与横轴的交点就是一个更好的近似解；然后在新的点上再画切线、找交点，如此反复。每一步都用直线来近似曲线，通常只需要很少的几步就能得到非常精确的结果。比如计算 2 的平方根，就是求“x 的平方减 2 等于 0”的解，用牛顿法从 1 开始，几步之内就能得到精确到小数点后很多位的结果。

用来求函数的最小值

求一个函数的最小值，相当于求它的导数等于零的点，因此可以对导数使用牛顿法。从另一个角度理解：在当前点附近，用一个二次函数来近似原来的函数，也就是做二阶泰勒展开，这个二次函数考虑了函数在这一点的值、斜率和弯曲程度；然后直接跳到这个二次函数的最低点，作为下一个迭代点。对于多变量的函数，弯曲程度由二阶偏导数组成的海森矩阵来描述，牛顿法的更新方向等于海森矩阵的逆矩阵乘以梯度，再取负号。

它为什么快

梯度下降只利用一阶导数，也就是梯度，每一步都沿着最陡的方向走一小步，步子的大小需要人为地设定。当函数的形状像一个狭长的山谷时，梯度下降会在山谷的两壁之间来回震荡，前进得很慢。牛顿法还利用了二阶导数，知道函数在各个方向上弯曲得有多厉害：在弯曲剧烈的方向上走小步，在平缓的方向上走大步，因此能够直接朝着最低点前进。对于一个本身就是二次函数的目标，牛顿法只需要一步就能到达最低点。在最优解附近，牛顿法具有“二次收敛”的速度：每迭代一次，结果的有效数字位数大约翻一倍，远远快于梯度下降。

它的缺点

计算代价高：需要计算海森矩阵，如果有 n 个变量，海森矩阵就有 n 乘 n 个元素；还需要对它求逆或者求解一个线性方程组，计算量大约与 n 的三次方成正比。当变量有成千上万甚至更多时，这是无法承受的。可能不往下走：如果海森矩阵不是正定的，比如在鞍点附近，牛顿法计算出的方向可能根本不是下降的方向，甚至会走向鞍点或最大值。对初始点敏感：如果初始点离最优解太远，二次近似可能很不准确，牛顿法可能跳得太远，导致不收敛。

改进和应用

为了克服这些缺点，实践中常常对牛顿法进行改进：加入线搜索，沿着牛顿方向寻找一个合适的步长，而不是直接走完一整步；给海森矩阵加上一个正数乘以单位矩阵，保证它是正定的，这叫阻尼牛顿法，列文伯格-马夸尔特方法就是这一思想在非线性最小二乘问题中的应用；使用信赖域方法，只在二次近似可信的范围内进行更新。拟牛顿法，比如 BFGS 和 L-BFGS，则通过梯度的变化逐步地近似海森矩阵，避免了直接计算二阶导数，在保持较快收敛速度的同时大大降低了计算成本。在机器学习中，逻辑回归常用的“迭代重加权最小二乘法”实际上就是牛顿法；广义线性模型的拟合、一些统计模型的参数估计也常使用牛顿法。在深度学习中，由于参数量极大，通常不直接使用牛顿法，而是使用梯度下降类的一阶方法，但研究者也在探索各种近似二阶信息的优化方法。