2019-04-10

作者: sea_monster | 来源:发表于2019-04-10 21:15 被阅读2次

共轭梯度

参考

主要参考这篇文章，非常推荐查看，文章最后还有个关于共轭梯度的图
 Conjugate gradient method wiki
Gram-Schmidt方法 wiki
在介绍共轭梯度之前，我们先介绍一下Gram-Schmidt过程(革兰氏-施密特方法)，看它如何对向量组进行正交归一化。

首先定义投影操作： $proj_u(v)=\frac{\langle u,v\rangle}{\langle u,u \rangle}u$
其中 $\langle u,v\rangle$ 表示向量u,v的在 $R^n$ 上的内积。该运算符将向量 $v$ 正交投影到向量 $u$ 所跨越的线上。如果 $u=0$ ，我们定义 $proj_u(v)=0$ 。

Gram-Schmidt过程的工作原理如下：
$u_1=v_1$
$u_2=v_2-proj_{u_1}(v_2)$
$u_3=v_3-proj_{u_1}(v_3)-proj_{u_2}(v_3)$
$\cdots$
$u_k=v_k-\sum\limits^{k-1}_{j=1}proj_{u_j}(v_k)$

该方法进行如下运算：为了计算 $u_i$ ，它首先将 $v_i$ 正交投影到 $u_1,\cdots,u_{i-1}$ 上，然后从向量 $u_i$ 中减去为 $v_i$ 与每个投影之间的差，从而保证与空间中的所有向量( $u_1,\cdots,u_{i-1}$ )正交。

图来源wiki
最终原理图如下所示：

optimization图23.gif

什么是共轭？
对矩阵 $A\in R^{n\times n}$ 对称正定，而 $p_1,p_2,\cdots, p_m$ 是 $R^n$ 中任意一组非零向量，若 $p_i^TAp_j=0(i\ne j)$ ，则称向量组 $p_1,p_2,\cdots, p_m$ 是相对于 $A$ 共轭的。

由于矩阵是 $A$ 是对称 $(A^T=A)$ 且正定的，则关于其的共轭内积可定义为：
${\displaystyle \langle u,v\rangle_A:=\langle Au,v\rangle}=\langle u,A^Tv\rangle=\langle u,Av\rangle=u^TAv$ 。
(由于我们将要处理的是共轭而不是正交( $A=I$ 时为正交)，所以在要运用Gram-Schmidt方法时需要运用共轭形式的内积。)

进入正题：

模型建立
假定待优化的函数： $\underset{x}{min}f(x)=\frac{1}{2}x^TAx-b^Tx$

(其中 $x$ 为待优化变量， $A$ 为正定矩阵， $b$ 为已知变量。)

下标k表示优化步数，负梯度为： $r_k=b-Ax_k$

假设最优变量为 $x^*$ ，则优化问题可变为求方程 $Ax^*=b$ 的解。梯度 $r$ 也可以称作为每一步的残差。
算法推导
优化方向确定：

假定第一次优化方向为初始负梯度方向： $p_1=r_0$

每一次优化方向与之前的优化方向正交，采用Gram-Schmidt方法进行向量正交化，每次优化方向根据当前步的梯度得出：
$p_k=r_k-\sum\limits^{k-1}_{i=1} \frac{p_i^TAr_k}{p^T_iAp_i}p_i$

再令 $\beta_{ik}=\frac{p^T_iAr_k}{p^T_iAp_i}$ (这个 $\beta$ 计算出来是个实数)，则有： $p_k=r_k-\sum\limits^{k-1}_{i=1}\beta_{ik} p_i$ 。

优化步长确定：

假定第 $k$ 步的优化步长为 $\alpha_k$ 。
对 $f(x_{k+1})=f(x_k+\alpha_kp_k)$ 求导令导数为零有： $\alpha_k= \frac{p_k^Tr_k}{p^T_kAp_k}$ (行搜索)。

共轭梯度其实到这里已经证明结束了，但一般选择其化简式。所以接下来对等式进行化简：
误差 $e_k$ 定义为 $x_k$ 与最优变量 $x^*$ 的差值:
$e_k=x^*-x_k=\sum\limits^n_{i=1}\alpha_ip_i-\sum\limits^k_{i=1}\alpha_ip_i=\sum\limits^n_{i=k+1}\alpha_ip_i$
对残差 $r_k$ 有：
$r_k=b-Ax_k=Ax^*-Ax_k=Ae_k$

在得到最终的等式前，证明下面两个性质：

1.残差与之前的所有的方向正交

证明：
任取一个方向 $p_j$ ，并且 $j\le k$ ：

${\displaystyle p_j^Tr_k=p_j^TAe_k=\sum\limits^n_{i=k+1}\alpha_i p_j^TAp_i}=0$

2.残差与之前的所有的残差正交
如果残差与搜索方向形成向量基正交，那么残差也会形成向量基。这意味着任何残差都与它先前的残差正交。
证明如下：
当 $k+1\le j$ 时：
$p_{k+1}=r_k-\sum\limits_{i\le k}\beta_{ik}p_i$
右乘 $r_j有$ ：
$p_{k+1}^Tr_j=r_k^Tr_j-\sum\limits_{i\le k}\beta_{ik}p_i^Tr_j$
$0=r_k^Tr_j+0$

基于残差的梯度步长：(求简化的 $\alpha$ )
由之前可得： $r_{k+1}^Tr_k=0$
又由于： $r_{k+1}=b-Ax_{k+1}$ 则：
$(b-Ax_{k+1})^Tr_k=0$
$(b-A(x_k+\alpha_{k+1}p_{k+1}))^Tr_k=0$
$(b-Ax_k)^Tr_k-\alpha_{k+1}(Ap_{k+1}^T)r_k=0$
$r_k^Tr_k-\alpha_{k+1}(Ap_{k+1})^Tr_k=0$
$\alpha_{k+1}=\frac{r_k^Tr_k}{p_{k+1}^TAr_k}$ ( $A=A^T$ )
又因为： $p_{k+1}=r_k-\sum\limits_{i\le k}\beta_i p_i$
$\alpha_{k+1}=\frac{r_k^Tr_k}{p_{k+1}^TAp_{k+1}}$

正交化步骤仅取决于先前的搜索方向：：(求简化的 $\beta$ )
$x_{k+1}=x_k+\alpha_{k+1}p_{k+1}$ (更新 $x_k$ 的值)
$b-Ax_{k+1}=b-Ax_k-\alpha_{k+1}Ap_{k+1}$
( $\alpha_{k+1}$ 的值为实数)
$r_{k+1}=r_k-\alpha_{k+1}Ap_{k+1}$
前乘 $r_j^T$ 值，求新的 $\beta$ 值：
$r_j^Tr_{k+1}=r_j^Tr_k-\alpha_{k+1}r_j^TAp_{k+1}$
$\alpha_{k+1}r_j^TAp_{k+1}=-r_j^Tr_{k+1}+r_j^Tr_k$
又因为： $\beta_{ik}=\frac{r_k^TAp_i}{p_i^TAp_i}$
$\alpha_{k+1}\beta_{k+1,j}p_{k+1}^TAp_{k+1}=-r_j^Tr_{k+1}+r_j^Tr_k$
$\beta_{k+1,j}r_k^Tr_k=-r_j^Tr_{k+1}+r_j^Tr_k$
用 $\alpha_{k+1}=\frac{r_k^Tr_k}{p^T_{k+1}Ap_{k+1}}$ 代替 $\alpha_{k+1}p_{k+1}^TAp_{k+1}$ 有：

得到 $\beta_{k+1,j}=\frac{-r_j^Tr_{k+1}+r_j^Tr_k}{r_k^Tr_k}$
变化一下得： $\beta_{k,j}=\frac{-r_j^Tr_{k}+r_j^Tr_{k-1}}{r_{k-1}^Tr_{k-1}}$
又因为： $p_{k+1}=r_k-\sum\limits_{i\le k}\beta_{ik}p_i=r_k-\sum\limits_{j\le k}\beta_{k,j}p_i$
可简化为： $p_{k+1}=r_k-\beta_{k,k}p_k$
其中： $\beta_{k,k}=\frac{-r_k^Tr_k}{r_{k-1}^Tr_{k-1}}$

伪代码：
在简化后：
$r_0=b-Ax_0$
$p_1=r_0$
$k=1$
repeat
$\alpha_k=\frac{r_{k-1}^Tr_{k-1}}{p_k^TAp_k}$
$x_k=x_{k-1}+\alpha_kp_k$
$r_k=r_{k-1}－\alpha_kAp_k$
$\beta_k=\frac{r_k^Tr_k}{r_{k-1}^Tr_{k-1}}$
$p_{k+1}=r_k+\beta_kp_k$
$k=k+1$
until $r_{k-1}<\epsilon$
(残差小于某个值便可以跳出来了。)
return $x_{k-1}$

2019-04-10

共轭梯度

参考

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

人工智能

大数据，机器学习，人工智能

机器学习和人工智能入门

人工智能