12、DY 共轭梯度法的一般性理论

本文与之前的 FR 共轭梯度法的一般性理论相类似，旨在建立 DY 共轭梯度法的一般性理论。这些工作也是由 戴彧虹 和 袁亚湘 完成。

1、简介

对于无约束优化问题
$\min_{x\in\mathbb{R}^n}~f(x)\tag{1}$
其中 $~f(x):\mathbb{R}^n\rightarrow\mathbb{R}~$ 是连续可微函数，其梯度函数记为 $~g(x):\mathbb{R}\rightarrow\mathbb{R}^n~$ .。其一般的迭代格式为:
$x_{k+1}=x_k+\alpha_k d_k\tag{2}$ ,
$d_k=\begin{cases} -g_k,\quad & k=1,\\ -g_k+\beta_k d_k, &k\ge 2,\end{cases}\tag{3}$
其中 $~g_k~$ 是迭代点 $~x_k~$ 处的梯度， $~\alpha_k~$ 是搜素步长， $~d_k~$ 是搜素方向， $~\beta_k~$ 为共轭参数。
考虑一般的 $~\beta_k~$ 与 $~\beta_k^{DY}~$ 的关系，定义
$\tau_k=\frac{\beta_k}{\beta_k^{DY}}\tag{4}$
$\beta_k^{DY}=\frac{\Vert g_k\Vert^2}{d_{k-1}^T(g_k-g_{k-1})}\tag{5}$
考虑 $~\rm{Wolfe}~$ 线搜索，即
$f(x_k+\alpha_k d_k)\le f(x_k)+\rho\alpha_k d_k\tag{6}$
$g(x_k+\alpha_k d_k)^Td_k\ge\sigma g_k d_k\tag{7}$

2、收敛性分析

定理：设目标函数 $~f(x)~$ 下方有界，导数 $~\rm{Lipschitz}~$ 连续，考虑方法 $~(2)~$ 和 $~(3)~$ ，其中步长 $~\alpha_k~$ 满足 $~\rm{Wolfe}~$ 条件 $~(6)~$ 和 $~(7)~$ ，参数 $~\beta_k~$ 使得
$\tau_k\in[-\frac{1-\sigma}{1+\sigma},1]\tag{8}$
成立，则有
$~\lim\inf\Vert g_k\Vert=0\tag{9}$
证明：将 $~(3)~$ 两端与 $~g_k~$ 作内积，并利用 $~(4)~$ 和 $~(5)~$ ，得
$g_k^T d_k=\frac{g_{k-1}^T d_{k-1}+(\tau_k-1)g_k^T d_{}k-1}{d_{k-1}^T (g_k-g_{k-1})}\Vert g_k\Vert^2\tag{10}$
再次应用 $~(4)~$ 和 $~(5)~$ ，并利用 $~(10)~$ ，知
$\beta_k=\tau_k\beta_k^{DY}=\frac{\tau_kg_k^T d_k}{g_{k-1}^T d_{k-1}+(\tau_k-1)g_k^T d_{k-1}}=\zeta_k\frac{g_k^T d_k}{g_{k-1}^T d_{k-1}}\tag{11}$
其中
$\zeta_k=\frac{\tau_k}{1+(\tau_k-1)l_{k-1}}\tag{12}$
$l_{k-1}=\frac{g_k^T d_{k-1}}{g_{k-1}^T d_{k-1}}\tag{13}$
令 $~r_k=-\frac{g_k^T d_k}{\Vert g_k\Vert^2}~$ ，则由 $~(10)~$ 式得
$r_k=\frac{1+(\tau_k-1)l_{k-1}}{1-l_{k-1}}\tag{14}$
由于 $~d_1=-g_1~$ ，故 $~r_1=1>0~$ 。设 $~r_{k-1}>0~$ ，故
$l_{k-1}\le\sigma\tag{15}$
利用 $~(14)~$ 和上式，得
$1+(\tau_k-1)l_{k-1}\ge 1+(-\frac{1-\sigma}{1+\sigma}-1)\sigma=\frac{1-\sigma}{1+\sigma}\tag{16}$
注意到 $~\sigma<1~$ ，故 $~r_k>0~$ ，从而根据归纳法， $~r_k>0~$ 对所有的 $~k\ge 1~$ 成立。
进一步，由 $(8)$ 和 $(16)$ ，有
$1+(\tau_k-1)l_{k-1}\ge-\tau_k\tag{17}$
另一方面，利用 $~(15)~$ 以及 $~\tau_k\le 1~$ ，知
$(1-\tau_k)(1-l_{k-1})\ge 0\tag{18}$
或者等价地，
$1+(\tau_k-1)l_{k-1}\ge\tau_k\tag{19}$
结合 $~(17)~$ 和 $~(19)~$ 两式，得
$\vert 1+(\tau_k-1)l_{k-1}\vert\ge\vert \tau_k\vert\tag{20}$
根据 $~\zeta_k~$ 的定义，必有
$\vert \zeta_k\vert\le 1\tag{21}$
故有
$\beta_k^2\le\frac{(g_k^T d_k)^2}{(g_{k-1}^T d_{k-1})^2}\tag{22}$
假定命题不成立，即存在 $~\gamma>0~$ ，对任意的 $~k\ge 1~$
$\Vert g_k\Vert\ge\gamma\tag{23}$
因为 $~d_k+g_k=\beta_k d_{k-1}~$ ，利用 $~(22)~$ 有
$\begin{align}\frac{\Vert d_k\Vert^2}{(g_k^T d_k)^2}&=\frac{\beta_k^2\Vert d_{k-1}\Vert^2}{(g_k^T d_k)^2}-\frac{\Vert g_k\Vert^2}{(g_k^T d_k)^2}-\frac{2}{g_k^T d_k}\\ &=\frac{\beta_k^2\Vert d_{k-1}\Vert^2}{(g_k^T d_k)^2}-(\frac{\Vert g_k\Vert}{g_k^T d_k}+\frac{1}{\Vert g_k\Vert})^2+\frac{1}{\Vert g_k\Vert^2}\\ &\le\frac{\beta_k^2\Vert d_{k-1}\Vert^2}{(g_k^T d_k)^2}+\frac{1}{\Vert g_k\Vert^2}\\ &\le\frac{\Vert d_{k-1}\Vert^2}{(g_{k-1}^T d_{k-1})^2}+\frac{1}{\Vert g_k\Vert^2}\end{align}\tag{24}$
根据递推，所有有
$\frac{\Vert d_k\Vert^2}{(g_k^T d_k)^2}\le\sum_{i=1}^k\frac{1}{\Vert g_i\Vert^2}\tag{25}$
利用 $~(23)~$ 和 $~(25)~$ ，我们有
$\frac{(g_k^T d_k)^2}{\Vert d_k\Vert^2}\ge\frac{\gamma^2}{k}\tag{26}$
根据 $~(26)~$ 有
$\sum_{k\ge 1}\frac{(g_k^T d_k)^2}{\Vert d_k\Vert^2}=\infty$
上式和 $~\rm{Zoutendijk}~$ 条件相矛盾，故假设不成立。命题得证

注：这个结论非常有用，戴彧虹和袁亚湘还表明，这个 $\tau_k\in[-\frac{1-\sigma}{1+\sigma},1]$ 这个界限在常数意义下是最优的，否则，会有反列。

利用上面定理，我们定义 $\rm{DY}$ 方法与 $\rm{HS}$ 方法的如下杂交共轭梯度法，其中 $~\rm{b}~$ 为参数
$\beta_k=\begin{cases} &-b\beta_k^{DY},~~&当~~\beta_k^{HS}<-b\beta_k^{DY}\\ &\beta_k^{HS},~~&当~~-b\beta_k^{DY}\le\beta_k^{HS}\le\beta_k^{DY}\\ &\beta_k^{DY},~~&当~~\beta_k^{HS}>\beta_k^{DY} \end{cases}$
分别取 $~b=\frac{1-\sigma}{1+\sigma}~$ 和 $~b=0~$ ，对每一种取值分别使用 $~\rm{Wolfe}~$ 线搜索和强 $~\rm{Wolfe}~$ 线搜索测试上面杂交算法。数值结果表明，当 $~\rm{b=0}~$ 并使用 $~\rm{Wolfe}~$ 线搜索时，上述杂交算法的计算效果最为理想，可以与 $~\rm{PRP}~$ 算法媲美，对于比较困难的优化问题，计算效果比 $~\rm{PRP}~$ 方法好得多。这表明在共轭梯度法领域中不使用传统的强 $~\rm{Wolfe}~$ 线搜索，而仅使用 $~\rm{Wolfe}~$ 线搜索，也能得到数值表现良好的共轭梯度法。
如果线搜索条件为 $~(6)~$ 和
$\sigma g_k^T d_k\le g(x_k+\alpha_k d_k)^T d_k\le 0$
其中 $~0<\rho<\sigma<1~$ ，这时利用上面线搜索与 $~\beta_k^{CD}~$ 和 $~\beta_k^{DY}~$ 的定义，知
$0\le\beta_k^{CD}\le\beta_k^{DY}$
根据上面定理，我们可以得出共轭下降法的收敛性理论，内容就不写了。

3、结束语

在此还想强调一下，上面定理非常有用。本文的参考文献如下
[1] Dai Y H , Yuan Y X. An efficient hybrid conjugate gradient method for unconstrained optimization[J]. 2001, Annals of Operations Research, 103, 33-47.
[2] 戴彧虹. 非线性共轭梯度法[M]. 科学出版社, 2000.

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

12、DY 共轭梯度法的一般性理论

1、简介

2、收敛性分析

3、结束语

推荐阅读更多精彩内容