簡(jiǎn)述
共軛梯度法是利用目標(biāo)函數(shù)的梯度逐步產(chǎn)生共軛方向并將其作為搜索方向的方法。 共軛梯度法是針對(duì)二次函數(shù)
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)=21?xTQx+bTx+c,x∈Rn
的無(wú)約束優(yōu)化問(wèn)題。此方法具有存儲(chǔ)變量少和收斂速度快的特點(diǎn)。
共軛方向
設(shè)共軛矩陣
A
A
A是
n
×
n
n \times n
n×n的對(duì)稱正定矩陣，若
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關(guān)于A相互共軛，或者稱它們?yōu)锳的m個(gè)共軛方向。如果A是單位矩陣，則兩個(gè)方向關(guān)于A共軛等價(jià)于兩個(gè)方向正交。
將一組共軛方向作為搜索方向?qū)o(wú)約束非線性規(guī)劃問(wèn)題進(jìn)行求解的方法稱為共軛方向法。共軛梯度法是將方向法與梯度方法結(jié)合起來(lái)考慮的一種優(yōu)化方法。
原理
考慮無(wú)約束凸二次規(guī)劃問(wèn)題
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)=21?xTQx+bTx+c,x∈Rn，其中矩陣
Q
∈
R
n
×
n
Q\in R^{n\times n}
Q∈Rn×n對(duì)稱正定，向量
b
∈
R
n
b\in R^n
b∈Rn，對(duì)目標(biāo)函數(shù)
f
(
x
)
f(x)
f(x)求一階導(dǎo)可得
?
f
(
x
)
=
Q
x
+
b
\nabla f(x)=Qx+b
?f(x)=Qx+b，求二階導(dǎo)可得
?
2
f
(
x
)
=
Q
\nabla^2 f(x)=Q
?2f(x)=Q為正定矩陣,因此
f
(
x
)
f(x)
f(x)是嚴(yán)格凸函數(shù)，并且
x
?
x^*
x?是此優(yōu)化問(wèn)題最優(yōu)解的充分必要條件是
?
f
(
x
?
)
=
0
\nabla f(x^*)=0
?f(x?)=0。
設(shè)從任意點(diǎn)
x
1
x^1
x1出發(fā)，若
?
f
(
x
1
)
=
0
\nabla f(x^1)=0
?f(x1)=0，則停止計(jì)算，
x
1
x^1
x1為無(wú)約束問(wèn)題的極小點(diǎn)。
若
?
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的方向進(jìn)行一維搜索，得到點(diǎn)
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)+β1?d1并且兩個(gè)方向
d
1
,
d
2
d^1,d^2
d1,d2關(guān)于Q共軛，
d
1
和
d
2
d^1和d^2
d1和d2應(yīng)滿足
(
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)+β1?d1)=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是關(guān)于Q共軛的。再?gòu)?span id="n5n3t3z" class="katex--inline">
x
2
x_2
x2?出發(fā)，沿著
d
2
d^2
d2方向進(jìn)行一維搜索，得到
x
3
x^3
x3，以此類推。假設(shè)在
x
k
x^k
xk處，
?
f
(
x
k
)
≠
0
\nabla f(x^k)\neq 0
?f(xk)=0，構(gòu)造
x
k
x^k
xk處的搜索方向?yàn)椋?br>
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?βi?di?(1)
因?yàn)橐獦?gòu)造的方向是關(guān)于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?βi?di?)=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)
當(dāng)k=n時(shí)，得到n個(gè)非零的Q共軛的方向，
x
n
+
1
x^{n+1}
xn+1為整個(gè)空間上的唯一極小點(diǎn)。
因?yàn)?span id="n5n3t3z" class="katex--display">
?
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?1?Qdk?1(4)
把（4）求解出Q帶入（3）化簡(jiǎn)整合得：
β
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))?
又因?yàn)?br>
β
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?
這樣用于一般可微函數(shù)得共軛梯度法。其搜索方向構(gòu)造如下：
{
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?1?dk?1?
設(shè)
{
x
k
}
\{x^k\}
{xk}為由采用精確線性搜索得共軛梯度法求解無(wú)約束非線性規(guī)劃問(wèn)題產(chǎn)生得點(diǎn)列，則向量組
{
d
i
}
,
(
i
=
1
,
2
,
?
?
,
k
?
1
)
\{d^i\},(i=1,2,\cdots,k-1)
{di},(i=1,2,?,k?1)關(guān)于Q相互共軛，且對(duì)于任意
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
步驟
已知目標(biāo)函數(shù) f ( x ) f(x) f(x)，終止限 ε > 0 \varepsilon >0 ε>0。操作步驟如下：文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-828499.html
- 選取初始點(diǎn) x x x，令 k = 1 k=1 k=1。
- 計(jì)算點(diǎn) 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為該問(wèn)題的最優(yōu)解，輸出 x k x^k xk,否則繼續(xù)執(zhí)行下一步。
- 構(gòu)造搜索方向 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?1?dk?1，其中 β k ? 1 = { 0 , 當(dāng) k = 1 時(shí) , ∣ ∣ ? f ( x k ) ∣ ∣ 2 ∣ ∣ ? f ( x k ? 1 ) ∣ ∣ 2 ， 當(dāng) k > 1 時(shí) \beta_{k-1}=\begin{cases} 0,\quad 當(dāng)k=1時(shí),\\\frac{||\nabla f(x^k)||^2}{||\nabla f(x^{k-1})||^2}，\quad \quad 當(dāng)k\gt 1時(shí)\end{cases} βk?1?={0,當(dāng)k=1時(shí),∣∣?f(xk?1)∣∣2∣∣?f(xk)∣∣2?，當(dāng)k>1時(shí)?
- 進(jìn)行一維搜索。由 m i n Φ ( α ) = f ( x + α k d k ) min \quad\Phi(\alpha)=f(x+\alpha_kd^k) minΦ(α)=f(x+αk?dk)得到 α k \alpha_k αk?，則 x k + 1 = x k + α k d k x^{k+1}=x^k+\alpha_k d^k xk+1=xk+αk?dk，令 k = k + 1 k=k+1 k=k+1，跳轉(zhuǎn)之第2步。
示例
設(shè)
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)=21?x12?+x22?,給定初始點(diǎn)
x
1
=
(
2
,
1
)
T
x^1=(2,1)^T
x1=(2,1)T，終止條件精度參數(shù)
ε
=
1
0
?
6
\varepsilon=10^{-6}
ε=10?6。
解： 首先計(jì)算
?
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)=(10?02?)
第一次迭代：
?
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+α1?d1=(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)+β1?d1=?(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+α2?d2=(32?,?31?)T+43?(?98?,94?)T=(0,0)
∣
∣
?
f
(
x
3
)
∣
∣
=
0
||\nabla f(x^3)||=0
∣∣?f(x3)∣∣=0
故最優(yōu)解為
x
?
=
x
3
=
(
0
,
0
)
T
x^*=x^3=(0,0)^T
x?=x3=(0,0)T
當(dāng)用于嚴(yán)格凸二次函數(shù)極小化問(wèn)題時(shí)，共軛梯度法產(chǎn)生的方向關(guān)于目標(biāo)函數(shù)的Hessian矩陣相互共軛。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-828499.html
到了這里，關(guān)于人工智能之?dāng)?shù)學(xué)基礎(chǔ)【共軛梯度法】的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
