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。