6、FR 共轭梯度法在广义线搜索下的收敛性

在前面，我们介绍了 FR 共轭梯度法在精确线搜索，强 Wolfe 线搜索和推广的 Wolfe 线搜索下的收敛性。本节，将介绍 FR 共轭梯度法在广义 Wolfe 线搜索和广义 Armijo 线搜索下的收敛性。广义线搜索的本质是在迭代的过程中搜索方向不一定是下降方向，若是上升方向，我们取其反方向搜素。与标准线搜索 $~\alpha_k>0~$ 不同，广义线搜索是在直线 $~\left\{x_k+\alpha_k d_k:~\alpha\in\mathbb{R}^1 \right\}~$ 进行搜素。

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,&k=1,\\-g_k+\beta_k d_{k-1},&k\ge2,\end{cases}\tag{3}$
其中 $~\beta_k~$ 是参数。不同的 $~\beta_k~$ 决定不同的共轭梯度法。
1964 年，Fletcher 和 Reeves $^{[1]}$ 首次提出了解决非线性函数的共轭梯度法，我们称为 FR 共轭梯度法，其形式为
$\beta_k=\frac{\Vert g_k\Vert^2}{\Vert g_{k-1}\Vert^2}\tag{4}$

2、广义线搜索

接下来我们介绍一下广义线搜索
步 1：计算 $~g_k^T d_k~$ 的值
步 2：若 $~g_k^T d_k=0~$ ，令 $~\alpha_k=0~$ ，返回；
否则，令 $~p_k=\rm{sign}(-g_k^T d_k)d_k~$ 。
步 3：沿方向 $~\lambda>0~$ 作标准线搜索，得到步长 $~\lambda>0~$
步 4：令 $~\alpha_k=\rm{sign}(-g_k^T d_k)p_k~$ ，返回。

对于上面，若 $~g_k^T d_k<0~$ ，则广义线搜索就是标准线搜索；若 $~g_k^T d_k>0~$ ，即 $~d_k~$ 是上升方向，则我们沿 $~d_k~$ 进行标准线搜索；若 $~g_k^T d_k==0~$ ，则 $~\alpha_k=0~$ ，因 $g_{k+1}=g_k~$ 及 $~g_{k}^T d_k=0~$ ，我们有
$g_{k+1}^T d_{k+1}=-\Vert g_{k+1}\Vert^2+\beta_k g_{k+1}^T d_k=-\Vert g_{k+1}\Vert^2$
可见下一个搜素方向 $~d_{k+1}~$ 是下降方向， FR 方法仍可继续下去。因此，讨论广义线搜素是有必要的。有了上面的铺垫，我们现在来具体介绍两种线搜索，广义的 Wolfe 线搜索和广义 Armijo 线搜索。
广义 Wolfe 线搜索： 将步 3 改为如下，选择 $~\lambda_k>0~$ ，其中 $~0<\rho<\sigma<1~$
$f(x_k+\lambda_k p_k)-f(x_k)\le\rho\lambda_k g_k^T p_k$
$g(x_k+\lambda_k p_k)^Tp_k\ge\sigma g_k^T p_k$
广义 Armijo 线搜索： 将步 3 改为如下，选择 $~\lambda_k>0~$ ，其中 $~\lambda\in(0,1),~\rho\in(0,1)~$ 且 $~S=\left\{0,1,2,\dots\right\}~$
$\lambda_k=\lambda^m$
$m=\min\left\{m\in S:f(x)\right\}$
$m=\min\left\{m\in S:f(x_k+\lambda_k p_k)-f(x_k)\le\rho\lambda_k g_k^T p_k\right\}$

3、收敛性证明

假定：(1) 函数 $~f(x)~$ 水平集 $~\Omega=\left\{x\in\mathbb{R}^n:~f(x)\le f(x_1)\right\}~$ 有下界 (2) 梯度函数 $~g(x)~$ 是 Lipchitz 连续，即存在 $~L>0~$ 使得
$\Vert g(x)-g(y)\Vert\le L\Vert x-y\Vert,~~\forall~x,y\in \Omega$
引理 2：假定 $~x_1~$ 是假定的起点，考虑形如 (2) 的任意点列，其中 $~d_k~$ 是任意方向，步长 $~\alpha_k~$ 满足广义 Wolfe 线搜索，则
$\sum_{k\ge 1,\Vert d_k\Vert\neq0}\frac{(g_k^T d_k)^2}{\Vert d_k\Vert^2}<\infty$
证明：首先广义 Wolfe 线搜索可以等价于
$f(x_k)-f(x_k+\alpha_k d_k)\ge -\rho\alpha_k g_k^T d_k\ge 0\tag{1}$
$g(x_k+\alpha_k d_k)^T d_kg_k^T d_k\le\sigma(g_k^T d_k)^2\tag{2}$
由 (1) 可知
$\sum_{k\ge 1}\vert \alpha_k g_k^T d_k\vert<\infty\tag{3}$
从 (2) 中可以得到
$g_k^T d_k[g(x_k+\alpha_k d-k)-g(x_k)]^T d_k\le-(1-\sigma)(g_k^T d_k)^2$
利用上式可知
$\vert [g(x_k+\alpha_k d_k)-g(x_k)]^Td_k\vert\ge(1-\sigma)\vert g_k^T d_k\vert$
因为 $~g(x)~$ 是 $~\Omega~$ 上的 Lipschitz 常数，则有
$\vert \alpha_k \vert L \Vert d_k\Vert^2\ge (1-\sigma)\vert g_k^T d_k\vert\tag{4}$
利用 (3) 和 (4)，则命题得证。

引理 3：假定 $~x_1~$ 是假定的起点，考虑形如 (2) 的任意点列，其中 $~d_k~$ 是任意方向，步长 $~\alpha_k~$ 满足广义 Armijo 线搜索，定义 $~N_1(k)=\left\{k\in Z^+:\vert a_k\vert=1\right\}~$ 和 $~Z_2(k)=\left\{k\in Z^+:\vert a_k\vert\in(0,1)\right\}~$ ，其中 $~Z_k~$ 是所有正整数集合。则有
$\lim\sum_{i\in N_1(k)}\vert g_i^T d_i\vert<\infty$
$\lim\sum_{i\in N_2(k)}\frac{(g_i^T d_i)^2}{\Vert d_i\Vert^2}<\infty$
注：我们假定对于任意的 $~k~$ 都有 $~g_k\neq 0~$ ，故 $~d_k\neq 0~$ 。因为 $~d_k=0~$ ，则 $~d_{k+1}~$ 为最速下降方向。

引理 4：我们首先假定
$t_k=\frac{\Vert d_k\Vert^2}{\Vert g_k\Vert^4},~~~r_k=-\frac{g_k^T d_k}{\Vert g_k\Vert^2}$
对于 FR 共轭梯度法 (2)-(4)，对于任意的 $~k~$ 都有
$t_k=-\sum_{i=1}^k\frac{1}{\Vert g_i\Vert^2}+\sum_{i=1}^k\frac{2r_i}{\Vert g_i\Vert^2}$
证明：因为 $~d_1=-g_1~$ ，结论对 $~k=1~$ 显然成立。当 $~k\ge 2~$ 时，有
$\Vert d_i\Vert^2=\beta_i^2\Vert d_{i-1}\Vert^2-\Vert g_i\Vert^2-2g_i^T d_i$
将上式除以 $~\Vert g_i\Vert^4~$ ，并利用定义。
$t_i=t_{i-1}-\frac{1}{\Vert g_i\Vert^2}+\frac{2r_i}{\Vert g_i\Vert^2}$
归纳递推
$t_k=t_1-\sum_{i=2}^k\frac{1}{\Vert g_i\Vert^2}+\sum_{i=2}^k\frac{2r_i}{\Vert g_i\Vert^2}$
利用 $~t_1=\frac{1}{\Vert g_1\Vert^2}~$ 和 $~r_1=1~$ ，利用上式，很显然可证得结论。

引理 5：设 $~l>0~$ ， $c~$ 为常数。如果正项级数 $~\left\{a_i\right\}~$ 对所有的 $~k~$ 都成立
$\sum_{i=1}^ka_i\ge lk+c$
则有
$\sum_{i\ge 1}\frac{a_i^2}{i}=\infty$
$\sum_{k\ge 1}\frac{a_k^2}{\sum_{i=1}^ka_i}=\infty$
注：这个引理的证明可以参考文献 [1]

定理 1：假定 $~x_1~$ 是假定的起点，考虑形如 (2) 的任意点列，其中步长 $~\alpha_k~$ 满足广义 Wolfe 线搜索或者广义 Armijo 线搜索，若
$\sum_{k\ge 1}r_k^2=\infty$
则有 $~\lim\inf\Vert g_k\Vert=0~$

注 1：由前面的文章可知，如果线搜索是强 Wolfe 线搜索，且 $~\sigma<\frac{1}{2}~$ ，则存在常数 $~c>0~$ ，使得
$r_k\ge c,~~\forall~k\ge 1$
注 2：由前面的文章可知，如果线搜索是推广的 Wolfe 线搜索，若 $~\sigma_1+\sigma_2\le 1~$ ，则有
$r_k+r_{k+1}\ge c$
因此充分下降对于相邻的两次迭代至少一次成立

注 3：如果假定成立且 水平集有界，若 $~\lim\inf \Vert g_k\Vert\neq 0~$ ，则有
$\sum_{i=1}^kr_i\ge ck$
以上的式子表明充分下降对任意 $~k~$ 次的平均成立，我们依然可以通过构造矛盾，得出收敛性

$\color{red}{显然定理~1~ 中的条件要比注 1，2，3中的条件要弱，至于定理 ~6~的证明可参考后面文献。}$

推论 1：假定 $~x_1~$ 是假定的起点，考虑 FR 共轭梯度法 (2)、(3)、和 (4)，若 $~\alpha_k~$ 是由广义强 Wolfe 线搜索，其中 $~0<\rho<\sigma<1~$ ，我们有 $~\lim\inf\Vert g_k\Vert=0~$ 。

定理 2：假定 $~x_1~$ 是假定的起点，考虑 FR 共轭梯度法 (2)、(3)、和 (4)，若 $~\alpha_k~$ 是由广义 Wolfe 线搜索或者是广义 Armijo 线搜索，若
$\sum_{k\ge1}\frac{1}{\Vert g_k\Vert^2}=\infty$
则
$~\lim\inf\Vert g_k\Vert=0~$
注：这个定理我们也不加以证明，具体过程参考后面的文献

推论 2：假定 $~x_1~$ 是假定的起点，考虑 FR 共轭梯度法 (2)、(3)、和 (4)，若 $~\alpha_k~$ 是由广义 Wolfe 线搜索或者是广义 Armijo 线搜索，若 $~f(x)~$ 水平集有界，我们就有 $~\lim\inf\Vert g_k\Vert=0~$

推论 3：假定 $~x_1~$ 是假定的起点，考虑 FR 共轭梯度法 (2)、(3)、和 (4)，若 $~\alpha_k~$ 是由广义 Wolfe 线搜索或者是广义 Armijo 线搜索，若
$~\sum_{k\ge 1}\Vert x_{k+1}-x_k\Vert<\infty~$
则
$~\lim\inf\Vert g_k\Vert=0~$
证明：利用柯西不等式和条件，我们有
$\sum_{i=1}^k\Vert x_{k+1}-x_k\Vert\le c\sqrt{k}$
其中 $~c=(\sum_{i=1}^{\infty}\Vert x_{k+1}-x_k\Vert^2)^{\frac{1}{2}}~$
由于
$\Vert g_{k+1}\Vert-\Vert g_k\Vert\le\Vert g_{k+1}-g_k\Vert\le L\Vert x_{k+1}-x_k\Vert$
利用上递推和前面关系，我们可知
$\sum_{k\ge 1}\frac{1}{\Vert g_k\Vert^2}=\infty$

4、结束语

以上便是 FR 共轭梯度法在广义线搜索下的收敛性，包括广义 Wolfe 和广义 Armijo 线搜索。其中具体的定理的证明并未给出，可以参考如下文献。

[1] Pu D, Yu W. On the convergence properties of the DFP algorithms, Annals of Operations Research, 1990, 24: 175.
[2] 戴彧虹, 袁亚湘. 广义 Wolfe 线搜索下 Fletcher-Reeves 方法的收敛性. 高等学校计算数学学报，1996，142-148.
[3] Dai Y H. Further insight into the convergence of the Fletcher-Reeves method. 1999, Science in China, 905-916.

最后编辑于：2022.08.12 09:59:33

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

6、FR 共轭梯度法在广义线搜索下的收敛性

1、简介

2、广义线搜索

3、收敛性证明

4、结束语

推荐阅读更多精彩内容