牛顿法与拟牛顿法例题详解

本文为《牛顿法与拟牛顿法》的配套例题集，通过详细的手工计算演示各种方法的具体实施过程，包含标准牛顿法、修正牛顿法、BFGS、DFP、L-BFGS等算法的实例。每个例题都提供完整的计算步骤、迭代表格和收敛性分析。

一、牛顿法基础例题

例题1：标准二次型的牛顿法

问题：使用牛顿法求解 \(\min f(x) = \frac{1}{2}x^T A x - b^T x + c\) 其中 \(A = \begin{pmatrix} 4 & 1 \\ 1 & 3 \end{pmatrix}\)，\(b = \begin{pmatrix} 2 \\ 4 \end{pmatrix}\)，\(c = 0\)，初值 \(x_0 = \begin{pmatrix} 0 \\ 0 \end{pmatrix}\)。

解析：

步骤1：确定理论最优解 \(\nabla f(x) = Ax - b = 0 \Rightarrow x^* = A^{-1}b = \frac{1}{11}\begin{pmatrix} 3 & -1 \\ -1 & 4 \end{pmatrix}\begin{pmatrix} 2 \\ 4 \end{pmatrix} = \begin{pmatrix} 2/11 \\ 14/11 \end{pmatrix}\)

步骤2：Hessian矩阵（常数） \(H(x) = \nabla^2 f(x) = A = \begin{pmatrix} 4 & 1 \\ 1 & 3 \end{pmatrix}\)

步骤3：牛顿法迭代

牛顿法迭代推导表

关键观察：

• 对于二次型，牛顿法一步精确收敛
• 牛顿方向直接指向最优解
• 不需要线搜索，\(\alpha = 1\) 总是最优步长

例题2：非二次函数的牛顿法

问题：求解 \(\min f(x_1, x_2) = e^{x_1 + x_2} + x_1^2 + x_2^2\) 初值 \(x_0 = \begin{pmatrix} 1 \\ 1 \end{pmatrix}\)。

解析：

步骤1：计算梯度和Hessian \(\nabla f(x) = \begin{pmatrix} e^{x_1 + x_2} + 2x_1 \\ e^{x_1 + x_2} + 2x_2 \end{pmatrix}\)

步骤2：详细迭代过程

非二次函数牛顿法迭代表

收敛分析：

• 函数值单调递减：\(9.39 \to 3.22 \to 2.78 \to \cdots\)
• 梯度范数快速减少：\(13.28 \to 5.26 \to 3.54 \to \cdots\)
• 显示二次收敛特性

例题3：修正牛顿法（处理非正定Hessian）

问题：求解 \(\min f(x_1, x_2) = x_1^4 - 2x_1^2 + x_2^2\) 初值 \(x_0 = \begin{pmatrix} 0.5 \\ 0.5 \end{pmatrix}\)。

解析：

步骤1：梯度和Hessian计算 \(\nabla f(x) = \begin{pmatrix} 4x_1^3 - 4x_1 \\ 2x_2 \end{pmatrix}\)

步骤2：识别问题 在 \(x_1 = 0\) 附近，\(H_{11} = -4 < 0\)，Hessian不正定。

步骤3：修正策略

修正牛顿法迭代表

修正公式： \(\tilde{H}_k = H_k + \mu_k I\) 其中 \(\mu_k = \max(0, \tau - \lambda_{\min}(H_k))\)，\(\tau = 0.1\)

二、BFGS算法例题详解

例题4：标准BFGS算法

问题：用BFGS求解Rosenbrock函数 \(\min f(x_1, x_2) = 100(x_2 - x_1^2)^2 + (1 - x_1)^2\) 初值 \(x_0 = \begin{pmatrix} -1.2 \\ 1 \end{pmatrix}\)。

解析：

步骤1：梯度计算 \(\nabla f(x) = \begin{pmatrix} -400x_1(x_2 - x_1^2) - 2(1 - x_1) \\ 200(x_2 - x_1^2) \end{pmatrix}\)

步骤2：BFGS迭代

BFGS算法迭代推导表

BFGS更新公式应用： \(H_1 = \left(I - \frac{s_0 y_0^T}{y_0^T s_0}\right) I \left(I - \frac{y_0 s_0^T}{y_0^T s_0}\right) + \frac{s_0 s_0^T}{y_0^T s_0}\)

其中：

• \[s_0 = x_1 - x_0 = (0.216, 0.088)^T\]
• \[y_0 = g_1 - g_0 = (112.4, 109.6)^T\]
• \[y_0^T s_0 = 112.4 \times 0.216 + 109.6 \times 0.088 = 33.92\]

例题5：BFGS vs 牛顿法对比

问题：对同一问题分别用牛顿法和BFGS求解 \(\min f(x) = \frac{1}{2}x^T \begin{pmatrix} 10 & 1 \\ 1 & 2 \end{pmatrix} x - \begin{pmatrix} 1 \\ 1 \end{pmatrix}^T x\)

解析：

方法性能对比表

关键观察：

• 牛顿法对二次函数一步收敛，但需要Hessian计算
• BFGS接近牛顿法性能，避免了Hessian计算
• BFGS在非二次函数上通常优于牛顿法

三、DFP算法例题

例题6：DFP与BFGS对比

问题：分别用DFP和BFGS求解 \(\min f(x_1, x_2) = x_1^2 + 4x_2^2 + x_1 x_2\)

解析：

DFP更新公式： \(H_{k+1} = H_k + \frac{s_k s_k^T}{s_k^T y_k} - \frac{H_k y_k y_k^T H_k}{y_k^T H_k y_k}\)

DFP vs BFGS 迭代对比

结论：

• BFGS通常比DFP更稳定
• BFGS的Hessian近似条件数增长更慢
• 实际应用中优先选择BFGS

四、L-BFGS算法例题

例题7：L-BFGS两循环递推详解

问题：用L-BFGS（m=3）求解高维问题 \(\min f(x) = \frac{1}{2}\sum_{i=1}^{100} (x_i - i)^2\)

解析：

步骤1：存储历史信息 保存最近3个 \(\{s_k, y_k\}\) 对：

• \[s_k = x_{k+1} - x_k\]
• \[y_k = g_{k+1} - g_k\]
• \[\rho_k = \frac{1}{y_k^T s_k}\]

步骤2：两循环递推算法

L-BFGS两循环递推过程

第一循环（向后）：

1
2
3
4
5
q = g_k = 当前梯度
for i = k-1, k-2, k-3 do
    α_i = ρ_i * s_i^T * q
    q = q - α_i * y_i
end for

中间步骤：

1
r = H_0 * q  （通常 H_0 = γI，γ = s_{k-1}^T y_{k-1} / y_{k-1}^T y_{k-1}）

第二循环（向前）：

1
2
3
4
5
for i = k-3, k-2, k-1 do
    β = ρ_i * y_i^T * r
    r = r + s_i * (α_i - β)
end for
return d_k = -r

例题8：L-BFGS存储需求分析

问题：比较不同方法的存储需求

存储需求对比表

关键优势：

• L-BFGS将存储从 \(O(n^2)\) 降至 \(O(mn)\)
• 对大规模问题（\(n > 10^4\)）具有决定性优势
• 通常 \(m = 5 \sim 20\) 就能获得良好性能

五、线搜索策略例题

例题9：Armijo条件验证

问题：验证Armijo条件在牛顿法中的应用 \(\min f(x) = x^4 - 2x^2 + 1\)，初值 \(x_0 = 1.5\)

解析：

Armijo条件： \(f(x_k + \alpha d_k) \leq f(x_k) + c_1 \alpha \nabla f(x_k)^T d_k\) 其中 \(c_1 = 10^{-4}\)，\(d_k = -\frac{\nabla f(x_k)}{\nabla^2 f(x_k)}\)

Armijo线搜索过程

选择策略：选择最大的满足Armijo条件的步长，通常 \(\alpha = 1.0\)

例题10：Wolfe条件的强化

问题：同时验证Armijo条件和曲率条件

强Wolfe条件：

1. Armijo条件：\(f(x_k + \alpha d_k) \leq f(x_k) + c_1 \alpha \nabla f(x_k)^T d_k\)

2. 曲率条件：$$

   \nabla f(x_k + \alpha d_k)^T d_k

   \leq c_2

   \nabla f(x_k)^T d_k

   $$

其中 \(c_1 = 10^{-4}\)，\(c_2 = 0.9\)

六、收敛性分析例题

例题11：收敛速度的数值验证

问题：验证不同方法的收敛阶

考虑函数：\(f(x) = \frac{1}{2}x^T A x - b^T x\)，其中 \(A\) 的条件数为 \(\kappa\)

收敛速度实验结果

理论vs实际：

• 牛顿法：二次收敛 \(\|e_{k+1}\| \leq C\|e_k\|^2\)
• BFGS：超线性收敛 \(\|e_{k+1}\| \leq C\|e_k\|^{1+\sigma}\)，\(\sigma > 0\)
• L-BFGS：接近超线性，受存储限制影响

例题12：病态问题的处理

问题：求解高条件数问题 \(A = \begin{pmatrix} 1000 & 1 \\ 1 & 1 \end{pmatrix}\)，\(\kappa(A) = 1999\)

策略对比：

病态问题求解策略

七、实际应用例题

例题13：机器学习中的逻辑回归

问题：用拟牛顿法求解逻辑回归 \(\min_w \sum_{i=1}^m \log(1 + e^{-y_i w^T x_i}) + \frac{\lambda}{2}\|w\|^2\)

解析：

梯度计算： \(\nabla f(w) = -\sum_{i=1}^m \frac{y_i x_i}{1 + e^{y_i w^T x_i}} + \lambda w\)

Hessian计算（牛顿法需要）： \(H(w) = \sum_{i=1}^m \frac{e^{y_i w^T x_i}}{(1 + e^{y_i w^T x_i})^2} x_i x_i^T + \lambda I\)

L-BFGS应用：

• 避免计算和存储 \(n \times n\) 的Hessian矩阵
• 特别适合高维特征空间（\(n > 10^4\)）
• 通常3-10步收敛

例题14：神经网络训练中的应用

问题：比较不同优化算法在神经网络训练中的表现

神经网络优化算法对比

八、数值实现技巧

8.1 数值稳定性

Hessian修正：

1
2
3
4
5
6
7
8
9
10
def modify_hessian(H, tau=1e-3):
    """修正Hessian矩阵确保正定性"""
    eigenvals = np.linalg.eigvals(H)
    min_eigval = np.min(eigenvals)
    
    if min_eigval < tau:
        mu = tau - min_eigval
        H_modified = H + mu * np.eye(H.shape[0])
        return H_modified
    return H

BFGS更新的跳过条件：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def bfgs_update(H, s, y, skip_threshold=1e-8):
    """BFGS更新，包含跳过条件"""
    sy = np.dot(s, y)
    
    if sy < skip_threshold:
        print("跳过BFGS更新：曲率条件不满足")
        return H
    
    # 标准BFGS更新
    rho = 1.0 / sy
    I = np.eye(len(s))
    V = I - rho * np.outer(s, y)
    H_new = V.T @ H @ V + rho * np.outer(s, s)
    
    return H_new

8.2 收敛判断

多重收敛准则：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def check_convergence(x_k, x_prev, g_k, f_k, f_prev, 
                     tol_x=1e-6, tol_g=1e-6, tol_f=1e-8):
    """检查多种收敛条件"""
    
    # 解的相对变化
    rel_x_change = np.linalg.norm(x_k - x_prev) / (1 + np.linalg.norm(x_k))
    
    # 梯度范数
    grad_norm = np.linalg.norm(g_k)
    
    # 函数值相对变化
    rel_f_change = abs(f_k - f_prev) / (1 + abs(f_k))
    
    converged = (rel_x_change < tol_x and 
                grad_norm < tol_g and 
                rel_f_change < tol_f)
    
    return converged

九、综合对比与总结

9.1 算法选择指南

优化算法选择决策树

9.2 性能总结

理论收敛率：

• 牛顿法：\(\|x_{k+1} - x^*\| \leq C\|x_k - x^*\|^2\)
• BFGS：\(\|x_{k+1} - x^*\| \leq C\|x_k - x^*\|^{1+\sigma}\)
• L-BFGS：接近BFGS，略有下降

实际性能：

• 牛顿法：最快收敛，但计算成本高
• BFGS：平衡收敛速度和计算成本
• L-BFGS：大规模问题的首选

9.3 实践建议

1. 初学者：从BFGS开始，理解拟牛顿思想
2. 研究者：牛顿法用于理论分析
3. 工程师：L-BFGS用于实际应用
4. 特殊情况：根据问题特征选择修正策略

十、进阶主题

10.1 信赖域方法

当线搜索失效时，信赖域方法提供了替代方案： \(\min_{d} g_k^T d + \frac{1}{2}d^T H_k d \quad \text{s.t.} \quad \|d\| \leq \Delta_k\)

10.2 非凸优化中的应用

在非凸问题中，拟牛顿法需要特殊处理：

• 负曲率方向的检测
• 鞍点的逃脱策略
• 全局收敛性保证

10.3 并行化实现

大规模问题的并行化策略：

• 梯度计算的并行化
• 矩阵向量乘的分布式实现
• L-BFGS的内存共享

相关文章:

• 《牛顿法与拟牛顿法详解》
• 《最速下降法与共轭梯度法例题详解》
• 《最优化理论基础》
• 《KKT条件详解》

• Previous
  最优化理论——牛顿法和拟牛顿法
• Next
  最优化理论——拉格朗日乘子法与增广拉格朗日乘子法