17、取常数步长因子的 PRP 方法

上节我们证明了 $~\rm{PRP}~$ 方法在一种 $~\rm{Armijo}~$ 型线搜索下的全局收敛性。本节将证明取常数步长因子的 $~\rm{PRP}~$ 方法的收敛性。

1、引言

PRP 共轭梯度法是由 Polak 和 Ribiere 和 Polyak 在 1969 年独立提出的一种非线性共轭梯度法，这种方法具有如下形式：
$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^{PRP}=\frac{g_k^T(g_k-g_{k-1})}{\Vert g_{k-1}\Vert^2}.\tag{3}$
在 $~(16)~$ 节，我们证明了 $~\rm{PRP}~$ 方法在一种 $~\rm{Armijo}~$ 型线搜索下的全局收敛性。通过上节的如下关系式
$-c_2\Vert g_k\Vert^2\le g_k^T d_k\le -c_1\Vert g_k\Vert^2\tag{4}$
$\alpha_k\ge c\frac{\vert g_k^T d_k\vert}{\Vert d_k\Vert^2}\tag{5}$
$\Vert d_k\Vert\le (1+c_2\tau L)\Vert g_k\Vert\tag{6}$
不难看出存在某常数 $~c>0~$ ，使得
$\alpha_k\ge c,~~\forall~k\ge 1$
这表明了取常数步长因子的 $~\rm{PRP}~$ 方法也可能全局收敛。下面我们给出严格证明

2、收敛性分析

定理 1：设目标函数 $~f(x)~$ 下方有界，导数 $~\rm{Lipschitz}~$ 连续可微，考虑 $~\rm{PRP}~$ 方法 $~(1)-(3)~$ ，其中步长因子 $~\alpha_k~$ 总取为
$\alpha_k=\eta<\frac{1}{4L}\tag{7}$
则对所有的 $~k\ge 1~$ ，
$g_k^T d_k<0.\tag{8}$
进一步，方法在下述意义下全局收敛：
$\lim\inf\Vert g_k\Vert=0\tag{9}$
证明：首先用归纳法证明：对所有的 $~k\ge 1~$ 有下式成立：
$c_1\Vert g_k\Vert^2\le -g_k^T d_k\le c_2\Vert g_k\Vert^2\tag{10}$
以及
$c_1\Vert g_k\Vert\le\Vert d_k\Vert\le c_2\Vert g_k\Vert\tag{11}$
因为 $~d_1=-g_1~$ ，而且 $~c_1<1<c_2~$ ， $(10)~$ 和 $~(11)~$ 对 $~k=1~$ 显然成立。设 $(10)~$ 和 $~(11)~$ 对 $~k\ge 1~$ 成立。由 $~(2)~$ 、 $(3)~$ 、导数的 $~\rm{Lipschitz}~$ 连续性、 $(7)~$ 及归纳假设知
$\begin{align}\vert g_{k+1}^T d_{k+1}+\Vert g_{k+1}\Vert^2\vert&\le\Vert g_{k+1}\Vert^2\frac{\Vert g_{k+1}-g_k\Vert\Vert d_k\Vert}{\Vert g_k\Vert^2}\\ &\le\frac{L\alpha_k\Vert d_k\Vert^2\Vert g_{k+1}\Vert^2}{\Vert g_k\Vert^2}\\ &\le \eta c_2^2 L\Vert g_{k+1}\Vert^2 \end{align}\tag{12}$
从而可以选取 $~c_1~$ 和 $~c_2~$ ，使得 $~1+\eta c_2^2L=c_2~$ 以及 $~1-\eta c_2^2 L=c_1~$ ，则可令 $~c_2=\frac{1-\sqrt{1-4L\eta}}{2L\eta}\in(1,2)~$ 和 $~c_1=2-c_2\in(0,1)~$ 。利用 $~(12)~$ 知， $(10)~$ 对 $~k+1~$ 也成立。类似地，可证明
$\begin{align}\Vert d_{k+1}+g_{k+1}\Vert&=\Vert \beta_{k+1} d_k\Vert\\ &\le\frac{L\eta\Vert g_{k+1}\Vert\Vert d_k\Vert^2}{\Vert g_k\Vert^2}\\ &\le\eta c_2^2 L\Vert g_{k+1}\Vert \end{align}\tag{13}$
故 $~(11)~$ 式对 $~k+1~$ 亦成立。从而根据归纳法， $(10)~$ 和 $~(11)~$ 对所有的 $~k\ge 1~$ 都成立。同时 $~(10)~$ 也表明 $~(8)~$ 式成立。
现在估计目标函数 $~f(x)~$ 在每一步的下降量。利用中值定理、 $(7)~$ 以及导数的 $~\rm{Lipschitz}~$ 连续性知
$\begin{align}f_{k+1}-f_k&=\int_0^1g(x_k+t\eta d_k)^T (\eta d_k)\rm{dt}\\ &\le\eta g_k^T d_k+\int_0^1[~g(x_k+t\eta d_k)-g_k]^T(\eta d_k)\rm{dt}\\ &\le\eta[~g_k^T d_k+\frac{1}{2}L\eta\Vert d_k\Vert^2] \end{align}\tag{14}$
将 $~(2)~$ 式写成 $~d_k+g_k=\beta_k d_{k-1}~$ ，然后取模平方，得
$\Vert d_k\Vert^2=\beta_k^2\Vert d_{k-1}\Vert^2-\Vert g_k\Vert^2-2g_k^T d_k\tag{15}$
由 $~(13)~$ 及 $~c_2~$ 的选取知
$\beta_k^2\Vert d_{k-1}\Vert^2\le (\eta c_2^2L)^2\Vert g_k\Vert^2=(c_2-1)^2\Vert g_k\Vert^2\tag{16}$
在 $~(14)~$ 中应用 $~(10),(15),(16)~$ 以及 $~c_1=2-c_2~$ ，得
$\begin{align}f_{k+1}-f_k&\le g_k^T d_k(1-L\eta)+\frac{1}{2}L\eta(-\Vert g_k\Vert^2+\beta_k^2\Vert d_{k-1}\Vert^2)\\ &\le-c_1\Vert g_k\Vert^2(1-L\eta)+\frac{1}{2}L\eta(c_2^2-2c_2)\Vert g_k\Vert^2\\ &=-c_1(1-\frac{1}{2}L\eta c_1)\Vert g_k\Vert^2 \end{align}\tag{17}$
由 $~\eta<\frac{1}{4L}~$ 以及 $~c_1\in(0,1)~$ 知， $c_1(1-\frac{1}{2}L\eta c_1)>0~$ ，对于 $~(17)~$ 对 $~k=1,2\dots~$ 求和，并注意到目标函数有下界，知
$\sum_{k\ge1}\Vert g_k\Vert^2<\infty\tag{18}$
从而 $~(9)~$ 式得证。故命题成立。

3、参考文献

[1] 戴彧虹. 非线性共轭梯度法. 2000, 科学出版社.

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

17、取常数步长因子的 PRP 方法

1、引言

2、收敛性分析

3、参考文献

推荐阅读更多精彩内容