梯度方法
梯度下降法——一阶优化方法，用于求解无约束最优化问题。选取适当的初始值
x
(
0
)
x^{(0)}
x
(
0
)
，并不断向负梯度方向迭代更新
x
x
x
，实现目标函数的极小化，直到收敛。
当目标函数是凸函数的时候，梯度下降法可以确保找到全局最优解，否则不一定能找到全局最优解，可能会陷入局部最优解。
梯度下降法原理
考虑最优化问题
min
x
f
(
x
)
\min \limits_{x}f(x)
x
min
f
(
x
)
，其中
f
(
x
)
f(x)
f
(
x
)
具有一阶连续偏导数。若第
k
k
k
次迭代值为
x
(
k
)
x^{(k)}
x
(
k
)
，对
f
(
x
)
f(x)
f
(
x
)
在
x
(
k
)
x^{(k)}
x
(
k
)
处进行一阶泰勒展开：
f
(
x
(
k
+
1
)
)
=
f
(
x
(
k
)
)
+
(
x
(
k
+
1
)
−
x
(
k
)
)
∇
f
(
x
(
k
)
)
f(x^{(k+1)})=f(x^{(k)})+(x^{(k+1)}-x^{(k)})\nabla f(x^{(k)})
f
(
x
(
k
+
1
)
)
=
f
(
x
(
k
)
)
+
(
x
(
k
+
1
)
−
x
(
k
)
)
∇
f
(
x
(
k
)
)
其中，
x
(
k
+
1
)
−
x
(
k
)
x^{(k+1)}-x^{(k)}
x
(
k
+
1
)
−
x
(
k
)
是微笑矢量，大小是步长
α
\alpha
α
，
x
(
k
+
1
)
−
x
(
k
)
x^{(k+1)}-x^{(k)}
x
(
k
+
1
)
−
x
(
k
)
的单位向量用
v
v
v
表示，则
x
(
k
+
1
)
−
x
(
k
)
x^{(k+1)}-x^{(k)}
x
(
k
+
1
)
−
x
(
k
)
可以表示为：
x
(
k
+
1
)
−
x
(
k
)
=
α
v
x^{(k+1)}-x^{(k)}=\alpha v
x
(
k
+
1
)
−
x
(
k
)
=
α
v
(1)式可表示为：
f
(
x
(
k
+
1
)
)
=
f
(
x
(
k
)
)
+
α
v
∇
f
(
x
(
k
)
)
f(x^{(k+1)})=f(x^{(k)})+\alpha v\nabla f(x^{(k)})
f
(
x
(
k
+
1
)
)
=
f
(
x
(
k
)
)
+
α
v
∇
f
(
x
(
k
)
)
每次迭代，都要使
f
(
x
(
k
+
1
)
)
f(x^{(k+1)})
f
(
x
(
k
+
1
)
)
变小，当
v
v
v
与
∇
f
(
x
(
k
)
)
\nabla f(x^{(k)})
∇
f
(
x
(
k
)
)
反向时，可使下降最快，故迭代公式可化为：
x
(
k
+
1
)
=
x
(
k
)
−
α
∇
f
(
x
(
k
)
)
x^{(k+1)}=x^{(k)}-\alpha \nabla f(x^{(k)})
x
(
k
+
1
)
=
x
(
k
)
−
α
∇
f
(
x
(
k
)
)
算法过程
输入：目标函数
f
(
x
)
f(x)
f
(
x
)
，梯度函数
∇
f
(
x
)
\nabla f(x)
∇
f
(
x
)
，计算精度
ϵ
\epsilon
ϵ
输出：
f
(
x
)
f(x)
f
(
x
)
的极小点
x
∗
x^*
x
∗
-
初始化相关参数。取初始值
x(
0
)
∈
R
n
x^{(0)}\in R^n
x
(
0
)
∈
R
n
，置迭代次数
k=
0
k=0
k
=
0
； -
计算
x(
0
)
x^{(0)}
x
(
0
)
的梯度
∇f
(
x
(
0
)
)
\nabla f(x^{(0)})
∇
f
(
x
(
0
)
)
； -
确定
x(
0
)
x^{(0)}
x
(
0
)
的步长：
α0
=
a
r
g
min
α
⩾
0
f
(
x
(
0
)
−
α
∇
f
(
x
(
0
)
)
)
\alpha_0=arg \min \limits_ {\alpha \geqslant 0}f(x^{(0)}-\alpha \nabla f(x^{(0)}))
α
0
=
a
r
g
α
⩾
0
min
f
(
x
(
0
)
−
α
∇
f
(
x
(
0
)
)
)
，使用一维搜索方法（割线法）； -
使用式(4)计算迭代点
x(
1
)
x^{(1)}
x
(
1
)
。满足精度要求则停止迭代，否则继续。
最速下降法应用到二次型函数
目标函数为：
f
(
x
)
=
1
2
x
T
Q
x
−
b
T
x
f(x)=\frac{1}{2}x^TQx-b^Tx
f
(
x
)
=
2
1
x
T
Q
x
−
b
T
x
由于
D
(
x
T
Q
x
)
=
x
T
(
Q
+
Q
T
)
=
2
x
T
Q
D(x^TQx)=x^T(Q+Q^T)=2x^TQ
D
(
x
T
Q
x
)
=
x
T
(
Q
+
Q
T
)
=
2
x
T
Q
，
D
(
b
T
x
)
=
b
T
D(b^Tx)=b^T
D
(
b
T
x
)
=
b
T
，得到：
∇
f
(
x
)
=
Q
x
−
b
\nabla f(x)=Qx-b
∇
f
(
x
)
=
Q
x
−
b
为方便起见，记
g
(
k
)
=
∇
f
(
x
(
k
)
)
g^{(k)}=\nabla f(x^{(k)})
g
(
k
)
=
∇
f
(
x
(
k
)
)
，针对二次型函数，最速下降法的迭代公式为：
x
(
k
+
1
)
=
x
(
k
)
−
α
k
g
(
k
)
x^{(k+1)}=x^{(k)}-\alpha_kg^{(k)}
x
(
k
+
1
)
=
x
(
k
)
−
α
k
g
(
k
)
利用局部极小点的一阶必要条件可以得到：
α
k
=
g
(
k
)
T
g
(
k
)
g
(
k
)
T
Q
g
(
k
)
x
(
k
+
1
)
=
x
(
k
)
−
g
(
k
)
T
g
(
k
)
g
(
k
)
T
Q
g
(
k
)
g
(
k
)
g
(
k
)
=
∇
f
(
x
(
k
)
)
=
Q
x
(
k
)
−
b
\alpha_k=\frac{g^{(k)T}g^{(k)}}{g^{(k)T}Qg^{(k)}} \\x^{(k+1)}=x^{(k)}-\frac{g^{(k)T}g^{(k)}}{g^{(k)T}Qg^{(k)}}g^{(k)} \\g^{(k)}=\nabla f(x^{(k)})=Qx^{(k)}-b
α
k
=
g
(
k
)
T
Q
g
(
k
)
g
(
k
)
T
g
(
k
)
x
(
k
+
1
)
=
x
(
k
)
−
g
(
k
)
T
Q
g
(
k
)
g
(
k
)
T
g
(
k
)
g
(
k
)
g
(
k
)
=
∇
f
(
x
(
k
)
)
=
Q
x
(
k
)
−
b
梯度方法收敛性分析
最速下降法和步长固定梯度法。
将目标函数设定为二次函数;
V
(
x
)
=
f
(
x
)
+
1
2
x
∗
T
Q
x
∗
=
1
2
(
x
−
x
∗
)
T
Q
(
x
−
x
∗
)
V(x)=f(x)+\frac{1}{2}x^{*T}Qx^*=\frac{1}{2}(x-x^*)^TQ(x-x^*)
V
(
x
)
=
f
(
x
)
+
2
1
x
∗
T
Q
x
∗
=
2
1
(
x
−
x
∗
)
T
Q
(
x
−
x
∗
)
极小点
x
∗
x^*
x
∗
通过求解方程
Q
x
=
b
Qx=b
Q
x
=
b
得到，
x
∗
=
Q
(
−
1
)
b
x^*=Q^{(-1)}b
x
∗
=
Q
(
−
1
)
b
。
假定对于所有
k
k
k
，都有
γ
k
>
0
\gamma_k>0
γ
k
>
0
。当且仅当：
∑
k
=
0
∞
γ
k
=
∞
\sum_{k=0} ^{\infty}\gamma_k=\infty
k
=
0
∑
∞
γ
k
=
∞
时，
x
(
k
)
x^{(k)}
x
(
k
)
在任何初始值
x
(
0
)
x^{(0)}
x
(
0
)
下都收敛到极小点
x
∗
x^*
x
∗
。
瑞利不等式：
λ
m
i
n
(
Q
)
∣
∣
x
∣
∣
2
⩽
x
T
Q
x
⩽
λ
m
a
x
(
Q
)
∣
∣
x
∣
∣
2
\lambda_{min}(Q)||x||^2\leqslant x^TQx\leqslant \lambda_{max}(Q)||x||^2
λ
m
i
n
(
Q
)
∣
∣
x
∣
∣
2
⩽
x
T
Q
x
⩽
λ
m
a
x
(
Q
)
∣
∣
x
∣
∣
2
最速下降法收敛性定理
对于最速下降法，对于任意的初始点
x
(
0
)
x^{(0)}
x
(
0
)
，都有
x
(
k
)
→
x
∗
x^{(k)}\rightarrow x^*
x
(
k
)
→
x
∗
。（所有的
k
k
k
，均有
γ
k
>
0
\gamma_k>0
γ
k
>
0
）
步长固定梯度法收敛性定理
对于步长固定梯度法，当且仅当步长
0
<
α
<
2
λ
m
a
x
(
Q
)
0<\alpha<\frac{2}{\lambda_{max}(Q)}
0
<
α
<
λ
m
a
x
(
Q
)
2
时，
x
(
k
)
→
x
∗
x^{(k)}\rightarrow x^*
x
(
k
)
→
x
∗
。
收敛率
利用最速下降法求解二次型函数的极小点，在任意第
k
k
k
次迭代，都有：
V
(
x
(
k
+
1
)
)
⩽
λ
m
a
x
(
Q
)
−
λ
m
i
n
(
Q
)
λ
m
a
x
(
Q
)
V
(
x
(
k
)
)
V(x^{(k+1)})\leqslant\frac{\lambda_{max}(Q)-\lambda_{min}(Q)}{\lambda_{max}(Q)}V(x^{(k)})
V
(
x
(
k
+
1
)
)
⩽
λ
m
a
x
(
Q
)
λ
m
a
x
(
Q
)
−
λ
m
i
n
(
Q
)
V
(
x
(
k
)
)
定义
r
=
λ
m
a
x
(
Q
)
λ
m
i
n
(
Q
)
=
∣
∣
Q
∣
∣
∣
∣
Q
−
1
∣
∣
r=\frac{\lambda_{max}(Q)}{\lambda_{min}(Q)}=||Q|| ||Q^{-1}||
r
=
λ
m
i
n
(
Q
)
λ
m
a
x
(
Q
)
=
∣
∣
Q
∣
∣
∣
∣
Q
−
1
∣
∣
为矩阵Q的条件数，故(13)式可表示为：
V
(
x
(
k
+
1
)
)
⩽
(
1
−
1
r
)
V
(
x
(
k
)
)
V(x^{(k+1)})\leqslant(1-\frac{1}{r})V(x^{(k)})
V
(
x
(
k
+
1
)
)
⩽
(
1
−
r
1
)
V
(
x
(
k
)
)
其中
(
1
−
1
r
)
(1-\frac{1}{r})
(
1
−
r
1
)
称为收敛率。
如果
0
<
lim
k
→
∞
∣
∣
x
(
k
+
1
)
−
x
∗
∣
∣
∣
∣
x
(
k
)
−
x
∗
∣
∣
p
<
∞
0<\lim_{k\to \infty}\frac{||x^{(k+1)}-x^*||}{||x^{(k)}-x^*||^p}<\infty
0
<
k
→
∞
lim
∣
∣
x
(
k
)
−
x
∗
∣
∣
p
∣
∣
x
(
k
+
1
)
−
x
∗
∣
∣
<
∞
则序列{
x
(
k
)
x^{(k)}
x
(
k
)
}的收敛阶数为
p
p
p
。
如果对于所有
p
>
0
p>0
p
>
0
，有
lim
k
→
∞
∣
∣
x
(
k
+
1
)
−
x
∗
∣
∣
∣
∣
x
(
k
)
−
x
∗
∣
∣
p
=
0
\lim_{k\to \infty}\frac{||x^{(k+1)}-x^*||}{||x^{(k)}-x^*||^p}=0
k
→
∞
lim
∣
∣
x
(
k
)
−
x
∗
∣
∣
p
∣
∣
x
(
k
+
1
)
−
x
∗
∣
∣
=
0
则称收敛阶数为
∞
\infty
∞
。
序列收敛的阶数是收敛率的评价指标，阶数越高，收敛率越高，收敛速度越快。任意收敛序列的收敛阶数不会小于1.