本文为《牛顿法与拟牛顿法》的配套例题集，通过详细的手工计算演示各种方法的具体实施过程，包含标准牛顿法、修正牛顿法、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：牛顿法迭代
牛顿法迭代推导表
k
\(x_k\)
\(g_k = \nabla f(x_k)\)
\(H_k = \nabla^2 f(x_k)\)
牛顿方向 \(d_k = -H_k^{-1}g_k\)
更新 \(x_{k+1} = x_k + d_k\)
0
\(\begin{pmatrix} 0 \\ 0 \end{pmatrix}\)
\(\begin{pmatrix} -2 \\ -4 \end{pmatrix}\)
\(\begin{pmatrix} 4 & 1 \\ 1 & 3 \end{pmatrix}\)
\(\begin{pmatrix} 2/11 \\ 14/11 \end{pmatrix}\)
\(\begin{pmatrix} 2/11 \\ 14/11 \end{pmatrix}\)
1
\(\begin{pmatrix} 2/11 \\ 14/11 \end{pmatrix}\)
\(\begin{pmatrix} 0 \\ 0 \end{pmatrix}\)
—
—
收敛
关键观察：
对于二次型，牛顿法一步精确收敛
牛顿方向直接指向最优解
不需要线搜索，\(\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}\)
\[H(x) = \begin{pmatrix} e^{x_1 + x_2} + 2 & e^{x_1 + x_2} \\ e^{x_1 + x_2} & e^{x_1 + x_2} + 2 \end{pmatrix}\]
步骤2：详细迭代过程
非二次函数牛顿法迭代表
k
\(x_k\)
\(f(x_k)\)
\(\nabla f(x_k)\)
\(|\nabla f(x_k)|\)
Hessian \(H_k\)
牛顿方向 \(d_k\)
\(x_{k+1}\)
0
\((1, 1)^T\)
\(e^2 + 2 \approx 9.39\)
\((e^2 + 2, e^2 + 2)^T \approx (9.39, 9.39)^T\)
\(13.28\)
\(\begin{pmatrix} e^2+2 & e^2 \\ e^2 & e^2+2 \end{pmatrix}\)
\((-0.5, -0.5)^T\)
\((0.5, 0.5)^T\)
1
\((0.5, 0.5)^T\)
\(e + 0.5 \approx 3.22\)
\((e + 1, e + 1)^T \approx (3.72, 3.72)^T\)
\(5.26\)
\(\begin{pmatrix} e+2 & e \\ e & e+2 \end{pmatrix}\)
\((-0.186, -0.186)^T\)
\((0.314, 0.314)^T\)
2
\((0.314, 0.314)^T\)
\(2.78\)
\((2.50, 2.50)^T\)
\(3.54\)
—
\((-0.119, -0.119)^T\)
\((0.195, 0.195)^T\)
收敛分析：
函数值单调递减：\(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}\)
\[H(x) = \begin{pmatrix} 12x_1^2 - 4 & 0 \\ 0 & 2 \end{pmatrix}\]
步骤2：识别问题
在 \(x_1 = 0\) 附近，\(H_{11} = -4 < 0\)，Hessian不正定。
步骤3：修正策略
修正牛顿法迭代表
k
\(x_k\)
\(H_k\) 特征值
修正
\(\tilde{H}_k\)
修正牛顿方向
\(x_{k+1}\)
0
\((0.5, 0.5)^T\)
\((-1, 2)\)
\(\mu = 1.1\)
\(\begin{pmatrix} 0.1 & 0 \\ 0 & 3.1 \end{pmatrix}\)
\((-5, -0.323)^T\)
线搜索后
1
\((0.2, 0.177)^T\)
\((0.48, 2)\)
无需修正
\(H_1\)
标准牛顿方向
继续迭代
修正公式：
\(\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算法迭代推导表
k
\(x_k\)
\(g_k\)
\(H_k\)
搜索方向 \(d_k = -H_k g_k\)
步长 \(\alpha_k\)
\(s_k\)
\(y_k\)
\(H_{k+1}\)
0
\((-1.2, 1)^T\)
\((-215.6, -88)^T\)
\(I\)
\((215.6, 88)^T\)
\(0.001\)
\((0.216, 0.088)^T\)
\((-112.4, 22.4)^T\)
BFGS更新
1
\((-0.984, 1.088)^T\)
\((-103.2, 21.6)^T\)
\(H_1\)
BFGS方向
线搜索
\(s_1\)
\(y_1\)
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计算次数
最终误差
计算复杂度
牛顿法
1
1
1
1
\(10^{-16}\)
\(O(n^3)\)
BFGS
2
6
3
0
\(10^{-12}\)
\(O(n^2)\)
最速下降
8
20
9
0
\(10^{-6}\)
\(O(n)\)
关键观察：
牛顿法对二次函数一步收敛，但需要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 迭代对比
k
方法
\(x_k\)
\(|g_k|\)
\(H_k\) 条件数
收敛速度
0
初值
\((1, 1)^T\)
\(7.07\)
\(1.0\)
—
1
DFP
\((0.6, 0.4)^T\)
\(2.83\)
\(2.1\)
快
1
BFGS
\((0.5, 0.5)^T\)
\(2.12\)
\(1.8\)
更快
2
DFP
\((0.2, 0.1)^T\)
\(0.89\)
\(3.2\)
中等
2
BFGS
\((0.1, 0.05)^T\)
\(0.35\)
\(2.5\)
快
结论：
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存储需求分析
问题：比较不同方法的存储需求
存储需求对比表
方法
存储矩阵
存储需求
n=1000时内存
n=10^6时内存
牛顿法
\(H^{-1}\)
\(O(n^2)\)
8MB
8TB
BFGS
\(H_k\)
\(O(n^2)\)
8MB
8TB
L-BFGS(m=10)
\(\{s_i,y_i\}\)
\(O(mn)\)
160KB
160MB
L-BFGS(m=20)
\(\{s_i,y_i\}\)
\(O(mn)\)
320KB
320MB
关键优势：
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线搜索过程
试探步长 \(\alpha\)
\(x_k + \alpha d_k\)
\(f(x_k + \alpha d_k)\)
Armijo右端
是否满足
1.0
1.125
0.423
0.832
?
0.5
1.313
0.612
0.916
?
0.25
1.406
0.751
0.958
?
选择策略：选择最大的满足Armijo条件的步长，通常 \(\alpha = 1.0\)
例题10：Wolfe条件的强化
问题：同时验证Armijo条件和曲率条件
强Wolfe条件：
Armijo条件：\(f(x_k + \alpha d_k) \leq f(x_k) + c_1 \alpha \nabla f(x_k)^T d_k\)
曲率条件：$$
\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\)
收敛速度实验结果
\(\kappa\)
牛顿法
BFGS
L-BFGS
最速下降
10
1步
2-3步
3-4步
15步
100
1步
4-5步
6-8步
150步
1000
1步
8-10步
12-15步
1500步
理论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\)
策略对比：
病态问题求解策略
方法
预处理
收敛步数
数值稳定性
实现复杂度
牛顿法
无
1
差
高
修正牛顿法
正则化
2-3
好
高
BFGS
无
15-20
中等
中等
L-BFGS
预条件
8-12
好
低
七、实际应用例题
例题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：神经网络训练中的应用
问题：比较不同优化算法在神经网络训练中的表现
神经网络优化算法对比
算法
收敛速度
内存需求
超参数调整
适用场景
SGD
慢
低
需要
大数据集
Adam
快
中等
较少
通用
L-BFGS
很快
高
很少
小批量
牛顿法
最快
很高
无
理论分析
八、数值实现技巧
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 算法选择指南
优化算法选择决策树
问题特征
推荐算法
理由
小规模（n < 100）+ 二次型
牛顿法
一步收敛，计算开销可接受
中等规模（100 < n < 1000）
BFGS
超线性收敛，无需Hessian
大规模（n > 1000）
L-BFGS
内存效率高，收敛快
非凸 + 多峰
修正牛顿法
处理负曲率，全局收敛
噪声梯度
拟牛顿法
对梯度误差鲁棒
实时应用
L-BFGS
计算效率最高
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 实践建议
初学者：从BFGS开始，理解拟牛顿思想
研究者：牛顿法用于理论分析
工程师：L-BFGS用于实际应用
特殊情况：根据问题特征选择修正策略
十、进阶主题
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
最优化理论——拉格朗日乘子法与增广拉格朗日乘子法