10、DY 共轭梯度法

这篇文章很早就在 CSCD 上面发表过，所以我就直接复制过来了。DY 共轭梯度法是由中国学者 戴彧虹 和 袁亚湘 提出来的，可以说是我们这个方向非常经典的文章，这两位大师在国际优化领域也大放光彩。戴彧虹 目前是中国《运筹学学会》会长，袁亚湘 是中科院院士。目前共轭梯度法里面的很多经典文章是出自于这两位大师之手。

1、简介
1952 年，Hestense 和 Stiefel 在求解线性方程组 AX=b 时提出了共轭梯度法，我们称为线性共轭梯度法。1964 年，Fletcher 和 Reeves 将共轭梯度法应用到求解二次函数的局部极小点问题中，这通常被认为是求解无约束优化问题的非线性共轭梯度法的开端。共轭梯度法由于只是需要一阶导数信息，所以具有存贮量小的特点，适合求解大型无约束无约束优化问题。
对于无约束优化问题
$\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~$ 决定不同的共轭梯度法，本文想说明的是 $~DY~$ 算法，其他算法便不在此处列出。
$\beta_k^{DY}=\frac{\Vert g_k\Vert^2}{d_{k-1}(g_k-g_{k-1})}\tag{4}$
决定步长 $~\alpha_k~$ 的线搜索此处仅给出两种
标准 Wolfe 线搜索
$f(x_k+\alpha_k d_k)\le f(x_k)+\rho\alpha_k d_k\tag{5}$
$g(x_k+\alpha_k d_k)^Td_k\ge\sigma g_k d_k\tag{6}$
强 Wolfe 线搜索
$f(x_k+\alpha_k d_k)\le f(x_k)+\rho\alpha_k d_k\tag{7}$
$\vert g(x_k+\alpha_k d_k)^Td_k\vert\le-\sigma g_k d_k\tag{8}$
其中 $~0<\rho<\sigma<1~$ .

2、DY 共轭梯度法的框架和假定
基于公式(2),(3),(4)和标准 Wolfe 线搜索 (5) 和 (6)，给出 DY 共轭梯度法的算法框架.
DY 共轭梯度法
步1：给定初始点 $~x_1\in\mathbb{R}^n~$ ， $\forall~\epsilon>0$ ， $~0<\rho<\sigma<1~$ ，令 $~d_1=-g_1$ ， $~k:=1~$ ，若 $~g_1<\epsilon~$ ，终止.
步2：由标准 Wolfe 线搜索 (5) 和 (6) 计算步长因子 $~\alpha_k~$ .
步3：迭代计算 $~x_{k+1}=x_k+\alpha_k d_k~$ ， $~g_{k+1}:=g(x_{k+1})~$ ，若 $~\Vert g_{k+1}\Vert\le\epsilon~$ ，终止.
步4：令 $~k:=k+1~$ ，转步2.

假定：(1) 函数 $~f(x)~$ 在水平集 $~\varOmega=\left\{x\in\mathbb{R}^n:f(x)\le f(x_1)\right\}~$ 上有下界.

(2) 在水平集 $~\varOmega~$ 的某个邻域 $~N~$ 上， $~f(x)~$ 的梯度函数 $~g(x)~$ 是 $~Lipschitz~$ 连续，存在常数 $~L>0~$ ，使得
$\Vert g(x)-g(y)\Vert\le L \Vert x-y\Vert,~~~\forall~x,y\in N\tag{9}$

2、DY共轭梯度法的收敛性证明
定理1： 设目标函数 $~f(x)~$ 有下界，梯度函数 $~g(x)~$ 满足 $~Lipschitz~$ 连续，考虑一般方法 $~x_{k+1}=x_k+\alpha_k d_k~$ ，其中 $~d_k~$ 满足 $~g_k^T d_k<0~$ ，步长因子 $~\alpha_k~$ 满足 (5) 和 (6)，则有
$\sum_{k\ge 1}\frac{(g_k^T d_k)^2}{\Vert d_k\Vert^2}<+\infty\tag{10}$
证明： 由 (6) 可知
$(g_{k+1}-g_k)^Td_k\ge (\sigma-1)g^T d_k$
另一方面，由 Lipchitz 条件 (9) 有
$(g_{k+1}-g_k)^T d_k\le\Vert g_{k+1}-g_k\Vert\Vert d_k\Vert\le\alpha_kL\Vert d_k\Vert^2$
利用上面两式得
$\alpha_k\ge\frac{\sigma-1}{L}\frac{g_k^Td_k}{\Vert d_k\Vert^2}$
由上式和 (5) 式得
$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)$ 有下界，则命题成立。
注：关系式 (10) 也被称为 $Zoutendijk$ 条件.

定理2：考虑方法 (2) 和 (3)，其中 $~\beta_k~$ 按 $~(4)~$ 计算， $~\alpha_k~$ 满足 (5) 和 (6)，则或者 $~g_k=0~$ 对某 $~k~$ 成立，或者
$g_k^T d_k<0,~~~\forall k>1\tag{11}$
证明： 假设对所有的 $~k\ge 1~$ ，均有
$\Vert g_k\Vert>0$
当 $~k\ge 2~$ 时， $~d_k=-g_k+\beta_k^{DY}d_{k-1}~$ ，两端与 $~g_k~$ 做内积。
$g_k^T d_k=-\Vert g_k\Vert^2+\beta_k^{DY}g_k^T d_{k-1}=\Vert g_k\Vert^2\frac{g_{k-1}^T d_{k-1}}{d_{k-1}^T(g_k-g_{k-1})}=\beta_k^{DY}g_{k-1}^T d_{k-1}\tag{12}$
因为 $~d_1=-g_1~$ ， $(11)$ 显然对 $~k=1~$ 成立。假设 $~g_{k-1}^Td_{k-1}<0~$ ，由 (6)式可知， $d_{k-1}^T(g_k-g_{k-1})>0$ ，故 $\beta_k^{DY}>0$ 。
由假设，可知 $~g_k^T d_k<0~$ ，利用数学归纳法，则 (11) 成立。
注：(1) 表明 DY 共轭梯度法可以保证每个迭代点的满足 $~g_k^T d_k<0~$ ，也即 $d_k$ 为 $f(x)$ 在 $~x_k~$ 处的下降方向
(2) 我们可有式 (12) 知 $~\beta_k^{DY}=\frac{g_k^T d_k}{g_{k-1}^T d_{k-1}}~$ ，在收敛性证明中这是非常重要的。

定理3：设目标函数 $~f(x)~$ 有下界，梯度 $~g(x)~$ 是 $Lipchitz$ 连续的，考虑方法 $~(2)~$ 和 $~(3)~$ ，其中 $~\beta_k~$ 按 $~(4)~$ 计算，步长 $~\alpha_k~$ 选择标准 Wolfe 线搜索 $~(5)~$ 和 $~(6)~$ ，则或者 $~g_k=0~$ 对某个 $~k~$ 成立，或者
$\lim_{k\rightarrow\infty}\inf\Vert g_k\Vert=0$
证明： 用反证法，假设结论不真，则必存在 $~\gamma>0~$ ，使得
$\Vert g_k\Vert\ge\gamma\tag{13}$
由定理 2 可知，DY 共轭梯度法的每一个搜索方向必为下降方向，故定理 1 中的 Zoutendijk 条件是成立的。
当 $~k\ge 2~$ 时， $~d_k+g_k=\beta_k d_{k-1}~$ ，两端取模平方并移项，可得
$\Vert d_k\Vert^2=\beta_k^2\Vert d_{k-1}\Vert^2-2g_k^Td_k-\Vert g_k\Vert^2$
将上式除以 $~(g_k^T d_k)^2~$ ，并利用 $~(12)~$ 得
$\begin{aligned} \frac{\Vert d_k\Vert^2}{(g_k^T d_k)^2}&=\frac{\Vert d_{k-1}\Vert^2}{(g_{k-1}^Td_{k-1})}-\frac{2}{g_k^T d_k}-\frac{\Vert g_k\Vert^2}{(g_k^T d_k)^2}\\ &=\frac{\Vert d_{k-1}\Vert^2}{(g_{k-1}^Td_{k-1})^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{\Vert d_{k-1}\Vert^2}{(g_{k-1}^Td_{k-1})^2}+\frac{1}{\Vert g_k\Vert^2} \end{aligned}$
由于 $~\frac{\Vert d_1\Vert^2}{(g_1^T d_1)^2}=\frac{1}{\Vert g_1\Vert^2}~$ ，根据上式递推，则有
$\frac{\Vert d_k\Vert^2}{(g_k^T d_k)^2}\le\sum_{i=1}^k\frac{1}{\Vert g_i\Vert^2}$
由 $~(13)~$ 式，则有
$\frac{\Vert d_k\Vert^2}{(g_k^T d_k)^2}\le\frac{k}{\gamma^2}$
从而
$\sum_{k\ge 1}\frac{(g_k^T d_k)^2}{\Vert d_k\Vert^2}\ge\sum_{k\ge1}\frac{\gamma^2}{k}=+\infty$
上式与 定理 1相矛盾，从而假设不成立，故命题得证。
注：该定理表明 DY 共轭梯度法在寻常假定下是全局收敛的，当然这是一种弱收敛，但是对于共轭梯度法的收敛性要求，这种收敛是完全可以接受的。

4、对 DY 共轭梯度法的进一步讨论
在 定理 2 中指出 DY 共轭梯度法的每一次搜索方向必是下降方向，即
$g_k^T d_k<0,~~~\forall k\ge 1\tag{14}$
在很多算法中我们可能需要每一次搜索方向是充分下降的，即存在常数 $~c>0~$ ，使得
$g_k^T d_k\le -c\Vert g_k\Vert^2,~~~\forall k\ge 1\tag{15}$
显然算法具有充分下降性则一定具有下降性，我们在此给出两种情况可以保证 DY 共轭梯度法具有充分下降性。一种是线搜索的加强，一种是函数的加强。
(1)、DY 共轭梯度法在强 Wolfe 线搜索下具有充分下降性
显然强 Wolfe 线搜索是标准 Wolfe 线搜索的特列，则 DY 共轭梯度法在标准 Wolfe 线搜索下具有下降性，则在强 Wolfe 线搜索下也一定具有下降性。因为
$\frac{g_k^T d_k}{\Vert g_k\Vert^2}=\frac{g_{k-1}^T d_{k-1}}{d_{k-1}^T (g_k-g_{k-1})}$
由强 Wolfe 线搜索 $~(8)~$ 可知
$d_{k-1}^T (g_k-g_{k-1})\le-(\sigma+1)g_{k-1}^T d_{k-1}$
利用 $~d_{k-1}^T(g_k-g_{k-1})>0~$ 和 $~g_{k-1}^T d_{k-1}<0~$ 以及上面两式，则有
$\frac{g_k^T d_k}{\Vert g_k\Vert^2}\le-\frac{1}{1+\sigma}$
故充分下降 $(15)$ 式中的 $~c~$ 可取 $~c=\frac{1}{1+\sigma}~$

（2)，DY 共轭梯度法在一致凸函数时考虑某些线搜索可保证充分下降性
在之前的文章我们已经介绍了凸集、凸函数、严格凸函数、一致凸函数（强凸函数）的定义，首先说明一下凸函数都是定义在凸集上。下面就简单说一下他们的定义

<1> 凸集
设集合 $~D\subset\mathbb{R}^n~$ ，若对于任意的 $~x,y\in D~$ ，对任意的实数 $~\alpha\in[0,1]~$ ，都有 $~\alpha x+(1-\alpha y)\in D~$ ，则称 $~D~$ 为凸集。

<2> 凸函数
设函数 $~f(x)~$ 定义在凸集 $~D\in\mathbb{R}^n~$ 上。若对于任意 $~x,y\in D~$ ，及任意实数 $~\alpha\in [0,1]~$ ，都有
$f(\alpha x+(1-\alpha)y)\le\alpha f(x)+(1-\alpha)f(y)$

<3> 严格凸函数
设函数 $~f(x)~$ 定义在凸集 $~D\in\mathbb{R}^n~$ 上。若对于任意 $~x,y\in D~$ ， $x\neq y$ ，及任意实数 $~\alpha\in (0,1)~$ ，都有
$f(\alpha x+(1-\alpha)y)<\alpha f(x)+(1-\alpha)f(y)$

<4> 一致凸函数
设函数 $~f(x)~$ 定义在凸集 $~D\in\mathbb{R}^n~$ 上。若存在常数 $~\eta>0~$ ，对任意 $~x,y\in D~$ ，及任意实数 $~\alpha\in [0,1]~$ ，都有
$f(\alpha x+(1-\alpha)y)\le\alpha f(x)+(1-\alpha)f(y)-\frac{1}{2}\alpha(1-\alpha)\eta\Vert x-y\Vert^2$
注: 无论是凸函数，严格凸函数，一致凸函数都未要求函数是连续可微的，若 $~f(x)~$ 是连续可微的，一致凸函数有如下等价表达，此处不给出证明，如果有兴趣，可以参考其他书籍。
$f(x)\ge f(y)+g(y)^T(x-y)+\frac{1}{2}\eta\Vert x-y\Vert^2\tag{16}$
或者
$(g(y)-g(x))^T(y-x)\ge\eta\Vert x-y\Vert^2\tag{17}$

现在说明以下某些线搜索，比如仅仅需要标准 Wolfe 线搜索中的 (5) 而不需要 (6)，或者其他的情况。主要两种如下情况
$f(x_k+\alpha_kd_k)\le f(x_k)+\rho \alpha_k d_k\tag{18}$
或者
$f(x_k+\alpha_k d_k)\le f(x_k)-\rho^2\alpha_k^2\Vert d_k\Vert^2\tag{19}$
其中 $~\rho\in(0,1)~$ .
<5> 若 $~f(x)~$ 为强凸函数且线搜索有公式 $~(18)~$ 的 DY 共轭梯度法满足充分下降性
由公式 $~(12)~$ 可知
$\frac{g_{k+1}^T d_{k+1}}{\Vert g_{k+1}\Vert^2}=\frac{g_{k}^T d_{k}}{d_{k}^T(g_{k+1}-g_{k})}\tag{20}$
因为 $~f(x)~$ 为一致凸函数，根据公式 $~(17)~$ 必有 $~d_{k-1}^T(g_k-g_{k-1})>0~$ ，其实这个性质， $~f(x)~$ 为严格凸函数也具有，是根据严格凸函数的等价定义 $~(g(y)-g(x))^T(y-x)\ge 0~$ ，由此，我们可以利用数学归纳法，证明若函数 $~f(x)~$ 为严格凸函数，则 DY 算法每次搜索方向必为下降方向，从而也可以得出 DY 共轭梯度法的收敛性，而且这种下降性和全局收敛性不依赖于任何线搜索。但是此处我们想讨论的是充分下降性，所以不能就此结束。

利用公式 $~(16)~$ 我们有
$f(x_k+\alpha_k d_k)-f(x_k)\ge \alpha_k g_k^T d_k+\frac{1}{2}\eta\alpha_k^2\Vert d_k\Vert^2$
结合公式 $~(18)~$ 我们有
$\alpha_k\le c_1\frac{\vert g_k^T d_k\vert}{\Vert d_k\Vert^2}\tag{21}$
其中 $~c_1=\frac{2(1-\rho)}{\eta}~$
根据梯度函数 $~Lipschitz~$ 条件，我们有
$\vert g_{k+1}^T d_k-g_k^T d_k\vert\le\Vert g_{k+1}-g_k\Vert\Vert d_k\Vert\le\alpha_k L\Vert d_k\Vert^2\tag{22}$
利用 $~(20)~$ ， $~(21)~$ 和 $~(22)~$ ，则
$\frac{g_{k+1}^T d_{k+1}}{\Vert g_{k+1}\Vert^2}=\frac{g_k^T d_k}{d_k^T(g_{k+1}-g_k)}\le\frac{g_k^T d_k}{L\alpha_k\Vert d_k\Vert^2}\le-\frac{1}{L c_1}\tag{23}$
故充分下降 $~(15)~$ 中的 $~c~$ 可取 $~c=\frac{1}{Lc_1}~$
<6> 若 $~f(x)~$ 为强凸函数且线搜索有公式 $~(19)~$ 的 DY 共轭梯度法满足充分下降性
此处证明过程基本与上相同，故在此简单说一下。
利用公式 $~(16)~$ 我们有
$f(x_k+\alpha_k d_k)-f(x_k)\ge \alpha_k g_k^T d_k+\frac{1}{2}\eta\alpha_k^2\Vert d_k\Vert^2$
结合公式 $~(19)~$ 我们有
$\alpha_k\le c_2\frac{\vert g_k^T d_k\vert}{\Vert d_k\Vert^2}$
其中 $~c_2=\frac{1}{\frac{1}{2}\eta+\rho}~$
后面与式 $~(23)~$ 中完全一样，只是其中 $~c_1~$ 换成 $~c_2~$ 而已。

注：很多人可能觉得式 (18) 或者 (19)线搜索是否存在，此处我想说的是当然存在，比如有 Armijo 线搜索，后面我可能会单独讲一下线搜索，此处不想过多讲述。

5、总结和参考文献
这篇文章的内容主要讲述了三个方面：一、 DY 共轭梯度法在标准 Wolfe 线搜索下的全局收敛性。二、DY共轭梯度法在强 Wolfe 线搜索下具有充分下降性并且全局收敛性。三、DY 共轭梯度法在一致凸函数加以某些条件具有充分下降性。
以上内容参考 袁亚湘 和 戴彧虹老师的文章，对了 DY 共轭梯度法中 D 和 Y 便是他们名字的首字母，是八种经典共轭梯度法(DY，FR，CD，PRP，HS，LS，DL，HZ)的其中之一。

参考文献
[1] Dai Y H , Yuan Y. A Nonlinear Conjugate Gradient with a Strong Global Convergence Property, SIAM Journal of Optimization, 2000, 10: 177-182
[2] Dai Y H, Yuan Y. Some properties of a new conjugate gradient method, in: Yuan Y, ed. Advances in Nonlinear Programming, Boston: Kluwer, 1998, 251~262.

最后编辑于：2022.08.11 13:50:51

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

10、DY 共轭梯度法

推荐阅读更多精彩内容