無約束優(yōu)化的間接搜索法課件

1、機械優(yōu)化設(shè)計太原科技大學(xué)張學(xué)良第1頁，共40頁。第五章 無約束優(yōu)化的間接搜索法 間搜索法是指搜索方向S(k)的構(gòu)建利用目標(biāo)函數(shù)的一階或二階導(dǎo)數(shù)信息的無約束優(yōu)化方法，如梯度法、牛頓法、共軛梯度法、變尺度法。 X (k+1)=X (k) + (k) S(k) (k =0 , 1 , 2 , )第2頁，共40頁。 基本思想 5.1 梯度法（最速下降法、負梯度法） 利用負梯度方向作為迭代計算的搜索方向，即S(k) = f (X(k) ) 或 S(k) = f (X(k) )/| f (X(k) ) | 迭代計算公式 X (k+1)=X (k) + (k) f (X(k) )或 X (k+1)=X (k

2、) + (k) f (X(k) )第3頁，共40頁。 舉例： 用梯度法求目標(biāo)函數(shù) f (X) = x12 + 4x22 的無約束最優(yōu)解。初始點X1(0)= 0 0 T ， X2(0)= 2 2 T。第4頁，共40頁。 基本思想和基本算法 5.2 牛頓法 在點X(k)的鄰域內(nèi)，用一個二次函數(shù)(X) 來近似代替原目標(biāo)函數(shù)，并以 (X ) 的極小點作為原目標(biāo)函數(shù)的極小點的近似值，若不滿足收斂精度要求，則將該近似極小點作為下一次迭代的初始點。如此反復(fù)迭代，直到所求的近似極小點滿足收斂精度要求為止。第5頁，共40頁。 f (X) f (X (k) + T f (X (k) (X - X (k) + 0.

3、5 (X - X (k) T 2 f (X (k) (X - X (k)= (X) (X)的極小點應(yīng)滿足： (X)=0 即 f (X (k)+ 2 f (X (k) (X - X (k) =02 f (X (k) (X - X (k) = - f (X (k) 當(dāng) 2 f (X (k) 正定且有逆陣時，上式兩邊同時左乘 2 f (X (k) -1， 得X = X (k) - 2 f (X (k) -1 f (X (k)第6頁，共40頁。 牛頓法的迭代公式為X (k+1) = X (k) - 2 f (X (k) -1 f (X (k) X (k+1)=X (k) + (k) S(k)牛頓方向：

4、S(k) = - 2 f (X (k) -1 f (X (k) 迭代步長：(k) =1 修正牛頓法（又稱阻尼牛頓法）的迭代公式為X (k+1) = X (k) - (k) 2 f (X (k) -1 f (X (k) 阻尼因子： (k) 第7頁，共40頁。 計算步驟及算法框圖 1） 任選初始點 X (0) ，給定收斂精度0， k=0； 2） 計算X (k)點的梯度f (X (k)及其模； 3） 檢驗終止條件： | f (X (k) | ？ 若滿足，則輸出最優(yōu)解：X * = X (k)， f * = f (X *) ，并終止迭代計算 ； 否則，繼續(xù)下一步迭代計算；第8頁，共40頁。 4）計算X

5、(k)點的海賽矩陣2 f (X (k)及其逆矩陣2 f (X (k) -1 5）沿牛頓方向S(k) = - 2 f (X (k) -1 f (X (k)進行一維搜索，求最佳步長(k)； 6）令X (k+1)=X (k) + (k) S(k) ，并令k k+1，轉(zhuǎn)2），重復(fù)上述迭代計算過程。第9頁，共40頁。舉例： 用牛頓法求目標(biāo)函數(shù) f (X) = x12 + 4x22 的無約束最優(yōu)解。初始點X1(0)= 0 0 T ， X2(0)= 2 2 T。 解： f (X) = 2x1 8x2 T2 f (X)= 00 82 f (X) -1 =0.5 00 0.125f (X1(0) ) = 0 0

6、 Tf (X2(0) ) = 4 16 TX1(1)= X1(0) - 2f (X1(0)-1 f (X1(0) ) = 0 0 T - 0.5 00 0.125 0 0 = 0 0 T 第10頁，共40頁。X2(1)= X2(0) - 2f (X2(0)-1 f (X2(0) ) = 2 2 T - 0.5 00 0.125 4 16 = 0 0 T 可見，X2(1)= X1(0) = 0 0 T 就是目標(biāo)函數(shù)的理論極小點，僅僅迭代了一次，與初始點的選擇無關(guān)。 由于一般函數(shù)在極小點附近呈現(xiàn)出較強的二次性，所以牛頓法在極小點附近收斂速度較快。但無論是牛頓法還是修正牛頓法在每次迭代計算時都要計算

7、目標(biāo)函數(shù)的海賽第11頁，共40頁。矩陣及其逆陣，因此計算工作量很大，特別是矩陣求逆，當(dāng)維數(shù)高時工作量更大，且當(dāng)海賽矩陣為奇異陣時，其逆陣不存在，無法使用牛頓法，所以在實際使用中受到一定限制。另外，從計算機存儲方面考慮，牛頓法所需要的存儲量是很大的。 若能設(shè)法構(gòu)造一個矩陣來逼近海賽矩陣的逆陣而避免計算海賽矩陣及其逆陣，這樣的方法統(tǒng)稱為擬牛頓法。如只用梯度信息但比梯度法快的共軛梯度法，以及針對牛頓法提出的變尺度法等。第12頁，共40頁。 基本思想5.3 共軛梯度法 共軛梯度法屬于共軛方向法中的一種方法。它是利用目標(biāo)函數(shù)在迭代點X(k)的梯度來構(gòu)造共軛搜索方向的，具有二次收斂性。 共軛梯度法搜索的第

8、一步沿負梯度方向，以后各步沿與上次搜索方向相共軛的方向進行搜索。共軛梯度法的關(guān)鍵是如何在迭代過程中不斷生成共軛搜索方向第13頁，共40頁。 共軛梯度法共軛搜索方向的生成 考慮二次函數(shù) f (X) = 0.5 XT H X + BT X + C 從 X(k) 出發(fā)，沿H的某一共軛方向S(k)作一維搜索得到 X(k+1)，即 X(k+1) X(k) = (k) S(k) （1）將f (X)在 X(k) 和 X(k+1)兩點處的梯度表示并記作 g(k) = f (X(k) ) = H X(k) + B （2） g(k+1) = f (X(k+1) ) = H X(k+1） + B （3）第14頁，共

9、40頁。（3）-（2）得 g(k+1) g(k) = H ( X(k+1) X(k) )= (k) H S(k) （4）（4）式兩邊同時左乘S(j) T，有S(j) Tg(k+1) g(k) = (k) S(j) TH S(k) = 0 若S(j)和S(k)關(guān)于H共軛，則有S(j) T H S(k) = 0即 S(j) T g(k+1) g(k) = 0 （5） 式（5）就是共軛方向與梯度之間的關(guān)系。它表明沿方向S(k) 進行一維搜索，其終點X(k+1)與始點X(k)梯度之差(g(k+1)g(k)與 S(k) 的共軛第15頁，共40頁。方向S(j)與正交。共軛梯度法就是利用這個性質(zhì)做到不必計算

10、矩陣H就能求得共軛方向的。 1）設(shè)初始點X(0) ，第一個搜索方向S(0)取X(0)點的負梯度方向 -g(0)。即 S(0) = -g(0) 沿S(0)進行一維搜索，得 X(1) = X(0) + (0) S(0)，并計算X(1)點的梯度 g(1) 。 那么， g(1)與S(0) 有什么關(guān)系呢？X(0)g(1)-g(0)X(1) 二者正交，即 g(1)TS(0)=0 或 S(0)Tg(1) =0 因此，S(0)與g(1)構(gòu)成平面正交系。第16頁，共40頁。 2）在S(0)與g(1)構(gòu)成的平面正交系中求S(0)的共軛方向S(1)，以此作為下一步迭代計算的搜索方向。取S(1)為S(0)與g(1)的

11、線性組合，即 S(1) = -g(1) + (0)S(0) 其中，(0)為待定常數(shù)，可以利用共軛方向與梯度之間的關(guān)系求得。 由 S(1) T g(1) g(0) = 0 有 -g(1) + (0)S(0) T g(1) g(0) = 0 展開，得- g(1)Tg(1) +g(1)Tg(0)+(0)S(0)Tg(1) - (0)S(0)Tg(0) = 0 第17頁，共40頁。所以 - g(1)Tg(1) - (0)S(0)Tg(0) = 0所以 (0) = - g(1)Tg(1) / S(0)Tg(0) = g(1)Tg(1) / g(0)Tg(0) = |g(1)|2 / |g(0)|2S(1

12、) = -g(1) + |g(1)|2 / |g(0)|2 S(0) 沿S(1)進行一維搜索，得 X(2) = X(1) + (1) S(1)，并計算X(2)點的梯度 g(2) ，則有S(1)Tg(2) =0第18頁，共40頁。 故有 -g(1) + (0)S(0) T g(2) = 0 （6） 因為S(0)和S(1)共軛，所以有S(0) T g(2) g(1) = 0 因為 S(0) T g(1) = 0 所以 S(0) T g(2) = 0 即 g(2) 與g(0)正交。 所以 S(0) T g(2) = 0 由式（6）得 g(1) T g(2) = 0 可見， g(0)、g(1) 、g(

13、2)構(gòu)成一個空間正交系。第19頁，共40頁。 3）在g(0)、g(1)、g(2)構(gòu)成的空間正交系中求與S(0)及S(1)均共軛的方向S(2)，以此作為下一步迭代計算的搜索方向。仍取S(2)為g(0)、g(1)、g(2) 的線性組合，即 S(2) = -g(2) + (1) g(1) + (0) g(0) 其中， (1) 、 (0) 為待定常數(shù)，可以利用共軛方向與梯度之間的關(guān)系求得。 S(2) T g(1) g(0) = 0 S(2) T g(2) g(1) = 0第20頁，共40頁。 即 -g(2) + (1) g(1) + (0) g(0) T g(1) g(0) = 0 -g(2) + (

14、1) g(1) + (0) g(0) T g(2) g(1) = 0 所以 (1)g(1)Tg(1) - (0) g(0)T g(0) = 0 -g(2)T g(2) - (1)g(1)Tg(1) = 0 令 (1) = - (1) 得 (1) = - (1) = g(2)T g(2)/ g(1)Tg(1) = |g(2)|2 / |g(1)|2 (0) = (1) g(1)T g(1)/ g(0)Tg(0) = - (1) (0)第21頁，共40頁。 因此 S(2) = -g(2) + (1) g(1) + (0) g(0) = -g(2) - (1) g(1) - (1) (0) g(0)

15、 = -g(2) + (1) - g(1) - (0) g(0) = -g(2) + (1) S(1) 故 S(2) = -g(2) + |g(2)|2 / |g(1)|2 S(1) 再沿S(2) 進行一維搜索，得 X(3) = X(2) + (2) S(2)，如此繼續(xù)下去，可以求得共軛方向的遞推公式為 S(k+1) = -g(k+1) + |g(k+1)|2 / |g(k)|2 S(k)(k = 0, 1, 2, , n-1)第22頁，共40頁。 沿著這些共軛搜索方向一直搜索下去，直到最后迭代點處梯度的模小于給定的允許值為止。若目標(biāo)函數(shù)為非二次函數(shù)，經(jīng)n次搜索還未達到最優(yōu)點時，則以最后得到的

16、點作為初始點，重新計算共軛方向，一直到滿足精度要求為止。 共軛梯度法的計算步驟及算法框圖 1）給定初始點X(0)及收斂精度0，k=0； 2）取 S(0) = f (X(0) )；第23頁，共40頁。 3） X(k+1) = X(k) + (k) S(k) ( k = 0, 1, 2, , n) (k) 為一維搜索所得的最佳步長。 4） 判斷 | f (X(k+1) ) | ? 若滿足，則輸出 X * = X(k+1) 和 f * = f (X * ) 否則，轉(zhuǎn)下一步； 5） 判斷 k+1=n ? 若 k+1=n ，令X(0) = X(k+1) ，轉(zhuǎn) 2）； 若 k+1n ，則計算 (k) =

17、| f (X(k+1) ) |2 / | f (X(k) ) |2第24頁，共40頁。 S(k+1) = - f (X(k+1) ) + (k) S(k) 并令 k k+1，轉(zhuǎn)3）。 1）盡管理論上可以證明目標(biāo)函數(shù)為n維正定二次函數(shù)時，共軛梯度法只需要n次迭代就可以達到最優(yōu)點，但由于計算機的舍入誤差，實際計算往往要多進行若干次才能得到滿足精度要求的結(jié)果；而對于一般的目標(biāo)函數(shù)，迭代次數(shù)將更多。 關(guān)于共軛梯度法的說明第25頁，共40頁。 2）由于n維設(shè)計空間中最多只能有n個線性無關(guān)的向量，所以n維優(yōu)化問題的共軛方向最多只有n個。因此，共軛梯度法進行n步搜索后，若仍不滿足精度要求，繼續(xù)產(chǎn)生共軛方向S

18、(n+1)進行迭代搜索是沒有意義的（效果很差），而應(yīng)令X(0) = X(n) ，重新開始新一輪的共軛梯度法迭代搜索。實踐證明，這樣處理一般都可以取得較好的效果。第26頁，共40頁。舉例： 用共軛梯度法求目標(biāo)函數(shù) f (X) = x12 + 4x22 的無約束最優(yōu)解。初始點X(0)= 2 2 T， =0.01 。 解： f (X) = 2x1 8x2 TS(0) = -f (X(0) ) = -4 -16 T X(1)= X(0) - (0)f (X(0) )=2 2 T - (0) 4 16T = 2 - 4(0) 2 - 16(0) T f (X(1) = (2 - 4(0)2 +4 (2 - 16(0)2據(jù) df (X(1)/d(0) = 0 得 (0)=0.13076923 X(1)=1.476923077 -0.09230768 T 第27頁，共40頁。f (X(1) ) = 2.953846154 -0.73846144 T(0) = | f (X(1) ) |2 / | f (X(0) ) |2 =0.034082837 S(1) = - f (X(1) ) + (0) S(0) = - 2.953846154 -0.73846144 T + 0.034