5、FR 共轭梯度法

  今天,应该是正式研究共轭梯度法的开始。如果只是运用共轭梯度法,而不去了解其算法的内在含义,这也不是我在《简书》上面写作的意义。所以从现在开始我们探讨 FR 共轭梯度法。

摘要:主要介绍了 FR 共轭梯度法的收敛性,包括精确线搜索和非精确线搜索。精确线搜索选自 Zoutendijk 和 Powell 的收敛性证明,虽然都是精确线搜索,但是假定条件不同。非精确线搜索选自 Al-Baali 证明在强 Wolfe 条件下且~\sigma<\frac{1}{2}~时满足充分下降性,并给出全局收敛性。戴彧虹 和 袁亚湘 提出了推广的 Wolfe 线搜索,并证明~\sigma_1+\sigma_2\le 1~,则 FR共轭梯度法满足下降性和具有全局收敛性。最后还给出反列,表明~\sigma_1+\sigma_2\le 1~这一条件不能进一步放宽,不过反列我没有看太懂,就没有给出。

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}
1970 年 Zoutendijk^{[2]} 和 1984 年 Powell^{[3]} 分别给出了 FR 共轭梯度法在精确线搜索下的全局收敛性(\color\red{他们虽然结论都是在精确线搜索下,但是假定条件不同})。1985 年,AI-Baali^{[4]} 给出了 FR 共轭梯度法在强 Wolfe 线搜索下
f(x_k+\alpha_k d_k)-f(x_k)\le\rho\alpha_k g_k^Td_k\tag{5}
\vert g(x_k+\alpha_k)^Td_k\vert\le -\sigma g_k^T d_k\tag{6}
其中~0<\rho<\sigma<\frac{1}{2}~的全局收敛性。1993 年,刘光辉,韩继页,阴红霞^{[5]} 把这一结果推广到~\sigma=\frac{1}{2}~。1996 年,戴彧虹 和 袁亚湘^{[6]}进一步延申,证明在推广的 Wolfe 线搜索下,即是 (5) 式和
\sigma_1 g_k^T d_k\le g(x_k+\alpha_k d_k)^T d_k\le-\sigma_2g_k^T d_k\tag{7}
其中~0<\rho<\sigma_1<1,\sigma_2>0~,若~\sigma_1+\sigma_2\le 1~,可以证明 FR共轭梯度法在推广的 Wolfe 线搜索下的全局收敛性。显然可以看出,推广的 Wolfe 线搜索是强 Wolfe 线搜索的一种推广。
  值得注意的是,AI-Baali 的在证明全局收敛性的同时给出了充分下降性,而 戴彧虹 和 袁亚湘 虽然推广了结果,但是只是满足下降性。为了力求全面,本文给出 FR 共轭梯度法的四种证明,分别是 Zoutendijk 和 Powell 在精确线搜索下的收敛性, AI-Baali 和 戴彧虹在非精确线搜索下的收敛性。

2、 FR 在 精确线搜索下的收敛性(Zoutendijk)

定理 1:给定~x_1\in\mathbb{R}^n~,假定水平集~L=\left\{x\in\mathbb{R}^n~|~f(x)\le f(x_1)\right\}~有界,~\left\{x_k\right\}~是由 (2), (3) 和 (4) 产生的点列。若~f(x)~是一阶连续可微的,则 FR 共轭梯度法或有限步终止,或者~\lim_{k\rightarrow} g(x_k)=0~
证明:当序列~\left\{x_k\right\}~是有穷点列时,结论是显然的。现假设序列~\left\{x_k\right\}~是无穷点列,这时有~g(x_k)\neq 0~,由于~d_k=-g_k+\beta_k d_{k-1}~,故
g_k^T d_k=-\Vert g_k\Vert^2+\beta_k g_k^Td_{k-1}=-\Vert g_k\Vert^2<0
从而~d_k~是下降方向,~\left\{f(x_k)\right\}~是单调下降序列,~\left\{x_k\right\}\subset L~,所以~\left\{x_k\right\}~是有界点列,因此必有聚点。
  设~x^{*}~~\left\{x_k\right\}~的一个聚点,则存在子列~\left\{x_k\right\}_{k\in K_1}~收敛到~x^{*}~,这里~K_1~是子序列的指标集。由~f~的连续性知,对于~k\in K_1~
f(x^{*}=f(\lim_{k\in K_1,k\rightarrow\infty }x_k)=\lim_{k\in K_1,k\rightarrow\infty}f(x_k)=f^{*}
类似地,~\left\{x_{k+1}\right\}_{k\in K_1}~也是有界点列,故存在子列~\left\{x_{k+1}\right\}_{k\in K_2}~收敛到~\overline{x}^{*}~,这里~K_2\subset K_1~是无穷序列,并且对于~k\in K_2~,有
f(\overline{x}^{*})=f(\lim_{k\in K_2,k\rightarrow\infty} x_{k+1})=\lim_{k\in K_2,k\rightarrow\infty}f(x_{k+1})=\infty
于是
f(\overline{x}^{*})=f(x^*)=f^*
  现在,用反证法证明~g(x^{*})=0~,假定~g(x^*)\neq 0~,则对于充分小的~\alpha~,有
f(x^*+\alpha d^*)<f(x^*)
由于
f(x_{k+1})=f(x_k+\alpha_k d_k)\le f(x_k+\alpha d_k),~~\forall~\alpha>0
故对于~k\in K_2\subset K_1~,令~k\rightarrow\infty~,可得
f(\overline{x}^*)\le f(x^*+\alpha d^*)<f(x^*)
与上矛盾,从而证明~g(x^*)=0~,即~x^*~~f~的驻点。

3、 FR 在 精确线搜索下的收敛性(Powell)

引理 2:设目标函数~f(x)~有下界,导数~\nabla f(x)~满足 Lipschitz 条件
\Vert \nabla f(x)-\nabla f(y)\Vert\le L\Vert x-y\Vert,~~\forall~x,y\in\mathbb{R}^n
考虑一般方法~x_{k+1}=x_k+\alpha_k d_k~,其中~d_k~满足~g_k^T d_k<0~\alpha_k~满足 (5) 和
g(x_k+\alpha_k d_k)^T d_k\ge\sigma g_k^Td_k\tag{8}
则有
\sum_{k\ge 1}\frac{(g_k^T d_k)^2}{\Vert d_k\Vert^2}<\infty
上述关系式也被称为 Zoutendijk 条件.
证明:由 (8) 知
(g_{k+1}-g_k)^Td_k\ge(\sigma-1)g_k^T d_k
另一方面,由 Lipschitz 条件有
(g_{k+1}-g_k)^T d_k\le\alpha_kL\Vert d_k\Vert^2
利用以上两式得
\alpha_k\ge\frac{1-\sigma}{L}\frac{g_k^Td_k}{\Vert d_k\Vert^2}
利用上式和 (6) 式得
f_k-f_{k+1}\ge c\frac{(g_k^Td_k)^2}{\Vert d_k\Vert^2}
其中~c=\frac{\rho(1-\sigma)}{L}~,对上式从~k=1,2,\dots~求和,注意~f(x)~下方有界,即知 Zoutendijk 条件成立。

定理 3:设目标函数~f(x)~有下界,导数 Lipschitz 连续。考虑 FR 共轭梯度法 (2) , (3) 和 (4),其中步长因子~\alpha_k~由精确线搜索求出,如果对~k\ge 1,~g_k\neq 0~,则
\lim_{k\rightarrow \infty} \inf\Vert g_k\Vert=0
证明:由于采用的是精确线搜索,令~\theta_k=<-g_k,d_k>~即有
\Vert d_k\Vert=\sec\theta_k\Vert g_k\Vert
\beta_{k+1}\Vert d_k\Vert=\tan\theta_{k+1}\Vert g_{k+1}\Vert
利用上面两式和 (4) 式,消除~\Vert d_k\Vert~,可得
\tan\theta_{k+1}=\sec\theta_{k}\Vert g_{k+1}\Vert/\Vert g_k\Vert
将上式平方,并注意到~\sec^2\theta_k=1=\tan^2\theta_k~,便有
\frac{tan^2\theta_{k+1}}{\Vert g_k\Vert^2}=\frac{1}{\Vert g_k\Vert^2}+\frac{\tan^2\theta_k}{\Vert g_k\Vert^2}
利用上式递推,得
\frac{\tan^2\theta_k}{\Vert g_k\Vert^2}=\frac{\tan\theta_1}{\Vert g_k\Vert^2}+\sum_{i=1}^{k-1}\frac{1}{\Vert g_i\Vert^2}\tag{9}
若定理不真,则必存在某常数~\gamma>0~,使得对所有的~k\ge 1~都有
\Vert g_k\Vert\ge\gamma\tag{10}
在 (9) 式中运用上式,可得
\frac{\tan^2\theta_k}{\Vert g_k\Vert^2}\le\frac{k}{\gamma^2}
上式表明
\sum_{k\ge1}\Vert g_k\Vert^2\cot^2\theta_k=\infty\tag{11}
利用夹角~\theta_k~的定义,可将 Zoutendijk 条件写成
\sum_{k\ge1}\Vert g_k\Vert^2\cos^2\theta_k<\infty\tag{12}
由上式和 (10) 式可知
\lim_{k\rightarrow\infty}\cos\theta_k=0
故对充分大的~k~,有
\cot^2\theta_k\le2\cos^2\theta_k
利用上式和 (11) 式,有
\sum_{k\ge1}\Vert g_k\Vert^2\cos^2\theta_k=\infty
上式和 (12) 式相矛盾,故假设不成立,命题得证。

4、FR共轭梯度法在强 Wolfe 线搜索的收敛性(AI-Baali)

引理 4:考虑 FR 共轭梯度法 (2)、(3) 和 (4),其中步长因子~\alpha_k~满足 (5) 和 (6). 如果参数~\sigma<\frac{1}{2}~,则对所有的~k~,有下式成立:
\frac{1-2\sigma+\sigma^2}{1-\sigma}\le\frac{-g_k^T d_k}{\Vert g_k\Vert^2}\le\frac{1-\sigma^k}{1-\sigma}
证明:用归纳法,当~k=1~时,因为~d_1=-g_1~,结论显然成立。现在假设对任何~k-1~结论都成立。将 (3) 式与~g_k~作内积,并利用 (4) 式,得
\frac{-g_k^T d_k}{\Vert g_k\Vert^2}=1-\frac{g_k^Td_{k-1}}{\Vert g_{k-1}\Vert^2}
在上式中利用 (6) 式,得
1+\sigma\frac{g_{k-1}^Td_{k-1}}{\Vert g_{k-1}\Vert^2}\le\frac{-g_k^Td_k}{\Vert g_k\Vert^2}\le1-\sigma\frac{g_k^Td_{k-1}}{\Vert g_{k-1}\Vert^2}
利用上式和归纳假设,我们有
\frac{-g_k^Td_k}{\Vert g_k\Vert^2}\ge1-\sigma\frac{1-\sigma^{k-1}}{1-\sigma}\ge\frac{1-2\sigma-\sigma^k}{1-\sigma}
\frac{-g_k^Td_k}{\Vert g_k\Vert^2}\le1+\sigma\frac{1-\sigma^{k-1}}{1-\sigma}=\frac{1-\sigma^k}{1-\sigma}
故结论对所有的~k~都成立,引理得证。

定理 5:设目标函数~f(x)~有下界,导数 Lipschitz 连续,考虑 FR 共轭梯度法 (2)、(3) 和 (4),其中步长因子~\alpha_k~满足强 Wolfe 线搜索 (5) 和 (6)。如果参数~\sigma<\frac{1}{2}~,则有~\lim\inf\Vert g_k\Vert=0~
证明:对 (3) 式两端取模平方,得
\Vert d_k\Vert^2=\Vert g_k\Vert^2-2\beta_kg_k^Td_{k-1}+\beta^2_k\Vert d_{k-1}\Vert^2
上式除以~\Vert g_k\Vert^4~,记~t_k=\frac{\Vert d_k\Vert^2}{\Vert g_k\Vert^4}~,并利用 (5) 式
t_k=t_{k-1}+\frac{1}{\Vert g_k\Vert^2}(1-\frac{2g_k^Td_{k-1}}{\Vert g_{k-1}\Vert^2})
利用 (6) 式和 引理 4
\frac{\vert g_k^T d_{k-1}\vert}{\Vert g_{k-1}\Vert^2}\le\frac{\sigma\vert g_k^T d_{k-1}\vert}{\Vert g_{k-1}\Vert^2}\le\frac{\sigma}{1-\sigma}
则有
t_k\le t_{k-1}+\frac{1+\sigma}{1-\sigma}\frac{1}{\Vert g_k\Vert^2}
注意到~t_1=\frac{1}{\Vert g_k\Vert^2}~,递推
t_k\le\frac{1+\sigma}{1-\sigma}\sum_{i=1}^k\frac{1}{\Vert g_i\Vert^2}
若定理不真,则必存在常数~\gamma>0~,使得
\Vert g_k\Vert\ge\gamma,~~\forall~k\ge 1
结合上面两式得
t_k\le\frac{(1+\sigma)k}{(1-\sigma)\gamma^2}
可见,~t_k~最多线性增长。于是
\sum_{k\ge1}t_k^{-1}=+\infty
上式和 引理 3 矛盾,故结论成立。
注:引理 4 中,我们可以看出,结论对~\sigma=\frac{1}{2}~仍然成立,但此时我们仅仅能推出
\frac{-g_k^T d_k}{\Vert g_k\Vert^2}\ge(\frac{1}{2})^{k-1}
此时,充分下降条件就不再成立。虽然如此,我们可以证明,只要每一个方向均下降,则采取强 Wolfe 线搜索的 FR 共轭梯度法每相邻两个迭代点列中必有一个使得充分下降成立成立,进而可证 FR 方法的全局收敛性。

5、FR共轭梯度法在推广的 Wolfe 线搜索的收敛性(戴彧虹 和 袁亚湘)

定理 6:设目标函数~f(x)~有下界,导数 Lipschitz 连续,考虑 FR 共轭梯度法 (2)、(3) 和 (4),其中步长因子~\alpha_k~满足推广的 Wolfe 线搜索 (5) 和 (7),如果
g_k^T d_k<0,~~\forall~k\ge1
则有~\lim\inf\Vert g_k\Vert=0~
证明:因为~k\ge 2~时,~d_k=-g_k+\beta_k d_{k-1}~,利用 (4) 式,则有
\frac{-g_k^T d_k}{\Vert g_k\Vert^2}=1-\frac{g_k^Td_{k-1}}{g_{k-1}^Td_{k-1}}
利用 (7) 式,定义~r_k=\frac{-g_k^T d_k}{\Vert g_k\Vert^2}~,则有
1-\sigma_2r_{k-1}\le r_k\le1+\sigma_1 r_{k-1}\tag{13}
根据上面的第一个不等式,我们有
1\le r_k+\sigma_2r_{k-1}\Rightarrow r_k^2+r_{k-1}^2\ge\frac{1}{(1+\sigma^2)}>0
利用第二个不等式,有
r_k\le\frac{1}{1-\sigma_1}\tag{14}
利用上式和~d_k=-g_k+\beta_k d_{k-1}~,我们有
\begin{align}\Vert d_k\Vert^2&=\Vert g_k\Vert^2+\beta_k^2\Vert d_{k-1}\Vert^2-2\beta_k g_k^T d_{k-1}\\ &=\Vert g_k\Vert^2+\frac{\Vert g_k\Vert^4}{\Vert g_{k-1}\Vert^4}\Vert d_{k-1}\Vert^2-2\frac{\Vert g_k\Vert^2}{\Vert g_{k-1}\Vert^2}g_k^Td_{k-1}\\ &\le\Vert g_k\Vert^2+\frac{\Vert g_k\Vert^4}{\Vert g_{k-1}\Vert^4}\Vert d_{k-1}\Vert^2-2\sigma_1\frac{\Vert g_k\Vert^2}{\Vert g_{k-1}\Vert^2}g_{k-1}^T d_{k-1}\\ &=\Vert g_k\Vert^2+\frac{\Vert g_k\Vert^4}{\Vert g_{k-1}\Vert^4}\Vert d_{k-1}\Vert^2+2\sigma_1r_{k-1}\Vert g_k\Vert^2\\ &\le\frac{\Vert g_k\Vert^4}{\Vert g_{k-1}\Vert^4}\Vert d_{k-1}\Vert^2+\frac{1+\sigma_1}{1-\sigma_1}\Vert g_k\Vert^2 \end{align}
~t_k=\frac{\Vert d_k\Vert^4}{\Vert g_k\Vert^4}~,利用上式,有
t_k\le t_{k-1}+\frac{1+\sigma_1}{1-\sigma_1}\frac{1}{\Vert g_k\Vert^2}
由于~t_1=\frac{1}{\Vert g_1\Vert^2}~,所以上式有
t_k\le\frac{1+\sigma_1}{1-\sigma_1}\sum_{i=1}^k\frac{1}{\Vert g_i\Vert^2}
假设~\lim\inf\Vert g_k\Vert\neq 0~,即存在~\gamma>0~,对任意的~k\ge 1~,都有
\Vert g_k\Vert\ge\gamma
从而有
t_k\le c k
其中~c=\frac{1}{\gamma^2}\frac{1+\sigma_1}{1-\sigma_1}~
上式表明
t_{2k}\ge\frac{1}{2ck}
t_{2k-1}\ge\frac{1}{c(2k-1)}\ge\frac{1}{2ck}
则有
\begin{align} \sum_{k\ge 1}\frac{(g_k^T d_k)^2}{\Vert d_k\Vert^2}&=\sum_{k\ge 1}\frac{r_k^2}{t_k}\\ &=\sum_{k\ge 1}(\frac{r_{2k}^2}{t_{2k}}+\frac{r_{2k-1}^2}{t_{2k-1}})\\ &\ge\sum_{k\ge1}(\frac{r_k^2}{2ck}+\frac{r_{2k-1}^2}{2ck})\\ &=+\infty \end{align}
与 Zoutendijk 条件相矛盾,故假设不成立,命题得证。

定理 7:设目标函数~f(x)~有下界,导数 Lipschitz 连续,考虑 FR 共轭梯度法 (2)、(3) 和 (4),其中步长因子~\alpha_k~满足推广的 Wolfe 线搜索 (5) 和 (7),若~\sigma_1+\sigma_2\le 1~,则
g_k^Td_k<0
证明:~k=1~时,~d_1=-g_1~,则~g_1^T d_1<0~。假设结论对~k-1~时成立,则
r_k\ge 1-\sigma_2 r_{k-1}> 1-\sigma_2\frac{1}{1-\sigma_1}=\frac{1-\sigma_1-\sigma_2}{1-\sigma_1}
~\sigma_1+\sigma_2<1~,则~r_k>0~,从而~d_k~是下降方向,命题得证

6、参考文献

[1] Fletcher R, Reeves C. Function minimization by conjugate gradients. Comput J, 1964, 7 ,149-154.
[2] Zoutendijk. Nonlinear programing, computational methods. Integer and Nonlinear Programming. Amsterdam: North-Holland, 1970,37-86.
[3] Powell. Nonconvex minimization calculations and the conjugate gradient method. Lecture Notes in Mathematics, 1984, 122-141.
[4] Liu G H, Han J Y, Yin H X. global convergence of the Fletcher-Reeves algorithm with an inexcat line search. Institute of Applied Mathematics, 1993.
[5] Dai Y H, Yuan Y X. Convergence properties of the Fletcher-Reeves method. IMA Journal of Numerical Analysis, 1996,16,155-164

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念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

推荐阅读更多精彩内容