牛顿法优化的二次终止性及阻尼牛顿法的全局收敛

牛顿法是求解优化问题的经典算法。理解它的核心优势（二次终止性）和改进版本（阻尼牛顿法），是掌握高效优化方法的关键。

第一部分：理解牛顿法的“二次终止性”

二次终止性指算法能在有限步内，精确求解二次函数的极值点。牛顿法天然具备这一特性。

1. 明确前提条件：假设我们要求解一个二次函数（即目标函数 $f(x)$ 的形式是 $f(x) = \frac{1}{2}x^T H x + b^T x + c$）的极小值点，其中 $H$ 是一个正定的对称矩阵（可以理解为曲率信息），$b$ 和 $c$ 是常数向量和标量。

2. 初始化一个点：选择 任意一个初始点 $x_k$ 作为起点。

3. 计算梯度与海森矩阵：计算 目标函数在当前点 $x_k$ 的梯度（即各方向的一阶导数，可以理解为变化最快的方向）$\nabla f(x_k) = H x_k + b$。同时，获得 该函数的海森矩阵 $H$。对于二次函数，海森矩阵 $H$ 是一个常量矩阵。

4. 执行牛顿迭代：应用 牛顿法的迭代公式：
   $$x_{k+1} = x_k - H^{-1} \nabla f(x_k)$$
   这个公式的直观解释是：沿着 当前点的梯度方向的反方向，调整 一个步长 $H^{-1} \nabla f(x_k)$ 来更新 $x$。其中 $H^{-1}$（海森矩阵的逆）起到了“修正”步长大小的作用，使得更新更加精准。

5. 验证一步收敛：将 步骤3中的梯度表达式代入步骤4的公式：
   $$x_{k+1} = x_k - H^{-1} (H x_k + b) = x_k - x_k - H^{-1} b = - H^{-1} b$$
   你会发现，结果 $x_{k+1}$ 不再依赖 于起点 $x_k$。这正是二次函数 $f(x)$ 的全局极小点 $x^* = - H^{-1} b$。因此，得出结论：对于正定二次函数，牛顿法一步迭代 即可求得精确解。这就是其“二次终止性”的体现。

第二部分：从牛顿法到阻尼牛顿法

现实中的函数往往不是简单的二次函数。标准牛顿法在非二次、非凸或远离极小点时可能失效，例如步长过大导致发散。阻尼牛顿法（或称带线搜索的牛顿法）通过引入一个步长因子 $\alpha$ 来解决这个问题，确保算法稳定地收敛。

1. 识别问题：意识到 标准牛顿法的更新步长 $d_k = - H(x_k)^{-1} \nabla f(x_k)$ 可能太大，导致函数值反而上升，算法无法收敛。

2. 引入阻尼机制：修改 迭代公式为：
   $$x_{k+1} = x_k + \alpha_k d_k$$
   其中 $d_k = - H(x_k)^{-1} \nabla f(x_k)$ 称为牛顿方向，$\alpha_k > 0$ 称为阻尼因子或步长。核心任务变为：如何选择一个合适的 $\alpha_k$。

3. 确保下降方向：检查 海森矩阵 $H(x_k)$ 是否正定。如果 $H(x_k)$ 正定，则牛顿方向 $d_k$ 一定是函数值下降的方向（$\nabla f(x_k)^T d_k < 0$）。这是算法能稳定下降的基础。如果 $H(x_k)$ 不正定，可能需要修改牛顿方向，但这超出了本基础指南的范围。

4. 执行线搜索：寻找 一个步长 $\alpha_k$，使得新的点 $x_{k+1}$ 处函数值有足够程度的下降。最常用的是Armijo准则（一种 backtracking 线搜索）：
   a. 设置 初始步长为 $\alpha = 1$（即标准牛顿步长）。
   b. 检查 条件：$f(x_k + \alpha d_k) \leq f(x_k) + c_1 \alpha \nabla f(x_k)^T d_k$。其中 $c_1$ 是一个小常数，例如 $0.0001$。
   c. 如果条件不满足，将 $\alpha$ 乘以 一个衰减因子 $\rho$（例如 $\rho = 0.5$），即 $\alpha := \rho \alpha$。
   d. 重复 步骤b和c，直到条件满足。最终得到的 $\alpha$ 即为 $\alpha_k$。

5. 实现全局收敛：组合 以上步骤，形成阻尼牛顿法的完整迭代：
   a. 初始化 点 $x_0$。
   b. 循环执行：
   i. 计算 梯度 $\nabla f(x_k)$ 和海森矩阵 $H(x_k)$。
   ii. 求解 线性方程组 $H(x_k) d_k = -\nabla f(x_k)$ 得到牛顿方向 $d_k$。
   iii. 进行 线搜索（如Armijo准则）确定步长 $\alpha_k$。
   iv. 更新 点 $x_{k+1} = x_k + \alpha_k d_k$。
   v. 检查 收敛条件（如梯度模 $\| \nabla f(x_k) \|$ 小于某个阈值 $\epsilon$），若满足则终止。
   c. 输出 最终收敛点。

6. 理解全局收敛含义：通过确保每一步迭代都使函数值下降一个可量化的程度（由Armijo准则保证），阻尼牛顿法避免了 在初始点远离极小值时发散的问题，从而能够从更广泛的起始点收敛到局部极小点。这就是“全局收敛性”的核心思想。