研究尋求多元函數f(x)=f(x1,x2,…,xn)在整個實n維空間Rn中局部極小值點的數值方法。它在非線性規劃的研究中占有很重要的位置,除瞭本身的意義與應用外,它也是許多帶約束優化方法的基礎。
大多數無約束優化方法都是迭代法,每一次迭代都從某一點x
![](/img3/10862.gif)
移到另一個適合條件
f(x
![](/img3/10863.gif)
)<
f(
x
![](/img3/10862.gif)
) (1)
的點
x
![](/img3/10863.gif)
。為瞭得到
x
![](/img3/10863.gif)
,首先要確定移動的方向
s
![](/img3/10862.gif)
,其次要確定沿方向
s
![](/img3/10862.gif)
移動的步長
λ
k,於是
x
![](/img3/10863.gif)
=
x
![](/img3/10862.gif)
+
λ
k
s
![](/img3/10862.gif)
。對應於
s
![](/img3/10862.gif)
與
λ
k的不同選取,就得到不同的算法。
直接法 往往以直觀或以計算實踐為基礎而產生,這類算法的特點是隻要求計算函數值本身,因而易於使用,但是與另一些要求計算偏導數值的方法相比,又收斂得慢。所以直接法常常用於變量極少而函數比較復雜且不易計算偏導數的情形。較為常用的直接法有鮑威爾法、單純形調優法和模式搜索法。
最陡下降法和牛頓-拉弗森方法 在要求計算偏導函數值的算法類中,一般取移動方向s
![](/img3/10862.gif)
滿足
![](/img3/10864.gif)
, (2)
這裡的T表示矩陣(或向量)的轉置運算,▽
f(
x)表示
f(
x)在點
x上的梯度,即
![](/img3/10865.gif)
。
式(2)保證瞭在以
x
![](/img3/10862.gif)
為始點,
s
![](/img3/10862.gif)
為方向的半直線
![](/img3/10866.gif)
(3)
上一定有點
x適合
f(
x)<
f(
x
![](/img3/10862.gif)
)。為瞭使式(2)成立,往往取
![](/img3/10867.gif)
, (4)
式中
H
k是一
n階的對稱正定矩陣。
通常,步長λk的選取原則是取λk使x
![](/img3/10863.gif)
為
f(
x)在半直線(3)上的最小值點。這樣選取步長
λ
k的過程稱為精確線性搜索或簡稱線性搜索。這時有
![](/img3/10868.gif)
, (5)
亦即點
x
![](/img3/10863.gif)
上的梯度方向與移動方向成正交。
隻要▽f(x
![](/img3/10862.gif)
)≠0,總可以按上述方法進行迭代。在一定的假設下,能夠證明▽
f(
x
![](/img3/10862.gif)
)→0,於是對於凸函數
f(
x),點列{
x
![](/img3/10862.gif)
}的任何極限點都是
f(
x)的最小值點;而對於一般的非凸函數,即使不能保證{
x
![](/img3/10862.gif)
}的極限點是局部最小值點,但因目標函數值逐次減少,往往也能得到滿意的結果。
可以證明,在由x
![](/img3/10862.gif)
出發的所有同樣長度的方向中,負梯度方向是使函數值下降最快的方向。於是取移動方向
s
![](/img3/10862.gif)
為負梯度方向-▽
f(
x
![](/img3/10862.gif)
),或者等價地取(4)中的
H
k為單位矩陣
I,並由線性搜索確定步長
λ
k與下一點
x
![](/img3/10863.gif)
。這就是通常所謂的最陡下降法。
牛頓-拉弗森法則以f(x)的二次近似
![](/img3/10870.gif)
為基礎,在二階偏導數矩陣▽
2
f(
x
![](/img3/10862.gif)
)為正定時,以此二次近似的最小值點為下一點,即取
![](/img3/10871.gif)
,
但這樣得到的
x
![](/img3/10863.gif)
未必適合式(1),因此又改成以
![](/img3/10873.gif)
為移動方向,或者等價地在(4)中取
H
k為(▽
2
f(
x
![](/img3/10862.gif)
))
-1,再通過線性搜索來確定
λ
k與
x
![](/img3/10863.gif)
。
在一些有關f(x)的假設下,對於這兩個古老的方法,都可證明▽f(x
![](/img3/10862.gif)
)→0。這兩個方法各有其優缺點。最陡下降法比較簡單,並且除瞭函數值本身外,隻需要計算一階偏導數的值;但是理論分析和計算實踐都表明這個方法的收斂速度很慢。事實上,由
![](/img3/10874.gif)
及式(5)可知,{
x
![](/img3/10862.gif)
}中的點沿著相互正交的方向交替前進,因此,即使對於二次嚴格凸函數
![](/img3/10875.gif)
, (6)
式中
A對稱正定,隻要
A不是數量矩陣α
I,那麼
x
![](/img3/10862.gif)
就曲折前進,且進展很慢。當
n=2時如圖
所示。
與此相反,牛頓-拉弗森方法收斂得快。特別對於形如(6)的二次嚴格凸函數,隻要一次迭代,就能達到最優解x*,即使對於一般的函數f(x),在某些假設下,也可證明{x
![](/img3/10862.gif)
}為二階收斂。這個方法不僅要計算
n個一階偏導數,而且還要計算
![](/img3/10877.gif)
個二階偏導數,因此隻在
n比較小或函數比較簡單的情形才使用。
共軛梯度法與變尺度法是既有較快的收斂速度又無需計算二階偏導函數的算法。
共軛梯度法 由於在局部最小值點的鄰近,函數的性狀與二次凸函數(6)十分相似,所以對於一個好的尋優方法,人們要求它在應用於二次凸函數時有較快的收斂速度,即使最小值點不能象牛頓-拉弗森方法那樣一步達到,也應在有限步內達到。事實上,沿著y空間中n個兩兩正交的方向依次作線性搜索,一定可以達到函數1/2(y-y*)T(y-y*) 的最小值點y*。於是通過變換y=A1/2x,沿著x空間中n個滿足
![](/img3/10878.gif)
(7)
的方向
s
(1),
s
(2),…,
s
(n)依次作線性搜索,就一定能達到函數(6)的最小值點
x
*。滿足式(7)的
n個非零方向
s
(1),
s
(2),…,
s
(n)稱為關於矩陣
A的共軛方向系。20世紀60年代R.弗萊徹和C.M.裡夫斯用梯度向量構造出共軛方向系,提出瞭共軛梯度法。它從任意的初始點
x
(1)開始,在第
k次迭代時取移動方向
然後沿著半直線(3)作線性搜索得到
x
![](/img3/10863.gif)
。在將它應用於二次凸函數(6)時,它就是一個共軛方向法,最多
n次迭代就能達到最小值點
x
*。共軛梯度法也適用於非二次的目標函數。在將共軛梯度法應用於非二次的目標函數時,常常采用周期性重開始的策略,也就是說,對於
n除餘1的自然數
k,移動方向
s
![](/img3/10862.gif)
都取為負梯度方向-▽
f(
x
![](/img3/10862.gif)
),而對其他的
k,
s
![](/img3/10862.gif)
則由(8)中第二個公式定義,采用這種策略,數值效果將有顯著改進,理論上也可證明可以達到
n步二階收斂,也即存在正常數α使對充分大的
k,都有
而若不采取周期性重開始的策略,其收斂階僅為線性。共軛梯度法由於隻需要存貯幾個向量,特別適宜於解大型問題。當然,還需要采用條件予優的方法以加速收斂。
變尺度方法 也有人稱為擬牛頓方法。這是近二十多年來發展起來的一類很有成效的尋優方法。理論分析和計算實踐都表明這類方法的收斂速度較快,同時又無需計算二階偏導數矩陣。這類方法的共同特點是:移動方向s
![](/img3/10862.gif)
由(4)定義,其中
H
k為
n階對稱正定方陣;
H
1可以任意選取,但通常取
H
1=
I;當
k>1時,
H
k由
H
k
-1和
![](/img3/10882.gif)
以及
![](/img3/10883.gif)
確定,並滿足如下的擬牛頓方程
![](/img3/10884.gif)
(9)
步長
λ
k和下一點
x
![](/img3/10863.gif)
由線性搜索確定。
第一個變尺度法是W.D.戴維登於1959年首先提出的,而由 R.弗萊徹和 M.J.D.鮑威爾在理論上作瞭研究並於1963年公開發表,所以通常稱為DFP方法,在這個方法中,Hk(k>1)的定義如下:
![](/img3/10885.gif)
。
由於DFP方法的成功,在其後十多年間,又提出瞭許多變尺度方法,這些方法隻在Hk(k>1)的定義方法上有所不同。在理論上,隻要x
![](/img3/10886.gif)
、
H
1取得相同,那麼在一定條件下,由不同的變尺度方法產生的點列{
x
![](/img3/10862.gif)
}都隻依賴於某一參數;但在實際計算中,由於舍入誤差的關系,由不同的變尺度方法產生的點列未盡相同。最成功的變尺度法是BFGS法,它的
H
k(
k>1)定義為
![](/img3/10887.gif)
與DFP方法相比,BFGS方法具有較好的數值穩定性。
無論是DFP方法或者 BFGS方法,都有以下一些性質:①隻要初始的矩陣H1正定,那麼以後的各個矩陣Hk(k≥1)也都正定;②將它們應用於二次嚴格凸函數(6)時,由算法所確定的移動方向序列s(1),s(2),…,s(n)是一組關於矩陣A的共軛方向系,所以最多經過n次迭代,一定能夠達到二次嚴格凸目標函數的最小點x*;③理論上可以證明這兩個算法在一定的條件下都是超線性收斂並且都是n步二階收斂的。
不精確線性搜索或可接受點準則 前述各法都是建立在線性搜索的基礎之上的,即取x
![](/img3/10863.gif)
恰為
f(
x)在半直線(3)上的最小值點,但在實際計算中,無法做到;雖然可以用黃金分割、二次插值等方法做到充分的近似,卻極為費時。近年來,人們註意建立在不精確線性搜索的基礎之上的方法。鮑威爾於1976年證明瞭:用適當的不精確線性搜索代替線性搜索後,BFGS算法仍是超線性收斂的。80年代,又出現瞭信賴域方法和基於錐模型的優化算法,已取得瞭良好的效果,受到瞭廣泛的重視。
最小平方和問題 一類具有特殊形式的無約束優化問題。在這類問題中,目標函數f(x)是一些函數的平方和,即
![](/img3/10888.gif)
。這類問題在數據擬合中經常出現,方程組的求解也可轉化為最小平方和的問題。由於目標函數具有特殊的形式,所以人們設計瞭專門的方法,如高斯-牛頓方法、萊文貝格-馬誇特方法等。
參考書目
R.Fletcher,Prαcticαl Methods of Optimizαtion,Unconstrαined Optimizαtion,Vol.1,John Wiley &Sons,New York,1979.