数值优化（2）——线搜索：步长选取条件的收敛性

学弱猹

发布于 2021-08-09 16:32:48

9570

发布于 2021-08-09 16:32:48

文章被收录于专栏：学弱猹的精品小屋学弱猹的精品小屋

上一节笔记传送门：数值优化（1）——引入，线搜索：步长选取条件

————————————————————————————————————

大家好！

在上一节，我们简单的介绍了数值优化中线搜索方法的思想和步长条件。那么这一节，我们更多的开始关注这些步长条件的理论性质，学优化最忌知其然，不知其所以然，所以我们需要我们帮助我们理解为什么给定的步长条件可以导出的一些好的，有助于优化的收敛性。

那么我们开始吧。

线搜索的全局收敛性

我们在上一节有简单说明各种步长选取条件和它们的来源思想。事实上，上一节的几个反例也说明了，如果我们不能够很好的选取步长，那么最后的收敛结果就不会是驻点所在的位置，这不是我们希望看到的。也是因为这个，我们需要保证我们的步长具有全局收敛性。换句话说，我们希望我们的优化方法，在给定步长条件下，能够收敛到驻点，这就够了。要说明这件事并不容易，我们会接触到大量的性质和定理。

理论好用的B-N条件

在说明这一件事之前，我们先要关心的是步长的存在性。存在即合理，不存在就啥也不是。

还有一个条件在哪里呢？还记得我们如何图解Wolfe条件的吗？我们再把这张图放出来

首先我们画出了A-G条件的范围，然后我们将

l(\alpha)

那条直线平移了下来，平移到与曲线相切的地方，之后的部分就是可以采用的步长。所以你也许你看出来了，我们要找的自然是那条切线，对应的就是数分一中提到的中值定理。

注意到

f \in C^1

也就是说

h \in C^1

所以我们有

h(\alpha') - h(0) = \alpha' h'(\tilde \alpha), \tilde \alpha \in (0, \alpha')

这样的话，我们联立两个式子，就可以得到

h'(\tilde \alpha) = c_1 h'(0) > c_2 h'(0)

注意

h'(0) < 0, c_1 < c_2

所以

\tilde \alpha

就是可接受的步长，这就证明了结论。

有的人可能发现了我们只是在说明弱Wolfe条件，但是强Wolfe条件其实只需要把那个式子两边取绝对值即可。因为

h'(0) < 0

所以不等式变号，所以我们就证明了结论。

好的，我们现在已经证明了步长的存在性，是不是可以证明全局收敛性了呢？不好意思，依然不行。这是因为我们的条件虽然已经足够让我们进行实操，但是我们的这两个条件在理论上不是很好用。为了弥补这个缺陷我们又提出了一个理论上好用的步长选取条件。

这里要注意的是，式子右边是与α无关的。也就是说它在证明中会给我们带来一定的普适性。我们之后会说明这个会导致什么不同。

我们说它“理论上好用”，意思是说我们会希望通过它来证明我们想得到的全局收敛性。也就是说，我们只是把它当作一个工具，而实战中我们还是使用A-G或者Wolfe条件。有的人会问，实战和理论使用的不是一套工具，不会出问题吗？答案确实是不会。这就是我们接下来要说明的事情。

我们证明一下这个结论。这里要注意的是，因为B-N条件式子的右边是与α无关的，所以我们要说明对于A-G条件的任何可能的步长选取情况，都能够推出B-N条件，才算完成证明。因此我们要通过考察每一步使用A-G条件进行迭代的实际情况来给出我们的证明。

首先我们要考虑一下迭代的初始步长。我们在上一节有说，对于A-G条件，步长会先从1开始，然后每一步做一个缩小。所以我们先考虑α=1的情况。在这个情况下，对应的不等式为

h(\alpha) \le l(\alpha) = h(0) + c_1 h'(0)

也就是说只要取

\chi_2 = c_1

即可说明B-N条件的第二个不等式满足。现在只需要考虑迭代的“中间步骤”即可。

注意到我们A-G条件的步长存在性证明（Theorem 1）说，任何一个

\alpha \in (0, \alpha')

都满足Armijo条件的（注意，不是A-G条件），但是我们要注意的是，A-G条件中要求了步长是一串序列中最大的那个（具体可以参考上一节）。所以换句话说，这个满足条件的α“回退”一步就不满足条件了。也就是说，一定存在一个

\tau < 1

使得

\frac \alpha \tau

这个步长是不满足条件的。所以这样我们就得到了两个式子

h(\alpha) \le h(0) + c_1 \alpha h'(0)

h(\dfrac \alpha \tau ) > h(0) + c_1 \dfrac \alpha \tau h'(0)

这样的话，我们对第二个式子考虑中值定理，容易得到

c_1 \alpha h'(0) < \alpha h'(\tilde \alpha), \tilde \alpha \in [0, \dfrac \alpha\tau]

注意到

h(\alpha) = f(x + \alpha p)

所以

h'(\alpha) = p^T\nabla f(x + \alpha p)

（数分三里讲到的多元函数求导链式法则）。因此我们左右两边约去α，再合并同类项，可以得到

(\nabla f(x + \tilde \alpha p) - \nabla f(x))^T p > (c_ 1 - 1)\nabla f(x)^T p

现在再看一下左边，事实上根据Cauchy不等式，容易得到

x^T y \le \|x\|\|y\|

因此

(\nabla f(x + \tilde \alpha p) - \nabla f(x))^T p \le L \tilde \alpha \|p\| \cdot \|p\| \le L \dfrac{\alpha}{\tau} \|p\|^2

（注意Lipschitz连续）

组合一下，这个时候我们就得到了一个不等式

\alpha > \dfrac{\tau(c_1 - 1)}{L}\dfrac{\nabla f(x)^T p}{\|p\|^2} = \dfrac{\tau(c_1 - 1)}{L}\dfrac{h'(0)}{\|p\|^2}

这个时候，我们只需要左右两边乘上

h'(0)

再代入A-G条件即可，你可以看出这个时候满足的是B-N条件的第一个式子，并且

\chi_1 = \frac{\tau(1- c_1)}{L}

这个证明是比较复杂的，这是因为我们要考虑到步长选取的任何一个情况，因此我们要假设存在一个满足条件的步长和一个不满足条件的步长，而不能够对步长本身施加任何的假设。而且要注意的问题是，对于初始步长的情况，初识步长的“前一步步长”是否是可接受的，实际上是未知的，因此不能够直接套用之后那一部分的证明。但是你也能看出来，这个式子就说明了，如果我们的导函数性质足够好（因为LIpschitz连续是一个很强的条件），是足够推出B-N条件的。为了使得B-N条件的普适性得以使用，我们确实花了不少功夫。

接下来我们来看看Wolfe条件的情况。

我们证明一下这个结论。还是那句话，Wolfe条件是A-G条件的加强，因此我们只需要对上面的证明稍作修改即可。

首先我们先考虑弱Wolfe条件，注意到弱Wolfe条件的第二个不等式

h'(\alpha) \ge c_2 h'(0)

所以采用相同的方法，就可以得到式子

(\nabla f(x + \alpha p) - \nabla f(x))^T p \ge (c_2 - 1)\nabla f(x)^T p

看到这个式子之后，直接再左边利用Cauchy不等式和LIpschitz条件，再将α的不等式代入Armijo条件（Wolfe条件的第一个不等式），就可以得到B-N条件的第一个式子满足，并且这个时候

\chi_1 = c_1 \frac {1- c_2}{L}

因此结论证完。

为什么不需要再考虑强Wolfe条件了呢？这是因为我们可以通过它的第二个式子来推出

h'(\alpha) \ge c_2 h'(0)

因此我们也可以说明结论成立了。

到此，我们算是结束了我们的推导，也就是说到目前为止，我们已经证明了我们的两个实际可用的步长选取条件可以推导出理论上好用的B-N条件。

联系步长与搜索方向的Zoutendijk条件

还是那句话，我们最终的目标，是希望我们的函数值能够收敛到一个驻点。换句话说我们希望我们的步长和搜索方向足够的好，使得我们的

\|\nabla f(x_k)\|

能够尽量趋于0。这就是我们这一部分要说明的Zoutendijk条件。

我们证明一下这个结论。

首先要观察到究竟这个求和式的每一项应该如何使用。可以看出来

p_k^T \nabla f(x_k)

就是第k步的时候的对应构造函数

h(\cdot)

的导数，也就是

h_k'(0)

因此我们有理由相信，

\cos^2 \theta_k \|\nabla f(x_k)\|^2 = \frac{h_k^{'2}(0)}{\|p\|^2}

这就对应上了B-N条件。而B-N条件的左边是两个函数的差

h(\alpha) - h(0)

这个是什么？就是上一步与下一步的函数差值。如果函数是有下界的，那么函数差值的和有可能为无穷的吗？因此我们的证明自然会想到构造函数差值。

假如说我们现在迭代走到了第k+1步，并设第k步的迭代自变量值为

x_k

这个时候有

\infty > f(x_0) - f(x_{k+1}) = \sum_{i=0}^k[f(x_i) - f(x_{i+1})] = \sum_{i=0}^k[h_i(0) - h_i(\alpha_i)]

注意我们的迭代步骤为

x_{k+1} = x_k + \alpha_k p_k

这样的话，考虑使用B-N条件，有

\sum_{i=0}^k[h_i(0) - h_i(\alpha_i)] \ge \sum_{i=0}^k \min (\chi_1 \frac{[h_i{'}(0)]^2}{\|p_i\|^2}, -\chi_2 h'(0))

= \sum_{i=0}^k \min(\chi_1 \cos^2 \theta_i |\nabla f(x_i)|^2, \chi_2 |\nabla f(x_i)| |p_i| \cos \theta_i)

\ge \sum_{i=0}^k \min(\chi_1 , \chi_2\mu) |\nabla f(x_i)|^2 \cos^2 \theta_i

注意最后一步的时候我们不仅用了条件，还多乘了一个

\cos(\theta_i)

有了这个式子之后，我们可以发现，令

k \to \infty

就可以得到说右边的式子是有限的，否则就会产生矛盾。因此结论成立。

其实Zoutendijk条件多加了一个条件，就是

\|p_k\| \ge \mu \|\nabla f(x_k)\|

我们其实可以发现，如果是Wolfe条件，那么因为我们全程不会推到B-N条件的第二个式子，所以这个条件是不需要的。同样的，这个条件也可以告诉我们，搜索方向的模长是有用的。换句话说，我们的迭代过程是不允许对搜索方向的模长标准化的。这个可能是一个很多人觉得奇怪的结论，但是其实直观想一下，如果一个方法只修改步长，那么可能还没什么问题。但是如果同时添加了方向的标准化约束，对于修改方向的算法而言是致命的打击。

全局收敛性的证明

有了这个Zoutendijk条件之后，其实我们下一步要考虑的就是如何利用Zoutendijk条件告诉我们的信息，来推出全局收敛性。

如果这个矩阵是往正交补空间的投影，那么它就必须落在

\operatorname{span}(a)

的核空间（零空间）。通俗一点来说就是

Qa = 0

但是这个很容易验证，所以我们就不再详细说了。

在这个题目中，

Q = I - \dfrac{\nabla f(x) p ^T}{p^T \nabla f(x)}

所以你可以看出，如果一个矩阵补足了核空间，另外一个矩阵补足了像空间，那么自然的这个矩阵就应该是满秩的了。这就相当于某一个点的坐标是

(a_1,\cdots, a_n)

然后一个矩阵把它投到了像空间对应的维度

(a_1, \cdots, a_t)

另一个矩阵把它投到了核空间对应的维度

(a_{t+1}, \cdots , a_n)

那么拼到一起，每一个分量上都有非零元素，自然可以联想到矩阵是满秩的结论。

现在还差最后一步就是对称。单纯设

H = P + Q

并不足够，因为

并没有对称性。但是这个问题不是很大，因为没有对称性的话，左边再乘一个对偶的矩阵即可。也就是说我们修改

为

Q = (I - \dfrac{p\nabla f(x)^T}{p^T \nabla f(x)})(I - \dfrac{\nabla f(x) p ^T}{p^T \nabla f(x)})

设

H = P + Q

我们就找到了这个

我们用一张图来进行几何解释。

为了让大家信服，我们最后再把证明写一遍。

Lemma 3:

H = (I - \dfrac{p\nabla f(x)^T}{p^T \nabla f(x)})(I - \dfrac{\nabla f(x) p ^T}{p^T \nabla f(x)}) - \dfrac{pp^T}{p^T \nabla f(x)}

是一个对称正定的矩阵。

如果我们设

-\frac 1{p^T\nabla f(x) }= a^2

的话，那么可以得到

H = (I + a^2 p \nabla f(x)^T)(I + a^2 \nabla f(x) p ^T) + a^2 p p^T

=\begin{bmatrix}I + a^2 p \nabla f(x)^T & ap\end{bmatrix}\begin{bmatrix}I + a^2 \nabla f(x)p^T \\ap^T\end{bmatrix}

=\begin{bmatrix}I + a^2 p \nabla f(x)^T & ap\end{bmatrix}\begin{bmatrix}I & a \nabla f(x)\\ & 1\end{bmatrix}\begin{bmatrix}I \\ ap^T\end{bmatrix}

如果我们设

的维度为

，那么可以得到

实际上就是三个矩阵的乘积，并且第一个矩阵是行满秩的，第三个矩阵列满秩，而第二个矩阵是满秩的方阵。这就可以得到

是满秩的，结合上

可以写成

X^TX

（推导

的第二步）的形式，所以就可以得到矩阵正定的结论。

这里有一个要注意的地方，就是实对称矩阵不一定正定，一定要把能够把它拆成

H = X^TX

的形式才可以。

到此，我们终于说明好了这个结论，这也可以算是对于矩阵论一些性质的复习。

到此，其实我们已经明晰：只要我们给定一个系列的

，就可以构造出一系列的下降方向。因此我们可以考虑把我们之前提到的最速下降法做一个推广，就可以得到我们真正意义上的线搜索算法，如下图所示。

而且我们已经做了那么多的准备工作，如果不能够证明全局收敛性，也不可能直接把算法放出来，对吧？

Theorem 5: 考虑线搜索算法，如果存在常数

M_1, M_2

使得

\|H_k\|\|H_k^{-1}\| \le M_1

，且

\|H_k^{-1}\| \le M_2

对无穷多个

k \in \mathbb N

成立，那么

\liminf_{k \to \infty} \|\nabla f(x_k)\| = 0

注意我们题干中说的是对无穷多个

k \in \mathbb{N}

，并不是对任意的

k \in \mathbb N

。也就是说我们最后可以找到一个子列，它的梯度序列收敛于驻点，但是并不是说每一步都会使得梯度严格下降。

很显然我们要使用的是Zoutendijk条件，而我们Theorem 4中如此关心

与

-\nabla f(x)

的夹角其实也能给我们一些思路。所以我们第一步就是要看如何创造出Zoutendijk条件所依赖的一些条件。

首先我们要证明存在一个

\mu > 0

使得

\|p_k\| \ge \mu \|\nabla f(x_k)\|

。注意到

\|p_k\| = \|H_k \nabla f(x_k)\| = \frac{\|H_k^{-1}\| \|H_k \nabla f(x_k)\|}{\|H_k^{-1}\|} \ge \frac{1}{\|H_k^{-1}\| }\|\nabla f(x_k)\| \ge \frac 1{M_2}\|\nabla f(x_k)\|

所以取

\mu = \frac 1 {M_2}

即可。

接下来，我们考虑一下Zoutendijk条件。注意到我们的求和式子蕴含两个元素：夹角和梯度模长。那么换句话说，如果有一个有下界，另外一个就必须趋于0（否则级数不可能有限）。因为这个我们可以来考虑一下夹角的性质。注意到

\cos \theta_k = \frac{- \nabla f(x_k)^T p_k}{\|\nabla f(x_k)\|\|p_k\|} = \frac{\nabla f(x_k)^T H_k f(x_k)}{\|\nabla f(x_k)\|^2} \cdot \frac{\|\nabla f(x_k)\|}{\|H_k \nabla f(x_k)\|}

第一个式子其实就是我们的Rayleigh商，可以参考https://zhuanlan.zhihu.com/p/52476330中的Proposition 1，它的最小值对应的就是矩阵

H_k

的最小特征值，也是最小奇异值（因为矩阵对称正定）。而第二个式子事实上与矩阵范数的定义有关，也就是说

\|A\| = \max_{\|x\| = 1} \frac{\|Ax\|}{\|x\|}

而我们的模长都是2-范数，对应到矩阵上就是最大奇异值。综合来看，我们可以得到

\cos \theta_k = \dfrac{\sigma_{min}}{\sigma_{max}} \ge \dfrac 1 {M_1}

这是因为矩阵的条件数就是

\|H_k\|\|H_k^{-1}\| = \frac{\sigma_{max}}{\sigma_{min}}

。到此我们的就说明了夹角是存在下界的，也就是说无论我们的迭代进行到哪一步，我们的方向都不会与负梯度方向垂直。

到此也许你可以看出来为什么梯度的下确界会趋于0了，因为如果这个结论不成立，那么必须

\cos \theta_k \to 0

（更严谨的说是存在子列趋于0）。这就与上面的推导矛盾了。

我们只使用下确界的原因在于我们的Theorem 5条件里面没有假设“任意的

k \in \mathbb N

”，换句话说，如果有这个条件，那么下确界这个条件是可以去掉的。

另外还需要明确的一点是，如果我们使用Wolfe条件作为步长选取条件，那么

\|H_k^{-1}\| \le M_2

这个条件是可以不用的。原因和上面某一个定理是相同的，我们留给读者思考。

到此，我们终于算是完整的给出了全局收敛性的证明。你通过这个证明相信也可以明白，为什么我们的最速下降法的步长选取，并不是简单的“取得大”还是“取得小”的问题。

至此，我们给出最终的成型的最速下降法的算法步骤

对应的是A-G条件中，

\tau_1 = \tau_2

的情形，一般我们还称它为回溯法 (backtracking)。

Case：最速下降法的局部收敛性

我们用这个问题来结束我们这一节。

首先当然要关心的是全局收敛性和局部收敛性到底有什么区别？全局收敛性关注的是收敛性，也就是说，给定任何的初始点，算法都能收敛到一个驻点。但是局部收敛性更多的关注的是收敛速度。也就是说初始点不能任意选取。而在这里我们就要给出最速下降法的一个局部收敛性质。

Theorem 6: 设

\mathcal N_{x_0} = \{x: f(x) \le f(x_0) \}

，设

f \in C^2

并且存在正常数

m < M

，满足

m \le \lambda _{min} (\nabla^2 f(x)) \le \lambda _{max}(\nabla^2 f(x)) \le M

（

\lambda

一般指的是特征值）对任意的

x \in \mathcal N_{x_0}

成立。设

x^*

是

的唯一极小值点，所有的迭代点

\{x_k\}

都满足B-N条件，那么我们有

f(x_k) - f(x^*) \le (1 - \beta\frac {m}M)^k (f(x_0) -f(x^*) )

其中

\beta

是常数。

也就是说，我们这里的海塞矩阵的正定性只在一个小区域上满足，并且这个正定性的要求还很高。因此梯度下降法是非常依赖一个函数的海塞矩阵的性质的。

我们证明一下这个结论。既然左边的式子相当于是一个函数差，题目中又有比较明显的海塞矩阵的提示，那么我们自然考虑Taylor展开，也就是说有

f(x^*) - f(x_k) = \nabla f(x_k)^T (x^* - x_k) + \frac 12 (x^* - x_k)^T \nabla ^2 f(x_k + \tilde t (x^* - x_k))(x^* - x_k)

因为在局部上海塞矩阵正定（但是这个局部也足够使用了，因为我们每一步都是下降的，所以我们自然有每一步的点都在

\mathcal N_{x_0}

内）。所以我们有

\nabla ^2 f(x_k + \tilde t (x^* - x_k)) > 0

，因此可以放缩掉这一项，得到

f(x_k) - f(x^*) \le \nabla f(x_k)^T(x_k - x^*) \le \|\nabla f(x_k)\|\|x^* - x_k\|

注意我们放缩的时候还取了一个负号。

在这一步的时候，我们注意到，如果利用上

\nabla f(x^*) = 0

的条件（极小值点），那么可以得到

\|x^* - x_k\|

与

\|\nabla f(x_k)\|

的关系。也就是说

\|\nabla f(x_k)\| \ge m\|x_k - x^*\|

我们跳过了一步，这可以通过Taylor展开说明。通过这个结论就可以推导出

f(x_k) - f(x^*) \le \frac 1m \|\nabla f(x_k)\|^2

还有一个要利用的条件是B-N条件，在最速下降法中，我们知道

h'(0) = -p^T \nabla f(x) = -\|\nabla f(x)\|^2

，所以可以得到

f(x_k) - f(x_{k+1}) \ge \chi \|\nabla f(x_k)\|^2

再加入我们之前推出的不等式，就可以得到

f(x_k) - f(x^*) \le \frac 1{m\chi} (f(x_k) - f(x_{k+1}))

通过这个式子其实就可以完成证明了，因为我们只需要左右两边再减去一个

f(x_k) - f(x_{k+1})

，就有

f(x_{k+1}) - f(x^*) \le (1 - m \chi)(f(x_k) - f(x^*))

现在的问题落到了

\chi

身上。回过头去看一下我们如何处理B-N条件（Theorem 2）。我们分别取了

\chi_2 = c_1

和

\chi_1 = \frac{\beta}{L}

（我们令分子那一串为

\beta

）。这个

会提示我们去寻找与Lipschitz连续相关的条件。

这里要注意的是，我们如果再次使用Taylor展开探索Lipschitz连续的常数，可以得到

\nabla f(x) - \nabla f(y) \le M \|x - y \|

在给定的一个范围内成立。也就是说

L \le M

。那么

\frac{\beta}{L} \ge \frac{\beta}{M}

，所以有

\chi \ge \frac {\beta}{M}

，这样的话代入，即可得到我们的不等式

f(x_{k+1}) - f(x^*) \le (1 - m \frac {\beta}{M})(f(x_k) - f(x^*))

有了这个递推不等式，就可以很容易的得到我们最终的结论了。至于

\chi_2

，因为

c_1

是我们可以事先给定的一个常数，所以不会干扰到我们的结论。

为什么我们一定要把

\chi

的性质找出来？这是因为如果我们能够导出

\chi \ge \frac{\beta}{M}

，就可以把这个每一步函数值下降的因子找出来。事实上我们可以看出来，因子是与海塞矩阵的条件数有关的。换句话说，如果给定的海塞矩阵的条件数不同，那么对应的收敛速度也会有不同。但是它依然是线性收敛速度，并且是根号收敛速度，代入我们第一节所说的定义即可验证。

事实上，如果海塞矩阵的性质很差，也就是说矩阵只有半正定。那么这个时候，对应的下界常数

就消失了。这个时候理论上可以证明仅仅存在次线性收敛速度。不过这部分内容超纲了，我们就不再这里赘述了。

好的，关于线搜索的绝大部分理论，我们算是介绍完毕了。还剩下一点线搜索实操方面的内容，我们到下一节再继续说。

小结

在这一节，我们层层推进，一切以证明收敛为目标，导出了一系列的结论。这一节也算是为优化的理论性正名了。事实上，看完这一节，你就会明白，为什么搜索方向不可以标准化，为什么梯度下降不仅仅是随便选一个大/小的步长那么简单。当然，如果你只是关心线搜索方法的真正的实现，那么这一节并没有什么作用（下一节就会很有作用）。但是反过来说，授之以鱼，不如授之以渔。如果你不知道这个工具怎么用，那么你就很难说会在工具出问题的时候，发现它真正的缺陷。

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2020-03-30，如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自学弱猹的精品小屋微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度