知识点：Barzilar-Borwein方法

知识点概述

Barzilar-Borwein（BB）方法是一种改进的梯度下降法。它通过利用前一步的迭代信息来近似海瑟矩阵，从而构造一个非单调的步长。BB方法在许多问题上比传统的梯度下降法收敛更快，且无需进行线搜索。

动机: 传统的梯度下降法步长选择困难，且收敛呈“锯齿”状。BB方法试图通过引入二阶信息来加速收敛，但又避免了计算真正的海瑟矩阵。
核心思想: 在第 $k$ 步，用一个简单的对角矩阵 $D_{k} = α_{k}^{- 1} I$ 来近似海瑟矩阵 $\nabla^{2} f (x_{k})$ 。这个近似满足割线方程（Secant Equation）： $D_{k} s_{k - 1} \approx y_{k - 1}$ ，其中 $s_{k - 1} = x_{k} - x_{k - 1}$ ， $y_{k - 1} = \nabla f (x_{k}) - \nabla f (x_{k - 1})$ 。
步长公式: 通过求解 $min_{α} ∥ α^{- 1} s_{k - 1} - y_{k - 1} ∥^{2}$ 或 $min_{α} ∥ s_{k - 1} - α y_{k - 1} ∥^{2}$ ，可以得到两个不同的BB步长：
1. $α_{k} = \frac{s _{k - 1}^{T} s _{k - 1}}{s _{k - 1}^{T} y _{k - 1}}$
2. $α_{k} = \frac{s _{k - 1}^{T} y _{k - 1}}{y _{k - 1}^{T} y _{k - 1}}$
性质:
- BB方法的步长序列是非单调的，这使得目标函数值在迭代过程中可能出现上升。
- 尽管函数值不单调下降，但对于凸二次问题，可以证明其R-超线性收敛性，远快于梯度下降的线性收敛。