基于改进的Barzilai-Borwein步长的自适应梯度法基础题

题目描述

考虑一个无约束非线性规划问题：

\[\min_{x \in \mathbb{R}^n} f(x) \]

其中目标函数 \(f: \mathbb{R}^n \to \mathbb{R}\) 是连续可微的，但可能不是严格凸的，其梯度 \(\nabla f(x)\) 可计算。我们要求解此问题，并使用一种结合了Barzilai-Borwein (BB) 步长思想和自适应步长调整的梯度下降法。BB步长是一种通过拟牛顿思想近似Hessian逆矩阵的标量步长，旨在在不计算二阶导数的前提下加速梯度下降的收敛。本题将引导你实现一个改进的BB步长策略，并嵌入到自适应梯度下降框架中，以在非凸、病态问题上获得比标准梯度下降更稳定、更快的收敛。

解题过程循序渐进讲解

第一步：回顾标准梯度下降法及其步长选择挑战

标准梯度下降法的迭代格式为：

\[x_{k+1} = x_k - \alpha_k \nabla f(x_k) \]

其中 \(\alpha_k > 0\) 是步长（学习率）。步长的选择至关重要：

• 固定步长：需谨慎选择，太大易发散，太小收敛慢。
• 线搜索（如Armijo准则）：保证下降，但每步需多次函数值计算，成本较高。

BB步长的目标：利用当前和上一步的迭代信息，自动计算一个“拟牛顿”步长，平衡收敛速度和计算开销。

第二步：理解经典Barzilai-Borwein (BB) 步长的两种形式

定义：

• 梯度变化： \(y_{k-1} = \nabla f(x_k) - \nabla f(x_{k-1})\)
• 变量变化： \(s_{k-1} = x_k - x_{k-1}\)

两种BB步长公式：

1. 长步长 (Long BB步长)：

\[ \alpha_{k}^{L} = \frac{s_{k-1}^T s_{k-1}}{s_{k-1}^T y_{k-1}} \]

该形式源自最小二乘逼近 \(\alpha^{-1} I\) 近似Hessian矩阵 \(H\)，使得 \(H s_{k-1} \approx y_{k-1}\)。

2. 短步长 (Short BB步长)：

\[ \alpha_{k}^{S} = \frac{s_{k-1}^T y_{k-1}}{y_{k-1}^T y_{k-1}} \]

该形式源自最小二乘逼近 \(\alpha I\) 近似Hessian逆矩阵 \(H^{-1}\)，使得 \(H^{-1} y_{k-1} \approx s_{k-1}\)。

通常，\(\alpha_{k}^{L} \ge \alpha_{k}^{S}\)，两者在二次严格凸问题中表现良好，但在非凸或非二次问题上可能不稳定，可能导致步长过大（发散）或过小（停滞）。

第三步：引入自适应调整策略——改进的BB步长（改进点）

为了增强鲁棒性，我们采用一种自适应策略，在长步长和短步长之间切换，并引入安全边界和重置机制。具体步骤：

1. 初始化：选择初始点 \(x_0\)，初始步长 \(\alpha_0 > 0\)（例如通过少量线搜索或固定值），计算梯度 \(g_0 = \nabla f(x_0)\)。设定常数 \(0 < \tau_{\min} < \tau_{\max}\)（例如 \(10^{-4}\) 和 \(10^4\) ），重置周期 \(R\)（例如每10次迭代），和步长阈值 \(\epsilon_{\alpha}\)（例如 \(10^{-8}\)）。

2. 迭代循环：对于 \(k = 1, 2, \dots\)
   a. 计算新点： \(x_k = x_{k-1} - \alpha_{k-1} g_{k-1}\)
   b. 计算当前梯度： \(g_k = \nabla f(x_k)\)
   c. 检查收敛条件：若 \(\| g_k \| \le \epsilon\)（给定容差），则停止。

3. 计算BB步长候选（仅当 \(k \ge 2\)）：

   • 计算 \(s_{k-1} = x_k - x_{k-1}\)， \(y_{k-1} = g_k - g_{k-1}\)
   • 计算长步长： \(\alpha_{k}^{L} = \frac{s_{k-1}^T s_{k-1}}{s_{k-1}^T y_{k-1}}\)
   • 计算短步长： \(\alpha_{k}^{S} = \frac{s_{k-1}^T y_{k-1}}{y_{k-1}^T y_{k-1}}\)
   • 注意：若分母接近零（如 \(|s_{k-1}^T y_{k-1}| < \epsilon_{\alpha}\)），则跳过BB更新，沿用上一步步长。

4. 自适应选择步长：

   • 采用交替策略：在奇数次迭代用长步长，偶数次迭代用短步长（或其他规则，如比较函数下降量选择更优者）。这里为简单，定义：

\[ \alpha_{k}^{BB} = \begin{cases} \alpha_{k}^{L} & \text{if } k \text{ is odd} \\ \alpha_{k}^{S} & \text{if } k \text{ is even} \end{cases} \]

• 将步长限制在安全范围：

\[ \alpha_k = \min(\tau_{\max}, \max(\tau_{\min}, \alpha_{k}^{BB})) \]

 避免步长过大或过小。

5. 重置机制：

   • 每 \(R\) 次迭代，或当函数值上升（ \(f(x_k) > f(x_{k-1})\) ）时，重置步长为初始步长 \(\alpha_0\) 或进行一次简单的回溯线搜索，确保下降性。这有助于跳出不稳定区域。

6. 继续迭代：用新步长 \(\alpha_k\) 进行下一步。

第四步：算法伪代码总结

输入：初始点 x0，梯度容差 ε，最大迭代次数 K，安全边界 τ_min, τ_max，重置周期 R
输出：近似最优解 x*
1: 设置 α0（如通过一次Armijo线搜索或固定值），计算 g0 = ∇f(x0)，k = 0
2: while k < K and ||gk|| > ε do
3:    x_{k+1} = x_k - α_k * g_k
4:    计算 g_{k+1} = ∇f(x_{k+1})
5:    if ||g_{k+1}|| ≤ ε then break
6:    if k ≥ 1 then
7:        计算 s_k = x_{k+1} - x_k, y_k = g_{k+1} - g_k
8:        if |s_k^T y_k| > ε_α then
9:            计算 α_L = (s_k^T s_k) / (s_k^T y_k)
10:           计算 α_S = (s_k^T y_k) / (y_k^T y_k)
11:           如果 k+1 为奇数: α_candidate = α_L
12:           否则: α_candidate = α_S
13:           α_{k+1} = min(τ_max, max(τ_min, α_candidate))
14:        else
15:           α_{k+1} = α_k  # 分母过小，沿用旧步长
16:        end if
17:    else
18:        α_{k+1} = α_0  # 第一步后尚无足够信息，用初始步长
19:    end if
20:    # 重置检查
21:    if (k+1) mod R == 0 or f(x_{k+1}) > f(x_k) then
22:        重置 α_{k+1} = α_0 或执行一步回溯线搜索得到新 α_{k+1}
23:    end if
24:    k = k + 1
25: end while
26: 返回 x_{k+1}

第五步：示例与注意事项

考虑测试函数：Rosenbrock函数 \(f(x) = 100(x_2 - x_1^2)^2 + (1 - x_1)^2\)，起点 \(x_0 = (-1.2, 1)^T\)。此函数非凸，具有狭窄弯曲山谷，传统梯度下降收敛极慢。

• 改进BB步长法能在山谷中自动调整步长，沿底部快速前进。
• 注意：BB步长不保证函数值单调下降，因此重置机制很重要。也可结合非单调线搜索（如Grippo-Lampariello-Lucidi准则）增强稳定性。
• 对于大规模问题，BB法常用于梯度法加速（如用于L-BFGS的初始化步长），计算开销小（仅向量内积）。

总结：改进的自适应BB步长梯度法，通过拟牛顿思想估计曲率，自适应切换和约束步长，并以重置机制保证鲁棒性，在中等规模非凸问题上能实现比固定步长梯度下降更快的收敛，且无需计算Hessian矩阵，是一种实用的一阶优化加速技术。