一、 引言
無約束優化問題是實際工程中最常見的問題之一。這類問題雖然形式比較簡單,但是對於某些大規模的或者非線性很強的問題,求解它們仍然是有相當難度的。
無約束問題的演算法大致分成兩類:一類在計算過程中要用到目標函式的導數,另一類則只要求目標函式值。本文中所講述的信賴域法,與牛頓法、最速下降法、共軛梯度法一樣,同屬於第一類方法。
二、 信賴域法的主要內容
2.1 信賴域法的基本思想
雖然信賴域法與最速下降法等同屬於一大類,但是在基本思想上還是有所不同。其他幾種方法的基本策略是:給定點x(k)後,定義搜尋方向d(k),再從x(k)出發沿d(k)作一維搜尋,信賴域法則不然,下面重點闡述一下其基本思想:
首先給定乙個所謂的「信賴域半徑」作為位移長度的上界,並以當前迭代點為中心以此「上界」為半徑確定乙個稱之為「信賴域」的閉球區域。然後,通過求解這個區域內的「信賴域子問題」(目標函式的二次近似模型)的最優點來確定「候選位移」。若候選位移能使目標函式值有充分的下降量,則接受該候選位移作為新的位移,並保持或擴大信賴域半徑,繼續新的迭代。
否則,說明二次模型與目標函式的近似度不夠理想,需要縮小信賴域半徑,再通過求解新的信賴域內的子問題得到新的候選位移。如此重複下去,直到滿足迭代終止條件。
2.2 信賴域法的數學分析
考慮無約束問題2-1)
將f(x)在給定點x(k)展開,取二次近似可得:
(2-2)
記d=x- x(k),得到二次模型
2-3)
為了在x(k)附近用近似f(x(k)+d),限定d的取值,令||d||≤rk,rk是給定的常數,稱為信賴域半徑,這樣求函式f(x)的極小點歸結為解一系列子問題
(2-4)
若d(k)是2-1式的最優解,則存在乘子,使得:
2-5)
記作2-6)
得到d(k)為最優解的必要條件
2-7)
設可逆,由式2-7可得,
2-8)
由上述條件易知,式2-7的解d(k)與信賴域半徑rk取值有關,如果rk充分大,的值有可能很小,從而d(k)與牛頓法中的牛頓方向接近,即
2-9)
如果rk趨近於0,則可得:
由此可知,當信賴域半徑rk由小到大逐漸增大時,d(k)在最速下降方向與牛頓方向之間連續變化。得出式2-4的最優解d(k)後,點x(k)+d(k) 能否作為式2-1的近似解,還要根據逼近f(x)是否成功來確定。如果函式值實際下降量與**下降量之比太小,就認為不成功,後繼點仍取x(k);若比較大,則逼近成功,令x(k+1)=x(k)+d(k)。
信賴域方法計算步驟如下:
1) 給定可行點x(1),信賴域半徑r1,引數(一般取=0.25, =0.75),精度要求,置k=1
2) 計算f(x(k)),.若,則停止計算,得解x(k);否則計算
3) 求解子問題
得到子問題的最優解並令
4) 如果,令x(k+1);如果,令x(k+1)= x(k) +d(k)
5) 修改rk。如果,令rk+1=;如果,令rk+1=;如果,令rk+1=
6) 置k=k+1,轉步驟(2)。
總的來說,其步驟可由圖2-1來表示。
2.3 信賴域法的收斂問題
在一定條件下,信賴域方法具有全域性收斂性。查閱相關資料,定理如下:設f(x)是上的實函式,x(1)是給定的初始點,是有界閉集,和在上連續,用信賴域方法求的序列{x(k)},則
三、 運用信賴域法求解具體問題
考慮無約束問題
取初點,信賴域半徑r1=1,取=0.25, =0.75.用信賴域法求解過程:
1) 將初值代入目標函式求得函式值f(x(1))=5,目標函式的梯度,hesse矩陣
2) 求解子問題
即為求解
可得最優解,函式值
3) 可得,逼近成功,令,
4) 進行二次迭代,函式值為2,,
5) 求解子問題
可得最優解,,
6) 可得,令,
7) 計算得是最優解
第三章無約束最優化方法
把乙個多維問題轉化為一系列較少維數的問題稱為降維。降維方法有幾種,座標輪換法是用得較多的一種,這是一種不需要求函式導數的直接探索目標函式最優解的方法。直接法 降維法 一 座標輪換法的基本思想 其基本思想就是通過每次僅對多元函式的乙個變數沿其座標軸進行一維探索,其餘各變數均固定不動,並依次輪換進行一維...
第十八章無約束最優化的梯度方法
目的是在找一點稱為此無約束最優化問題的全域性最優點。然而在實際中,大多數最優化方法只能求到區域性最優點,即在中可找到一點使得在的某個鄰域中有。但在實際中,可以根據問題的意義來判斷求得的區域性極小點是否為全域性最優點,無約束最優化可以分為兩大類 一類是使用導數的方法,也就是根據目標函式的梯度 一階導數...