数值计算之 梯度下降法与函数极值
- 前言
- 微积分基础
- 一元函数的极值，导数与泰勒展开
- 多元函数的泰勒展开
- 梯度下降法
- 梯度方向
- 终止条件
- 代码举例
- 后记
前言
本篇将开始介绍优化算法。首先是梯度下降法，在最小二乘与深度学习中，都是最常用的最优化求解方法和思想。
微积分基础
一元函数的极值，导数与泰勒展开
对于一元函数
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!1f′′(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
