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

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成，浏览时请结合常识与多方信息审慎甄别。
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

相关阅读更多精彩内容

友情链接更多精彩内容