優(yōu)化算法-共軛梯度法

(2012-04-20 08:57:05) 轉(zhuǎn)載▼

標(biāo)簽： 雜談

?

最速下降法

1.最速下降方向

函數(shù)f(x)在點(diǎn)x處沿方向d的變化率可用方向?qū)?shù)來(lái)表示。對(duì)于可微函數(shù)，方向?qū)?shù)等于梯度與方向的內(nèi)積，即：

Df(x;d)?=?▽f(x)Td,

因此，求函數(shù)f(x)在點(diǎn)x處的下降最快的方向，可歸結(jié)為求解下列非線性規(guī)劃：

min?▽f(x)Td

s.t.??||d||?≤?1

當(dāng)????????????????????????????d?=?-▽f(x)?/?||▽f(x)||???

時(shí)等號(hào)成立。因此，在點(diǎn)x處沿上式所定義的方向變化率最小，即負(fù)梯度方向?yàn)樽钏傧陆捣较颉?/span>

2.最速下降算法

最速下降法的迭代公式是

x(k+1)?=?x(k)?+?λkd(k)?,

其中d(k)是從x(k)出發(fā)的搜索方向，這里取在x(k)處的最速下降方向，即

d?=?-▽f(x(k)).

λk是從x(k)出發(fā)沿方向d(k)進(jìn)行一維搜索的步長(zhǎng)，即λk滿足

f(x(k)?+?λkd(k))?=?min?f(x(k)+λd(k))???(λ≥0).

計(jì)算步驟如下：

(1)給定初點(diǎn)x(1)?∈?Rn，允許誤差ε>?0，?置k?=?1。

(2)計(jì)算搜索方向d?=?-▽f(x(k))。

(3)若||d(k)||?≤?ε，則停止計(jì)算；否則，從x(k)出發(fā)，沿d(k)進(jìn)行一維搜索，求λk，使

f(x(k)?+?λkd(k))?=?min?f(x(k)+λd(k))???(λ≥0).

(4)令x(k+1)?=?x(k)?+?λkd(k)?，置k?=?k?+?1，轉(zhuǎn)步驟(2)。

??

?

共軛梯度法

1.共軛方向

無(wú)約束問(wèn)題最優(yōu)化方法的核心問(wèn)題是選擇搜索方向。

以正定二次函數(shù)為例，來(lái)觀察兩個(gè)方向關(guān)于矩陣Ａ共軛的幾何意義。

設(shè)有二次函數(shù)：

f(x)?=?1/2?(x?-?x*)TA(x?-?x*)?,

其中A是n×n對(duì)稱正定矩陣，x*是一個(gè)定點(diǎn)，函數(shù)f(x)的等值面

1/2?(x?-?x*)TA(x?-?x*)?=?c

是以x*為中心的橢球面，由于

▽f(x*)?=?A(x?-?x*)?=?0，

A正定，因此x*是f(x)的極小點(diǎn)。

設(shè)x(1)是在某個(gè)等值面上的一點(diǎn)，該等值面在點(diǎn)x(1)處的法向量

▽f(x(1))?=?A(x(1)?-?x*)。

又設(shè)d(1)是這個(gè)等值面在d(1)處的一個(gè)切向量。記作

d(2)?=?x*?-?x(1)。

自然，d(1)與▽f(x(1))正交，即d(1)T▽f(x(1))?=?0，因此有

d(1)TAd(2)?=?0，

即等值面上一點(diǎn)處的切向量與由這一點(diǎn)指向極小點(diǎn)的向量關(guān)于A共軛。

?

由此可知，極小化式所定義的二次函數(shù)，若依次沿著d(1)和d(2)進(jìn)行一維搜索，則經(jīng)兩次迭代必達(dá)到極小點(diǎn)。

1.共軛梯度法

共軛梯度法最初由Hesteness和Stiefel于1952年為求解線性方程組而提出的。后來(lái)，人們把這種方法用于求解無(wú)約束最優(yōu)化問(wèn)題，使之成為一種重要的最優(yōu)化方法。

Fletcher-Reeves共軛梯度法，簡(jiǎn)稱FR法。

共軛梯度法的基本思想是把共軛性與最速下降方法相結(jié)合，利用已知點(diǎn)處的梯度構(gòu)造一組共軛方向，并沿這組方向進(jìn)行搜素，求出目標(biāo)函數(shù)的極小點(diǎn)。根據(jù)共軛方向基本性質(zhì)，這種方法具有二次終止性。

對(duì)于二次凸函數(shù)的共軛梯度法：

min?f(x)?=?1/2?xTAx?+?bTx?+?c,

其中x∈?Rn，A是對(duì)稱正定矩陣，c是常數(shù)。

具體求解方法如下：

首先，任意給定一個(gè)初始點(diǎn)x(1)，計(jì)算出目標(biāo)函數(shù)f(x)在這點(diǎn)的梯度，若||g1||?=?0，則停止計(jì)算；否則，令

d(1)?=?-▽f(x(1))?=?-g1。

沿方向d(1)搜索，得到點(diǎn)x(2)。計(jì)算在x(2)處的梯度，若||g2||?≠?0，則利用-g2和d(1)構(gòu)造第2個(gè)搜索方向d(2)，在沿d(2)搜索。

一般地，若已知點(diǎn)x(k)和搜索方向d(k)，則從x(k)出發(fā)，沿d(k)進(jìn)行搜索，得到

x(k+1)?=?x(k)?+?λkd(k)?,

其中步長(zhǎng)λk滿足

f(x(k)?+?λkd(k))?=?min?f(x(k)+λd(k))。

此時(shí)可求出λk的顯示表達(dá)

?

?

計(jì)算f(x)在x(k+1)處的梯度。若||gk+1||?=?0，則停止計(jì)算；否則，用-gk+1和d(k)構(gòu)造下一個(gè)搜索方向d(k+1)，并使d(k+1)和d(k)關(guān)于A共軛。按此設(shè)想，令

d(k+1)?=?-gk+1?+?βkd(k)，

上式兩端左乘d(k)TA，并令

d(k)TAd(k+1)?=?-d(k)TAgk+1?+?βkd(k)TAd(k)?=?0，

由此得到

βk?=?d(k)TAgk+1?/?d(k)TAd(k)。

再?gòu)?/span>x(k+1)出發(fā)，沿方向d(k+1)搜索。

在FR法中，初始搜索方向必須取最速下降方向，這一點(diǎn)決不可忽視。因子βk可以簡(jiǎn)化為：βk?=?||gk+1||2?/?||gk||2。

3.非線性共軛梯度

當(dāng)目標(biāo)函數(shù)是高于二次的連續(xù)函數(shù)(即目標(biāo)函數(shù)的梯度存在)時(shí)，其對(duì)應(yīng)的解方程是非線性方程，非線性問(wèn)題的目標(biāo)函數(shù)可能存在局部極值，并且破壞了二次截止性，共軛梯度法需要在兩個(gè)方面加以改進(jìn)后，仍然可以用于實(shí)際的反演計(jì)算，但共軛梯度法不能確保收斂到全局極值。

(1)首先是共軛梯度法不能在n維空間內(nèi)依靠n步搜索到達(dá)極值點(diǎn)，需要重啟共軛梯度法，繼續(xù)迭代，以完成搜索極值點(diǎn)的工作。

(2)在目標(biāo)函數(shù)復(fù)雜，在計(jì)算時(shí)，由于需要局部線性化，需計(jì)算Hessian矩陣A，且計(jì)算工作量比較大，矩陣A也有可能是病態(tài)的。Fletcher和Reeves的方案最為常用，拋棄了矩陣A的計(jì)算，具體形式如下：

?

式中gk-1和gk分別為第k-1和第k次搜索是計(jì)算出來(lái)的目標(biāo)函數(shù)的梯度。http://blog.sina.com.cn/s/blog_72bc796901011v2q.html

分享：

1

喜歡

《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的优化算法-共轭梯度法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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