1.最速下降方向

函數f(x)在點x處沿方向d的變化率可用方向導數來表示。對于可微函數，方向導數等于梯度與方向的內積，即：

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

因此，求函數f(x)在點x處的下降最快的方向，可歸結為求解下列非線性規劃：

min▽f(x)Td

s.t.||d||≤1

當d=-▽f(x)/||▽f(x)||

時等號成立。因此，在點x處沿上式所定義的方向變化率最小，即負梯度方向為最速下降方向。

2.最速下降算法

最速下降法的迭代公式是

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

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

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

λk是從x(k)出發沿方向d(k)進行一維搜索的步長，即λk滿足

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

計算步驟如下：

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

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

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

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

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

共軛梯度法

1.共軛方向

無約束問題最優化方法的核心問題是選擇搜索方向。

以正定二次函數為例，來觀察兩個方向關于矩陣Ａ共軛的幾何意義。

設有二次函數：

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

其中A是n×n對稱正定矩陣，x*是一個定點，函數f(x)的等值面

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

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

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

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

設x(1)是在某個等值面上的一點，該等值面在點x(1)處的法向量

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

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

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

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

d(1)TAd(2)=0，

即等值面上一點處的切向量與由這一點指向極小點的向量關于A共軛。

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

1.共軛梯度法

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

Fletcher-Reeves共軛梯度法，簡稱FR法。

共軛梯度法的基本思想是把共軛性與最速下降方法相結合，利用已知點處的梯度構造一組共軛方向，并沿這組方向進行搜素，求出目標函數的極小點。根據共軛方向基本性質，這種方法具有二次終止性。

對于二次凸函數的共軛梯度法：

minf(x)=1/2xTAx+bTx+c,

其中x∈Rn，A是對稱正定矩陣，c是常數。

具體求解方法如下：

首先，任意給定一個初始點x(1)，計算出目標函數f(x)在這點的梯度，若||g1||=0，則停止計算；否則，令

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

沿方向d(1)搜索，得到點x(2)。計算在x(2)處的梯度，若||g2||≠0，則利用-g2和d(1)構造第2個搜索方向d(2)，在沿d(2)搜索。

一般地，若已知點x(k)和搜索方向d(k)，則從x(k)出發，沿d(k)進行搜索，得到

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

其中步長λk滿足

f(x(k)+λkd(k))=minf(x(k)+λd(k))。

此時可求出λk的顯示表達

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

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)。

再從x(k+1)出發，沿方向d(k+1)搜索。

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

3.非線性共軛梯度

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

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

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

式中gk-1和gk分別為第k-1和第k次搜索是計算出來的目標函數的梯度。

總結

以上是生活随笔為你收集整理的最速下降法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。