3、线性共轭梯度法

从这节开始，我们开始介绍线性共轭梯度法。首先，在此我想更正一下大家的认识。共轭梯度法分为线性共轭梯度法和非线性共轭梯度法，网上几乎所有的文章都将线性共轭梯度法看成是共轭梯度法，我认为这是不太准确的。线性共轭梯度法面对的函数是二次函数且采取的线搜索为精确线搜索，因此具有二次终止性。但是非线性共轭梯度法面对的函数是一般函数，且采取的线搜索可以是任意的线搜索，一般也不具备二次终止性。后面会详细介绍

1、引言

1952 年，Hestense 和 stiefel 在研究求解线性方程组
$A x=b\tag{1}$
其中 $~A\in\mathbb{R}^{n\times n}~$ 为正定矩阵， $~x,b\in\mathbb{R}^n~$ 时提出了一种新的算法，我们称为线性共轭梯度法，之所以叫这个名字，是因为它解决是线性方程组且取当前点的负梯度方向与前面搜索方向共轭化，后面会详细介绍。（求解 (1) 的方法之前就有主元法，高斯-赛德尔迭代法，雅可比迭代法，详细的可参考《数值分析》）
求解 (1) 的解等价于求解下面的一个二次函数的极小值
$f(x)=\frac{1}{2}x^T Ax-b^T x\tag{2}$
关于，(1) 和 (2) 这两个问题之所以会等价，这在前面的文章《最优化理论的基础》里面有谈到过。

2、共轭方向法

首先需明确的是共轭方向法是假定存在一组共轭方向，探讨是一般的性质问题。非线性共轭梯度法只是共轭方向法的一种而已，它教会我们如何构造共轭方向。所有对共轭方向法的探讨很有必要。

$\textbf{定义 1}$ ：设 $~A~$ 为 $~n~$ 阶对称正定矩阵， $~d_1,d_2,\dots,d_m(m\le n)~$ 为一组 $~n~$ 维向量组，如果
$d_i^T G d_j=0,~~i\neq j$
则称 $~d_1,d_2,\dots,d_m~$ 是 $~G~$ 共轭的.
如果 $~G=E~$ ，则共轭性就等价于正交性。显然，如果 $~d_1,d_2,\dots,d_m~$ 是 $~G~$ 共轭的，则他们是线性无关的。这个证明很简单，在此就不详细给出。

对于 (2) 中的问题，任给初始点 $~x_1~$ ，采用精确线搜索，即是采取如下迭代方式
$x_{k+1}=x_k+\alpha_k d_k\tag{3}$
$\alpha_k=\arg\min_{\alpha>0}~f(x_k+\alpha d_k)\tag{4}$
$\textbf{定理 2}$ ：对于 $~(2)~$ 中的函数，考虑 $~(3)~$ 和 $~(4)~$ ，则 $~(3)~$ 中的迭代至多进行 $~n~$ 步，且每一个迭代点 $~x_{k+1}~$ 都是 $~f(x)~$ 在 $~x_1~$ 和方向 $~d_1,d_2,\dots,d_k~$ 所张成的线性流形
$\left\{x~|~x=x_1+\sum_{j=1}^k\alpha_j d_j,~\forall~ \alpha_j\right\}$
中的极小点

$\textbf{证明}$ ：证明分为两步：
(1)、证明对所有的 $~k\le n~$ ，有
$g_{k+1}^T d_j=0,~~j=1,2,\dots,k\tag{5}$
由于
$~y_l=g_{l+1}-g_l=G(x_{l+1}-x_l)=\alpha_lG d_l~$
故当 $~j<k~$ 时有
$g_{k+1}^T d_j=g_{j+1}^Td_j+\sum_{l=j+1}^ky_l^Td_j=g_{j+1}^Td_j+\sum_{l=j+1}^k\alpha_ld_l^T G d_j=0$
$~\textbf{注}~$ ：上式中第一项为 $~0~$ 是由于精确线搜索，第二项为 $~0~$ 是由于共轭向量组。
当 $~j=k~$ 时， $~g_{k+1}^T d_k=0~$ ，故 $~(5)~$ 式成立。
(2)、证 $~x_{k+1}~$ 是 $~f(x)~$ 在线性流形上的极小点。设
$h(\alpha_1,\alpha_2,\dots,\alpha_k)=f(x_1+\sum_{j=1}^k\alpha_jd_j),~~x_{k+1}=x_k+\sum_{j=1}^k\hat{\alpha}_kd_k.$
那么
$\nabla h(\hat{\alpha}_1,\hat{\alpha}_2,\dots,\hat{\alpha}_k)=(g_{k+1}^Td_1,g_{k+1}^Td_2,\dots,g_{k+1}^Td_k)=0$
$\nabla^2h(\hat{\alpha}_1,\hat{\alpha}_2,\dots,\hat{\alpha}_k)=D_k^T GD_k$
其中 $~D_k=[d_1,d_2,\dots,d_k]~$ 。由于 $~d_1,d_2,\dots,d_n~$ 是线性无关的， $~D_k~$ 是列满秩，所有 $~D_k^TGD_k~$ 是正定的，故而 $~x_{k+1}~$ 是函数 $~h~$ 的极小值点。

$\textbf{注}$ ：(1)、上面的过程需要用到之前的《最优化理论的基础》
(2) 、由于 $~\mathbb{R}^n~$ 是 $~n~$ 维线性空间，那个线性无关的 $~d_1,d_2,\dots,d_n~$ 必定可以张成 $~n~$ 维线性空间，所有共轭方向法具有二次终止性，即是对于二次函数，采用精确线搜索，共轭方向法能够有限步终止。

3、共轭梯度法

共轭梯度法是著名的共轭方向法，它的基本思想是取当前点的负梯度方向与搜索方向进行共轭化，从而产生当前点的搜索方向。共轭梯度法需要较少的存储和计算量，所有处理无约束优化问题是非常有效的。
考虑一般的二次目标函数，其实这里写的有点啰嗦，与 (2) 等价
$f(x)=\frac{1}{2}x^T Gx+b^T x+c\tag{6}$
则其梯度
$g(x)=Gx+b\tag{7}$
令初始搜索方向为负梯度方向
$d_1=-g_1\tag{8}$
则
$x_2=x_1+\alpha_1 d_1\tag{9}$
其中 $~\alpha_1~$ 由精确线搜索得到，根据共轭方向法的性质，我们有 $~g_2^T d_1=0~$ ，令
$d_2=-g_2+\beta_2 d_1\tag{10}$
选择合适的 $~\beta_2~$ ，使得
$d_2^TGd_1=0$
在 (8) 式两边同时左乘 $~d_1^T G~$ 得
$\beta_2=\frac{g_2^T G d_1}{d_1^TGd_1}\tag{11}$
$\textbf{注:}$ 以上只是简单展示了 $~\beta_2~$ 是如何计算出来的，但是却很有必要，因为我们要通过数学归纳法来说明，网上有很多共轭梯度法的版本，都不严谨。

既然已知 $~\beta_2~$ ，由 $~(10)~$ 式，我们就可以知 $~d_2~$ ，再由精确线搜索，就可知 $~x_3~$ .
由前面共轭方向法，我们知 $~g_3^Td_1=0,~~g_3^T d_2=0~$ ，由 (8) 和 (10) 我们有
$g_3^T g_1=0,~g_3^T g_2=0,~g_1^T d_1=-g_1^T g_1,~g_2^T d_2=-g_2^T g_2$

现归纳假设已得到相互共轭的搜索方向 $~d_1,d_2,\dots,d_{k-1}~$ ，精确线搜索得到的步长为 $~\alpha_1,\alpha_2,\dots,\alpha_{k-1}~$ ，且满足
$d_{k-1}^TGd_i=0,~~i=1,2,\dots,k-2\tag{12}$
$g_{k}^Tg_i=0,~~g_{k}^T d_i=0,~~i=1,2,\dots,k-1\tag{13}$
$g_i^T d_i=-g_i^T g_i,~~i=1,2,\dots,k-1\tag{14}$
现令
$d_{k}=-g_{k}+\beta_kd_{k-1}+\sum_{i=1}^{k-2}\beta_{k,i}d_i\tag{15}$
其中 $~\beta_k,\beta_{k,i}(i=1,2,\dots,k-1)~$ 的选择满足
$d_k^TGd_i=0,~~i=1,2,\dots,k-1$
对 (15) 左乘 $~d_j^TG,~j=1,2,\dots,k-1~$ ，得
$\beta_k=\frac{g_k^TGd_{k-1}}{d_{k-1}^T Gd_{k-1}},~~\beta_{k,i}=\frac{g_k^T Gd_j}{d_j^T Gd_j},~~j=1,2,\dots,k-2$
利用 (13) 式，我们有
$\beta_{k,i}=\frac{g_k^T Gd_j}{d_j^TGd_j}=\frac{\alpha_jg_k^TGd_j}{\alpha_jd_j^TGd_j}=\frac{g_k^T(g_{j+1}-g_j)}{a_jd_j^TGd_j}=0\tag{16}$
设 $~x_{k+1}=x_k+\alpha_k d_k~$ ，其中 $~\alpha_k~$ 由精确线搜索得到，根据共轭方向法的 $\textbf{定理 2}$ ，我们有
$g_{k+1}^Td_i=0,~~i=1,2,\dots,k\tag{17}$
又由 $~d_i~$ 的表达式
$d_i=-g_i+\beta_id_{i-1}+\sum_{j=1}^{i-2}\beta_{ij}d_j$
与 (17) 相结合有
$g_{k+1}^Tg_i=0,~~i=1,2,\dots,k\tag{18}$
由 (16) 式和 (18) 式，我们就有
$g_{k+1}^Td_{k+1}=-g_{k+1}^Tg_{k+1}$
所以，我们便得到了一组由负梯度方向形成的共轭方向，形式如下
$d_k=\begin{cases}-g_1&k=1\\-g_k+\beta_k d_{k-1}&k\ge2\end{cases}\tag{19}$
$\beta_k=\frac{g_k^T G d_{k-1}}{d_{k-1}^TGd_{k-1}}\tag{20}$
若 $~f(x)~$ 为二次函数， $~\alpha_k~$ 采用精确线搜索，上面的 $~\beta_k~$ 等价于
$\beta_k^{HS}=\frac{g_k^T (g_k-g_{k-1})}{d_{k-1}^T(g_k-g_{k-1})}\tag{21}$
特别地，它是满足 (12)，（13）和（14）的关系。直白来说就是当前的搜索方向与前面的方向都共轭，当前点的梯度方向与前面的方向与梯度都正交，还有就是当前点的梯度与方向作内积是当前点梯度的欧式范数的平方（其实这是说明共轭梯度法产生的方向是充分下降的，以后肯定会详细介绍充分下降）

以上便是线性共轭梯度法的知识，到此也就结束了，不过在此提一下，我们的证明可能看似复杂，主要是我们还想表明共轭梯度法具有 (13) 和 (14) 的性质。

还有就是后面的推导的时候，我是分两个时间段写的，感觉不是很连贯。之所以没有参考书籍，因为 (19) 式很多书上描述的不一样，主要也就是系数的差别，其实也无关紧要，不过现在论文都是按照 (19) 式写，所以我也想统一一下。

最后编辑于：2022.08.10 19:51:22

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

3、线性共轭梯度法

1、引言

2、共轭方向法

3、共轭梯度法

推荐阅读更多精彩内容