7、FR 共轭梯度法的一般性理论

前面给出了 FR 共轭梯度法在强 Wolfe 线搜索、推广 Wolfe 线搜素和广义线搜素下的收敛性，本节将给出关于 FR 共轭梯度法的一般性理论，即与其他共轭梯度法的关系，得出一般性的收敛结果。

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}$
由于不同的 $~\beta_k~$ 决定不同的共轭梯度法，现在我们考虑与 FR 方法相关的一般共轭梯度法，若有
$\vert \beta_k\vert\le\beta_k^{FR}\tag{5}$
1992 年，Gilbert 和 Nocedal $^{[1]}$ 证明了在强 Wolfe 线搜素，即
$f(x_k+\alpha_k d_k)-f(x_k)\le\rho\alpha_k g_k^T d_k$
$\vert g(x_k+\alpha_k d_k)^T d_k\vert\le-\sigma g_k^T d_k$
且 $~0<\rho<\sigma<\frac{1}{2}~$ 时，满足 (5) 关系的 $\beta_k~$ 的共轭梯度法是充分下降并且全局收敛的。戴彧虹 $^{[2]}$ 推广到 $~0<\rho<\sigma\le\frac{1}{2}~$ 时，满足 (5) 关系的 $\beta_k~$ 的共轭梯度法是下降的并且全局收敛的。再后来就是由杜学武和徐成贤 $^{[3]}$ 推广到广义 Wolfe 线搜素，本质是很简单的，我之前也写过，不过后来发现被前人已经写了。在此，我们只是给出文 [2] 中的证明。

2、收敛性证明

定理：设目标函数 $~f(x)~$ 下方有界，导数 Lipschitz 连续。考虑 FR 共轭梯度法 (2)、(3) 和 (4) ，参数 $~\beta_k~$ 满足 (5)。如果 $~\sigma\le\frac{1}{2}~$ ，则方法在下述意义下全局收敛
$\lim\inf\Vert g_k\Vert=0$
证明：将 (3) 式两端与 $~g_k~$ 作内积，并利用 (5) 式得
$\frac{-g_k^T d_k}{\Vert g_k\Vert^2}=1-\frac{\beta_k}{\beta_k^{FR}}\frac{g_k^T d_{k-1}}{\Vert g_{k-1}\Vert^2}$
因为 $~\vert \beta_k\vert\le\beta_k^{FR}~$ ，由强 Wolfe 线搜素知
$1-\sigma\frac{\vert g_{k-1}^T d_{k-1}\vert}{\Vert g_{k-1}\Vert^2}\le\frac{-g_k^T d_k}{\Vert g_k\Vert^2}\le1+\sigma\frac{\vert g_{k-1}^T d_{k-1}\vert}{\Vert g_{k-1}\Vert^2}\tag{6}$
将上式第二个不等式递推，并注意到 $~\frac{-g_1^T d_1}{\Vert g_1\Vert^2}=1~$ ，得知
$\frac{-g_k^T d_k}{\Vert g_k\Vert^2}\le\frac{1-\sigma^k}{1-\sigma}\tag{7}$
对于所有的 $~k\ge 1~$ 成立，利用 (6) 的第一个不等式和 (7) 式以及 $~\sigma\le\frac{1}{2}~$ ，得
$\frac{-g_k^T d_k}{\Vert g_k\Vert^2}\ge\frac{1-2\sigma+\sigma^k}{1-\sigma}>0$
故每一个搜素方向均为下降方向。记
$r_k=\frac{-g_k^T d_k}{\Vert g_k\Vert^2}$
由 (6) 的第一个不等式可知，若 $~r_{k-1}\le\frac{1}{2}~$ ，则 $~r_k\ge 1-\frac{\sigma}{2}\ge \frac{1}{2}~$ ，从而必有
$\max\left\{r_{k-1},r_k\right\}\ge\frac{1}{2}$
由之前的内容可知或者后面会再次谈到这个问题，若 $~\sum_{k\ge 1}r_k^2=\infty~$ ，且 $~g_k^T d_k<0~$ ，则 $~\lim\inf\Vert g_k\Vert=0~$

3、结束语

这节内容很简单，但是却是 FR 共轭梯度法最有用的一节，也经常会用到。而且在此多说一句，如果 定理 1 中的 $~\vert \beta_k\vert\le\beta_k^{FR}~$ 这一界限在常数意义下不可被放宽，否则便会有反列表明算法不收敛。

参考文献
[1] Gilbert J C, Nocedal J. Global convergence properties of conjugate gradient methods for optimization[J]. SIAM, J Optimization, 1992, 2(1) : 21-42.
[2] 戴彧虹. 非线性共轭梯度法[M]. 科学出版社, 2000.
[3] 杜学武, 徐成贤. 由 FR 共轭梯度法控制的两类优化算法的全局收敛性[J]. 高等学校计算数学学报, 2000, 4: 311-318.

最后编辑于：2022.08.11 18:59:48

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念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

7、FR 共轭梯度法的一般性理论

1、简介

2、收敛性证明

3、结束语

推荐阅读更多精彩内容