一、基本共軛方向算法

???? 對于n維二次型函數(shù)的最小化問題：
f(x)=12xTQx?xTb
其中，Q=QT>0,x∈Rn。因為Q>0,所以函數(shù)f有一個全局極小點，可以通過求解Qx=b得到。

基本共軛方向算法 給定初始點x(0)和一組關(guān)于Q共軛的方向d(0),d(1),…,d(n?1),迭代公式為(k≥0表示迭代次數(shù))：

g(k)=?f(x(k))=Qx(k)?bak=?g(k)Td(k)d(k)TQd(k)x(k+1)=x(k)+akd(k)

二、定理及其證明

對于任意初始點x(0)，基本共軛方向算法都能在n次迭代之內(nèi)收斂到唯一全局極小點x?，即x(n)=x?.

證明：由于方向d(i),i=0,1,…,n?1線性無關(guān)，因此，x??x(0)∈Rn可以由它們線性表出，即：

x??x(0)=β0d(0)+β1x(1)+?+βn?1d(n?1)
其中， βi,i=0,1,…,n?1為常數(shù)。
上式同時左乘 d(k)TQ,
d(k)TQ(x??x(0))=βkd(k)TQd(k)
整理下，可得：
βk=?d(k)TQ(x??x(0))d(k)TQd(k)
迭代點 x(k)可以寫為：
x(k)=x(0)+a0d(0)+a1x(1)+?+ak?1d(k?1)
則：
x(k)?x(0)=a0d(0)+a1x(1)+?+ak?1d(k?1)
上式同時左乘 d(k)TQ,因為 g(k)=Qx(k)?b,Qx?=b,可得：
d(k)TQ(x??x(0))=d(k)TQ(x??x(k))=?g(k)Td(k)
所以：
βk=?g(k)Td(k)d(k)TQd(k)=ak
這說明 x(n)=x?.
證畢。

總結(jié)

以上是生活随笔為你收集整理的最优化学习笔记（九）——基本的共轭方向算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。