数值计算之 梯度下降法与函数极值

前言

本篇将开始介绍优化算法。首先是梯度下降法，在最小二乘与深度学习中，都是最常用的最优化求解方法和思想。

微积分基础 一元函数的极值，导数与泰勒展开

对于一元函数 f ( x ) f(x) f(x)而言，当 x 0 x_0 x0​满足以下条件时， f ( x 0 ) f(x_0) f(x0​)取得极值： f ′ ( x 0 ) = 0 , f ′ ′ ( x 0 ) ≠ 0 f'(x_0)=0,f''(x_0)\ne 0 f′(x0​)=0,f′′(x0​)​=0 将 f ( x ) f(x) f(x)在 x 0 x_0 x0​处泰勒展开： f ( x ) = f ( x 0 ) + f ′ ( x 0 ) ( x − x 0 ) + 1 2 ! f ′ ′ ( x 0 ) ( x − x 0 ) 2 + o ( ( x − x 0 ) 2 ) f(x)=f(x_0)+f'(x_0)(x-x_0)+\frac{1}{2!}f''(x_0)(x-x_0)^2+o((x-x_0)^2) f(x)=f(x0​)+f′(x0​)(x−x0​)+2!1​f′′(x0​)(x−x0​)2+o((x−x0​)2) 可以从泰勒展开中看出，当 f ′ ( x ) = 0 , f ′ ′ ( x 0 ) > 0 f'(x)=0,f''(x_0)> 0 f′(x)=0,f′′(x0​)>0，在 x 0 x_0 x0​附近必然有 f ( x ) > f ( x 0 ) f(x)>f(x_0) f(x)>f(x0​)成立；当 f ′ ( x ) = 0 , f ′ ′ ( x 0 ) < 0 f'(x)=0,f''(x_0)< 0 f′(x)=0,f′′(x0​)f(x0​)，同时也存在某一点 x \bf x x使得 f ( x ) < f ( x 0 ) f({\bf x})f({\bf x_0}) f(x)>f(x0​)，到达点 x 1 \bf x_1 x1​，然后再选择周围某一个点 x = Δ x + x 1 {\bf x}=\Delta \bf x+ x_1 x=Δx+x1​，继续迭代到满足局部极值条件为止。寻找极小值同理。

这就是梯度下降（上升）法的思想。

梯度下降法

以上迭代具有两个核心问题：①如何选择周围点，也就是如何选择 Δ x \Delta \bf x Δx；②如何判断满足局部极值条件，也是就是什么时候结束迭代。下面以最常见的寻找局部最小为例。

梯度方向

首先讨论问题①，回到多元泰勒展开式： f ( x ) = f ( x 0 ) + ∇ f ( x 0 ) ⋅ ( x − x 0 ) + 1 2 ( x − x 0 ) T H ( x 0 ) ( x − x 0 ) + o n f({\bf x})=f({\bf x_0})+ \nabla f({\bf x_0}) \cdot ({\bf x}-{\bf x_0})+ \frac{1}{2} ({\bf x}-{\bf x_0})^TH({\bf x_0}) ({\bf x}-{\bf x_0}) +o^n f(x)=f(x0​)+∇f(x0​)⋅(x−x0​)+21​(x−x0​)TH(x0​)(x−x0​)+on 梯度 ∇ f ( x 0 ) ≠ 0 \nabla f({\bf x_0}) \ne {\bf 0} ∇f(x0​)​=0。假设我们要寻找的 Δ x \Delta \bf x Δx的长度固定，则每次迭代的函数增量为： Δ f = f ( x ) − f ( x 0 ) = ∇ f ( x 0 ) ⋅ ( Δ x ) + o n \Delta f=f({\bf x})-f({\bf x_0})=\nabla f({\bf x_0}) \cdot (\Delta \bf x)+o^n Δf=f(x)−f(x0​)=∇f(x0​)⋅(Δx)+on 等式右边是一个内积，可以简化表示为： g x 0 = ∇ f ( x 0 ) e Δ x = Δ x Δ f = f ( x ) − f ( x 0 ) = g x 0 ⋅ e Δ x = ∣ g x 0 ∣ ∣ e Δ x ∣ cos ⁡ θ g_{\bf x_0}=\nabla f({\bf x_0}) \\ e_{\Delta \bf x} = {\Delta \bf x} \\ \Delta f=f({\bf x})-f({\bf x_0}) = g_{\bf x_0} \cdot e_{\Delta \bf x}=|g_{\bf x_0}||e_{\Delta \bf x}|\cos \theta gx0​​=∇f(x0​)eΔx​=ΔxΔf=f(x)−f(x0​)=gx0​​⋅eΔx​=∣gx0​​∣∣eΔx​∣cosθ 其中， cos ⁡ θ \cos \theta cosθ是梯度向量 ∇ f ( x 0 ) \nabla f(\bf x_0) ∇f(x0​)与 Δ x \Delta \bf x Δx的夹角。 θ = 0 \theta=0 θ=0， Δ f > 0 \Delta f>0 Δf>0并且取最大值； θ = π \theta=\pi θ=π， Δ f < 0 \Delta f