13、Wolfe 线搜索下一般性收敛定理

在之前的第九篇文章，我们分析了采取强 $~\rm{Wolfe}~$ 线搜索的一般共轭梯度法，并在没有充分下降条件的情况下给出了方法全局收敛的一般性定理。这一节将分析采取 $~\rm{Wolfe}~$ 线搜索的一般共轭梯度法。值得注意的是，这节的标题是 $~\rm{Wolfe}~$ 线搜索下一般性定理，不是说这些收敛定理，只在 $~\rm{Wolfe}~$ 线搜索下得到，满足条件在其他的线搜索也可以得到。

1、简介

共轭梯度法是解决无约束优化问题的常用方法之一，问题如下
$\min_{x\in\mathbb{R}^n} f(x)\tag{1}$
求解此问题，一般采取线搜索技巧，其基本迭代格式形如
$x_{k+1}=x_k+\alpha_k d_k\tag{2}$
$d_k=\begin{cases} -g_k,\quad & k=1,\\ -g_k+\beta_k d_k, &k\ge 2,\end{cases}\tag{3}$
其中 $~g_k~$ 是迭代点 $~x_k~$ 处的梯度， $~\alpha_k~$ 是搜素步长， $~d_k~$ 是搜素方向， $~\beta_k~$ 为共轭参数，不同的参数 $~\beta_k~$ 决定不同的共轭梯度法。我们知道
$\beta_k^{FR}=\frac{\Vert g_k\Vert^2}{\Vert g_{k-1}\Vert^2}\tag{4}$
$\beta_k^{DY}=\frac{\Vert g_k\Vert^2}{d_{k-1}^T (g_k-g_{k-1})}\tag{5}$
利用 $~(3)~$ 和 $~(5)~$ ，我们有
$\beta_k^{DY}=\frac{g_k^T d_k}{g_{k-1}^T d_{k-1}}\tag{6}$
从 $~(4)~$ 和 $~(6)~$ 可以看出， $~\rm{FR}~$ 方法和 $~\rm{DY}~$ 方法关于参数 $~\rm{\beta_k}~$ 的计算公式其分子和分母的下标只是相差1，即他们可以形式地表为
$\beta_k=\frac{\phi_k}{\phi_{k-1}}\tag{7}$
对于 $~\rm{FR}~$ 方法，可取 $~\rm{\phi_k=\Vert g_k\Vert^2}~$ ；对于 $~\rm{DY}~$ 方法，可取 $~\rm{\phi_k=-g_k^T d_k}~$ 。对一般共轭梯度法，定义
$\phi_k=\begin{cases} &\Vert g_1\Vert^2,&~k=1\\ &\prod \limits_{i=2}^k\beta_i,&~k\ge 2 \end{cases}\tag{8}$
则 $~\beta_k~$ 也可以携程 $~(7)~$ 的形式，可见 $~(7)~$ 式具有普遍性。由于当 $~\beta_k=0~$ ， $d_k~$ 为最速下降方向，因此在下面的分析中，我们总假定 $~\beta_k\neq 0~$ ，这时也有 $~\phi_k\neq 0~$ 。定义
$t_k=\frac{\Vert d_k\Vert^2}{\phi_k^2}\tag{9}$
$\overline{r}_k=-\frac{g_k^T d_k}{\phi_k}\tag{10}$

2、收敛性分析

首先证明如下引理
引理 1：考虑方法 $~(2)~$ 和 $~(3)~$ ，其中 $~\beta_k~$ 由 $~(7)~$ 给出，则对所有的 $~k\ge 1~$ ，有下式成立。
$t_k=-2\sum_{i=1}^k\frac{g_i^T d_i}{\phi_i}-\sum_{i=1}^k\frac{\Vert g_i\Vert^2}{\phi_i^2}\tag{11}$
证明：因为 $~d_1=-g_1~$ ，显然 $~(11)~$ 对 $~k=1~$ 成立。对于 $~k\ge 2~$ ，由 $~(3)~$ 可知
$d_i+g_i=\beta_i d_{i-1}\tag{12}$
两端取模平方，则有
$\Vert d_i\Vert^2=\beta_i^2\Vert d_{i-1}\Vert^2-\Vert g_i\Vert^2-2g_i^T d_i\tag{13}$
对 $~(13)~$ 式两端除以 $~\phi_i^2~$ ，并利用 $~(7)~$ 和 $~(9)~$ ，得
$t_i=t_{i-1}-\frac{2g_i^T d_i}{\phi_i^2}-\frac{\Vert g_i\Vert^2}{\phi_i^2}\tag{14}$
将上式从 $~i=2~$ 至 $~k~$ 求和，便得
$t_k=t_{1}-2\sum_{i=2}^k\frac{g_i^T d_i}{\phi_i^2}-\sum_{i=2}^k\frac{\Vert g_i\Vert^2}{\phi_i^2}\tag{15}$
注意到 $~d_1=-g_1~$ 以及 $~t_1=\frac{\Vert g_1\Vert^2}{\phi_1^2}~$ ，上式同 $~(11)~$ 式等价，故 $~(11)~$ 对所有的 $~k\ge 1~$ 均成立。

引理 2：设 $~\left\{a_i\right\}~$ 和 $~\left\{b_i\right\}~$ 为两个正项级数，且 $~\sum_{i=1}^{\infty}a_i~$ 发散，若存在正常数 $~c_1~$ 和 $~c_2~$ ，使得
$b_k\le c_1+c_2\sum_{i=1}^ka_i\tag{16}$
对所有 $~k\ge 1~$ 成立，则 $~\sum_{i=1}^{\infty}\frac{a_i}{b_i}~$ 亦发散。
证明：这是一个《数学分析》的知识，证明过程参考文献[1]，故在此省略。

定理 1：设目标函数 $~f(x)~$ 下方有界，导数 $~\rm{Lipschitz}~$ 连续，考虑方法 $~(2)~$ 和 $~(3)~$ ，其中 $~\beta_k~$ 具有形式 $~(7)~$ ， $\alpha_k~$ 使得 $~\rm{Zoutendijk}~$ 条件
$\sum_{k\ge 1}\frac{(g_k^T d_k)^2}{\Vert d_k\Vert^2}<\infty\tag{17}$
和
$g_k^T d_k<0,~~\forall~k\ge 1\tag{18}$
如果
$\sum_{k\ge 1}\overline{r}_k^2=\infty\tag{19}$
则必有
$\lim_{k\rightarrow\infty}\inf\Vert g_k\Vert=0\tag{20}$
证明：注意到
$-2g_i^T d_i-\Vert g_i\Vert^2\le\frac{(g_i^T d_i)^2}{\Vert g_i\Vert^2}\tag{21}$
由 $~(11)~$ 可以推出
$t_k\le\sum_{i=1}^k\frac{(g_i^T d_i)^2}{\Vert g_i\Vert^2\phi_i^2}\tag{22}$
或等价地
$t_k\le\sum_{i=1}^k\frac{\overline{r}_i^2}{\Vert g_i\Vert^2}\tag{23}$
若
$\lim_{k\rightarrow\infty}\inf\Vert g_k\Vert\neq 0\tag{24}$
则存在常数 $~\gamma>0~$ ，使得
$\Vert g_k\Vert\ge \gamma,~~\forall~k\ge 1\tag{25}$
上式和 $~(23)~$ 表明了
$t_k\le\frac{1}{\gamma^2}\sum_{i=1}^k\overline{r}_i^2\tag{26}$
利用 $~(19),(26)~$ 以及引理 2可得
$\sum_{k\ge 1}\frac{(g_k^T d_k)^2}{\Vert d_k\Vert^2}=\sum_{k\ge 1}\frac{\overline{r}_i^2}{t_i}=\infty\tag{27}$
与 $~(17)~$ 相矛盾，故假设不成立，定理得证。

定理 2：设目标函数 $~f(x)~$ 下方有界，导数 $~\rm{Lipschitz}~$ 连续，考虑方法 $~(2)~$ 和 $~(3)~$ ，其中 $~\beta_k~$ 具有形式 $~(7)~$ ， $\alpha_k~$ 使得 $~(17)~$ 和 $~(18)~$ 成立
如果
$\sum_{k\ge 1}\frac{\Vert g_i\Vert^2}{\phi_k^2}=\infty\tag{28}$
则必有 $\lim_{k\rightarrow\infty}\inf\Vert g_k\Vert=0$
证明：注意到
$t_k\ge 0,~~\forall~k\ge 1\tag{29}$
利用 $~(11)~$ 和 $~(29)~$ 可推出
$-2\sum_{i-1}^k\frac{g_i^T d_i}{\phi_i^2}\ge\sum_{i=1}^k\frac{\Vert g_i\Vert^2}{\phi_i^2}\tag{30}$
利用
$-4g_i^T d_i-\Vert g_i\Vert^2\le\frac{4(g_i^T d_i)^2}{\Vert g_i\Vert^2}\tag{31}$
故有
$4\sum_{i=1}^k\frac{(g_i^T d_i)^2}{\Vert g_i\Vert^2\phi_i^2}\ge-4\sum_{i=1}^k\frac{g_i^T d_i}{\phi_i^2}-\sum_{i=1}^k\frac{\Vert g_i\Vert^2}{\phi_i^2}\ge\sum_{i=1}^k\frac{\Vert g_i\Vert^2}{\phi_i^2}\tag{32}$
从而若 $~(28)~$ 成立，利用 $~(32)~$ ，有
$\sum_{k\ge 1}\frac{(g_k^T d_k)^2}{\Vert g_k\Vert^2\phi_k^2}=\infty\tag{33}$
由于 $~(22)~$ 仍然成立，结合 $~(33)~$ 以及 引理 2，则有
$\sum_{k\ge 1}\frac{(g_k^T d_k)^2}{\Vert g_k\Vert^2\Vert d_k\Vert^2}=\infty\tag{34}$
若 $~(20)~$ 不成立，则 $~(25)~$ 成立。从而
$\sum_{k\ge1}\frac{(g_k^T d_k)^2}{\Vert d_k\Vert^2}=\sum_{k\ge 1}\frac{(g_k^T d_k)^2}{\Vert g_k\Vert^2\Vert d_k\Vert^2}\Vert g_k\Vert^2=\infty$
上式和 $~(17)~$ 矛盾，故假设不成立，定理得证。

这样我们对方法 $(7)$ 给出了两个一般性的定理，他们仅需要线搜索满足 $~\rm{Zoutendijk}~$ 条件(17)和下降方向(18)，而不需要强 $~\rm{Wolfe}~$ 条件或充分下降条件。当目标函数满足一定假设时，采取 $~\rm{Wolfe}~$ 线搜索的点列方法必然使得 $~\rm{Zoutendijk}~$ 条件(17)成立。因此为证共轭梯度法在 $~\rm{Wolfe}~$ 线搜索的收敛性，我们可以分两步来证，即先证每一步搜索方向的下降性，再证关系式 $~(19)~$ 和 $~(28)~$ 其中之一成立。如果采取广义线搜索，则只需证明关系式 $~(19)~$ 或 $~(28)~$ 成立即可。
对于 $~$ DY $~$ 方法，因为 $~\phi_k=-g_k^T d_k,\overline{r}_k=1~$ ，故 $~(19)~$ 成立。对于 $~$ FR $~$ 方法，因为 $~\phi_k=\Vert g_k\Vert^2~$ ，故当 $~\left\{\Vert g_k\Vert\right\}~$ 一致有界时， $~(28)~$ 成立。于是，利用 $~$ 定理1 $~$ 和 $~$ 定理2 $~$ 可立即获得 $~$ DY方法 $~$ 和 $~$ FR方法 $~$ 在适当函数假定下的全局收敛性。
对一般方法 $~(2)~$ 和 $~(3)~$ ，由于 $~\beta_k~$ 也可写为 $~(7)~$ 的形式，其中 $~\phi_k~$ 由 $~(8)~$ 定义。利用下面定理，便给出一个仅与参数 $~\beta_k~$ 有关的充分条件。

定理 3：设目标函数 $~f(x)~$ 下方有界，导数 $~\rm{Lipschitz}~$ 连续，考虑方法 $~(2)~$ 和 $~(3)~$ ，其中 $~\beta_k~$ 具有形式 $~(7)~$ ， $\alpha_k~$ 使得 $~(17)~$ 和 $~(18)~$ 成立。如果
$\sum_{k\ge 2}\prod \limits_{i=2}^k\beta_i^{-2}=\infty\tag{35}$
则必有 $\lim_{k\rightarrow\infty}\inf\Vert g_k\Vert=0$
证明：利用 $~(8)~$ 知， $(35)~$ 等价于
$\sum_{k\ge 2}\frac{1}{\phi_k^2}=\infty\tag{36}$
故若 $\lim_{k\rightarrow\infty}\inf\Vert g_k\Vert\neq 0$ ，则必有 $~(28)~$ 成立，从而由定理 $(2)$ 可知， $\lim_{k\rightarrow\infty}\inf\Vert g_k\Vert=0$ 。与假设矛盾，因此定理为真。

为了使用方便，我们利用定理1、定理2 和定理3 给出如下推论。
推论：设目标函数 $~f(x)~$ 下方有界，导数 $~\rm{Lipschitz}~$ 连续，考虑方法 $~(2)~$ 和 $~(3)~$ ，其中 $~\beta_k~$ 具有形式 $~(7)~$ ， $\alpha_k~$ 使得 $~(17)~$ 和 $~(18)~$ 成立。如果
$\prod_{i=2}^k\beta_i^2\le c\max \left\{1,\Vert g_k\Vert^2,(g_k^T d_k) \right\}k\tag{37}$
证明：条件 $~(37)~$ 表明
$\sum_{k\ge 2}\frac{ \max\left\{1,\Vert g_k\Vert^2,(g_k^T d_k) \right\}}{\phi_k^2}=\infty\tag{38}$
因此和式 $~\sum\frac{1}{\phi_k^2}~$ 、 $~\sum\frac{\Vert g_k\Vert^2}{\phi_k^2}~$ 和 $~\sum\frac{(g_k^T d_k)^2}{\phi_k^2}~$ 至少有一个发散。利用定理1、定理2 和定理3 其中之一知，此推论为真。