机器学习笔记之优化算法(七)线搜索方法(步长角度；非精确搜索；Wolfe Condition)-Toy模板网

这篇具有很好参考价值的文章主要介绍了机器学习笔记之优化算法(七)线搜索方法(步长角度；非精确搜索；Wolfe Condition)。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

引言

上一节介绍了 $\text{Glodstein}$ 准则 $(\text{Glodstein Condition})$ 及其弊端。本节将针对该弊端，介绍 $\text{Wolfe}$ 准则 $(\text{Wolfe Condition})$ 。

回顾：

$\text{Armijo}$ 准则及其弊端

在当前迭代步骤中，为了能够得到更精炼的 $\phi(\alpha)$ 选择范围， $\text{Armijo}$ 准则 $(\text{Armijo Condition})$ 提出一种关于 $\phi(\alpha)$ 的筛选方式，使其比 $\phi(\alpha) < f(x_k)$ 更加严格：
$\text{Armijo Condition : } \begin{cases} \phi(\alpha) < \mathcal L(\alpha) = f(x_k) + \mathcal C_1 \cdot [\nabla f(x_k)]^T \mathcal P_k \cdot \alpha \\ \quad \\ \mathcal C_1 \in (0,1) \end{cases}$
这种操作产生的弊端是： $\mathcal C_1$ 在取值过程中，可能出现数量较少的、并且并非 $\phi(\alpha)$ 主要部分的选择空间。见下图：
机器学习笔记之优化算法(七)线搜索方法(步长角度；非精确搜索；Wolfe Condition),机器学习,深度学习,Armijo准则与弊端,Glodstein准则与弊端,线搜索方法非精确搜索,优化方法,Wolfe Condition
这种情况可能导致：
下面的两种情况都指向同一个问题: $\mathcal L(\alpha)$ 所划分的 $\alpha$ 范围从整个 $\phi(\alpha)$ 角度观察，是片面的、局部的。

可选择的 $\alpha$ 范围较小；
该小范围内的 $\alpha$ 结果，其对应的 $\phi(\alpha)$ 并不优质。
这里的‘优质’是指与整个 $\phi(\alpha)$ 函数结果相比都属于一个较小的结果。最优质的自然是 $\alpha^* = \mathop{\arg\min}\limits_{\alpha > 0} \phi(\alpha)$ ,但我们在每次迭代过程中并不执著于 $\alpha^*$ ，仅希望选择出的 $\alpha$ 结果能够有效地使 $\{f(x_{k})\}_{k=0}^{\infty}$ 收敛到最优值 $f^*$ 。

$\text{Glodstein}$ 准则及其弊端

针对 $\text{Armijo}$ 准则的问题， $\text{Glodstein}$ 准则在其基础上添加一个下界：
$\text{Glodstein Condition : } \begin{cases} \begin{aligned} & \underbrace{f(x_k) + (1 - \mathcal C) \cdot [\nabla f(x_k)]^T \mathcal P_k \cdot \alpha}_{\text{Lower Bound}} \leq \phi(\alpha) \leq f(x_k) + \mathcal C \cdot [\nabla f(x_k)]^T \mathcal P_k \cdot \alpha \\ & \mathcal C \in \left(0,\frac{1}{2}\right) \end{aligned} \end{cases}$
其中分别描述上界、下界的划分函数：

$\text{Upper Bound : } \begin{aligned}\mathcal L_{\mathcal U}(\alpha) = f(x_k) + \mathcal C \cdot [\nabla f(x_k)]^T \mathcal P_k \cdot \alpha\end{aligned}$
$\text{Lower Bound : } \mathcal L_{\mathcal L}(\alpha) = f(x_k) + (1 - \mathcal C) \cdot [\nabla f(x_k)]^T \mathcal P_k \cdot \alpha$

关于 $\begin{aligned}f(x_k) + \frac{1}{2} [\nabla f(x_k)]^T \mathcal P_k \cdot \alpha\end{aligned}$ 对称。这能保证满足该范围的 $\alpha$ 结果，其对应的 $\phi(\alpha)$ 总是位于 $\phi(\alpha)$ 的核心部分，而不是片面的、局部的部分。见下图：
其中两条绿色实线之间区域内的 $\phi(\alpha)$ 结果相比 $\text{Armijo}$ 准则，其描述的范围更加核心。
机器学习笔记之优化算法(七)线搜索方法(步长角度；非精确搜索；Wolfe Condition),机器学习,深度学习,Armijo准则与弊端,Glodstein准则与弊端,线搜索方法非精确搜索,优化方法,Wolfe Condition
但 $\text{Goldstein}$ 准则自身同样存在弊端：当参数 $\mathcal C$ 靠近 $\begin{aligned}\frac{1}{2}\end{aligned}$ 时，对应上下界包含的 $\phi(\alpha)$ 结果极少。从而可能使一些优质 $\alpha$ 结果丢失。见下图：
机器学习笔记之优化算法(七)线搜索方法(步长角度；非精确搜索；Wolfe Condition),机器学习,深度学习,Armijo准则与弊端,Glodstein准则与弊端,线搜索方法非精确搜索,优化方法,Wolfe Condition

Wolfe Condition \text{Wolfe Condition} Wolfe Condition

首先，我们可以发现一个关于 $\text{Armijo}$ 准则与 $\text{Goldstein}$ 准则的共同问题：被选择的仅仅是满足划分边界条件的 $\alpha$ 结果，而被选择的 $\alpha$ 结果是否存在被选择的意义是未知的。
换句话说，基于这两种准则选择出的 $\alpha$ 结果仅仅是因为：

该 $\alpha$ 对应的 $\phi(\alpha)$ 位于决策边界 $\mathcal L(\alpha) = f(x_k) + \mathcal C_1 \cdot [\nabla f(x_k)]^T \mathcal P_k \cdot \alpha$ 的下方 $(\text{Armijo Condition})$ ;
该 $\alpha$ 对应的 $\phi(\alpha)$ 位于上决策边界 $\mathcal L_{\mathcal U}(\alpha)$ 与下决策边界 $\mathcal L_{\mathcal L}(\alpha)$ 所围成的范围之间 $(\text{Glodstein Condition})$ 。

这意味着：我们确实得到了若干 $\alpha$ 结果，但是这些结果是否优质属于未知状态。

我们尝试从满足 $\text{Armijo}$ 准则的基础上，通过某种规则剔除掉部分没有竞争力的 $\alpha$ 结果，从而在剩余结果中找到优质的 $\alpha$ 结果。见下图：
机器学习笔记之优化算法(七)线搜索方法(步长角度；非精确搜索；Wolfe Condition),机器学习,深度学习,Armijo准则与弊端,Glodstein准则与弊端,线搜索方法非精确搜索,优化方法,Wolfe Condition
初始状态下，我们找到了一个 $\mathcal C_1 \in (0,1)$ ，并描述出了它的划分边界 $\mathcal L(\alpha)$ ；由于 $\mathcal L(\alpha)$ 的斜率 $\mathcal C_1 \cdot [\nabla f(x_k)]^T \mathcal P_k$ 必然大于 $l(\alpha)$ 的斜率 $[\nabla f(x_k)]^T \mathcal P_k$ ，因此从 $\alpha = 0$ 出发，找到切线斜率与 $\mathcal L(\alpha)$ 斜率相同的点：
下图中的绿色虚线表示切线斜率与 $\mathcal L(\alpha)$ 斜率相同的 $\alpha$ 点，短绿线表示寻找过程，点 $\mathcal A$ 表示满足条件的切点。
机器学习笔记之优化算法(七)线搜索方法(步长角度；非精确搜索；Wolfe Condition),机器学习,深度学习,Armijo准则与弊端,Glodstein准则与弊端,线搜索方法非精确搜索,优化方法,Wolfe Condition
通过观察可以发现：点 $\mathcal A$ 必然不是极值点(虽然看起来有点像~)，因为该点处的斜率 $\neq 0$ 。这里能够确定：从 $0,f(x_k)]$ 到 $\mathcal A$ 点这一段函数内的所有点相比于 $\mathcal A$ 都没有竞争力。而这些点的切线斜率 $\phi'(\alpha)$ 满足：
$[\nabla f(x_k)]^T \mathcal P_k \leq \phi'(\alpha) \leq \mathcal C_1 \cdot [\nabla f(x_k)]^T \mathcal P_k$

关于仅与参数 $\mathcal C_1$ 相关的武断做法

如果将这些没有竞争力的点去除掉，保留剩余的点，结合 $\text{Armijo}$ 准则，会有如下的步长 $\alpha$ 选择方式：

其中 $\begin{aligned}\phi'(\alpha) = \frac{\partial f(x_k + \alpha \cdot \mathcal P_k)}{\partial \alpha} = [\nabla f(x_k + \alpha \cdot \mathcal P_k)]^T \mathcal P_k\end{aligned}$ ,在后续的计算中均简化写作 $\phi'(\alpha)$ 。
关于斜率 $\phi'(\alpha)\leq \mathcal C_1 \cdot [\nabla f(x_k)]^T \mathcal P_k$ 点不再理会，而 $[\nabla f(x_k)]^T \mathcal P_k$ 是 $\phi(0)$ 的斜率，作为下界。
$\begin{cases} \phi(\alpha) \leq f(x_k) + \mathcal C_1 \cdot [\nabla f(x_k)]^T \mathcal P_k \cdot \alpha \\ \phi'(\alpha) \geq \mathcal C_1 \cdot [\nabla f(x_{k})]^T \mathcal P_k \\ \mathcal C_1 \in (0,1) \end{cases}$

基于上述逻辑，被选择的 $\phi(\alpha)$ 见下图：
其中 $\mathcal A'$ 点表示该图像中斜率与 $\mathcal L(\alpha)$ 相同的其他位置的点。
机器学习笔记之优化算法(七)线搜索方法(步长角度；非精确搜索；Wolfe Condition),机器学习,深度学习,Armijo准则与弊端,Glodstein准则与弊端,线搜索方法非精确搜索,优化方法,Wolfe Condition

上述这种方式可取吗 $?$ 从逻辑角度上是可行的，但不可取。

关于 $\mathcal C_1$ 武断做法不可取的逻辑解释

由于 $\mathcal C_1 \in (0,1)$ ，因而 $\mathcal C_1 \cdot [\nabla f(x_k)]^T \mathcal P_k < 0$ 恒成立。也就是说：无论 $\mathcal C_1$ 如何趋近于 $0$ ， $\text{Armijo}$ 准则划分边界 $\mathcal L(\alpha)$ 如何趋近于 $\phi(\alpha) = f(x_k)$ ，都无法获取使 $\phi'(\alpha) = 0$ 的极值解。
很简单，就是因为取不到~

而与此同时，我们为了追求这个极值解，可能反而会损失一系列 $\phi(\alpha)$ 优质的 $\alpha$ 点。
如果仅使用 $\mathcal C_1$ 一个参数，那么要去除的点在 $\text{Armijo}$ 准则划分边界 $\mathcal L(\alpha)$ 确定的那一刻就已经被确定了，这势必会误伤一些 $\phi(\alpha)$ 优质的 $\alpha$ 结果。
其次，这里的操作是非精确搜索，因而不执著去追求极值解(那不就变成精确搜索了吗~)，并且这仅仅是一次迭代的计算过程，没有必要消耗计算代价去追求更优质的 $\phi(\alpha)$ ，这也是我们希望尽量保留 $\phi(\alpha)$ 优质解的核心原因：
与上一张图被选择的 $\phi(\alpha)$ 值对比观察，红色椭圆形虚线区域中描述的 $\phi(\alpha)$ 值是比较优质的，但因为 $\mathcal C_1$ 的原因导致该部分结果被‘一刀切’了。这并不是我们希望看到的结果。

关于 $\mathcal C_1$ 武断做法的改进： $\text{Wolfe Condition}$

如何避免上述一刀切的情况出现 $?$ $\text{Wolfe}$ 准则提供了而一种更软性的操作。

设置一个参数 $\mathcal C_2 \in (\mathcal C_1,1)$ ，该参数对应的斜率表示为 $\mathcal C_2 \cdot [\nabla f(x_k)]^T \mathcal P_k$ ，而该斜率在 $([\nabla f(x_k)]^T \mathcal P_k,\mathcal C_1 \cdot [\nabla f(x_k)]^T \mathcal P_k )$ 之间滑动(变换)。此时会出现一种缓和的情况：即便假设 $\mathcal C_1$ 无限接近于 $0$ ，但由于 $\mathcal C_2$ 的作用，使 $\phi(\alpha)$ 点的选择与 $\mathcal C_1$ 没有太大关联：

这里相当于将斜率 $\mathcal C_1 \cdot [\nabla f(x_k)]^T \mathcal P_k$ 视作一个边界。
上面的一刀切情况相当于 $\mathcal C_1 \Rightarrow 0$ 的同时， $\mathcal C_2 \Rightarrow\mathcal C_1$ 的情况。
由于 $\mathcal C_2 \in (\mathcal C_1,1)$ 因而完全可以通过调整 $\mathcal C_2$ 针对那些斜率小于 $\mathcal C_1 \cdot [\nabla f(x_k)]^T \mathcal P_k$ ，但 $\phi(\alpha)$ 优质的结果进行酌情选择。

最终根据 $\text{Armijo}$ 准则， $\text{Wolfe}$ 准则操作如下：
$\begin{cases} \phi(\alpha) \leq f(x_k) + \mathcal C_1 [\nabla f(x_k)]^T \mathcal P_k \cdot \alpha \\ \phi'(\alpha) \geq \mathcal C_2 \cdot [\nabla f(x_k)]^T \mathcal P_k \\ \mathcal C_1 \in (0,1) \\ \mathcal C_2 \in (\mathcal C_1,1) \end{cases}$

个人理解： Wolfe \text{Wolfe} Wolfe准则与 Armijo \text{Armijo} Armijo准则

在开头部分提到关于 $\text{Armijio}$ 准则的弊端，在介绍完 $\text{Wolfe}$ 准则之后，有种 $\text{Armijo}$ 准则的弊端卷土重来的感觉。个人认为： $\text{Wolfe}$ 准则提出的这种基于 $\mathcal C_2 \in (\mathcal C_1,1)$ 的软性下界同样也在影响 $\mathcal C_1$ 的选择：

如果是单纯的 $\text{Armijo}$ 准则，我们可能更偏好 $\mathcal C_1$ 远离 $0$ 一些。因为 $\mathcal C_1 \Rightarrow 0$ 意味着这种状态越趋近优化算法(四)中描述的必要不充分条件；这种 $\mathcal C_1$ 的选择方式也势必会增加 $\text{Armijo}$ 准则弊端的风险；
而 $\text{Wolfe}$ 准则中，即便 $\mathcal C_1$ 偏向 $0$ 方向，我们依然可以通过调整 $\mathcal C_2$ 对相对不优质的 $\phi(\alpha)$ 点进行过滤。从剩余的优质点中选择并进行迭代。