Barzilai-Borwein 梯度法（BB 法）基础题
题目描述
考虑无约束非线性规划问题：
\[\min_{x \in \mathbb{R}^n} f(x) \]
其中目标函数 \(f: \mathbb{R}^n \to \mathbb{R}\) 是连续可微的，但可能非凸，且计算其梯度 \(\nabla f(x)\) 的代价较高。我们无法或不想计算目标函数的二阶导数（Hessian 矩阵），但仍希望利用梯度信息构造一种拟牛顿风格的迭代方法，以比最速下降法更快的速度收敛。
Barzilai-Borwein (BB) 法是一种特殊的梯度法，它通过巧妙地利用相邻两步的迭代点和梯度差，构造一个标量步长来近似牛顿法的行为，从而在计算量仅略高于最速下降法的情况下，显著提高收敛速度。
你的任务是：阐述 BB 法的基本思想，推导其两种经典的步长选择公式，并详细解释其迭代步骤、收敛性特点以及一个简单的数值实现流程。
解题过程循序渐进讲解
1. 问题背景与核心思想
在梯度下降法中，迭代格式为：
\[x_{k+1} = x_k - \alpha_k \nabla f(x_k) \]
其中步长 \(\alpha_k > 0\)。最速下降法在每次迭代时通过线性搜索（如精确搜索、Armijo 准则等）确定 \(\alpha_k\)，但收敛速度常为线性，且可能呈现“锯齿”现象。
牛顿法的迭代格式为：
\[x_{k+1} = x_k - H_k^{-1} \nabla f(x_k) \]
其中 \(H_k = \nabla^2 f(x_k)\) 是 Hessian 矩阵。牛顿法具有局部二次收敛速度，但需要计算和求逆 Hessian 矩阵，计算成本高。
BB 法的核心思想是：用一个标量 \(\alpha_k\) 来近似 Hessian 矩阵的逆。我们希望这个标量 \(\alpha_k\) 能使得拟牛顿方程（割线方程）在某种意义下得到近似满足。拟牛顿方程要求矩阵 \(B_{k+1}\) 满足：
\[B_{k+1} s_k = y_k \]
其中 \(s_k = x_{k+1} - x_k\)， \(y_k = \nabla f(x_{k+1}) - \nabla f(x_k)\)。在 BB 法中，我们强制 \(B_{k+1} = (1/\alpha_k) I\) 是一个单位矩阵的倍数。那么拟牛顿方程变为：
\[\frac{1}{\alpha_k} s_k \approx y_k \]
这显然无法精确满足，因为 \(s_k\) 和 \(y_k\) 通常不共线。BB 法通过求解以下两个最小二乘问题来得到 \(\alpha_k\) 的两种选择。
2. 两种步长公式的推导
公式一（BB1）： 我们希望标量 \(\alpha_k\) 使得 \(\frac{1}{\alpha_k} s_k\) 尽可能接近 \(y_k\)。这转化为最小化残差的 2-范数：
\[\min_{\alpha > 0} \left\| \frac{1}{\alpha} s_k - y_k \right\|^2 \]
忽略与 \(\alpha\) 无关的项，等价于：
\[\min_{\alpha > 0} \left( \frac{1}{\alpha^2} \|s_k\|^2 - \frac{2}{\alpha} s_k^T y_k \right) \]
对 \(\alpha\) 求导并令其为零：
\[-\frac{2}{\alpha^3} \|s_k\|^2 + \frac{2}{\alpha^2} s_k^T y_k = 0 \]
解得：
\[\alpha_k^{\text{BB1}} = \frac{s_{k-1}^T s_{k-1}}{s_{k-1}^T y_{k-1}} \]
注意这里下标有偏移：在得到 \(x_k\) 和 \(x_{k-1}\) 后，我们用 \(s_{k-1} = x_k - x_{k-1}\) 和 \(y_{k-1} = \nabla f(x_k) - \nabla f(x_{k-1})\) 来计算下一步的步长 \(\alpha_k\)。这个步长用于从 \(x_k\) 到 \(x_{k+1}\) 的迭代。
公式二（BB2）： 另一种思路是希望 \(\alpha_k y_k\) 尽可能接近 \(s_k\)。即最小化：
\[\min_{\alpha > 0} \| s_k - \alpha y_k \|^2 \]
同样求导得：
\[\alpha_k^{\text{BB2}} = \frac{s_{k-1}^T y_{k-1}}{y_{k-1}^T y_{k-1}} \]
3. 迭代步骤详解
-
初始化：选择初始点 \(x_0 \in \mathbb{R}^n\)，设定初始步长 \(\alpha_0 > 0\)（例如通过一次简单的线搜索得到），收敛容差 \(\epsilon > 0\)。令 \(k = 0\)。
-
计算梯度：计算当前点的梯度 \(g_k = \nabla f(x_k)\)。
-
收敛性检查：如果 \(\|g_k\| \le \epsilon\)，则停止迭代，输出 \(x_k\) 作为近似极小点。
-
确定搜索方向：采用负梯度方向 \(d_k = -g_k\)。
-
计算步长：
- 如果 \(k = 0\)，则使用初始步长 \(\alpha_0\)。
- 如果 \(k \ge 1\)，则计算：
\[ s_{k-1} = x_k - x_{k-1}, \quad y_{k-1} = g_k - g_{k-1} \]
选择 BB1 或 BB2 公式计算步长：
\[ \alpha_k^{\text{BB1}} = \frac{s_{k-1}^T s_{k-1}}{s_{k-1}^T y_{k-1}} \quad \text{或} \quad \alpha_k^{\text{BB2}} = \frac{s_{k-1}^T y_{k-1}}{y_{k-1}^T y_{k-1}} \]
注意：分母可能为零或接近零，需要保护（例如设置一个最小阈值）。
- 更新迭代点：
\[ x_{k+1} = x_k - \alpha_k g_k \]
注意，这里没有额外的线搜索！BB 步长直接用于更新。这是它与传统梯度法的重要区别，也使其计算成本极低。
- 迭代递增：令 \(k := k + 1\)，返回步骤 2。
4. 算法特性与注意事项
- 非单调性：BB 法产生的函数值序列 \(\{f(x_k)\}\) 不一定是单调递减的，这是其与最速下降法的显著不同。它可能会“跳过”一些局部下降的机会以获得更长的整体步长，从而加速收敛。
- 步长正性：为确保步长为正，通常需要满足曲率条件 \(s_{k-1}^T y_{k-1} > 0\)。对于凸函数，此条件成立。对于非凸函数，若不满足，可采取保护措施，如采用一个固定的正步长或执行一次回溯线搜索。
- 两种步长的交替使用：实际应用中，常常交替使用 BB1 和 BB2 步长，或将它们与周期性的梯度步长（带线搜索）结合，以提高鲁棒性，这称为循环 BB 法。
- 收敛性：对于一致凸的二次函数，BB 法具有 R-超线性收敛速度。对于一般光滑非线性函数，在适当的条件下（如目标函数强凸且梯度 Lipschitz 连续），它能保证全局收敛到稳定点，但收敛速度分析比二次情形复杂。
5. 一个简单的数值实现流程（以 BB1 为例，包含保护策略）
输入：目标函数 f，梯度函数 grad_f，初始点 x0，初始步长 alpha0=1.0，最大迭代次数 max_iter，容差 tol=1e-6，保护阈值 delta=1e-8。
过程：
1. x = x0
2. g = grad_f(x)
3. alpha = alpha0
4. for k = 1 to max_iter do：
5. if norm(g) < tol: break
6. d = -g
7. x_new = x + alpha * d
8. g_new = grad_f(x_new)
9. if k >= 1:
10. s = x_new - x
11. y = g_new - g
12. sTy = s^T * y
13. if |sTy| < delta: # 曲率条件不满足
14. alpha = alpha0 # 重置为初始步长或执行一次回溯线搜索
15. else:
16. alpha = (s^T * s) / sTy # BB1 公式
17. x = x_new
18. g = g_new
19. 结束循环
输出：近似解 x
总结
BB 法是一种巧妙、高效的一阶优化算法。它通过利用前两步的梯度差和位移差，构造一个标量步长来近似 Hessian 的信息，从而在仅增加少量计算（主要是向量内积）的情况下，获得了远超传统梯度法的收敛性能，特别适合大规模、梯度计算成本较高的优化问题。理解其思想是掌握许多现代一阶优化方法（如梯度法变种）的重要基础。