牛顿法

一、直观理解：用局部「抛物面」一次看清谷底在哪

牛顿法（Newton's Method）在优化中的思想是：在当前点用二阶泰勒展开把目标近似成一个开口朝上的抛物面（二次模型），直接跳到该抛物面的最低点，再重新近似、再跳。

一维时，对 $f'(x)=0$ 做牛顿迭代：

$$x_{k+1}=x_k-\frac{f'(x_k)}{f''(x_k)}$$

多维时用梯度与海森矩阵：

$$x_{k+1}=x_k-H_k^{-1}\nabla f(x_k),\quad H_k=\nabla^2 f(x_k)$$

与梯度下降「只知道坡度、小步试探」不同，牛顿法还知道「坡度变化有多快」（曲率），因此在良态点附近往往具有二次收敛：靠近根时，正确位数近似成倍增加。

代价是：每步需要海森及其线性方程组，非凸时 $H_k$ 可能不正定，方向甚至不是下降方向，需要阻尼、修正或改用拟牛顿。

二、适用场景与优缺点

类型	说明
适用场景	中小规模光滑无约束优化；梯度与海森可解析；需要高精度局部解；理解 fminunc 中牛顿/拟牛顿行为；求解非线性方程组。
核心优点	局部收敛极快；利用曲率信息，病态程度通常好于纯梯度法；精度高。
局限与缺点	海森计算与存储 $O(n^2)$、分解 $O(n^3)$；非凸时需修正；对初值敏感；有约束时要嵌入 SQP/内点等框架。

使用前确认：

1. $n$ 是否过大（过大优先拟牛顿 L-BFGS）；
2. 海森是否昂贵或易错；
3. 问题局部是否接近二次凸；
4. 是否只需局部最优。

三、核心原理：二次模型与牛顿方向

1. 二次近似

$$m_k(d)=f(x_k)+\nabla f(x_k)^\mathsf{T}d+\frac12 d^\mathsf{T}H_k d$$

若 $H_k\succ 0$，则 $m_k$ 的最小点满足：

$$H_k d_k=-\nabla f(x_k)$$

$d_k$ 称为牛顿方向。更新 $x_{k+1}=x_k+d_k$（纯牛顿）或 $x_{k+1}=x_k+\alpha_k d_k$（阻尼牛顿）。

2. 局部二次收敛

在极小点附近，若 $H(x^*)$ 正定且 Lipschitz，$x_0$ 充分靠近，则：

$$\|x_{k+1}-x^*\|\le C\|x_k-x^*\|^2$$

这是牛顿法最吸引人的理论性质。

3. 海森不正定时的修正

若 $H_k$ 有负特征值，二次模型可能无下界。常用：

• 加性修正 $H_k+\tau I$ 使正定；
• 改用负曲率方向逃离；
• 退回梯度方向。

4. 拟牛顿法（BFGS 等）

不直接算 $H$，而用梯度差近似逆海森 $B_k\approx H^{-1}$，每步 $O(n^2)$ 更新。MATLAB fminunc 的 quasi-newton 即此类，兼顾速度与实现难度。

5. 与梯度下降比较

项目	梯度下降	牛顿法
信息	一阶	二阶
每步成本	低	高
局部收敛	线性	二次（典型）
病态谷	易震荡	通常更好
规模	可很大	中小更佳

四、关键决策

1. 纯牛顿还是阻尼牛顿

远离最优时纯牛顿可能上升或发散，应配合线搜索 $\alpha_k\in(0,1]$。

2. 解析海森的正确性

海森写错比梯度写错更隐蔽。可用有限差分核对 $\nabla^2 f$ 与 $\nabla f$ 的一致性。

3. 线性方程组求解

解 $H d=-g$ 比显式求逆稳定。注意条件数与缩放。

4. 工具箱优先

竞赛中除非题目要求自写，否则 fminunc/fmincon 的成熟实现更可靠；自写牛顿用于小例子与原理验证。

5. 约束问题

牛顿思想出现在 SQP 的二次子问题、内点法的牛顿步中，但实现远比无约束复杂。

五、MATLAB 示例

例 1：手写牛顿法（二维凸二次 + 轻微非线性）

目标 $f(x,y)= (x-1)^2+10(y-2)^2+\frac14 x^4$。

f = @(x) (x(1)-1)^2 + 10*(x(2)-2)^2 + 0.25*x(1)^4;

% 梯度与海森
grad = @(x) [ ...
    2*(x(1)-1) + x(1)^3; ...
    20*(x(2)-2) ...
];
hess = @(x) [ ...
    2 + 3*x(1)^2, 0; ...
    0, 20 ...
];

x = [3; -1];
maxIter = 50;
for k = 1:maxIter
    g = grad(x);
    if norm(g) < 1e-10
        break;
    end
    H = hess(x);
    % 若不正定则修正
    [V, D] = eig((H+H')/2);
    dH = diag(D);
    if any(dH <= 1e-8)
        dH = max(dH, 1e-3);
        H = V * diag(dH) * V';
    end
    p = -H \ g;   % 牛顿方向
    % 回溯
    alpha = 1;
    while f(x + alpha*p) > f(x) + 1e-4*alpha*(g'*p) && alpha > 1e-12
        alpha = alpha * 0.5;
    end
    x = x + alpha * p;
    fprintf("k=%2d alpha=%.3f x=(%.6f,%.6f) f=%.3e ||g||=%.3e\n", ...
        k, alpha, x(1), x(2), f(x), norm(grad(x)));
end

例 2：fminunc 使用解析梯度（拟牛顿）

function [f, g] = objWithGrad(x)
    f = (x(1)-1)^2 + 10*(x(2)-2)^2 + 0.25*x(1)^4;
    if nargout > 1
        g = [2*(x(1)-1) + x(1)^3; 20*(x(2)-2)];
    end
end

x0 = [3; -1];
opts = optimoptions("fminunc", ...
    "Algorithm", "quasi-newton", ...
    "SpecifyObjectiveGradient", true, ...
    "Display", "iter");
[xOpt, fOpt, ef, out] = fminunc(@objWithGrad, x0, opts);
fprintf("exit=%d, x=(%.6f,%.6f), f=%.6e, iter=%d\n", ...
    ef, xOpt(1), xOpt(2), fOpt, out.iterations);

例 3：与梯度下降的迭代次数对比（二次函数）

% f = 0.5 x' A x - b' x， A 病态
A = [100, 0; 0, 1];
b = [1; 1];
% 牛顿一步到位（严格二次）
xN = A \ b;
% 梯度下降需许多步
x = [0; 0];
for k = 1:500
    g = A*x - b;
    if norm(g) < 1e-8, break; end
    alpha = (g'*g) / (g'*A*g);  % 精确线搜索
    x = x - alpha * g;
end
fprintf("牛顿解=[%.4f,%.4f]; GD 用 %d 步得 [%.4f,%.4f]\n", ...
    xN(1), xN(2), k, x(1), x(2));

六、如何解释结果

完整报告包括：

1. 是否使用解析海森/拟牛顿；
2. 初值与最终解、目标值、梯度范数；
3. 迭代次数；若后期 $\|g\|$ 呈二次下降，可说明进入牛顿快速区；
4. 海森在最优点的特征值（正定 ⇒ 严格局部极小的二阶充分条件）；
5. 多初值结果是否一致；
6. 与梯度法/工具箱对照是否吻合。

二阶充分条件回顾：$\nabla f(x^*)=0$ 且 $\nabla^2 f(x^*)\succ 0$ ⇒ 严格局部极小。

七、常见误区

1. 把求根牛顿与优化牛顿的符号记混

优化中是减 $H^{-1}g$，对应找 $\nabla f=0$。

2. 海森奇异仍强行求逆

应修正或改用伪逆/改算法。

3. 非凸问题宣称全局最优

牛顿法给局部解；多峰需全局策略或多启动。

4. 高维硬算稠密海森

$n$ 很大时用 L-BFGS、共轭梯度或结构稀疏牛顿。

5. 无线搜索的纯牛顿远离最优点

可能发散；务必阻尼或信赖域。

6. 数值海森当精确曲率

差分海森误差大时，牛顿步质量下降，不如拟牛顿稳定。

八、小结

牛顿法的核心思想可以概括为：

在当前点用二阶泰勒模型逼近目标，通过求解线性系统得到牛顿步，快速逼近满足 $\nabla f=0$ 的局部极小。

它是光滑无约束非线性规划中追求高精度与快速局部收敛的代表方法。实践中重视海森正定修正、线搜索与规模限制；工具箱拟牛顿往往是工程默认。有约束时，牛顿思想融入更一般的约束优化算法，并与 KKT 条件衔接。