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.

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 202,056评论 5赞 474
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 84,842评论 2赞 378
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 148,938评论 0赞 335
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 54,296评论 1赞 272
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 63,292评论 5赞 363
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 48,413评论 1赞 281
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 37,824评论 3赞 393
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,493评论 0赞 256
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 40,686评论 1赞 295
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,502评论 2赞 318
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 37,553评论 1赞 329
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,281评论 4赞 318
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 38,820评论 3赞 305
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 29,873评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,109评论 1赞 258
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 42,699评论 2赞 348
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,257评论 2赞 341

19、两种 Armijo 类型线搜索

1、引言

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

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

4、结束语

推荐阅读更多精彩内容