19、两种 Armijo 类型线搜索

本节，我们将提出两种 $~\rm{Armijo}~$ 类型的线搜索，他们都是依据标准 $~\rm{Armijo}~$ 线搜索。本文的第一种 $~\rm{Armijo}~$ 线搜索且要求 $~\beta_k>0~$ 能够保证在每一步产生一个下降方向，在这种线搜索下， $\rm{FR}$ ， $\rm{CD}~$ 和 $~\rm{PRP}~$ 方法且 $~\beta_k~$ 非负都能够建立全局收敛性。然而我们如果想对原始的 $~\rm{PRP}~$ 方法建立全局收敛性，所以就有了第二种类型的 $~\rm{Armijo}~$ 线搜索。

1、引言

共轭梯度法的基本迭代形式为：
$x_{k+1}=x_k+\alpha_k d_k,\tag{1}$
$d_k=\begin{cases} -g_k,\quad & k=1,\\ -g_k+\beta_k d_k, &k\ge 2,\end{cases}\tag{2}$
其中参数 $~\beta_k~$ 由以下公式计算：
$\beta_k^{FR}=\frac{\Vert g_k\Vert^2}{\Vert g_{k-1}\Vert^2}\tag{3}$
$\beta_k^{CD}=\frac{\Vert g_k\Vert^2}{- g_k^T d_k}\tag{4}$
$\beta_k^{PRP}=\frac{g_k^T (g_k-g_{k-1})}{\Vert g_{k-1}\Vert^2}\tag{5}$
$\beta_k^{PRP^+}=\max\left\{~0,\beta_k^{PRP}\right\}\tag{6}$

2、第一种 Armijo 型线搜索的收敛性

线搜索 (A) : 给定常数 $~\lambda,\rho\in(0,1)~$ 且 $~\sigma_1\in (0,1]~$ ，取最小的整数 $~m\ge 0~$ ，步长因子 $~\alpha_k=\lambda^m~$ ，使其满足
$f(x_{k_{k+1}})-f(x_k)\le\rho\alpha_k g_k^T d_k\tag{7}$
$g_{k+1}^T d_{k+1}\le -\sigma_1\Vert g_k\Vert^2\tag{8}$
引理 1：若函数 $~f(x)~$ 在水平集上有界，且梯度函数 $~g(x)~$ 是 $~\rm{Lipschitz}~$ 连续的，考虑方法 $~(1)-(2)~$ ，其中 $~\beta_k\ge 0~$ 。考虑 线搜索 (A) 存在 $~\alpha_k>0~$ ，更进一步，我们有
$\alpha_k\ge \min\left\{1,c_1\frac{\vert g_k^T d_k\vert}{\Vert d_k\Vert^2}\right\}\tag{9}$
证明：因为 $~d_1=-g_1~$ ，故 $~d_1~$ 是下降方向，假定 $~d_k~$ 满足
$g_k^T d_k<0\tag{10}$
利用 $~(2)~$ ，则有
$\begin{align}g_{k+1}^T d_{k+1}=-\Vert g_{k+1}\Vert^2+\beta_{k+1} g_{k+1}^T d_k=-\Vert g_{k+1}\Vert^2+\beta_{k+1}[g_k^T d_k+(g_{k+1}-g_k)^T d_k]\end{align}\tag{11}$
因为 $~\sigma_1\in(0,1]~$ ，利用 $\beta_k\ge 0~$ ，要使 $~(8)~$ 式成立，则
$g_k^T d_k+(g_{k+1}-g_k)^T d_k\le 0\tag{12}$
利用 $~\rm{Lipschitz}~$ 连续，若
$g_k^T d_k+L\alpha_k\Vert d_k\Vert^2\le 0\tag{13}$
成立，则 $~(12)~$ 式必成立。利用 $~(10)~$ 式，故 $~\alpha_k~$ 满足
$\alpha_k\in (0,\frac{\vert g_k^T d_k\vert}{L\Vert d_k\Vert^2}]\tag{14}$
另一方面，根据中值定理和 $~\rm{Lipschitz}~$ 连续，有
$\begin{align}f(x_{k+1})-f(x_k)&=\int_0^1 g(x_k+t\alpha_k d_k)^T(\alpha_k d_k)\rm{dt}\\ &=\alpha_k g_k^T d_k+\int_0^1[g(x_k+t\alpha_k d_k)-g_k]^T(\alpha_k d_k)\rm{dt}\\ &\le \alpha_k g_k^T d_k+\frac{1}{2}L\alpha_k ^2\Vert d_k\Vert^2\end{align}\tag{15}$
要使 $~(7)~$ 式成立，即要求
$\alpha_k\in (0,\frac{2(1-\rho)}{L}\frac{\vert g_k^T d_k\vert}{\Vert d_k\Vert^2}]\tag{16}$
利用 $~(14)~$ 和 $~(16)~$ 知，存在这样的 $~\alpha_k>0~$ 满足 $~(7)~$ 和 $~(8)~$ 式。要使 $~(9)~$ 式成立，只须令
$c_1=\min\left\{\frac{1}{L},\frac{2(1-\rho)}{L}\right\}$
利用 $~(8)~$ 式，我们知道 $~(10)~$ 式定义合理，故引理得证。

利用 $~(8)~$ 式，定义
$r_k=\frac{-g_k^T d_k}{\Vert g_k\Vert^2}\tag{17}$
从而有
$\sum_{k\ge 1}r_k^2=\infty\tag{18}$
定理 2：若函数 $~f(x)~$ 在水平集上有界，且梯度函数 $~g(x)~$ 是 $~\rm{Lipschitz}~$ 连续的，考虑方法 $~(1)-(2)~$ ，其中 $~\beta_k=\beta_k^{FR}~$ 。考虑 线搜索 (A) ，则有
$\lim\inf\Vert g_k\Vert=0\tag{19}$
证明：主要是 $~\beta_k^{FR}=\frac{\Vert g_k\Vert^2}{\Vert g_{k-1}\Vert^2}>0~$ ，且利用 $~(8)~$ 式知道 $~(10)~$ 和 $~(18)~$ 式成立。结合之前在 $~FR~$ 共轭梯度法的结论，我们知结论成立。

如果我们假定的是水平集有界，而不是函数 $~f(x)~$ 在水平集有界，同样梯度函数 $~g(x)~$ 是 $~\rm{Lipschitz}~$ 连续的，则存在常数 $~\overline{\gamma}>0~$ ，使得
$\Vert g(x)\Vert\le\overline{\gamma}\tag{20}$
对于 $~FR~$ 共轭梯度法，我们将线搜索 (A) 中的 $~(8)~$ 替换成
$g_{k+1}^T d_{k+1}<0\tag{21}$
很明显 $~(21)~$ 比 $~(8)~$ 要弱，所以我们可以得到一个修正的线搜索。利用 $~(20)~$ ，我们有
$\sum_{k\ge 1}\frac{1}{\Vert g_k\Vert^2}=\infty\tag{22}$

定理 3：若水平集有界，且梯度函数 $~g(x)~$ 是 $~\rm{Lipschitz}~$ 连续的，考虑方法 $~(1)-(2)~$ ，其中 $~\beta_k=\beta_k^{FR}~$ 。考虑 线搜索 (A) 且将 $~(8)~$ 式替换成 $~(21)~$ 式，则有 $~(19)~$ 式成立。

证明：我们首先肯定的是这样修正的线搜索当然是存在 $~\alpha_k>0~$ 且 $~(9)~$ 式依然成立，故 $~\rm{Zoutendijk}~$ 条件成立。根据我们在前面分析的 $~\rm{FR}~$ 共轭梯度法的知识，知道该定理成立。这非常需要用到前面 $~\rm{FR}~$ 共轭梯度法的知识，不熟悉的可以回到前面看。

定理 4：若函数 $~f(x)~$ 在水平集上有界，且梯度函数 $~g(x)~$ 是 $~\rm{Lipschitz}~$ 连续的，考虑方法 $~(1)-(2)~$ ，其中 $~\beta_k=\beta_k^{CD}~$ 。考虑 线搜索 (A) 且 $~\sigma_1=1~$ ，则有 $~(19)~$ 式成立。
证明：利用 $~(8)~$ 式和 $~\sigma_1=1~$ ，以及 $~(3)~$ 和 $~(4)~$ ，我们知道
$0\le\beta_k^{CD}\le\beta_k^{FR}\tag{23}$
后面的证明，我也不是很明白，书上表述，应该是要在强 $~\rm{Wolfe}~$ 线搜索下，这个强 $~\rm{Wolfe}~$ 在收敛性的证明应该要用到。而此处没有，我个人也很奇怪。

下面考虑 $~\rm{PRP}~$ 共轭梯度法
定理 5：若函数 $~f(x)~$ 在水平集上有界，且梯度函数 $~g(x)~$ 是 $~\rm{Lipschitz}~$ 连续的，考虑方法 $~(1)-(2)~$ ，其中 $~\beta_k=\beta_k^{PRP}~$ 。考虑 线搜索 (A) ，则有 $~(19)~$ 式成立。
证明：假定存在一个无穷子列 $~\left\{k_i\right\}~$ 满足
$~\alpha_{k_i}=1,~~\forall~i\ge 1\tag{24}$
由于函数 $~f(x)~$ 有界且利用 $~(7)~$ 式和上式，有
$\lim_{i\rightarrow\infty} g_{k_i}^T d_{k_i}=0\tag{25}$
利用 $~(8)~$ 和 $~(25)~$ ，我们有
$\lim_{i\rightarrow\infty}\Vert g_i\Vert=0\tag{26}$
否则，利用 $~(9)~$ 式，我们假定
$\alpha_k\ge c_1\frac{\vert g_k^T d_k\vert}{\Vert d_k\Vert^2}\tag{27}$
对充分大的 $~k~$ 成立。利用函数 $~f(x)~$ 有界和 $~(7)~$ 式，我们可以得到 $~\rm{Zoutendijk}~$ 条件成立：
$\sum_{k\ge 1}\frac{(g_k^T d_k)^2}{\Vert d_k\Vert^2}<\infty\tag{28}$
后面的证明就和经典 $~\rm{PRP}~$ 证明相同。

3、第一种 Armijo 型线搜索的收敛性

线搜索 (A) : 给定常数 $~\lambda,\rho\in(0,1)~$ 且 $~\sigma_1\in (0,1)~$ ，取最小的整数 $~m\ge 0~$ ，步长因子 $~\alpha_k=\lambda^m~$ ，使其满足
$f(x_{k_{k+1}})-f(x_k)\le\rho\alpha_k g_k^T d_k\tag{29}$
$0\neq g_{k+1}^T d_{k+1}\le -\sigma_2\Vert d_k\Vert^2\tag{30}$
引理 6：若函数 $~f(x)~$ 在水平集上有界，且梯度函数 $~g(x)~$ 是 $~\rm{Lipschitz}~$ 连续的，考虑方法 $~(1)-(2)~$ ，其中 $~\beta_k=\beta_k^{PRP}~$ 。步长因子 $~\alpha_k~$ 由 线搜索 B 决定，则对于任意的 $~k~$ ，都存在 $~\alpha_k>0~$ ，更进一步，我们有
$\alpha_k\ge c_2\tag{31}$
其中 $~c_1~$ 是正常数
证明：因为 $~d_1=-g_1~$ 且 $~\sigma_2\in (0,1)~$ ，所以有
$g_k^T d_k\le -\sigma_2\Vert d_k\Vert^2\tag{32}$
对 $~k=1~$ 成立，假定 $~(32)~$ 对某个 $~k~$ 成立，利用 $~a^T b\le\Vert a\Vert\Vert b\Vert~$ ，对任意的 $~a,b\in\mathbb{R}^n~$ ，利用 $~(32)~$ 有
$\Vert d_k\Vert\le\sigma_2^{-1}\Vert g_k\Vert\tag{33}$
因为我们假定 $~(32)~$ 成立，故 $~d_k~$ 是下降方向 $~~$ (注意： $d_k=0$ ，则 $~x_{k+1}=x_k~$ )，依然想要 $~(15)~$ 式成立，利用 $~(32)~$ 式，则有
$f(x_{k+1})-f_k\le \rho\alpha_kg_k^Td_k~~\forall~\alpha_k\in(0,\frac{2\sigma_2(1-\rho)}{L})\tag{34}$
我们令 $~c_3=\frac{2\sigma_2(1-\rho)}{L}~$ .
利用 $~(2)、(5)~$ 和 $~\rm{Lipschitz}~$ 连续
$\Vert d_{k+1}\Vert\le\Vert g_{k+1}\Vert[1+\frac{L\alpha_k^2\Vert d_k\Vert^2}{\Vert g_k\Vert^2}]\tag{35}$
和
$-g_{k+1}^T d_{k+1}=\Vert g_{k+1}\Vert^2[1-\frac{g_{k+1}^T(g_{k+1}-g_k)}{\Vert g_k\Vert^2}\frac{g_{k+1}^Td_k}{\Vert g_{k+1}\Vert^2}]\ge\Vert g_{k+1}\Vert^2[1-\frac{L\alpha_k\Vert d_k\Vert^2}{\Vert g_k\Vert^2}]\tag{36}$
因此，我们选择一个正常数 $~c_4>0~$ ，使得
$1-c_4\ge \sigma_2(1+c_4^2)\tag{37}$
利用 $~(36)~$ 和 $~(37)~$ ，我们有
$g_{k+1}^T d_{k+1}\le -\sigma_2\Vert d_{k+1}\Vert^2,~~\forall~k\in(0,\frac{c_4\Vert g_k\Vert^2}{L\Vert d_k\Vert^2})\tag{38}$
由 $~(33),(34),(38)~$ ，我们知道 线搜索 B 能够决定一个正步长，而且满足 $~(31)~$ 式，只需令
$c_2=\left\{1,\lambda c_3,\frac{\lambda c_4\sigma_2^2}{L}\right\}\tag{39}$
$~(38)~$ 表明 $~(32)~$ 对 $~k+1~$ 也成立。因此，我们证明了该引理成立。

通过以上的引理，我们可以证明原始 $~\rm{PRP}~$ 共轭梯度法的强收敛性。而我们之前证明原始 $~\rm{PRP}~$ 共轭梯度法的强收敛性是依据如下条件
$f_{k+1}-f_k\le -\gamma\alpha_k^2\Vert d_k\Vert^2\tag{40}$

定理 7：若函数 $~f(x)~$ 在水平集上有界，且梯度函数 $~g(x)~$ 是 $~\rm{Lipschitz}~$ 连续的，考虑方法 $~(1)-(2)~$ ，其中 $~\beta_k=\beta_k^{PRP}~$ 。步长因子 $~\alpha_k~$ 由 线搜索 B 决定，则有
$\lim\Vert g_k\Vert=0\tag{41}$
证明：因为函数 $~f(x)~$ 在水平集上有界，所以从 $~(29),(31)~$ 可以知道
$\lim_{k\rightarrow\infty}g_k^T d_k=0\tag{42}$
利用 $~(30)~$ 和 $~(42)~$ ，有
$\lim_{k\rightarrow\infty}\Vert d_k\Vert=0\tag{43}$
利用 $~g(x)~$ 是 $~\rm{Lipschitz}~$ 连续的， $\alpha_k\le1~$ 和 $~(33)~$ ，有
$\Vert g_{k+1}\Vert\le\Vert g_k\vert+\Vert g_{k+1}-g_k\Vert\le\Vert g_k\Vert+L\alpha_k\Vert d_k\Vert\le(1+L\sigma_2^{-1})\Vert g_k\Vert\tag{44}$
进一步，利用 $~(2),(5),(33),(44)~$ 和 $~g(x)~$ 是 $~\rm{Lipschitz}~$ 连续的，有
$\begin{align}\Vert g_{k+1}\Vert&\le\Vert d_{k+1}\vert+\frac{\vert g_{k+1}^T(g_{k+1}-g_k)\vert}{\Vert g_k\Vert^2}\Vert d_k\Vert\\ &\le\Vert d_{k+1}\Vert+\frac{L\alpha_k^2\Vert d_k\Vert^2}{\Vert g_k\Vert^2}\Vert g_{k+1}\Vert\\ &\le\Vert d_{k+1}\Vert+L(1+L\sigma_2^{-1})\sigma_2^{-1}\Vert d_k\Vert\end{align}\tag{45}$
结合 $~(43)~$ 和 $~(45)~$ ，定理得证。

4、结束语

以上依据标准 $~\rm{Armijo}~$ 线搜索提出了两种 $~\rm{Armijo}~$ 类型的线搜索，并对经典的共轭梯度法建立起了全局收敛性，包括 $~\rm{PRP,CD,FR}~$ 共轭梯度法。但是我们不知道是否有相似的结果对于其他的共轭梯度法，特别是 $~\rm{HS}~$ 共轭梯度法。就我目前所知，没有一种线搜索能够保证对原始的 $~\rm{HS}~$ 共轭梯度法建立全局收敛性。参考文献如下
[1] Dai Yu Hong. Gonjugate gradient method methods with Armijo-type Line searchs.

19、两种 Armijo 类型线搜索

1、引言

2、第一种 Armijo 型线搜索的收敛性

3、第一种 Armijo 型线搜索的收敛性

4、结束语

推荐阅读更多精彩内容