简述
共轭梯度法是利用目标函数的梯度逐步产生共轭方向并将其作为搜索方向的方法。 共轭梯度法是针对二次函数
f
(
x
)
=
1
2
x
T
Q
x
+
b
T
x
+
c
,
x
∈
R
n
f(x)=\frac{1}{2}x^TQx+b^Tx+c,x \in R^n
f(x)=21xTQx+bTx+c,x∈Rn
的无约束优化问题。此方法具有存储变量少和收敛速度快的特点。
共轭方向
设共轭矩阵
A
A
A是
n
×
n
n \times n
n×n的对称正定矩阵，若
d
1
,
d
2
,
⋯
,
d
m
∈
R
n
d^1,d^2,\cdots,d^m\in R^n
d1,d2,⋯,dm∈Rn，并且
i
,
j
=
1
,
2
,
⋯
,
m
i,j=1,2,\cdots,m
i,j=1,2,⋯,m，有
(
d
i
)
T
A
d
j
=
0
,
i
≠
j
(d^i)TAd^j=0,i\neq j
(di)TAdj=0,i=j，则称
d
1
,
d
2
,
⋯
,
d
m
d^1,d^2,\cdots,d^m
d1,d2,⋯,dm关于A相互共轭，或者称它们为A的m个共轭方向。如果A是单位矩阵，则两个方向关于A共轭等价于两个方向正交。
将一组共轭方向作为搜索方向对无约束非线性规划问题进行求解的方法称为共轭方向法。共轭梯度法是将方向法与梯度方法结合起来考虑的一种优化方法。
原理
考虑无约束凸二次规划问题
f
(
x
)
=
1
2
x
T
Q
x
+
b
T
x
+
c
,
x
∈
R
n
f(x)=\frac{1}{2}x^TQx+b^Tx+c,x \in R^n
f(x)=21xTQx+bTx+c,x∈Rn，其中矩阵
Q
∈
R
n
×
n
Q\in R^{n\times n}
Q∈Rn×n对称正定，向量
b
∈
R
n
b\in R^n
b∈Rn，对目标函数
f
(
x
)
f(x)
f(x)求一阶导可得
∇
f
(
x
)
=
Q
x
+
b
\nabla f(x)=Qx+b
∇f(x)=Qx+b，求二阶导可得
∇
2
f
(
x
)
=
Q
\nabla^2 f(x)=Q
∇2f(x)=Q为正定矩阵,因此
f
(
x
)
f(x)
f(x)是严格凸函数，并且
x
∗
x^*
x∗是此优化问题最优解的充分必要条件是
∇
f
(
x
∗
)
=
0
\nabla f(x^*)=0
∇f(x∗)=0。
设从任意点
x
1
x^1
x1出发，若
∇
f
(
x
1
)
=
0
\nabla f(x^1)=0
∇f(x1)=0，则停止计算，
x
1
x^1
x1为无约束问题的极小点。
若
∇
f
(
x
1
)
≠
0
\nabla f(x^1) \neq 0
∇f(x1)=0，则
d
1
=
−
∇
f
(
x
1
)
d^1=-\nabla f(x^1)
d1=−∇f(x1)沿着
d
1
d^1
d1的方向进行一维搜索，得到点
x
2
x^2
x2。若
∇
f
(
x
2
)
≠
0
\nabla f(x^2) \neq 0
∇f(x2)=0，则令
d
2
=
−
∇
f
(
x
2
)
+
β
1
d
1
d^2=-\nabla f(x^2)+\beta_1d^1
d2=−∇f(x2)+β1d1并且两个方向
d
1
,
d
2
d^1,d^2
d1,d2关于Q共轭，
d
1
和
d
2
d^1和d^2
d1和d2应满足
(
d
1
)
T
Q
A
d
2
=
0
(d^1)^TQAd^2=0
(d1)TQAd2=0,有
(
d
1
)
T
Q
A
(
−
∇
f
(
x
2
)
+
β
1
d
1
)
=
0
(d^1)^TQA(-\nabla f(x^2)+\beta_1d^1)=0
(d1)TQA(−∇f(x2)+β1d1)=0解得：
β
1
=
(
d
1
)
T
Q
∇
f
(
x
2
)
(
d
1
)
T
Q
d
1
\beta_1=\frac{(d^1)^TQ\nabla f(x^2)}{(d^1)^TQd^1}
β1=(d1)TQd1(d1)TQ∇f(x2)
这样得到
d
2
d^2
d2和
d
1
d^1
d1是关于Q共轭的。再从
x
2
x_2
x2出发，沿着
d
2
d^2
d2方向进行一维搜索，得到
x
3
x^3
x3，以此类推。假设在
x
k
x^k
xk处，
∇
f
(
x
k
)
≠
0
\nabla f(x^k)\neq 0
∇f(xk)=0，构造
x
k
x^k
xk处的搜索方向为：
d
k
=
−
∇
f
(
x
k
)
+
∑
i
=
1
k
−
1
β
i
d
i
(
1
)
d^k=-\nabla f(x^k)+\sum_{i=1}^{k-1}\beta_id_i \quad \quad (1)
dk=−∇f(xk)+i=1∑k−1βidi(1)
因为要构造的方向是关于Q共轭因此：
(
d
k
−
1
)
T
Q
d
k
=
0
(
2
)
(d^{k-1})^TQd^k=0 \quad \quad (2)
(dk−1)TQdk=0(2)
把（1）带入（2）:
(
d
k
−
1
)
T
Q
(
−
∇
f
(
x
k
)
+
∑
i
=
1
k
−
1
β
i
d
i
)
=
0
(d^{k-1})^TQ(-\nabla f(x^k)+\sum_{i=1}^{k-1}\beta_id_i)=0
(dk−1)TQ(−∇f(xk)+i=1∑k−1βidi)=0解得：
β
k
−
1
=
(
d
k
−
1
)
T
Q
∇
f
(
x
k
)
(
d
k
−
1
)
T
Q
d
k
−
1
(
3
)
\beta_{k-1}=\frac{(d^{k-1})^TQ\nabla f(x^k)}{(d^{k-1})^TQd^{k-1}}\quad \quad \quad (3)
βk−1=(dk−1)TQdk−1(dk−1)TQ∇f(xk)(3)
当k=n时，得到n个非零的Q共轭的方向，
x
n
+
1
x^{n+1}
xn+1为整个空间上的唯一极小点。
因为
∇
f
(
x
k
)
−
∇
f
(
x
k
−
1
)
=
Q
(
x
k
−
x
k
−
1
)
=
α
k
−
1
Q
d
k
−
1
(
4
)
\nabla f(x^k)-\nabla f(x^{k-1})=Q(x^k-x^{k-1})=\alpha_{k-1}Qd^{k-1}\quad \quad \quad (4)
∇f(xk)−∇f(xk−1)=Q(xk−xk−1)=αk−1Qdk−1(4)
把（4）求解出Q带入（3）化简整合得：
β
k
−
1
=
(
∇
f
(
x
k
−
1
)
)
T
∇
f
(
x
k
−
1
)
\beta_{k-1}=(\nabla f(x^{k-1}))^T\nabla f(x^{k-1})
βk−1=(∇f(xk−1))T∇f(xk−1)
从而
β
k
−
1
=
∇
f
(
x
k
)
T
(
∇
f
(
x
k
)
−
∇
f
(
x
k
−
1
)
)
(
∇
f
(
x
k
−
1
)
)
T
∇
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})}
βk−1=(∇f(xk−1))T∇f(xk−1)∇f(xk)T(∇f(xk)−∇f(xk−1))
又因为
β
k
−
1
=
∣
∣
∇
f
(
x
k
)
∣
∣
2
∣
∣
∇
f
(
x
k
−
1
)
∣
∣
2
\beta_{k-1}=\frac{||\nabla f(x^k)||^2}{||\nabla f(x^{k-1})||^2}
βk−1=∣∣∇f(xk−1)∣∣2∣∣∇f(xk)∣∣2
这样用于一般可微函数得共轭梯度法。其搜索方向构造如下：
{
d
1
=
−
∇
f
(
x
1
)
d
k
=
−
∇
f
(
x
k
)
+
β
k
−
1
d
k
−
1
\begin{cases} d^1=-\nabla f(x^1) \\d^k=-\nabla f(x^k)+\beta_{k-1}d^{k-1} \end{cases}
{d1=−∇f(x1)dk=−∇f(xk)+βk−1dk−1
设
{
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
≤
n
k\leq n
k≤n有
∇
f
(
x
k
)
T
d
j
=
0
,
∇
f
(
x
k
)
T
∇
f
(
x
j
)
=
0
,
∀
j
<
k
\nabla f(x^k)^Td^j=0,\nabla f(x^k)^T\nabla f(x^j)=0,\forall j\lt k
∇f(xk)Tdj=0,∇f(xk)T∇f(xj)=0,∀j<k
步骤
已知目标函数 f ( x ) f(x) f(x)，终止限 ε > 0 \varepsilon >0 ε>0。操作步骤如下：文章来源：https://www.toymoban.com/news/detail-828499.html
- 选取初始点 x x x，令 k = 1 k=1 k=1。
- 计算点 x k x^k xk的梯度 ∇ f ( x k ) ， ∣ ∣ ∇ f ( x k ) ∣ ∣ < ε \nabla f(x^k)，||\nabla f(x^k)||< \varepsilon ∇f(xk)，∣∣∇f(xk)∣∣<ε，停止迭代， x k x^k xk为该问题的最优解，输出 x k x^k xk,否则继续执行下一步。
- 构造搜索方向 d k d^k dk。 d k = − ∇ f ( x k ) − β k − 1 d k − 1 d^k=-\nabla f(x^k)-\beta_{k-1}d^{k-1} dk=−∇f(xk)−βk−1dk−1，其中 β k − 1 = { 0 , 当 k = 1 时 , ∣ ∣ ∇ f ( x k ) ∣ ∣ 2 ∣ ∣ ∇ f ( x k − 1 ) ∣ ∣ 2 ， 当 k > 1 时 \beta_{k-1}=\begin{cases} 0,\quad 当k=1时,\\\frac{||\nabla f(x^k)||^2}{||\nabla f(x^{k-1})||^2}，\quad \quad 当k\gt 1时\end{cases} βk−1={0,当k=1时,∣∣∇f(xk−1)∣∣2∣∣∇f(xk)∣∣2，当k>1时
- 进行一维搜索。由 m i n Φ ( α ) = f ( x + α k d k ) min \quad\Phi(\alpha)=f(x+\alpha_kd^k) minΦ(α)=f(x+αkdk)得到 α k \alpha_k αk，则 x k + 1 = x k + α k d k x^{k+1}=x^k+\alpha_k d^k xk+1=xk+αkdk，令 k = k + 1 k=k+1 k=k+1，跳转之第2步。
示例
设
m
i
n
f
(
x
)
=
1
2
x
1
2
+
x
2
2
minf(x)=\frac{1}{2}x_1^2+x_2^2
minf(x)=21x12+x22,给定初始点
x
1
=
(
2
,
1
)
T
x^1=(2,1)^T
x1=(2,1)T，终止条件精度参数
ε
=
1
0
−
6
\varepsilon=10^{-6}
ε=10−6。
解： 首先计算
∇
f
(
x
)
=
(
x
1
,
2
x
2
)
T
,
Q
=
∇
2
f
(
x
)
=
(
1
0
0
2
)
\nabla f(x)=(x_1,2x_2)^T,\\Q=\nabla^2f(x)=\left( \begin{matrix} 1 &0\\ 0 & 2 \end{matrix} \right)
∇f(x)=(x1,2x2)T,Q=∇2f(x)=(1002)
第一次迭代：
∇
f
(
x
1
)
=
(
2
,
2
)
T
≠
0
d
1
=
−
∇
f
(
x
1
)
=
(
−
2
,
−
2
)
T
\nabla f(x^1)=(2,2)^T\neq0 \\d^1=-\nabla f(x^1)=(-2,-2)^T
∇f(x1)=(2,2)T=0d1=−∇f(x1)=(−2,−2)T
α
1
=
−
∇
f
(
x
1
)
T
d
1
(
d
1
)
T
Q
d
1
=
2
3
\alpha_1=-\frac{\nabla f(x^1)^Td^1}{(d^1)^TQd^1}=\frac{2}{3}
α1=−(d1)TQd1∇f(x1)Td1=32
x
2
=
x
1
+
α
1
d
1
=
(
2
,
1
)
T
+
2
3
(
−
2
,
−
2
)
T
=
(
2
3
,
−
1
3
)
x_2=x^1+\alpha_1d^1=(2,1)^T+\frac{2}{3}(-2,-2)^T=(\frac{2}{3},-\frac{1}{3})
x2=x1+α1d1=(2,1)T+32(−2,−2)T=(32,−31)
第二次迭代：
∇
f
(
x
2
)
=
(
2
3
,
2
3
)
T
≠
0
d
1
=
−
∇
f
(
x
1
)
=
(
−
2
,
−
2
)
T
\nabla f(x^2)=(\frac{2}{3},\frac{2}{3})^T\neq0 \\d^1=-\nabla f(x^1)=(-2,-2)^T
∇f(x2)=(32,32)T=0d1=−∇f(x1)=(−2,−2)T
β
1
=
−
∣
∣
∇
f
(
x
2
)
∣
∣
2
∣
∣
∇
f
(
x
1
)
∣
∣
2
=
1
9
\beta_1=-\frac{||\nabla f(x^2)||^2}{||\nabla f(x^1)||^2}=\frac{1}{9}
β1=−∣∣∇f(x1)∣∣2∣∣∇f(x2)∣∣2=91
d
2
=
−
∇
f
(
x
2
)
+
β
1
d
1
=
−
(
2
3
,
2
3
)
T
+
1
9
(
−
2
,
−
2
)
T
=
(
−
8
9
,
4
9
)
T
d_2=-\nabla f(x^2)+\beta_1d^1=-(\frac{2}{3},\frac{2}{3})^T+\frac{1}{9}(-2,-2)^T=(-\frac{8}{9},\frac{4}{9})^T
d2=−∇f(x2)+β1d1=−(32,32)T+91(−2,−2)T=(−98,94)T
α
2
=
−
∇
f
(
x
2
)
T
d
2
(
d
2
)
T
Q
d
2
=
2
3
\alpha_2=-\frac{\nabla f(x^2)^Td^2}{(d^2)^TQd^2}=\frac{2}{3}
α2=−(d2)TQd2∇f(x2)Td2=32
x
3
=
x
2
+
α
2
d
2
=
(
2
3
,
−
1
3
)
T
+
3
4
(
−
8
9
,
4
9
)
T
=
(
0
,
0
)
x_3=x^2+\alpha_2d^2=(\frac{2}{3},-\frac{1}{3})^T+\frac{3}{4}(-\frac{8}{9},\frac{4}{9})^T=(0,0)
x3=x2+α2d2=(32,−31)T+43(−98,94)T=(0,0)
∣
∣
∇
f
(
x
3
)
∣
∣
=
0
||\nabla f(x^3)||=0
∣∣∇f(x3)∣∣=0
故最优解为
x
∗
=
x
3
=
(
0
,
0
)
T
x^*=x^3=(0,0)^T
x∗=x3=(0,0)T
当用于严格凸二次函数极小化问题时，共轭梯度法产生的方向关于目标函数的Hessian矩阵相互共轭。文章来源地址https://www.toymoban.com/news/detail-828499.html
到了这里，关于人工智能之数学基础【共轭梯度法】的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
