回顾线搜索方法

线搜索方法作为一种常见优化问题的策略该方法的特点是其迭代过程中将数值解的方向和步长分开执行。

对应数学符号表达如下

\mathcal

f(xk1​)−f(xk​)≈[∇f(xk​)]TPk​⋅αk​0

\mathcal

∣∣∇f(xk​)∣∣,∣∣Pk​∣∣均表示向量的模(均为固定的正值)因而

cos

f(xk1​)−f(xk​)可取得最小值从而达到最佳的优化方向。

而此时下降方向

\mathcal

\mathop{\arg\min}\limits_{\alpha

f(x_{k1})

\mathop{\arg\min}\limits_{\alpha

f(x_k

\mathop{\arg\min}\limits_{\alpha

\phi(\alpha)

αk​​α0argmin​f(xk1​)α0argmin​f(xk​α⋅Pk​)α0argmin​ϕ(α)​

\alpha

∇f(xk​α⋅Pk​)可能非常复杂。

这仅仅是一次迭代步骤的解。

也就是说每次迭代都要求解精确解。

这无疑增加了迭代的计算代价我们仅希望迭代产生的步长能够收敛到

lim

k⇒∞lim​f(xk​)⇒f∗它的中间过程是否准确并不在乎。

\frac{\partial

⎧​​∂α∂ϕ(α)​ϕ′(α)[∇f(xk​α⋅Pk​)]TPk​ϕ′(α)0⇒αk​​​

非精确搜索相比于精确搜索我们不计较迭代产生的步长结果是否最优仅需要该结果能够帮助

f(x_k)

梯度下降法也被称作最速下降法。

这个最速下降方向仅仅是每一个迭代步骤中向量

x_k

xk​所在位置的最速下降方向而不是全局最速下降方向。

这与贪心算法类似是一个局部最优。

如下图:

很明显蓝色实线是指本次迭代步骤中的最优方向;而蓝色虚线是指全局最优方向。

上图描述的是二维权重特征对应的迭代过程。

如果权重特征只有一维特征(一维向量;标量)对应图像表示如下

此时函数关于

∇f(xk​)[f′(xk​)]1×1​,在迭代过程中寻找最优方向时仅存在两个方向进行选择沿着坐标轴与逆着坐标轴(红色箭头)。

而此时

f(x_k)

f′(xk​)0,因而我们将数轴的正方向视作梯度方向对应地将数轴的反方向视作负梯度方向。

针对当前的斜率信息我们沿着负梯度方向更新到

x_{k1}

在后续过程中将介绍梯度下降法中如何求解精确步长以及相应的限制条件。

这里加一个传送门

关于非精确搜索求解步长这里补充一点关于各非精确搜索方法之间的一些逻辑上的关系。

在简单认识

⎧​ϕ(α)f(xk​)C1​⋅[∇f(xk​)]TPk​⋅αC1​∈(0,1)​Wolfe

Condition

⎧​ϕ(α)≤f(xk​)C1​⋅[∇f(xk​)]TPk​⋅αϕ′(α)≥C2​⋅[∇f(xk​)]TPk​C1​∈(0,1)C2​∈(C1​,1)​​

Armijo

\left(\frac{1}{2},1\right)\end{aligned}

C2​∈(21​,1)​使得斜率分别为

\left(0,\frac{1}{2}\right)\end{aligned}

C1​∈(0,21​)​情况下

\begin{aligned}\left(\frac{1}{2},1\right)\end{aligned}

(21​,1)​。

因此必然能够找到这个合适的点从而使该点情况下

Wolfe

关于梯度下降法的收敛速度相比梯度下降法的收敛性我们更关心在已知收敛的情况下它的收敛速度情况。

在上一节中对收敛速度进行了简单认识

\mathcal

∇f(⋅)必然服从利普希兹连续。

而利普希兹连续的作用在于目标函数梯度

\nabla

∇f(⋅)进行约束很容易会出现梯度爆炸。

因为可能存在目标函数梯度可能在某一范围内飙升至极大。

f(\cdot)

∣∣x−y∣∣∣∣∇f(x)−∇f(y)∣∣​∇2f(ξ)​详见拉格朗日中值定理。

\forall

∀x,y∈Rn:∣∣x−y∣∣∣∣∇f(x)−∇f(y)∣∣​∇2f(ξ)≼L⋅I​

相关参考