梯度方法
# 0x1.梯度方法
# 1.回顾水平集
水平集概念:
$𝐿_𝑐={𝒙:𝑓(𝒙)=𝑐,𝒙∈ℝ^𝑛}$
如下图所示元素:
𝐿~𝑐~中点𝒙处的梯度𝛻𝑓(𝒙)与𝐿~𝑐~中过𝒙的曲线在𝒙处的切线正交。
梯度方向𝛻𝑓(𝑥)就是==函数𝑓在𝒙处增加最快的方向==。
$\frac{𝜕𝑓}{𝜕𝑑} (𝑥)=<𝛻𝑓(𝑥),𝑑>$
基于梯度方法的迭代搜索公式:
$𝑥^{(𝑘+1)}=𝑥^{(𝑘)}−𝑎_𝑘 𝛻𝑓(𝑥^{(𝑘)})$
# 0x2.最速下降法
最速下降法是==梯度方法的一种具体体现==,其理念为再每次迭代中选择合适的步长a~k~,使得目标函数值能够得到最大程度的减小。而普通的梯度方法是步长固定的或者不确定的。
迭代公式:
$𝑥^{(𝑘+1)}=𝑥^{(𝑘)}−𝑎_𝑘 𝛻𝑓(𝑥^{(𝑘)})$
$𝑎_𝑘={arg\ min\atop {𝑎≥0}}𝑓(𝑥^{(𝑘)}−𝑎𝛻𝑓(𝑥^{(𝑘)} ))$
解释:
x代表一个点,即(0,0,0)等坐标源点到x的向量。
每次都会以上一个下降向量为基准,正交得到下一次的下降向量,并尝试得到可以最大减小函数值的步长,最后形成“锯齿状”的搜索路径。
终止条件:
例子:
# 1.命题8.1(相邻向量垂直)
利用最速下降法搜索函数𝑓:ℝ^𝑛^→ℝ的极小点,迭代过程产生的序列为{𝑥^(𝑘)^}~𝑘=0~^∞^ 。那么𝑥^(𝑘+1)^−𝑥^(𝑘)^与𝑥^(𝑘+2)^−𝑥^(𝑘+1)^正交对于所有的𝑘≥0都成立。
即:每次迭代寻找极小值的方向向量都是依次正交的。
证明:
说明:上述$φ_k(a_k)=𝑓(𝑥^{(𝑘)}−𝑎_k𝛻𝑓(𝑥^{(𝑘)} ))$
# 2.命题8.2(函数值单调递减)
利用最速下降法搜索函数𝑓:ℝ^𝑛^→ℝ的极小点,迭代过程产生的序列为{𝑥^(𝑘)^}~𝑘=0~^∞^ 。如果𝛻𝑓(𝑥^(𝑘)^)≠0,那么𝑓(𝑥^(𝑘+1)^)<𝑓(𝑥^(𝑘)^)
即:每次迭代寻找极小值后得到的函数值都是小于上一个点函数值,即搜索序列单调递减。
证明:
# 0x3.梯度方法性质分析
目标函数设定为二次型函数 $$ \begin{align*} 𝑉(𝒙)&=𝑓(𝒙)+\frac12𝒙^{∗⊺} 𝑄𝒙^∗ \ &=\frac12(𝒙−𝒙^∗)^⊺ 𝑄(𝒙−𝒙^∗) \end{align*} $$ 其中𝑄是对称正定矩阵。
# 1-1.引理8.1
# 1-2.定理8.1(x必收敛至极小点)
定理8.1
{𝒙^(𝑘)^}表示梯度方法产生迭代点序列, 𝒙^(𝑘+1)^=𝒙^(𝑘)^−𝑎~𝑘~ 𝒈^(𝑘)^。𝛾~𝑘~按照引理8.1里的方式定义,且假定对于所有𝑘, 𝛾~𝑘~>0。那么当且仅当 $$ ∑_{𝑘=0}^\infty𝛾_𝑘=\infty $$ 时, {𝒙^(𝑘)^}在任意初始值𝒙^(0)^下都收敛到极小点𝒙^∗^。
# 2-1.引理8.2
# 2-2.定理8.2(最速任意均收敛)
对于最速下降法,对于任意的初始点𝑥^(0)^,都有𝑥^(𝑘)^→𝑥^∗^。
# 3.定理8.3
对于步长固定梯度法,当且仅当 $$ 0<𝑎<\frac2{𝜆_{𝑚𝑎𝑥} (𝑄)} $$ 时, 𝑥^(𝑘)^→𝑥^∗^。
# 4.定理8.4
利用最速下降法求解二次型函数的极小点,在任意第𝑘次迭代,都有 $$ 𝑉(𝑥^{(𝑘+1)})≤\frac{𝜆_{𝑚𝑎𝑥} (𝑄)−𝜆_{𝑚𝑖𝑛} (𝑄)}{𝜆_{𝑚𝑎𝑥} (𝑄) } 𝑉(𝑥^{(𝑘)} ) $$ $𝑟=\frac{𝜆_{𝑚𝑎𝑥} (𝑄)}{𝜆_{𝑚𝑖𝑛} (𝑄) }=\big||𝑄|\big|||𝑄^{−1} ||$称为矩阵𝑄的条件数。 $$ 𝑉(𝑥^{(𝑘+1)} )≤(1−\frac{1}{𝑟})𝑉(𝑥^{(𝑘)} ) $$ 因子(1−1/𝑟)称为==收敛率==。
# 5.定理8.5
已知序列{𝑥^(𝑘)^}收敛到𝑥^∗^,如果
‖𝒙^(𝑘+1)^−𝒙^∗^ ‖=𝑂(‖𝒙^(𝑘)^−𝒙^∗^ ‖^𝑝^)
那么,序列的收敛阶数(如果存在)至少为𝑝。
# 6.引理8.3
对于最速下降法而言,如果对于所有𝑘,𝒈^(𝑘)^≠0,那么当且仅当𝒈^(𝑘)^是矩阵𝑄的一个特征向量时,𝛾~𝑘~=1。
# 7.定理8.6
最速下降法在求解目标函数𝑓的极小点时,产生一个收敛的迭代点序列{𝒙^(𝑘)^},该序列在最坏的情况下收敛阶数为1。也就是说存在一个目标函数𝑓和某个点𝒙^(0)^,能够使得{𝒙^(𝑘)^}的收敛阶数为1。