最优化考试之共轭梯度法

---

一、共轭梯度法

1.前言

共轭梯度法在第一次时迭代的过程和最速下降法一样，但从第二步开始共轭梯度法就发生了变化，共轭梯度法的梯度下降方法不再是直接根据当前点计算?f(x)

2.问题条件

共轭梯度法的相关问题中的条件提炼出来如下，如果题目没有误差e，那就要求最后迭代出来的梯度值 $?f(x)$ 接近0或等于0，一般自行选取e。

1. 目标函数 $?f(x)$
2. 初始点 $x^0$
3. 误差 e

3.计算过程

1. 选取初始点$x^0$，$k=0$
2. 计算 $?f$($x^k$) ，若||$?f$($x^k$)||$<=e$，停止迭代，输出结果$x^k$
3. 第一次的梯度$d=??f(x^k)$，跳至第6步
4. 除第一次迭代外，要计算的系数b如下
   
5. $d_{k+1}=??f(x^k)+b?d_k$
6. 下一个迭代点 $x^{k+1}$=$x^k$+$t_k$*$d_{k+1}$
7. 设函数$g(t_k)=f($$x^{k+1}$)，对$g(t_k)$求导，计算当$g^{\prime }(t_k)=0$时步长$t_k$的值；因此推导出$x^{k+1}$，k=k+1，跳至第2步

4.例子

4.1 第一次迭代

和最速下降法一样，先计算梯度下降方向$d_0=??f(x^0)=[1,?1{]}^T$

下一个迭代点 $x^1=x^0+d_0?t_0$

设函数$g(t_0)=f(x^0)={t_0}^2?2?t_0$

对$g(t_0)$求导，当$g^{\prime }(t_0)=0$时，$t_0=1$，代入求得$x^1=[1,?1{]}^T$

4.2 第二次迭代

先计算系数 $b=1$

梯度下降方向$d_1=??f(x^1)+b?d_0=[2,0{]}^T$

下一个迭代点 $x^2=x^1+d_1?t_1$

设函数$g(t_1)=f(x^2)={4?t_1}^2?2?t_1?1$

对$g(t_1)$求导，当$g^{\prime }(t_1)=0$时，$t_1=1/4$，代入求得$x^2=[3/2,?1{]}^T$

此时$?f(x^2)=0<e$，因此$x^2$为最优解点，最优解为$f(x^2)=5/4$

PS：

后续迭代按照第二次迭代的方法依次计算即可