🚀个人主页：欢迎访问Ali.S主页

📆 最近更新：2022年7月19日

⛽ Java框架学习系列：Mybatis框架

⛳ Java基础学习系列：面向对象飞机大战

🏆 通信仿真学习系列：【硬件】【通信】【MATLAB】【最优化】

🍄 个人简介：通信工程本硕🌈、Java程序员🚴。目前只会CURD😂

💌 点赞 👍 收藏 💗留言 💬 都是我最大的动力💯

一、共轭梯度法介绍

前面介绍过为了解决牛顿法中可能出现在某步迭代时，目标函数数值上升的问题，引入阻尼牛顿法进行修正，但是在牛顿法和阻尼牛顿法中都存在计算Hesse矩阵的问题，使得在多次迭代时可能会出现计算量过大的问题，为解决Hesse矩阵的问题，这里引入共轭梯度法对优化问题进行处理。共轭梯度法是介于最速下降法与牛顿法之间的一个方法，它不需要对Hesse矩阵进行计算，只需要对函数的一阶导数进行处理，不仅克服了最速下降法收敛慢的缺点，而且避免了牛顿法需要计算Hesse矩阵并求逆的缺陷，共轭梯度法是非常重要的一种求解无约束问题的算法，其优点是超线性收敛，且算法简单，编程容易实现。

二、共轭梯度法原理

在求解n维正定二次函数时，极小值点产生一组共轭方向作为搜索方向，在最优步长的搜索下，迭代n步得到极小点，经过适当修正之后，可以推广到其它阶函数的优化问题的求解上来。下面以严格凸二次函数进行讨论：
对于严格二次凸函数：A为对称正定矩阵；

取：

下式中a0为最优步长，

由前面最速下降法中：

可以类比得到：

令：

其中B的选取需要满足：

从上式可以解出：

所以就得到dk的迭代关系为：

多次重复上述步骤得到：

最终整理得到共轭梯度法的迭代公式为：

三、共轭梯度法步骤

1. 给定初始点x(0)，设置允许误差0<ε<1
2. 计算初始点的梯度，并取负梯度作为d0
3. 判断梯度范数与允许误差的大小
4. 若梯度范数大于允许误差，则进行下面的计算：
   
   否则停止搜索，得到最优解。
5. 迭代次数更新：k=k+1
6. 转步骤（2）继续进行后续搜索，直至得到满足精度要求的最优解。

四、共轭梯度法代码

共轭梯度函数

     function [k,x,val]=linecg(A,b,x0,epsilon,N)
     if nargin<5,
         N=1000;
     end
     if nargin<4, 
         epsilon=1.e-5;
     end
     if nargin<3, 
         x0=zeros(length(b),1);
     end
     k=0;
     gk=A*x0-b;
     dk=-gk;
     while(k<N)
         temp=A*dk;
         alpha=-gk'*dk/(dk'*temp);
         x=x0+alpha*dk;
         gk=A*x-b;
         betak=gk'*temp/(dk'*temp);
         dk=-gk+betak*dk;
         if(norm(gk)<epsilon), 
             break;
         end
         x0=x;
         k=k+1;
     end
     val=0.5*x'*A*x-b'*x;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

梯度函数

 function gf=gfun(x)
    gf=[4*x(1)-2*x(2);2*x(2)-2*x(1)-2];
1
2

五、共轭梯度法测试

    function f=fun(x)
    f=2*x(1)^2+x(2)^2-2*x(1)*x(2)-2*x(2);
1
2

k =
    10
x =

    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000


val =

 -101.0000
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109

总结

共轭梯度法是介于最速下降法与牛顿法之间的一个方法，它不需要对Hesse矩阵进行计算，只需要对函数的一阶导数进行处理，不仅克服了最速下降法收敛慢的缺点，而且避免了牛顿法需要计算Hesse矩阵并求逆的缺陷，共轭梯度法是非常重要的一种求解无约束问题的算法，其优点是超线性收敛。