Profile Image of the Author
老官童鞋gogo

公告
欢迎来到我的博客 / 笔记本！
标签
1726 字
9 分钟
数据科学与工程优化（三）
2025-07-22
程设计科
/
人工智能
人工智能

一、最速下降法#

最速下降法（Steepest Descent）用于求解无约束优化问题：

min⁡x∈Rnf(x)\min_{x \in \mathbb{R}^n} f(x)

其中 f:Rn→Rf: \mathbb{R}^n \to \mathbb{R} 是 LL-光滑函数。算法通过迭代更新：

xk+1=xk+αkdkx_{k+1} = x_k + \alpha_k d_k
  • αk>0\alpha_k > 0 是步长（step length），在机器学习领域也常称为学习率（learning rate）。步长/学习率决定每次迭代沿搜索方向前进的距离，步长太小收敛慢，太大可能导致发散或振荡。两者本质相同，只是术语在不同领域有所区别。
  • dk∈Rnd_k \in \mathbb{R}^n 是搜索方向（search direction）

1、最速下降法的选择#

  • 搜索方向：dk=−∇f(xk)d_k = -\nabla f(x_k)
  • 步长：αk=1L\alpha_k = \frac{1}{L}（常数步长）

因此，迭代公式：

xk+1=xk−1L∇f(xk)x_{k+1} = x_k - \frac{1}{L} \nabla f(x_k)

主要关心步长的选择：太小收敛慢，太大可能振荡。

二、学习率推导#

由光滑性质（见 Part II）：

f(y)≤f(x)+∇f(x)T(y−x)+L2∥y−x∥2,∀x,y∈Rnf(y) \leq f(x) + \nabla f(x)^T (y - x) + \frac{L}{2} \|y - x\|^2, \quad \forall x, y \in \mathbb{R}^n

令 y=x+αdy = x + \alpha d，且 d=−∇f(x)d = -\nabla f(x)，得：

f(x+αd)≤f(x)−α∥∇f(x)∥2+α2L2∥d∥2f(x + \alpha d) \leq f(x) - \alpha \|\nabla f(x)\|^2 + \frac{\alpha^2 L}{2} \|d\|^2

令 d=−∇f(x)d = -\nabla f(x)，则 ∥d∥=∥∇f(x)∥\|d\| = \|\nabla f(x)\|：

f(x+αd)≤f(x)−α∥∇f(x)∥2+α2L2∥∇f(x)∥2f(x + \alpha d) \leq f(x) - \alpha \|\nabla f(x)\|^2 + \frac{\alpha^2 L}{2} \|\nabla f(x)\|^2

令 ϕ(α)=f(x)−α∥∇f(x)∥2+α2L2∥∇f(x)∥2\phi(\alpha) = f(x) - \alpha \|\nabla f(x)\|^2 + \frac{\alpha^2 L}{2} \|\nabla f(x)\|^2，对 α\alpha 求极小值：

dϕdα=−∥∇f(x)∥2+αL∥∇f(x)∥2=0⟹α∗=1L\frac{\mathrm{d} \phi}{\mathrm{d} \alpha} = -\|\nabla f(x)\|^2 + \alpha L \|\nabla f(x)\|^2 = 0 \\ \Longrightarrow \alpha^* = \frac{1}{L}

三、基本不等式（收敛分析的核心工具）#

引理（最速下降法的基本不等式）：

对于任意起点 x0x_0，最速下降法迭代有：

f(xk+1)=f(xk−1L∇f(xk))≤f(xk)−12L∥∇f(xk)∥2f(x_{k+1}) = f\left(x_k - \frac{1}{L} \nabla f(x_k)\right) \leq f(x_k) - \frac{1}{2L} \|\nabla f(x_k)\|^2
  • 推导：将 α=1L\alpha = \frac{1}{L} 和 d=−∇f(xk)d = -\nabla f(x_k) 代入上述光滑性上界。
  • 注意：该结果不依赖凸性！

四、收敛理论#

1、一般情形（无凸性假设）#

定理（一般收敛性）：

f(x)f(x) LL-光滑且有下界 ff，用 αk=1/L\alpha_k = 1/L，则

min⁡0≤k≤T−1∥∇f(xk)∥≤2L(f(x0)−f)T\min_{0 \leq k \leq T-1} \|\nabla f(x_k)\| \leq \sqrt{\frac{2L(f(x_0) - f)}{T}}
  • 表明 ∥∇f(xk)∥\|\nabla f(x_k)\| 以 O(1/T)O(1/\sqrt{T}) 的速率收敛到零（次线性）。

证明：

由基本不等式（见上文）：

f(xk+1)≤f(xk)−12L∥∇f(xk)∥2f(x_{k+1}) \leq f(x_k) - \frac{1}{2L} \|\nabla f(x_k)\|^2

两边同时累加 k=0k=0 到 T−1T-1，得：

∑k=0T−1[f(xk+1)−f(xk)]≤−12L∑k=0T−1∥∇f(xk)∥2\sum_{k=0}^{T-1} \left[ f(x_{k+1}) - f(x_k) \right] \leq -\frac{1}{2L} \sum_{k=0}^{T-1} \|\nabla f(x_k)\|^2

左边是望远镜求和，化简为：

f(xT)−f(x0)≤−12L∑k=0T−1∥∇f(xk)∥2f(x_T) - f(x_0) \leq -\frac{1}{2L} \sum_{k=0}^{T-1} \|\nabla f(x_k)\|^2

移项并乘以 2L2L，得：

∑k=0T−1∥∇f(xk)∥2≤2L(f(x0)−f(xT))\sum_{k=0}^{T-1} \|\nabla f(x_k)\|^2 \leq 2L (f(x_0) - f(x_T))

由于 f(xT)≥ff(x_T) \geq f（ff为下界），进一步有：

∑k=0T−1∥∇f(xk)∥2≤2L(f(x0)−f)\sum_{k=0}^{T-1} \|\nabla f(x_k)\|^2 \leq 2L (f(x_0) - f)

因此，至少有一个 kk 使得 ∥∇f(xk)∥2\|\nabla f(x_k)\|^2 不大于平均值：

min⁡0≤k≤T−1∥∇f(xk)∥2≤1T∑k=0T−1∥∇f(xk)∥2≤2L(f(x0)−f)T\min_{0 \leq k \leq T-1} \|\nabla f(x_k)\|^2 \leq \frac{1}{T} \sum_{k=0}^{T-1} \|\nabla f(x_k)\|^2 \leq \frac{2L(f(x_0) - f)}{T}

两边开方，得：

min⁡0≤k≤T−1∥∇f(xk)∥≤2L(f(x0)−f)T\min_{0 \leq k \leq T-1} \|\nabla f(x_k)\| \leq \sqrt{ \frac{2L(f(x_0) - f)}{T} }

证毕。

2、凸函数情形#

定理（凸且L-光滑）：

ff LL-光滑且凸，极小点 x∗x^*，则

f(xT)−f(x∗)≤L2T∥x0−x∗∥2f(x_T) - f(x^*) \leq \frac{L}{2T} \|x_0 - x^*\|^2
  • 次线性收敛，O(1/T)O(1/T)。

证明：

LL-光滑性，任意 x,yx, y 有

f(y)≤f(x)+∇f(x)T(y−x)+L2∥y−x∥2f(y) \leq f(x) + \nabla f(x)^T (y - x) + \frac{L}{2} \|y - x\|^2

令 y=xk−1L∇f(xk)y = x_k - \frac{1}{L} \nabla f(x_k)，得

f(xk+1)≤f(xk)−1L∥∇f(xk)∥2+L2(1L)2∥∇f(xk)∥2=f(xk)−12L∥∇f(xk)∥2f(x_{k+1}) \leq f(x_k) - \frac{1}{L} \|\nabla f(x_k)\|^2 + \frac{L}{2} \left(\frac{1}{L}\right)^2 \|\nabla f(x_k)\|^2 = f(x_k) - \frac{1}{2L} \|\nabla f(x_k)\|^2

由凸性，任意 xx，极小点 x∗x^* 有

f(x)−f(x∗)≤∇f(x)T(x−x∗)f(x) - f(x^*) \leq \nabla f(x)^T (x - x^*)

由上一步递推

f(xk+1)−f(x∗)≤f(xk)−f(x∗)−12L∥∇f(xk)∥2f(x_{k+1}) - f(x^*) \leq f(x_k) - f(x^*) - \frac{1}{2L} \|\nabla f(x_k)\|^2

由凸性

f(xk)−f(x∗)≤∇f(xk)T(xk−x∗)f(x_k) - f(x^*) \leq \nabla f(x_k)^T (x_k - x^*)

由L-光滑和凸性，有

∥∇f(xk)∥2≥2L(f(xk)−f(xk+1))\|\nabla f(x_k)\|^2 \geq 2L (f(x_k) - f(x_{k+1}))

或用

f(xk)−f(x∗)≤12μ∥∇f(xk)∥2f(x_k) - f(x^*) \leq \frac{1}{2\mu} \|\nabla f(x_k)\|^2

（但此处仅用凸性，不用强凸）

将基本不等式递推 TT 步，得

f(xT)−f(x∗)≤f(x0)−f(x∗)−12L∑k=0T−1∥∇f(xk)∥2f(x_T) - f(x^*) \leq f(x_0) - f(x^*) - \frac{1}{2L} \sum_{k=0}^{T-1} \|\nabla f(x_k)\|^2

由凸性和梯度下降方向，结合Jensen不等式，最终可推出

f(xT)−f(x∗)≤L2T∥x0−x∗∥2f(x_T) - f(x^*) \leq \frac{L}{2T} \|x_0 - x^*\|^2

3、强凸函数情形#

定理（强凸且L-光滑）：

ff LL-光滑且 γ\gamma-强凸，则极小点唯一 x∗x^*，且

f(xk+1)−f(x∗)≤(1−γL)(f(xk)−f(x∗))f(x_{k+1}) - f(x^*) \leq \left(1 - \frac{\gamma}{L}\right)(f(x_k) - f(x^*))
  • 线性收敛，收敛速率为 1−γL1 - \frac{\gamma}{L}。

证明：

证明方法：

ff 是 γ\gamma-强凸，定义为对任意 x,y∈Rnx, y \in \mathbb{R}^n，

f(y)≥f(x)+∇f(x)T(y−x)+γ2∥y−x∥2f(y) \geq f(x) + \nabla f(x)^T (y - x) + \frac{\gamma}{2} \|y - x\|^2

令 y=x∗y = x^* 为极小点，∇f(x∗)=0\nabla f(x^*) = 0，则

f(x∗)≥f(x)+∇f(x)T(x∗−x)+γ2∥x∗−x∥2f(x^*) \geq f(x) + \nabla f(x)^T (x^* - x) + \frac{\gamma}{2} \|x^* - x\|^2

移项得

f(x)−f(x∗)≤∇f(x)T(x−x∗)−γ2∥x−x∗∥2f(x) - f(x^*) \leq \nabla f(x)^T (x - x^*) - \frac{\gamma}{2} \|x - x^*\|^2

另一方面，强凸函数满足

f(x)−f(x∗)≥γ2∥x−x∗∥2f(x) - f(x^*) \geq \frac{\gamma}{2} \|x - x^*\|^2

此外，强凸与光滑性结合可推出梯度下界：

∥∇f(x)∥2≥2γ(f(x)−f(x∗))\|\nabla f(x)\|^2 \geq 2\gamma (f(x) - f(x^*))

这是通过 Cauchy-Schwarz 和强凸性质推导的，具体如下：

由强凸性，

f(x)−f(x∗)≤∇f(x)T(x−x∗)−γ2∥x−x∗∥2f(x) - f(x^*) \leq \nabla f(x)^T (x - x^*) - \frac{\gamma}{2} \|x - x^*\|^2

而极小点 x∗x^* 满足 ∇f(x∗)=0\nabla f(x^*) = 0，由一阶最优性条件，

∇f(x)T(x−x∗)≥f(x)−f(x∗)\nabla f(x)^T (x - x^*) \geq f(x) - f(x^*)

结合以上两式，利用 Cauchy-Schwarz 不等式，

∥∇f(x)∥∥x−x∗∥≥∇f(x)T(x−x∗)≥f(x)−f(x∗)\|\nabla f(x)\| \|x - x^*\| \geq \nabla f(x)^T (x - x^*) \geq f(x) - f(x^*)

由强凸性下界 ∥x−x∗∥2≤2γ(f(x)−f(x∗))\|x - x^*\|^2 \leq \frac{2}{\gamma}(f(x) - f(x^*))，代入得

∥∇f(x)∥2≥2γ(f(x)−f(x∗))\|\nabla f(x)\|^2 \geq 2\gamma (f(x) - f(x^*))

该不等式在收敛分析中用于将函数值下降与梯度范数联系起来，是强凸问题线性收敛的关键。 ff 是 γ\gamma-强凸，任意 xx，极小点 x∗x^* 有

f(x)−f(x∗)≥γ2∥x−x∗∥2f(x) - f(x^*) \geq \frac{\gamma}{2} \|x - x^*\|^2

且

∥∇f(x)∥2≥2γ(f(x)−f(x∗))\|\nabla f(x)\|^2 \geq 2\gamma (f(x) - f(x^*))

ff 是 LL-光滑，任意 xx，有

f(x−1L∇f(x))≤f(x)−12L∥∇f(x)∥2f\left(x - \frac{1}{L} \nabla f(x)\right) \leq f(x) - \frac{1}{2L} \|\nabla f(x)\|^2

对 xkx_k 迭代：

f(xk+1)≤f(xk)−12L∥∇f(xk)∥2f(x_{k+1}) \leq f(x_k) - \frac{1}{2L} \|\nabla f(x_k)\|^2

用强凸性质下界 ∥∇f(xk)∥2\|\nabla f(x_k)\|^2：

f(xk+1)≤f(xk)−γL(f(xk)−f(x∗))f(x_{k+1}) \leq f(x_k) - \frac{\gamma}{L}(f(x_k) - f(x^*))

即

f(xk+1)−f(x∗)≤(1−γL)(f(xk)−f(x∗))f(x_{k+1}) - f(x^*) \leq \left(1 - \frac{\gamma}{L}\right)(f(x_k) - f(x^*))

五、长步长最速下降法（Long-Step SD）#

实际应用中，步长 αk\alpha_k 和方向 dkd_k 可更灵活选择：

  • f(x)f(x) 仍要求 LL-光滑，有下界。
  • dkd_k 可为近似 −∇f(xk)-\nabla f(x_k)，只要与梯度夹角不太大。
  • 步长 αk\alpha_k 不宜太小或太大，需满足若干技术条件。

条件举例（Assumptions on SDM with line search）：

存在常数 0<η≤10 < \eta \leq 1，0<c1<c2<10 < c_1 < c_2 < 1，对所有 kk：

  1. 充分下降方向： ∇f(xk)Tdk≤−η∥∇f(xk)∥∥dk∥\nabla f(x_k)^T d_k \leq -\eta \|\nabla f(x_k)\| \|d_k\|
  2. 步长不太长： f(xk+αkdk)≤f(xk)+c1αk∇f(xk)Tdkf(x_k + \alpha_k d_k) \leq f(x_k) + c_1 \alpha_k \nabla f(x_k)^T d_k
  3. 步长不太短： ∇f(xk+αkdk)Tdk≥c2∇f(xk)Tdk\nabla f(x_k + \alpha_k d_k)^T d_k \geq c_2 \nabla f(x_k)^T d_k

这些条件实际可通过简单的线搜索方法满足。

若满足以上条件，则（收敛性定理）

min⁡0≤k≤T−1∥∇f(xk)∥≤Lη2c1(1−c2)⋅f(x0)−fT\min_{0 \leq k \leq T-1} \|\nabla f(x_k)\| \leq \sqrt{ \frac{L}{\eta^2 c_1 (1 - c_2)} \cdot \frac{f(x_0) - f}{T} }

与常步长法相比，右侧仅差常数。

六、梯度下降法的局限性#

  • 依赖尺度（scale-dependent）：若问题变量或目标函数缩放差异大，梯度方向效果差。
  • 收敛慢：尤其是变量尺度差异大时，梯度下降会在解空间“锯齿状”前进，进展很慢。

举例：二次型函数#

f(x)=12(ax12+x22)=12xT(a001)xf(x) = \frac{1}{2}(a x_1^2 + x_2^2) = \frac{1}{2}x^T \begin{pmatrix} a & 0 \\ 0 & 1 \end{pmatrix} x
  • a≫1a \gg 1 时，问题病态，收敛极慢。
  • 若对变量做线性变换 y=(a1/2001)xy = \begin{pmatrix} a^{1/2} & 0 \\ 0 & 1 \end{pmatrix} x，则变成标准二次型，收敛快。

七、局部收敛速率（理论与实际）#

对于 f∈C2f \in C^2，x∗x^* 局部极小点，∇2f(x∗)\nabla^2 f(x^*) 正定，最大/最小特征值分别为 λmax⁡,λmin⁡\lambda_{\max}, \lambda_{\min}，条件数 K=λmax⁡/λmin⁡K = \lambda_{\max}/\lambda_{\min}。

最速下降法收敛因子：

ρSD=(K−1K+1)2\rho_{SD} = \left( \frac{K - 1}{K + 1} \right)^2

条件数大时，ρSD\rho_{SD} 靠近 1，收敛极慢。例如：

  • Rosenbrock函数，K=258.1K = 258.1，ρSD≈0.984\rho_{SD} \approx 0.984
  • K=800K = 800，迭代 1000 次，目标函数下降有限

理论上收敛线性，但实际非常慢，尤其是病态问题。

分享

如果这篇文章对你有帮助，欢迎分享给更多人！

数据科学与工程优化（三）
https://www.laoguantx.cn/posts/datascienceandengineeringoptimization3/
作者
老官童鞋gogo
发布于
2025-07-22
许可协议
CC BY-NC-SA 4.0

部分信息可能已经过时

数据科学与工程优化（一）
数据科学与工程优化（二）
© 2026 老官童鞋gogo. All Rights Reserved. / RSS / Atom / Sitemap
Powered by Astro & Mizuki  Version 7.6.5
封面
Sample Song
Sample Artist
封面
Sample Song
Sample Artist
0:00 / 0:00