8、CD 共轭梯度法

前面介绍了 FR 共轭梯度法，给出了其他不同线搜素下的全局收敛性。本节将讲述 CD 共轭梯度法，与 FR 的性质相类似，有了前面的基础，所以收敛性的证明很简单。
1987 年，Fletcher $^{[1]}$ 提出了 CD 共轭梯度法，也被称为共轭下降法。这种算法的独特优点在于使用强 Wolfe 条件，CD 共轭梯度法显然满足充分下降性，显然对于 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~$ 决定不同的共轭梯度法。
1987 年，Fletcher $^{[1]}$ 提出了 CD 共轭梯度法，其形式为
$\beta_k=\frac{\Vert g_k\Vert^2}{-g_{k-1}^Td_{k-1}}\tag{4}$
我们考虑推广的 Wolfe 线搜素，其条件为
$f(x_k)-f(x_k+\alpha_kd_k)\ge -\rho\alpha_kg_k^T d_k\tag{5}$
$\sigma_1g_k^T d_k\le g(x_k+\alpha_k d_k)^T d_k\le-\sigma_2g_k^T d_k\tag{6}$
其中参数 $~0<\rho<\sigma_1<1~$ 以及 $~0\le\sigma_2<1~$ 。显然，如果 $~\sigma_1=\sigma_2~$ ，则上述搜素条件就是强 Wolfe 条件，由 (3) 和 (4)，知
$-g_k^T d_k=\Vert g_k\Vert^2(1+\frac{g_k^Td_{k-1}}{g_{k-1}^T d_{k-1}})$
利用上式和 (6) 式，得
$1-\sigma_2\le\frac{-g_k^T d_k}{\Vert g_k\Vert^2}\le 1+\sigma_1\tag{7}$
从上式中的第一个不等式及 $~\sigma_2<1~$ ，则 $~d_k~$ 必为下降方向，并使得充分下降条件
$-g_k^T d_k\ge c\Vert g_k\Vert^2\tag{8}$
对某常数 $~c>0~$ 成立
在充分下降条件 (8) 和 Zoutendijk 条件成立的情况下，如果
$\sum_{k\ge 1}\frac{\Vert g_k\Vert^t}{\Vert d_k\Vert^2}=\infty\tag{9}$
对某 $~t\in [0,4]~$ 成立，不难推知收敛关系式 $~\lim\inf\Vert g_k\Vert=0~$ 成立。 $\color{red}{对于采取强 \rm{Wolfe} 非精确线搜素的共轭梯度法，下节我们给出一个一般性的定理。}$
$\color{red}{该定理表明，只要搜素方向下降，即}$
$\color{red}{g_k^T d_k<0,~~\forall~k\ge 1}$
$\color{red}{则 ~(9)~即可保证形如 (2) 和 (3) 方法的收敛性。这一结果并不需要方向 ~\rm{d_k}~是充分下降条件，而且适用于一般的共轭梯度法。 }$
设线搜素条件 (5) 和 (6) 中的参数满足
$\sigma_1<1,~~~\sigma_2=0\tag{10}$
根据 $~\beta_k^{FR}=\frac{\Vert g_k\Vert^2}{\Vert g_{k-1}\Vert^2}~$ 和 (4) 式及 (7) 式，不难看出
$0\le\beta^{CD}\le\beta_k^{FR}$
这时，类似于 FR 的收敛性，可证明
$\frac{\Vert d_k\Vert^2}{\Vert g_k\Vert^4}\le c\sum_{i=1}^k\frac{1}{\Vert g_i\Vert^2}$
对某常数 $~c>0~$ 成立，故如果方法不收敛，序列 $~\left\{\frac{\Vert d_k\Vert^2}{\Vert g_k\Vert^4}\right\}~$ 最多线性增长，从而 (9) 式成立，则 $~\lim\inf\Vert g_k\Vert=0~$ ，导致矛盾，因此当参数 $~\sigma_1~$ 和 $~\sigma_2~$ 满足 (10) 式时，共轭下降法必全局收敛。

2、收敛性分析

定理：设目标函数 $~f(x)~$ 下方有界，导数 $~\rm{Lipschitz}~$ 连续，考虑 CD 共轭梯度法 $~\rm{(2)-(4)}~$ ，其中步长因子 $~\alpha_k~$ 满足推广的 $\rm{Wolfe}$ 线搜素 $~\rm{(5)-(6)}~$ 。如果 $~\sigma_1<1~$ 且 $~\sigma_2=0~$ ，则有 $~\lim\inf\Vert g_k\Vert=0~$ 。

注：上述定理证明很简单，类似于 FR 共轭梯度法，不在此给出。对于 $~\sigma_1\ge 1~$ 和 $~\sigma_2>0~$ ，戴彧虹表明 CD 共轭梯度法会不收敛，因此 (10) 中的条件对于 CD 共轭梯度法的收敛性是充分必要的。这些反例的构造挺难的，我个人感觉不是很重要，也不想给出。

3、参考文献

[1] Fletcher R. Practical methods of optimization, vol I: unconstrained optimization[M]. New York: John Wiley and Sons, 1987.
[2] 戴彧虹. 非线性共轭梯度法[M]. 科学出版社, 2000.

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

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

8、CD 共轭梯度法

1、简介

2、收敛性分析

3、参考文献

推荐阅读更多精彩内容