1、适用范围#

适合凸二次型函数：

其中 $A$ 对称，特征值落在 $[\gamma, L]$，即 $f$ 是 $L$-光滑且 $\gamma$-强凸。

2、迭代公式#

• 第一步是梯度下降，第二项是动量项（momentum）。

3、收敛性定理（无需证明）#

令

则存在常数 $C>0$，有

• 若 $\gamma \approx L$，$\alpha \approx \frac{1}{L}$，$\beta \approx 0$（退化为普通梯度下降）。
• 若 $\gamma \ll L$，$\alpha \approx \frac{4}{L}$，$\beta \approx 1$。

4、目标函数收敛速率#

利用 $L$-光滑性，

近似有

5、与最速下降法比较#

• 若 $\gamma = 0.01L$，则重球法每步目标函数减少三分之一 $(1-2\sqrt{\gamma/L})^2 = 0.64$。
• 最速下降法每步仅减少 $1\%$，$(1-\gamma/L) = 0.99$。
• 重球法对病态（ill-conditioned）问题优势明显。

3.1 算法思想#

Nesterov加速法是重球法的推广，适用于一般强凸目标。

2、收敛性定理（强凸情形）#

若 $f$ $L$-光滑且 $\gamma$-强凸，取

则

• 加速收敛，$(1-\sqrt{\gamma/L}) < (1-\gamma/L)$。
• 例如 $\gamma = 0.01L$，Nesterov每步减少 $10\%$，而最速下降法仅 $1\%$。

1、算法步骤#

适用于 $f$ $L$-光滑凸，L不一定已知。算法采用两组变量 $x_k, y_k$，并自适应步长。

算法流程：

1. 设 $y_0 \neq z \in \mathbb{R}^n$，$\alpha_{-1} := \frac{\|y_0 - z\|}{\|\nabla f(y_0) - \nabla f(z)\|}$，$\lambda_0 := 1$，$x_{-1} := y_0$。
2. 对 $k = 0, 1, 2, \ldots$，重复：
   1. 用回溯线搜索找最小 $i$ 使 $$f\left(y_k - 2^{-i} \alpha_{k-1} \nabla f(y_k)\right) \leq f(y_k) - 2^{-(i+1)} \alpha_{k-1} \|\nabla f(y_k)\|^2$$ 令 $\alpha_k = 2^{-i} \alpha_{k-1}$
   2. $x_k = y_k - \alpha_k \nabla f(y_k)$
   3. $\lambda_{k+1} = \frac{1}{2}\left(1 + \sqrt{4\lambda_k^2 + 1}\right)$
   4. $y_{k+1} = x_k + \frac{\lambda_k - 1}{\lambda_{k+1}}(x_k - x_{k-1})$
3. 直到 $\|x_k - x_{k-1}\|$ 足够小。

2、理论最优复杂度#

• 该方法的迭代复杂度为 $O(\epsilon^{-1/2})$，即达到 $f(x_k) - f^* < \epsilon$ 只需 $O(1/\sqrt{\epsilon})$ 步。
• 这是理论上最优的复杂度。

1、主要结论#

设 $f$ 为 $L$-光滑凸函数，有极小点 $x^*$，则算法产生的序列满足

因此，$\epsilon$-最优所需迭代步数为

2、关键推导步骤（简要概述）#

• 定义辅助变量 $p_k = (\lambda_k - 1)(x_{k-1} - x_k)$，随 $k$ 增大逐步变大。
• 通过一系列递推与凸性、不等式，建立 $p_{k+1} - x_{k+1} + x^*$ 的范数递推关系。
• 用望远镜求和技巧，最终得出 $f(x_k) - f^*$ 的上界随 $1/(k+2)^2$ 衰减。