人工智能之数学基础【共轭梯度法】

本文主要是介绍人工智能之数学基础【共轭梯度法】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

简述

共轭梯度法是利用目标函数的梯度逐步产生共轭方向并将其作为搜索方向的方法。 共轭梯度法是针对二次函数$$f(x)=\frac{1}{2}{x}^{T}Qx+b^{T}x+c,x\in R^n$$
的无约束优化问题。此方法具有存储变量少和收敛速度快的特点。

共轭方向

设共轭矩阵$A$是$n\times n$的对称正定矩阵，若$d^1,d^2,\cdots ,d^m\in R^n$，并且$i,j=1,2,\cdots ,m$，有$(d^i)TA{d}^j=0,i\ne j$，则称$d^1,d^2,\cdots ,d^m$关于A相互共轭，或者称它们为A的m个共轭方向。如果A是单位矩阵，则两个方向关于A共轭等价于两个方向正交。
将一组共轭方向作为搜索方向对无约束非线性规划问题进行求解的方法称为共轭方向法。共轭梯度法是将方向法与梯度方法结合起来考虑的一种优化方法。

原理

考虑无约束凸二次规划问题$$f(x)=\frac{1}{2}{x}^{T}Qx+b^{T}x+c,x\in R^n$$，其中矩阵$Q\in R^{n\times n}$对称正定，向量$b\in R^n$，对目标函数$f(x)$求一阶导可得$\nabla f(x)=Qx+b$，求二阶导可得${\nabla }^{2}f(x)=Q$为正定矩阵,因此$f(x)$是严格凸函数，并且$x^{\ast }$是此优化问题最优解的充分必要条件是$\nabla f(x^{\ast })=0$。
设从任意点$x^1$出发，若$\nabla f(x^1)=0$，则停止计算，$x^1$为无约束问题的极小点。
若$\nabla f(x^1)\ne 0$，则$$d^1=-\nabla f(x^1)$$沿着$d^1$的方向进行一维搜索，得到点$x^2$。若$\nabla f(x^2)\ne 0$，则令$$d^2=-\nabla f(x^2)+{\beta }_1{d}^1$$并且两个方向$d^1,d^2$关于Q共轭，$d^1和d^2$应满足$(d^1{)}^{T}QA{d}^2=0$,有$$(d^1{)}^{T}QA(-\nabla f(x^2)+{\beta }_1{d}^1)=0$$解得：
$${\beta }_1=\frac{(d^1{)}^{T}Q\nabla f(x^2)}{(d^1{)}^{T}Q{d}^1}$$
这样得到$d^2$和$d^1$是关于Q共轭的。再从$x_2$出发，沿着$d^2$方向进行一维搜索，得到$x^3$，以此类推。假设在$x^k$处，$\nabla f(x^k)\ne 0$，构造$x^k$处的搜索方向为：
$$d^k=-\nabla f(x^k)+\sum _{i=1}^{k-1}{\beta }_i{d}_i(1)$$
因为要构造的方向是关于Q共轭因此：
$$(d^{k-1}{)}^{T}Q{d}^k=0(2)$$
把（1）带入（2）:
$$(d^{k-1}{)}^{T}Q(-\nabla f(x^k)+\sum _{i=1}^{k-1}{\beta }_i{d}_i)=0$$解得：
$${\beta }_{k-1}=\frac{(d^{k-1}{)}^{T}Q\nabla f(x^k)}{(d^{k-1}{)}^{T}Q{d}^{k-1}}(3)$$
当k=n时，得到n个非零的Q共轭的方向，$x^{n+1}$为整个空间上的唯一极小点。
因为$$\nabla f(x^k)-\nabla f(x^{k-1})=Q(x^k-x^{k-1})={\alpha }_{k-1}Q{d}^{k-1}(4)$$
把（4）求解出Q带入（3）化简整合得：
$${\beta }_{k-1}=(\nabla f(x^{k-1}){)}^T\nabla f(x^{k-1})$$
从而
$${\beta }_{k-1}=\frac{\nabla f(x^k{)}^T(\nabla f(x^k)-\nabla f(x^{k-1}))}{(\nabla f(x^{k-1}){)}^T\nabla f(x^{k-1})}$$
又因为
$${\beta }_{k-1}=\frac{||\nabla f(x^k)|{|}^2}{||\nabla f(x^{k-1})|{|}^2}$$
这样用于一般可微函数得共轭梯度法。其搜索方向构造如下：
$$\{\begin{array}{l}{d}^1=-\nabla f(x^1)\\ d^k=-\nabla f(x^k)+{\beta }_{k-1}{d}^{k-1}\end{array}$$
设 { x k } \{x^k\} {xk}为由采用精确线性搜索得共轭梯度法求解无约束非线性规划问题产生得点列，则向量组 { d i } , ( i = 1 , 2 , ⋯ , k − 1 ) \{d^i\},(i=1,2,\cdots,k-1) {di},(i=1,2,⋯,k−1)关于Q相互共轭，且对于任意$k\le n$有$$\nabla f(x^k{)}^T{d}^j=0,\nabla f(x^k{)}^T\nabla f(x^j)=0,\forall j<k$$

步骤

已知目标函数$f(x)$，终止限$\epsilon >0$。操作步骤如下：

1. 选取初始点$x$，令$k=1$。
2. 计算点$x^k$的梯度$\nabla f(x^k)，||\nabla f(x^k)||<\epsilon$，停止迭代，$x^k$为该问题的最优解，输出$x^k$,否则继续执行下一步。
3. 构造搜索方向$d^k$。$$d^k=-\nabla f(x^k)-{\beta }_{k-1}{d}^{k-1}$$，其中$${\beta }_{k-1}=\{\begin{array}{l}0,当k=1时,\\ \frac{||\nabla f(x^k)|{|}^2}{||\nabla f(x^{k-1})|{|}^2}，当k>1时\end{array}$$
4. 进行一维搜索。由$min\Phi (\alpha )=f(x+{\alpha }_k{d}^k)$得到${\alpha }_k$，则$$x^{k+1}=x^k+{\alpha }_k{d}^k$$，令$k=k+1$，跳转之第2步。

示例

设$minf(x)=\frac{1}{2}{x}_1^2+x_2^2$,给定初始点$x^1=(2,1{)}^T$，终止条件精度参数$\epsilon =10^{-6}$。
解： 首先计算$$\begin{gathered} \nabla f(x)=(x_1,2x_2{)}^T, \\ Q={\nabla }^{2}f(x)=\left(\begin{array}{cc}1& 0\\ 0& 2\end{array}\right) \end{gathered}$$
第一次迭代：
$$\begin{gathered} \nabla f(x^1)=(2,2{)}^T\ne 0 \\ {d}^1=-\nabla f(x^1)=(-2,-2{)}^T \end{gathered}$$
$${\alpha }_1=-\frac{\nabla f(x^1{)}^T{d}^1}{(d^1{)}^{T}Q{d}^1}=\frac{2}{3}$$
$$x_2=x^1+{\alpha }_1{d}^1=(2,1{)}^T+\frac{2}{3}(-2,-2{)}^T=(\frac{2}{3},-\frac{1}{3})$$
第二次迭代：
$$\begin{gathered} \nabla f(x^2)=(\frac{2}{3},\frac{2}{3}{)}^T\ne 0 \\ {d}^1=-\nabla f(x^1)=(-2,-2{)}^T \end{gathered}$$
$${\beta }_1=-\frac{||\nabla f(x^2)|{|}^2}{||\nabla f(x^1)|{|}^2}=\frac{1}{9}$$
$$d_2=-\nabla f(x^2)+{\beta }_1{d}^1=-(\frac{2}{3},\frac{2}{3}{)}^T+\frac{1}{9}(-2,-2{)}^T=(-\frac{8}{9},\frac{4}{9}{)}^T$$
$${\alpha }_2=-\frac{\nabla f(x^2{)}^T{d}^2}{(d^2{)}^{T}Q{d}^2}=\frac{2}{3}$$
$$x_3=x^2+{\alpha }_2{d}^2=(\frac{2}{3},-\frac{1}{3}{)}^T+\frac{3}{4}(-\frac{8}{9},\frac{4}{9}{)}^T=(0,0)$$
$$||\nabla f(x^3)||=0$$
故最优解为$$x^{\ast }=x^3=(0,0{)}^T$$
当用于严格凸二次函数极小化问题时，共轭梯度法产生的方向关于目标函数的Hessian矩阵相互共轭。

这篇关于人工智能之数学基础【共轭梯度法】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---