---

[toc]

共轭方向

我们首先看一个函数$f(x)=x_1^2+x_2^2$，图像是一个圆

在$x_1,x_2$的坐标轴中，由于$x_1,x_2$是解耦合的,即是$x_1,x_2$是对正交向量，$x_1,x_2$构成了一个向量空间，也就是$x_1,x_2$构成这个空间的基，所以我们可以先沿着$x_1$的方向走到最优点所在的$x_1$的坐标，然后在沿着$x_2$的方向走，最后到达最优点。在这迭代的过程中，两次方向$g_{k+1}g_k=0$

但是如果这个函数不是刚好一个圆呢？如果是倾斜一点的话，相当于加上了$ax_1x_2$耦合了$x_1,x_2$，因为$g_{k+1}g_k=0$，下一步和上一步的方向是垂直的，我们发现我们没办法先沿着$x_1$走然后再沿着$x_2$走，也就是两步没办法找到最优点了。

这时候我们引入共轭，即通过对空间的线性变换，在变换的过程中，使得新的空间下，$ax_1x_2$被消除，从而对$x_1,x_2$解耦合，在新的空间中，通过变换的$\tilde x_1,\tilde x_2$是$x_1,x_2$的共轭方向，然后我们就可以沿着$\tilde x_1$走，然后再向$\tilde x_2$走，直接两步走到最优点

又$d_kd_{k+1}=0$是在度量空间$I$下，相当于$d_kId_{k+1}=0$,通过线性变换$Q$，使得度量空间变为$Q$，所以有$d_kQd_{k+1}=0$,注意在新的空间下，$d_kd_{k+1}=0$仍然成立，因为我们只是改了表示的方法，事实上性质没有改变

子空间拓展定理

设$G$是正定矩阵，$d_0,d_1,…,d_{n-1}$是关于$G$的共轭方程组，则对于$f(x)=\frac{1}{2}x^TGx+b^Tx$，第k+1步得到的迭代点处梯度方向是之前所有的搜索方向张成的线性空间正交，即是$g_k^Td_j=0,j=0,…,k-1$。

证明：对所有$i\leq n-1$都有$g_{i+1}^Td_j=0,j=0,1,…,i$

1. $j=i$时，根据精确线搜索，有$\Large\frac{\partial}{\partial\alpha}\normalsize f(x_i+\alpha d_i)=\nabla f(x_{i+1})^Td_i=g_{i+1}^Td_i=0$

2. $j<i$时

   $$\begin{aligned} g_{i+1}^Td_j &= g_{i+1}^Td_j + \sum_{k=j+1}^i(g_k^Td_j-g_k^Td_j)\\ &=g_{i+1}^Td_j+g_{j+1}^Td_j-g_{j+1}^Td_j + \sum_{k=j+1}^i(g_k^Td_j-g_k^Td_j)\\ &=g_{j+1}^Td_j + (-g_{j+1}+g_{j+1}+...+g_i+g_{i+1})^Td_j-\sum_{k=j+1}^ig_k^Td_j \\ &=g_{j+1}^Td_j+\sum_{k=j+2}^{i+1}g_{k}^Td_j-\sum_{k=j+1}^ig_k^Td_j\\ &=g_{j+1}^Td_j+\sum_{k=j+1}^i(g_{k+1}-g_k)^Td_j\quad(g_{j+1}^Td_j=0)\\ &=\sum_{k=j+1}^i(g_{k+1}-g_k)^Td_j\\ &=\sum_{k=j+1}^i[G(x_{k+1}-x_k)]^Td_j\\ &=\sum_{k=j+1}^i\alpha_kd_kGd_j=0\quad(d_kGd_j=0,共轭) \end{aligned}$$

我们第$k+1$次得到的迭代点处的梯度值与之前所有的搜索方向正交，也就是说之前所有的搜索方向在梯度方向上分量都为0

共轭梯度法

前置知识

因为共轭向量组中的向量一定线性无关和子空间拓展可知，$d_k,g_k$不在$d_i,i=0,…,k-1$生成的子空间，又$g_k^Td_j=0,j=0,…,k-1$，$g_k$可以与$d_0,…,d_{k-1}$张成一个$k+1$维子空间，所以$d_k$为$g_k,d_0,…,d_{k-1}$的线性组合，其中$g_k$的系数取-1

---

建立$d_k=-g_k+\sum_{i=0}^{k-1}\beta_i^{(k-1)}d_i$

代入$d_k^TGd_j=0$,得到$d_k=(-g_k+\sum_{i=0}^{k-1}\beta_i^{(k-1)}d_i)^TGd_j=0$

由$d_i,d_j(i\neq j)$具有共轭性,可得$\beta_j^{(k-1)}=\Large\frac{g_k^TGd_j}{d_j^TGd_j},\normalsize j=0,…,k-1$

---

由于$x_{j+1}=x_j+\alpha_jd_j$,且$g_j=Gx_j+b$

对$\beta_j^{(k-1)}$的分子同乘于$\alpha_j$,得到

$$\begin{aligned} \alpha_j g_k^TGd_j &= g_k^TG\alpha_jd_j\\ &=g_k^TG(x_{j+1}-x_j)\\ &=g_k^T(g_{j+1}-g_j) \end{aligned}$$

又

$$\begin{aligned} &\because d_k=-g_k+\sum_{i=0}^{k-1}\beta_i^{(k-1)}d_i\\ &\therefore g_j=-d_j + \sum_{i=0}^{j-1}\beta_i^{(k-1)}d_i\\ &\because g_kd_j=0\\ &\therefore g_k(-g_j+\sum_{i=0}^{j-1}\beta_i^{(k-1)}d_i)=0\\ &\therefore g_kg_j=\sum_{i=0}^{j-1}\beta_i^{(k-1)}g_kd_i=0\\ &\therefore g_kg_j=0 \end{aligned}$$

所以

$$g_k^T(g_{j+1}-g_j)=\left\{ \begin{aligned} &0,&j=0,...,k-2\\ &g^T_k(g_k-g_{k-1}),&j=k-1 \end{aligned} \right.$$

所以

$$\begin{aligned} d_k&=-g_k+\sum_{i=0}^{k-1}\beta_i^{(k-1)}d_i\\ &=-g_k+\beta_{k-1}d_{k-1} \end{aligned}$$

---

从上面我们可以知道

1. 搜索方向都是共轭的
2. 搜索方向是$-g_k$和$d_{k-1}$的线性组合

求β

Hestenes-Stiefel公式

对$d_k=-g_k+\beta_{k-1}d_{k-1}$,等式两边同乘$d_{k-1}^TQ$，且$d_{k-1}^TQd_k=0$

$$\begin{aligned} \therefore d_{k-1}^TQd_k&= -d_{k-1}^TQg_k+d_{k-1}^TQ\beta_{k-1}d_{k-1}\\ 0 &=-d_{k-1}^TQg_k+d_{k-1}^TQ\beta_{k-1}d_{k-1}\\ \therefore \beta_{k-1}^{HS}&=\frac{d_{k-1}^TQg_k}{d_{k-1}^TQd_{k-1}}\\ &=\frac{d_{k-1}^TGg_k}{d_{k-1}^TGd_{k-1}}\\ &=\frac{g_k^TGd_{k-1}}{d_{k-1}^TGd_{k-1}} \end{aligned}$$

Crowder-Wolfe公式

$$\begin{aligned} \because g_{k+1}-g_k&=G(x_{k+1}-x_k)=\alpha{Gd_k}\\ \therefore \beta^{CW}_{k-1}&=\frac{g_k^TGd_{k-1}}{d_{k-1}^TGd_{k-1}}\\ &=\frac{g_k^T(g_k-g_{k-1})}{d_{k-1}^T(g_k-g_{k-1})}\\ \end{aligned}$$

Fletcher-Reeves公式

对$d_k=-g_k+\beta_{k-1}d_{k-1}$

有

$$\begin{aligned} d_k&=-g_k+\beta_{k-1}d_{k-1}\\ d_k^T&=-g_k^T+d_{k-1}^T\beta_{k-1}\\ d_k^Tg_{k+1}&=-g_k^Tg_{k+1}+d_{k-1}^T\beta_{k-1}g_{k+1}\\ \therefore &d_k^Tg_{k+1}=d_{k-1}^Tg_{k+1}=0\\ \therefore &g_k^Tg_{k+1}=g_{k+1}^Tg_k=0 \end{aligned}$$

代入CW得

$$\begin{aligned} \beta_{k-1}^{CW}&=\frac{g_k^T(g_{k}-g_{k-1})}{d_{k-1}^T(g_{k}-g_{k-1})}\\ &=\frac{g_k^Tg_k}{-d_{k-1}g_{k-1}}\\ \because-d_{k-1}&g_{k-1}=g_{k-1}^Tg_{k-1} \\ &=\frac{g_k^Tg_k}{g_{k-1}^Tg_{k-1}}\\ \therefore \beta_{k-1}^{FR}&=\frac{g_k^Tg_k}{g_{k-1}^Tg_{k-1}} \end{aligned}$$

其中

$$\begin{aligned} d_{k-1}^Tg_{k-1}&=(-g_{k-1}+\beta_{k-2}d_{k-2})^Tg_{k-1}\\ &=-g_{k-1}^Tg_{k-1}+d_{k-2}^T\beta_{k-2}g_{k-1}\\ &=-g_{k-1}^Tg_{k-1}+\beta_{k-2}d_{k-2}^Tg_{k-1}\\ \because &\quad d_{k-2}^Tg_{k-1}=0\\ \therefore &\quad d_{k-1}^Tg_{k-1}=-g_{k-1}^Tg_{k-1} \end{aligned}$$

Polak-Ribiere-Polyak公式

因为

$$\begin{aligned} \beta_{k-1}^{CW}&=\frac{g_k^T(g_k-g_{k-1})}{d_{k-1}^T(g_k-g_{k-1})}\\ &=\frac{g_k^T(g_k-g_{k-1})}{d_{k-1}^Tg_k-d_{k-1}^Tg_{k-1}}\\ \because &d_{k-1}^Tg_k=0\\ &d_{k-1}^Tg_{k-1}=g_{k-1}^Tg_{k-1}\\ \therefore g_{k-1}^{PRP}&=\frac{g_k^T(g_k-g_{k-1})}{g_{k-1}^Tg_{k-1}} \end{aligned}$$

Conjugate-Descent公式

$$\begin{aligned} &\beta_{k-1}^{CW}=\frac{g_k^T(g_{k}-g_{k-1})}{d_{k-1}^T(g_{k}-g_{k-1})}\\ \because &g_k^Tg_{k-1}=0\\ &d_{k-1}^Tg_{k}=0\\ \therefore&\beta^{CD}_{k-1}=-\frac{g_k^Tg_k}{d_{k-1}^Tg_{k-1}} \end{aligned}$$

Dai-Yuan公式

$$\begin{aligned} &\beta_{k-1}^{CW}=\frac{g_k^T(g_{k}-g_{k-1})}{d_{k-1}^T(g_{k}-g_{k-1})}\\ \because &g^T_kg_{k-1}=0\\ \therefore &\beta^{DY}_{k-1}=\frac{g_k^Tg_k}{d_{k-1}^T(g_{k}-g_{k-1})} \end{aligned}$$

求步长α

$$\begin{aligned} \because &g_{k+1}-g_k=G(x_{k+1}-x_k)=\alpha_kGd_k\\ \therefore &d_k^T(g_{k+1}-g_k)=\alpha_kd_k^TGd_k\\ &\alpha_k=\frac{d_k^T(g_{k+1}-g_k)}{d_k^TGd_k}\\ &\quad=\frac{d_k^Tg_k}{d_k^TGd_k}\\ &\quad=\frac{g_k^Tg_k}{d_k^TGd_k} \end{aligned}$$