数值优化（4）——非线性共轭梯度法，信赖域法

学弱猹

发布于 2021-08-09 16:36:01

1K0

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

上一节笔记：

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

大家好！抱歉让大家久等啦！

在这一节我们会继续介绍非线性共轭梯度法的内容，并且开始对于信赖域算法展开介绍。信赖域算法算是线搜索方法的一个拓展，也是一种解优化问题的框架，之后的很多具体的优化算法都会在信赖域的框架下去实现。

那么我们开始吧。

Source

J. Nocedal, S. J. Wright, Numerical Optimization
厦门大学课堂笔记，教授主页：https://www.math.fsu.edu/~whuang2/index.html
Y. H. Dai and Y. Yuan. A nonlinear conjugate gradient method with a strong global convergence property.
Arthur I. Cohen. Rate of convergence of several conjugate gradient algorithms.

线性共轭梯度法的具体实现

我们在上一节介绍了线性共轭梯度法可以带来的几个性质，我们放在这里再给大家复习一下。

Theorem 1: 设线性共轭梯度法的第

步迭代的结果

x_k

不是解，那么有以下结论成立 (1)

\operatorname{span} (r_0, r_1, \cdots, r_k) = \operatorname{span}(r_0, Ar_0, \cdots, A^k r_0)

(2)

\operatorname{span}(p_0, p_1, \cdots, p_k) = \operatorname{span}(r_0, Ar_0, \cdots, A^k r_0)

(3)

r_k^T p_i = 0, \forall i < k

(4)

p_k^T Ap_i = 0, \forall i < k

具体的来说，我们的算法构造可以写成这样的一个形式

关于

\alpha_k, x_{k + 1}, r_{k+1}, p_{k + 1}

的选取和定义我们都在上一节有提过。只有

\beta_{k + 1}

怎么取我们没有说，但是事实上，根据我们的

p_{k + 1} = - r_{k + 1} + \beta_{k + 1}p_k

，左乘一个

p_{k}^T A

即可（因为我们的共轭性保证了

p_{k}^T Ap_{k + 1} = 0

）。

但是这个方法事实上还是差了点意思，这是因为在实现方式上，我们发现有些矩阵与向量的乘法，可以通过向量与向量的内积做代替，而有些可以重复利用的部分，我们也可以只计算一次。所以就会演变成下面这样的方法

为什么这样的修改可以？我们把它单独列成一个性质。

Proposition 1: 证明图中的公式等价。

其实这些公式的证明关键都落在我们最开头的几个共轭性上，我们一个一个来看。

对于

\alpha_k = \frac{-r_k^T p_k}{p_k A p_k}

，注意到我们有

p_k = -r_k + \beta_k p_{k - 1}

，再利用上

r_k^T p_{k - 1} = 0

即可。对于

r_{k + 1} = Ax_{k + 1} - b

，其实只需要注意到

r_k = Ax_k - b

，所以归根到底就是

r_{k + 1} - r_k = A(x_{k + 1} - x_k) = A\alpha_k p _k

所以这个性质也不难说明。至于

\beta_{k + 1} = \frac{r_{k+1}^T A p_k}{p_k^T A p_k}

，我们其实根据上面这个可以得到

Ap_k = \frac{r_{k + 1} - r_{k}}{\alpha_k}

代入就可以得到分子为

r_{k+1}^T r_{k + 1}

，因为

r_{k+1}^T r_k = 0

（想想为什么？）。至于分母，注意到

p_k^T r_{k + 1} = 0

，

p_k^T r_k = r_k^T r_k

（想想为什么？），就可以得到为

r_k^T r_k

，所以最终的

\beta_{k+1}

的形式我们也算证明完成了。

在新的这个实现方式下，其实主要的计算开销就落在了

Ap_k

p_k^T (A p_k)

和

r_k^T r_k

上。相比较之前的而言，我们不需要计算

Ax_k

这样的东西，这算是一个比较好的优化。

非线性共轭梯度法

事实上，非线性共轭梯度法相比较线性共轭梯度法而言，只是修改了几个标记而已。但是它们的成功也是有理论保障的，我们会慢慢看到。

首先我们根据我们之前的线性共轭梯度法的框架来看一下非线性的情况究竟改了哪些。

初值上，我们一开始是

r_0 = Ax_0 - b

，这是因为我们是以二次凸问题作为线性共轭梯度法来举例的。在这种情况下，事实上一开始的这个残差就是梯度，所以在非线性的情况下，我们设置了

r_0 = \nabla f(x_0)

，也就是说，初始搜索方向设置为负梯度方向。同理也可以解释我们的第4步和第5步，在线性共轭梯度法中，它的目标是为了解

Ax = b

，使得

Ax-b

尽可能的小。但是本质上，其实就是为了使得优化时梯度可以尽量的趋于0，这也符合我们对优化算法的要求。

看似到这里问题就结束了，但是有一个隐含的问题在于算法的第2步。一般情况下，由于数值误差的存在，优化的精确步长是难以求得的。所以在非线性共轭梯度法下，实际的效果总是会差那么一些。同样的也正是因为这个，我们对于步长会放松限制，不再采用精确步长。有一种可以采纳的思路就是使用Strong-Wolfe条件来选取步长（可以去看一下第1-2节）。下面的这个性质保证了这样的选取的步长的方向依然是下降方向。

Proposition 2: 设

\{x_k\}

为使用Fletcher-Reeves格式（也即

\beta_{k + 1} = \frac{\nabla f(x_{k + 1})^T \nabla f(x_{k+1})}{\nabla f(x_k)^T \nabla f(x_k)}

）非线性共轭梯度法得到的迭代点序列。Strong-Wolfe条件的系数满足

0 < c_1 < c_2 < 0.5

，那么搜索方向

p_k

满足

-\frac 1 {1 - c_2} \le \frac{\nabla f(x_k)^T p_k}{\|\nabla f(x_k)\|^2} \le \frac{2c_2 - 1}{1 - c_2}

对于这种第一眼看毫无想法的式子，往往可以使用数学归纳法。

k = 0

的情况对应着初值的情况，因为我们初始的搜索方向为负梯度方向，所以这个时候步长与梯度的夹角为平角（也就是余弦为1），代入不难得到结论成立。

现在考虑一下，如果对于

成立，对于

k + 1

的情况会如何？注意到我们根据公式

p_{k + 1} = -\nabla f(x_{k+1}) + \beta_{k+1}p_k

，有

\frac{\nabla f(x_{k+1})^Tp_{k + 1}}{\|\nabla f(x_{k+1})\|^2} = -1 + \beta_{k + 1}\frac{\nabla f(x_{k+1})^Tp_k}{\|\nabla f(x_{k+1})\|^2} = - 1 + \frac{\nabla f(x_{k+1})^T p_k}{\|\nabla f(x_k)\|^2}

最后的一项是因为

\beta_{k+1} = \frac{\|\nabla f(x_{k + 1})\|^2}{\|\nabla f(x_k)\|^2}

。那么根据Strong-Wolfe条件中的第二个不等式，我们有

|h'(\alpha)| \le c_2 |h'(0)|

而如果代入这个算法，就可以得到

|\nabla f(x_{k+1})^T p_k| \le -c_2 \nabla f(x_k)^T p_k

这个式子就搭建了一个桥梁，把它代入之后就可以得到

-1 + c_2 \frac{\nabla f(x_k)^T p_k}{\|\nabla f(x_k)\|^2} \le- 1 + \frac{\nabla f(x_{k+1})^T p_k}{\|\nabla f(x_k)\|^2} \le -1 -c_2 \frac{\nabla f(x_k)^T p_k}{\|\nabla f(x_k)\|^2}

代入我们的归设即可得到结论。

好的，看来我们解决了这个步长的问题。但是却产生了一个新的问题：迭代可以顺利进行吗？具体来说，就是，这个方法是不是可以自行修正的？我们考虑一下假如说我们有

\cos (\theta_k) \simeq 0

，也就是说

\frac{-\nabla f(x_k)^T p_k}{\|\nabla f(x_k) \| \| p_k \|} \simeq 0

，也就是说

p_k

与负梯度方向几乎正交。这个时候我们会发现，我们根据Proposition 2，有

\frac{1 - 2 c_2}{1 - c_2} \frac{\|\nabla f(x_k)\|}{\|p_k\|} \le \cos \theta_k \le \frac{1}{1 - c_2} \frac{\|\nabla f(x_k)\|}{\|p_k\|}

那么可以得到的结论是

\|\nabla f(x_k)\| << \|p_k\|

，同时因为搜索方向近乎垂直，就很难得到好的下降，所以我们也会有

x_{k + 1} - x_k \simeq 0

，那么这个时候呢，你可以发现，迭代几乎没有进行，也就是说梯度几乎没有变化，

\beta_{k + 1} \simeq 1

，这个时候，根据

p_{k + 1} = - \nabla f(x_{k+1}) + \beta_{k+1} p_k \simeq -\nabla f(x_k) + p_k \simeq p_k

（根据梯度模长与

\|p_k\|

的比较关系），就可以得到我们这个时候，搜索方向也几乎没有变化。结合这两点来看，你会发现其实如果在某一步搜索方向取得不好，之后也别指望算法能够自己修好。所以这样的格式其实是不可取的。

下面这张图解释了为什么我们认为

x_{k+1} \simeq x_k

说了这么多，那么有什么解决方案吗？我们看出来，只要破坏任何一条我们思考的依据，都应该算是可行的。因此我们可以考虑设置一些其它的

\beta

的格式。

Definition 1: Polak-Ribiere, Hestenes-Stiefel 定义P-R格式和H-S格式的

\beta

为

\beta_{k + 1}^{PR} = \frac{\nabla f(x_{k + 1})^T (\nabla f(x_{k+1}) - \nabla f(x_k))}{\nabla f(x_k)^T \nabla f(x_k)}

\beta_{k + 1}^{HS} = \frac{\nabla f(x_{k+1})^T (\nabla f(x_{k + 1}) - \nabla f(x_k))}{(\nabla f(x_{k + 1}) - \nabla f(x_k))^T p_k}

在精确步长的意义下，这两个式子是等价的，并且化归到二次凸问题也是可行的。但是因为它们不是我们的重点，所以我们这里就不证明了，感兴趣的读者可以自己尝试。

解决问题了吗？很遗憾，依然没有。这两个格式都不存在全局收敛性。为了使得全局收敛性满足，基于这两个格式的修正也有很多，这里提一个格式为下面的这个格式。

Definition 2: Dai-Yuan

\beta_{k + 1}^{DY} = \frac{\nabla f(x_{k + 1})^T \nabla f(x_{k+1})}{(\nabla f(x_{k+1}) - \nabla f(x_k))^T p_k}

这个方法同时可以保证全局收敛性，也就是对应的下面的这个定理。

Theorem 2: 设

\mathcal{N}_{x_0} = \{x: f(x) \le f(x_0)\}, f\in C^1

，

\nabla f(x)

在

\mathcal{N}_{x_0}

内是Lipschitz连续的，步长采取Wolfe条件，那么有

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

要说明全局收敛性，我们会使用到Zoutendijk条件（忘了的话可以看一下第2节~）。也就是说，一方面，我们希望观察一下

\sum_{k = 0}^\infty \cos^2 \theta_k |g_k|^2 = \sum_{k = 0}^\infty \frac{(g_k^Tp_k)^2}{|p_k|^2}

。这里

g_k = \nabla f(x_k)

。另一方面，我们希望看看我们的方向是不是下降方向。如果是最速下降法自然不需要说明后面这一件事，但是在共轭梯度法上其实这一点没有那么显然。

注意到，因为我们对步长要求是Wolfe条件，所以可以推出这个级数是收敛的。那么自然的，我们希望说明的就是，如果我们的结论不成立，那么这个级数就无法收敛。

自然希望说明级数收敛，自然我们希望看到的就是对

\frac{(g_k^Tp_k)^2}{\|p_k\|^2}

的估计。而

g_k^Tp_k

也正好可以用来判断方向是否是下降方向。注意到我们有

p_{k + 1} = - g_{k + 1} + \beta_{k + 1} p_k = -g_{k + 1} + \frac{\|g_{k + 1}\|^2p_k}{(g_{k + 1} - g_k)^T p_k}

所以化简就可以得到

g_{k + 1}^T p_{k + 1} = \beta_{k + 1}^{DY} g_k^T p_k

（想想为什么？）有了这个式子之后，可以看出，如果我们的第一步的方向是下降方向，那么之后是否一直是下降方向，取决于

\beta_{k + 1}^{DY}

的情况。而注意到根据weak-wolfe条件的第二个不等式（也可以说是Curvature条件），我们可以得到

(g_{k+1} - g_k)^T p_k \ge (c_2 - 1)g_k^T p_k

所以如果第一步的方向是下降方向，那么可以得到

(g_{k+1} - g_k)^T p_k >0

，对应的就是

\beta_{k+1}^{DY}

，结合我们第一步方向是负梯度方向，就可以得到我们每一步都是下降方向的结论。

好的，我们现在再来看看怎么估计我们的

\frac{(g_k^Tp_k)^2}{\|p_k\|^2}

，而分子其实我们已经有了一个很好的估计，所以现在只需要再看看

\|p_k\|^2

可以怎么估计就可以了。注意到我们有

p_{k + 1} + g_{k + 1} = \beta_{k + 1}p_k

，两边平方，有

\|p_{k + 1}\|^2 = \beta_{k + 1}^2 \|p_k\|^2 - 2 g_{k + 1}^T p_{k + 1} - \|g_{k + 1}\|^2

然后除以

g_{k+1}^T p_{k +1}

，代入我们之前证明的性质，就可以得到

\frac{\|p_{k + 1}\|^2}{(g_{k + 1}^T p_{k + 1})^2} = \frac{ \|p_k\|^2}{(g_k^T p_k)^2} - \frac{2}{ g_{k + 1}^T p_{k + 1}} - \frac{\|g_{k + 1}\|^2}{(g_{k + 1}^T p_{k + 1})^2}

根据配方法（具体怎么配留给读者思考），我们可以得到

\frac{\|p_{k + 1}\|^2}{(g_{k + 1}^T p_{k + 1})^2} \le \frac{ \|p_k\|^2}{(g_k^T p_k)^2} + \frac 1 {\|g_{k + 1}\|^2}

你会发现，这样的话就相当于找到了相邻两项差的上界。所以可以通过递推的方式得到这个项的估计。事实上，代入初始的负梯度方向就可以得到

\frac{\|p_{k + 1}\|^2}{(g_{k + 1}^T p_{k + 1})^2} \le \sum_{i = 0}^{k + 1}\frac 1{\|g_{i}\|^2}

万事俱备，只差反证。如果说存在

c > 0

，使得

\|g_k\| \ge c

，那么这个时候，你会发现第

项其实都

\ge \frac {c^2}{k}

，注意到调和级数是发散的，所以和式不收敛，这就矛盾了，也就说明了结论的成立。

到此，我们算是得到了一个能用的非线性共轭梯度法。当然了实际情况下，如果有了更多的信息（比方说对于函数的性质了解很透彻），之前的方法也不是不能使用，但是如果毫无了解，使用一个没有全局收敛性的算法，还是过于冒险了一点。

最后我们提一个实际算法中会经常使用的trick。因为这个算法非常依赖步长的性质（因为有一步要求是精确步长），加上它基本上没有自我修复的能力，所以很多时候需要加一些外界的干预。有一个方法是判断

|\frac{\nabla f(x_{k + 1})^T \nabla f(x_k)}{\|\nabla f(x_{k +1})^2\|}| < \epsilon

如果这个条件满足，那么说明

\nabla f(x_{k+1})

和

\nabla f(x_k)

是差别很大的，也就是说

x_{k+1} \simeq x_k

不太可能。这个时候我们认为算法运行正常，就不做干预。反过来，如果不满足，那么说明可能算法“卡住了”。这个时候可能会做一步重启，也就是考虑重新设置搜索方向为当前的负梯度方向。

预条件方法

预条件（Preconditioning）方法算是一个最近比较火的方法。它的主要思路是对问题做一个线性变换，使得新的问题的计算具有更低的复杂度。比方说对于二次凸问题，在数值上，共轭梯度法会受到线性系统矩阵的条件数的影响。所以为了降低这个影响，有一种思路是考虑设置一个变换

\hat x = Cx

这个时候，我们会得到对应的二次凸问题为

\frac12 x^T A x - b^T x = \frac12 \hat x ^T C^{-T} A C^{-1}\hat x - (C^{-T}b)^T \hat x

这个时候，令

\hat A = C^{-T}AC^{-1}

\hat b = C^{-T}b

，就可以得到一个和之前的系统形式完全一样的优化目标。

我们在之前提到过，在原始的方法中，

Ap_k

是一个大的计算开销的部分，那么在这个地方，其实对应的就是

C^{-T}AC^{-1}

这个东西，我们希望这个东西的条件数小一些，这个时候计算复杂度也就相对应的会小一些。所以事实上我们希望做的事情就是使得

C^TC \simeq A

有一个很好的例子就是偏微分方程数值解。在https://zhuanlan.zhihu.com/p/65247362中，我们有提过，对于三大经典方程，我们一般都会得到一个三对角的矩阵。这个矩阵的性质比较好，但是实际的运作中可能会出现非三对角的情况比较杂乱的情况，因此有一个方案就是取

C^TC

为矩阵的三对角的部分。这个时候就会发现，一方面我们避开了那些数值误差导致的杂乱的矩阵元素（所以条件数会大大下降），另一方面也可以使得它与原始矩阵

的差距不会那么大。

这样的一个预条件做完之后自然还需要把原始的点再映射回来，所以综合起来，我们可以把算法写成这样的格式。

这样的话，其实主要的开销就会变成

(C^TC)^{-1}r_k

这样的东西。而如果我们考虑之前的那种方法（也就是说这个东西为矩阵

的三对角部分），就会使得这个线性系统的计算也比较方便。

对于非线性共轭梯度法，其实它的主要的开销依然没有变，只不过这个时候主要的开销会变成

(C^TC)^{-1}\nabla f(x_k)

这样的东西，同时因为非线性共轭梯度法的情况下，

不是恒定的，但是我们注意到它其实就是二次凸问题的海塞矩阵。所以一般来说，我们会让

C^TC

逼近于海塞矩阵，同时拥有较低的条件数，这样的话预条件才算达到了目标。

一个比较实用的带预条件的非线性共轭梯度法如下

最后，我们放一个共轭梯度法的数值实验结果。

这里的

坐标对应为梯度的模长。

c_2

就是wolfe条件中第二个不等式的系数。这个系数就限制了对于步长是否精确的要求。可以看出，

c_2

如果取得越小，对应的步长就要求越靠近精确步长（想想为什么？），所以可以看出共轭梯度法的表现就越好。

到此，我们算是介绍完了共轭梯度法的相关内容。

信赖域方法

信赖域（Trust-Region）方法算是线搜索方法的一个拓展。它的核心思想是用一个好解的局部模型去近似当前迭代点附近的函数情况。线搜索方法每一次都会找到下一步的迭代点，同时我们也有很完备的理论，但是仅仅是探索一个点和一个方向总是感觉有点不放心。事实上到后面我们会看到，有些方法会更适合使用信赖域的思想，也正是因为它在使用线搜索框架的时候，会遇到一些麻烦。

简单的概括一下信赖域算法思想的重点，就是。

找到一个好解的局部模型，设置这个局部模型的探索范围。
如果这个解符合真实情况，就采用，否则不采用
如果这个解符合真实情况，那么扩大模型探索的范围，否则缩小范围。

下面是一个比较常见的信赖域算法的框架。

我们可以看出，这里牵涉到了几个元素：半径

\Delta

，下降程度

\rho_k

，模型

m_k(p)

，事实上就对应了我们之前说的信赖域算法的核心思想。这里

\mathbb{B}(\Delta)

就是半径为

\Delta

的球。

半径

\Delta

表示了步长可以取的范围，换句话说，我的这个步长可以伸多远？而

\rho_k

就是衡量我的下降情况的。如果

\rho_k

很大，那么这个时候相当于分子很大（因为分母是你设置的模型，因为要求在你规定的模型下取到最小，所以

m_k(0) - m_k(p_k)

一般是固定的，与

无关的），也就是说下降的很多。那自然就认为你的模型符合了函数的真实情况。符合了真实情况我们就会采用这个步长，也就是更新为

x_{k + 1} = x_k + p_k

，否则就不会改变。同样的，如果说我们的模型表现的好，下降的很多，一般来说会考虑扩大半径，反过来就会缩小半径。当然了如果表现的一般，不好不坏，那么这个时候就会考虑维持当前的半径。

在上面的这个模型中，我们的假设是

m_k(p) = f(x_k) + \nabla f(x_k)p + \frac12 p^T B_k p

这是二次模型，事实上也可以取三次模型等，具体的形式因为我们用不上，所以这里就不给出了。事实上模型的次数越高，逼近效果也就越好，但是对应的计算的复杂度也就会上升。另外，这里的

B_k

取的是对称阵。这么取的原因主要在于一些比较经典的算法都会依赖到对称阵的结构。具体的我们到后面的章节会看到。

柯西点

如果我们加一些限制条件，在方向的导出上只考虑一次模型，得到的这样的解的点就是柯西（Cauchy）点。虽然信赖域算法中基本上没有模型使用一次函数的逼近，但是我们有性质说明，即使这样的算法也可以保证全局收敛性。

首先我们要看一下如何导出柯西点。第一步找方向。首先我们注意到，一次模型就是去掉了关于

p_k

的二次项，也就是说

p_k^s = \arg\min_{\|p\| \le \Delta_k}f(x_k) + \nabla f(x_k)^T p

那么注意到

f(x_k)

是一个常数，所以这个时候只需要

\nabla f(x_k)

与

方向相反就好，这个时候结合

\|p\| \le \Delta_k

，可以得到

p_k^s = \frac{-\nabla f(x_k)}{\|\nabla f(x_k)\|} \Delta_k

第二步找收缩因子，我们考虑一下计算收缩因子

\tau_k

，满足

\tau_k = \arg \min_{\tau \ge 0, \|\tau p_k^s\| \le \Delta_k}m_k(\tau p_k^s)

这个时候也不难求得

\tau_k = \begin{cases}1 & \nabla f(x_k)^T B_k \nabla f(x_k) \le 0 \\ \min(\frac{\|\nabla f(x_k)\|^3}{(\Delta_k \nabla f(x_k)^T B_k \nabla f(x_k))}, 1) & \operatorname{otherwise}\end{cases}

这个式子看似比较复杂，但是其实就是一个二次函数极值的讨论，属于高一数学的难度。这里我们就不展示具体计算细节了，留给读者思考。

最终，我们可以得到

p_k^c = -\tau_k \frac{\nabla f(x_k)}{\|\nabla f(x_k)\|} \Delta_k

这也就是最终的柯西点。

柯西点的全局收敛性

接下来我们要说明的就是柯西点的全局收敛性。为此我们先给出一个不等式。

Proposition 3: 存在

c_1 \in (0, 1)

，使得

m_k(0) - m_k(p_k^c) \ge c_1 \|\nabla f(x_k)\| \min (\Delta_k, \frac{\|\nabla f(x_k)\|}{\|B_k\|})

我们证明一下这个结论。既然我们的

\tau_k

有多种情况，那么自然需要分情况讨论。

如果

\nabla f(x_k)^T B_k \nabla f(x_k) \le 0

，那么这个时候，

\tau_k = 1

，所以可以直接把

p_k^c

代入，可以得到

m(p_k^c) - m(0) = -\frac{ \Delta_k \nabla f(x_k)^T \nabla f(x_k)}{\|\nabla f(x_k)\|} + \frac 12 \frac{\Delta_k^2}{\|\nabla f(x_k)\|^2}\nabla f(x_k)^T B_k \nabla f(x_k)

第二项根据条件就可以得到它是小于0的，所以我们可以考虑去掉它。所以化简第一项，可以得到

m(p_k^c) - m(0) \le-\|\nabla f(x_k)\|\Delta_k \le - \|\nabla f(x_k)\| \min (\Delta_k, \frac{\nabla f(x_k)}{\|B_k\|})

再两边同乘-1，即可得到结论。

如果是另一个情况，也就是说

\nabla f(x_k)^T B_k \nabla f(x_k) > 0

，那么这个时候，

\tau_k

又会对应两种情况。如果说

\frac{\|\nabla f(x_k)\|^3}{(\Delta_k \nabla f(x_k)^T B_k \nabla f(x_k))} \le 1

，那么这个时候对应的式子自然会写的很长，我们直接给出化简后的结果，也即

m(p_k^c) - m(0) = -\frac12 \frac{\|\nabla f(x_k)\|^4}{\nabla f(x_k)^T B_k \nabla f(x_k)} \le -\frac12 \frac{\|\nabla f(x_k)\|^2}{\|B_k\|} \le -\frac12 \|\nabla f(x_k)\| \min (\Delta_k, \frac{\|\nabla f(x_k)\|}{\|B_k\|})

如果说有

\frac{\|\nabla f(x_k)\|^3}{(\Delta_k \nabla f(x_k)^T B_k \nabla f(x_k))} \ge 1

，这个情况下

\tau_k = 1

，结论也很好证明，因为这个时候式子和之前的形式一样，并且我们有

\frac{\|\nabla f(x_k)\|^3}{\Delta_k} \ge \nabla f(x_k)^T B_k \nabla f(x_k)

。所以不难得到

m(p_k^c) - m(0) \le -\frac12 \Delta_k \|f(x_k)\|

后面的话相信也都知道怎么写了，这里就略过了。

这个性质就是用来证明下面的全局收敛性的。

Theorem 3: 设在信赖域算法中

\eta = 0

，设存在

\beta

，使得

\|B_k\| \le \beta

，并且存在

\delta

，使得

在

\mathcal{N}_{x_0}

上存在下界，且在

\mathcal{N}_{x_0}^\delta = \{x: \|x - y\| \le \delta, \exist y \in \mathcal{N}_{x_0}\}

上Lipschitz连续，并且子问题的解均满足Proposition 3，那么有

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

我们证明一下这个结论，还是一样，考虑反证。设对任意的

k \ge K

，我们都有

\|\nabla f(x_k)\| \ge \epsilon

，那么我们的想法是，观察一下我们的下降情况

\rho_k

，看它是否会有一些异常。注意这里我们的方法不再是线搜索方法了，所以不能再使用Zoutendijk了。

注意到我们可以考虑构造式子

|\rho_k - 1| = |\frac{m_k(p_k) - f(x_k + p_k)}{m_k(0) - m_k (p_k)}|

分母非常好办，因为我们上面的那个式子

m_k(0) - m_k(p_k) \ge c_1 \epsilon \min(\Delta_k, \frac{\epsilon}{\beta})

（中间是有跳步的，读者可以自己补上），分子稍微麻烦些，把式子写开可以得到

|m_k(p_k) - f(x_k + p_k)| = |\nabla f(x_k)^T p_k + \frac12 p_k^T B_k p_k + f(x_k) - f(x_k+p_k)|

根据Taylor展开，我们有

f(x_k + p_k) = f(x_k) + \nabla f(x_k)^T p_k + [\nabla f(x_k + tp_k) - \nabla f(x_k)]^T p_k

其中

t \in (0, 1)

。在这种情况下，可以发现前两项代回之后会被消掉，所以其实只会剩下

|m_k(p_k) - f(x_k + p_k)| \le |\frac12 p_k^T B_k p_k + [\nabla f(x_k + tp_k) - \nabla f(x_k)]^T p_k| \\ \le \frac \beta 2 \|p_k\|^2+L \|p_k\|^2

这里用到的主要是柯西不等式和各种题目给的条件。综合起来，加上

\|p_k\| \le \Delta_k

，就会有

|\rho_k -1| \le \frac{\Delta_k^2 (\frac12 \beta + L)}{c_1 \epsilon \min (\Delta_k, \frac\epsilon \beta)}

为什么要给定这个呢？这是因为我们希望，在这个条件下，我们能够找到一个半径与下降情况的制衡，进而得到矛盾。事实上，我们希望说明的是

Lemma 1: 若

\Delta_k \le \bar \Delta = \min (\frac12 \frac{c_1 \epsilon}{\frac \beta 2 + L}, \delta)

，那么会有

|\rho_k - 1| \le \frac12

。

这个性质的说明不是很困难，因为我们有

\bar \Delta \le \frac \epsilon \beta

，所以分母其实那个值是固定的。也就是说可以得到

|\rho_k - 1| \le \frac{\Delta_k (\frac \beta 2 + L)}{c_1 \epsilon} \le \frac12

我们依然有所跳步，留给读者补充。

这个性质证明完之后，其实我们就可以发现，如果我们的半径取得足够的小，那么对应的

\rho_k

就会足够的好，这种情况下半径就无法得到收缩。反过来，如果我们的

\rho_k

比较一般，那么这个时候半径就会收缩，收缩到最后又会使得步长足够的好。这个思考逻辑指引我们考虑

\rho_k

的取值情况。

如果说我们存在一个无限子列

，满足

\rho_k \ge \frac14,\forall k \in S

，那么这个时候，我们可以考虑，对于任意的

k \ge K, k \in S

（

足够大），我们可以得到

f(x_k) - f(x_{k + 1}) \ge \frac14 [m_k(0) - m_k(p_k)] \ge \frac14 c_1 \epsilon \min(\Delta_k, \frac \epsilon \beta)

可以看到右边并不是一个趋于0的项，所以事实上可以考虑对子列中的所有项求和，那么因为左边实质上是函数的差，求和有限，右边却会得到一个无限的值，因此这会产生矛盾。

反过来，如果说这样的子列不存在，那么也就是说，只有有限个

\rho_k \ge \frac 14

，相当于说

\Delta_{k + 1} = \frac14 \Delta_k

会发生无数次，那么这个时候可以推出来

\Delta_k \to 0

。这是不可能的，因为我们知道

\Delta_k

足够小的时候，

\rho_k

取得会足够的好，导致半径无法收缩。所以这也是个矛盾。

到此我们就证明了这个全局收敛性，而事实上，我们的柯西点就是满足Proposition 3这个不等式的，因此即使是随便取的柯西点，我们也能保证算法是有效的。

好的，这一节就到这里，关于信赖域法还剩下一点内容，我们到之后再说。

小结

本节主要介绍了非线性共轭梯度法和信赖域法。非线性共轭梯度法的形式和线性共轭梯度法相同，但是我们为了保证它的有效性，也介绍了很多有趣的技巧。对于信赖域方法，它是一种不同于线搜索方法的优化框架，我们这一节的后半部分也介绍了一些简单的情形，但是即使是简单的情形，也可以推出很好的性质。所以也不难怪为什么很多方法会更倾向于使用信赖域方法了。

事实上，如果需要解完全的二次模型，也有很多成型的方法，我们下一节的开始会介绍这些。

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

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

编程算法

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

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

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

编程算法