第4章無約束優(yōu)化方法

1、2021/3/231機械優(yōu)化設計2021/3/232第四章第四章 無約束優(yōu)化方法無約束優(yōu)化方法機械優(yōu)化設計2021/3/2334.14.24.34.44.54.64.74.84.9機械優(yōu)化設計2021/3/234,數(shù)值解法數(shù)值解法: :是利用是利用已有已有的信息的信息, ,通過計算點一步一步地直接通過計算點一步一步地直接移動移動, ,逐步逼近逐步逼近最后達到最優(yōu)點。最后達到最優(yōu)點。 1(0,1,)kkkkxxdk1 1）選擇迭代方向即探索方向）選擇迭代方向即探索方向; ;2 2）在確定的方向上選擇適當步長邁步進行探索）在確定的方向上選擇適當步長邁步進行探索 機械優(yōu)化設計2021/3/235,

2、一類是利用目標函數(shù)的一類是利用目標函數(shù)的一階或二階導數(shù)一階或二階導數(shù)的無約束優(yōu)化的無約束優(yōu)化方方法（如最速下降法、共軛梯度法、牛頓法及變尺度法）法（如最速下降法、共軛梯度法、牛頓法及變尺度法）; ; 另一類另一類只利用目標函數(shù)只利用目標函數(shù)的無約束優(yōu)化方法（如坐標輪的無約束優(yōu)化方法（如坐標輪換換法、單形替換法及鮑威爾法等）。法、單形替換法及鮑威爾法等）。機械優(yōu)化設計2021/3/236, 最速下降法就是采用使目標函數(shù)值下降得最快的最速下降法就是采用使目標函數(shù)值下降得最快的負負梯度方向梯度方向作為探索方向作為探索方向, ,來求目標函數(shù)的極小值的方法來求目標函數(shù)的極小值的方法, ,又稱為又稱為梯度

3、法梯度法。1()(0,1,)kkkkxxf xk最速下最速下降法的降法的迭代公迭代公式式機械優(yōu)化設計2021/3/237, 011*10();3minmin4|;1,kkkkkkkkkkkkkxkdf xfxa daxxa dxxxxkk 1）給定初始點 和收斂精度 ，置；2）計算梯度，并構造搜索方向）用一維搜索的方法求解得最佳步長 ，代入得到新的迭代點；）若，則停止迭代，得最優(yōu)解否則，轉到第二步。機械優(yōu)化設計2021/3/2382212 ( )25 f xxx例：用最速下降法求目標函數(shù)的極小點。,1()(0,1,)kkkkxxf xk機械優(yōu)化設計2021/3/239, 1 1）對）對初始搜索

4、點初始搜索點無嚴格要求無嚴格要求; ; 2 2）收斂）收斂速度不快速度不快; ; 3 3）相鄰兩次相鄰兩次迭代搜索迭代搜索方向方向互相互相垂直垂直, ,在遠離極值點處收在遠離極值點處收斂快斂快, ,在靠近極值點處收斂慢在靠近極值點處收斂慢; ; 4 4）收斂速度與）收斂速度與目標函數(shù)值的性質(zhì)目標函數(shù)值的性質(zhì)有關有關, ,對等值線是對等值線是同心同心圓圓的目標函數(shù)來說的目標函數(shù)來說, ,經(jīng)過經(jīng)過一次迭代一次迭代就可以達到極值點。就可以達到極值點。機械優(yōu)化設計2021/3/2310, 利用利用二次曲線二次曲線來逐點來逐點近似原目標函數(shù)近似原目標函數(shù), ,以以二次曲線的二次曲線的極極小點小點來來近似

5、原目標函數(shù)的極小點近似原目標函數(shù)的極小點并逐漸逼近該點。并逐漸逼近該點。 基本牛頓法的迭代公式：基本牛頓法的迭代公式：11 (0,1,2)()kkkkkkxxdkdG xf x 機械優(yōu)化設計2021/3/2311,基本牛頓法的迭代公式：基本牛頓法的迭代公式：11 (0,1,2)()kkkkkkxxdkdG xf x 022121211,1 ,0.1 min( )224Txf xxxx xx例：用基本牛頓法求解下列無約束優(yōu)化問題，已知。機械優(yōu)化設計2021/3/2312,基本牛頓法的迭代公式：基本牛頓法的迭代公式：11 (0,1,2)()kkkkkkxxdkdG xf x 阻尼牛頓法的迭代公式：

6、阻尼牛頓法的迭代公式：11 (0,1,2,)() kkkkkkkxxdkdG xfx 機械優(yōu)化設計2021/3/2313,01111*1,0;()()()()34|;1,kkkkkkkkkkkkkkkxkf xG xG xdG xf xxxddxxxxkk 1）給定初始點收斂精度 ，置2）計算、和，得到；）求，其中，是沿著進行一維搜索的最佳步長；）檢查收斂精度。若，則停止迭代，得最優(yōu)解否則，轉到第二步繼續(xù)進行搜索。機械優(yōu)化設計2021/3/2314,022121211,1 ,0.1 min( )224Txf xxxx xx例：用阻尼牛頓法求解下列無約束優(yōu)化問題，已知。阻尼牛頓法的迭代公式：阻尼

7、牛頓法的迭代公式：11 (0,1,2,)() kkkkkkkxxdkdG xfx 機械優(yōu)化設計2021/3/2315,10()0Tf xd 在下一次迭代時，選擇搜索方在下一次迭代時，選擇搜索方d d1 1指向極小點指向極小點x x* *， *111xxa d以以二元函數(shù)二元函數(shù)為例：為例： 我們?nèi)我膺x擇一個我們?nèi)我膺x擇一個初始點初始點x x0 0點，點，沿著沿著某個下降方向某個下降方向d d0 0作一維搜索作一維搜索 1000 xxa d 12TTfxx Gxb xc010TdGd 機械優(yōu)化設計2021/3/2316,01m 101m 1Gnmddd()0 ( ,0,1,1) ()dddGGi

8、 TjdGdi jmij設 是n n對稱正定矩陣，若 維空間中有 個非零向量 、 、 、滿足 則稱 、 、 、對 共軛，或稱它們是 的共軛方向。01m 1G I()0 ()dddiTjddij當= （單位矩陣）時，有，即向量、 、 、互相正交。機械優(yōu)化設計2021/3/2317, 01m 1001n 1*dddG() m2nn3xnGdddn1x2TTf xx Gxb xc性質(zhì)1：若非零向量系、 、 、是對實對稱正定矩陣共軛的，則這 個向量是線性無關的。性質(zhì) ：在 維空間中互相共軛的非零向量個數(shù)不超過 。性質(zhì) ：從任意初始點點出發(fā)，順次沿 個 的共軛方向、 、 、進行一維搜索，最多經(jīng)過 次迭代

9、就可以 找到二次函數(shù)的極小點 。機械優(yōu)化設計2021/3/2318,00k111111xdkd340j01 2k5kk+1kkkkkkTkjkxxa df xxddGd）選定初始點 ，下降方向和收斂精度 ， 置0；2）沿方向進行一維搜索，得；）判斷是否滿足，滿足則打印， 否則，轉到第四步；）提供新的共軛方向，使， ， ，；）置，轉第二步。機械優(yōu)化設計2021/3/2319,111,0iiriirrdvdn n個線性無關的向量系個線性無關的向量系vi vi（i=0,1,i=0,1, ,n-1 n-1 ）一組獨立向量一組獨立向量d dr r（r=0,1,r=0,1, ,n-1n-1） 11,()(

10、)jTiijjTjdGvdGd 1110()()jTiijiijTjjdGvdvddGd機械優(yōu)化設計2021/3/2320012210G=121012ddd例：求的一組共軛向量系、 、。,1110()()jTiijiijTjjdGvdvddGd111,0iiriirrdvd11,()()jTiijjTjdGvdGd 機械優(yōu)化設計2021/3/2321, 先沿先沿最速下降方向最速下降方向( (負梯度方向負梯度方向) )探索第一步探索第一步, ,然后沿與該然后沿與該負梯度方向相負梯度方向相共軛的方向共軛的方向進行探索。進行探索。機械優(yōu)化設計2021/3/2322,1()0Tjkkdgg 它表示沿著

11、方向它表示沿著方向d dk k做一維搜索做一維搜索, ,它的終點它的終點x xk+1k+1與始點與始點x xk k的梯度之差的梯度之差與與d dk k的共軛方向的共軛方向d dj j正交。正交。 機械優(yōu)化設計2021/3/2323,21112| |(0,1,2,1)kkkkkgdgdgkn 機械優(yōu)化設計2021/3/2324,001(1)*1*10121;(),0;3);4)(),()(),5|kkkkkkkkkkkkkdf xkdxxdf xxxf xf xknxxg 1)給定初始點x 和計算精度2）取x 的負梯度方向作為搜索方向：置沿方向作一維搜索得判斷收斂：若滿足則令，結束迭代；否則，轉

12、到第五步；）若，則令，轉到第二步開始新的一輪的迭代；否則，轉到第六步；6）構造新的共軛方向112,|1,kkkkkdgdgkk ，令轉到第三步。機械優(yōu)化設計2021/3/2325,機械優(yōu)化設計2021/3/2326221212112( ,)242f x xxxxx x例：用共軛梯度法求二次函數(shù)的極小點及極小值。,21112| |(0,1,2,1)kkkkkgdgdgkn 機械優(yōu)化設計2021/3/2327 設法構造出一個設法構造出一個對稱正定矩陣對稱正定矩陣 來代替來代替 ，并，并在迭代過程中使在迭代過程中使 逐漸逼近逐漸逼近 , ,那么就簡化了牛頓那么就簡化了牛頓法的計算，并且保持了牛頓法收

13、斂快的優(yōu)點。法的計算，并且保持了牛頓法收斂快的優(yōu)點。kH1()kG x1()kG xkH,1()kkkdG xfx 1 (0,1,2)kkkkkxxHfxk尺度矩陣尺度矩陣機械優(yōu)化設計2021/3/2328, 12TTfxx Gxb xcxQx12TTx Q GQxG G 正定正定TQ GQI牛頓迭代公式：牛頓迭代公式：1kkTkkxxQQf x1TQQGTHQQ1kkkkkxxHfx目標函數(shù)的偏心率減小到零。機械優(yōu)化設計2021/3/2329,1kkkkkxxHf x變尺度法的迭代公式：變尺度法的迭代公式：搜索方向：搜索方向： =kkkkkdHfxH g 尺度矩陣應具備的條件尺度矩陣應具備的

14、條件: :1 1）為正定對稱矩陣；）為正定對稱矩陣；2 2）具有簡單的迭代形式）具有簡單的迭代形式: :3 3）滿足擬牛頓條件：）滿足擬牛頓條件：令令 則則111()kkkkkHggxx1kkkHHE1kkkygg1kkksxx1kkkHys機械優(yōu)化設計2021/3/2330,0000011111*11)2)()03)=4)(),5)66)kkkkkkkkkkkkkkkkkkxgf xHHIkdH gdxxdgf xsxxyggxxnH 選定初始點和收斂精度 ；計算，選定初始對稱正定矩陣 （如），置；計算搜索方向；沿方向進行一維搜索，計算， ；判斷是否滿足迭代終止條件，若滿足則，停機，否則轉到

15、 ；若迭代 次后還沒有找到極小點，重置為單位矩陣011277)13kkkkIxxHHEkk，并以當前設計點 為初始點，返回 進行下一輪迭代，否則轉到 ；計算矩陣，置，返回 。機械優(yōu)化設計2021/3/2331,機械優(yōu)化設計2021/3/2332,DFPDFP算法的校正公式算法的校正公式1 (0,1,2,)TTkkkkkkkkkkTTkkkkks sH y y HHHEHks yy H y機械優(yōu)化設計2021/3/2333,221212112DFP,242 f x xxxxx x例：用算法求的極值解。1 (0,1,2,)TTkkkkkkkkkkTTkkkkks sH y y HHHEHks yy

16、 H y機械優(yōu)化設計2021/3/2334, 每次僅對多元函數(shù)的每次僅對多元函數(shù)的一個變量一個變量沿其沿其坐標軸坐標軸進行進行一維探索一維探索, ,其余各變量均固定不動其余各變量均固定不動, ,并并依次輪換依次輪換進行進行一維一維探索的坐標軸探索的坐標軸, ,完成第一輪探索后再重新進行第二輪探索完成第一輪探索后再重新進行第二輪探索, ,直到找到目標函數(shù)在全域上的最小點為止。直到找到目標函數(shù)在全域上的最小點為止。將一個將一個多維多維的無約束最優(yōu)化問題的無約束最優(yōu)化問題, ,轉化為轉化為一系列一系列的一維問題的一維問題來求解。來求解。機械優(yōu)化設計2021/3/2335,二維問題二維問題機械優(yōu)化設計

17、2021/3/2336,1 (0,1,2, 1,2, )kkkkiiiixxdkin00100kTiide11()()kkkkiiiif xdf x包括正負包括正負機械優(yōu)化設計2021/3/2337,隨機選擇方法隨機選擇方法加速步長法加速步長法最優(yōu)步長法（一維搜索方法最優(yōu)步長法（一維搜索方法, ,如如: :黃金分割法、二黃金分割法、二次插值法次插值法, ,來確定最優(yōu)步長）來確定最優(yōu)步長）11()()kkkkiiiif xdf x11min()()kkkkkiiiiif xdf xd機械優(yōu)化設計2021/3/2338,1111)2)()()3)()J 1()J4)kkiikkkkkiiiiiik

18、iikiihff xf xdff xff x先以試驗步長確定步長的正負，當沿坐標軸正方向探索能使目標函數(shù)值減小時，則取正值，否則應取負值；按所取步長計算目標函數(shù)值若，則取加速步長，使其沿同一方向延伸；若延伸至第次時，則延伸至第 次為止。當步長不宜延伸而宜縮小時，亦可縮小，也是一直到函數(shù)值達到最小值為止；改kid變方向，在新的方向上重復前述過程，直到函數(shù)值達到最小值為止，終止計算。機械優(yōu)化設計2021/3/2339,機械優(yōu)化設計2021/3/2340, 計算簡單、概念清楚、易于掌握計算簡單、概念清楚、易于掌握; ;但搜索路線較長（需但搜索路線較長（需要經(jīng)過多次曲折迂回的路徑才能達到極值點）要經(jīng)過

19、多次曲折迂回的路徑才能達到極值點）, ,計算率較計算率較低低, ,特別是當維數(shù)很高時很費時特別是當維數(shù)很高時很費時, ,所以坐標輪換法只能用所以坐標輪換法只能用于低維（于低維（n10n10）的優(yōu)化問題求解。此外）的優(yōu)化問題求解。此外, ,坐標輪換法的效坐標輪換法的效率在很大程度上取決于目標函數(shù)的性態(tài)率在很大程度上取決于目標函數(shù)的性態(tài), ,也就是等值線的也就是等值線的形態(tài)與坐標軸的關系。形態(tài)與坐標軸的關系。 機械優(yōu)化設計2021/3/2341,直接利用迭代點的直接利用迭代點的目標函數(shù)值目標函數(shù)值來來構造共軛構造共軛方向方向, ,然后再從任一初始點出發(fā)然后再從任一初始點出發(fā), ,逐次的共軛方向逐次

20、的共軛方向作作一維搜索求極值點。一維搜索求極值點。機械優(yōu)化設計2021/3/2342,共軛方向的生成共軛方向的生成: :結論結論: :從從不同的兩不同的兩點點出發(fā)出發(fā), ,沿沿同一方同一方向向進行兩次一維進行兩次一維搜索搜索, ,所得所得兩個極兩個極小點的連線方向小點的連線方向便是便是原方向共軛原方向共軛的另一方向。的另一方向。機械優(yōu)化設計2021/3/2343,共軛方向的生成共軛方向的生成: :二維情況二維情況: :任意點出發(fā)沿著任意點出發(fā)沿著x1x1軸軸方方向和向和ABAB方向搜索方向搜索, ,即可即可得到極小點。得到極小點。機械優(yōu)化設計2021/3/2344,基本基本POWELLPOWE

21、LL法（二維）法（二維）: :012012001001220112012111021121)1 00 12)3)TTxeexeexxdxxxdxedxedxx任選一初始點 ，再選兩個線性無關的向量，如坐標單位向量和作為初始搜索方向。從 出發(fā)，順次沿著 、 作一維搜索得到點、 ，兩點連線得到一個新的方向。再從 出發(fā)沿著作一維搜索得到點 ，作為下一輪迭代的初始點。下一輪迭代的搜索方向 、 。從 出發(fā)，順次沿著 、作一維搜索，得到點 、211212012222*dxxddGxdxxx，兩點連線得一個新的方向。同一起對 共軛。再從 出發(fā)，沿著作一維搜索得到點 。 點就是該二維問題的極小點 。機械優(yōu)化設

22、計2021/3/2345基本基本POWELLPOWELL法（法（n n維）維）: :1 1）從初）從初始點始點出發(fā)出發(fā), ,首先沿著首先沿著n n個坐標軸方向個坐標軸方向進行一維搜索進行一維搜索, ,得到一得到一個終點個終點; ;2 2）由初）由初始點和終點連線始點和終點連線形成一個形成一個新方向新方向, ,該方向排在原方向組該方向排在原方向組的最后的最后, ,去掉原方向組的的第一個方向去掉原方向組的的第一個方向, ,形成新的方向組形成新的方向組; ;3 3）從上一輪的搜索）從上一輪的搜索終點終點出發(fā)沿出發(fā)沿新的搜索方向新的搜索方向作一維搜索而得到作一維搜索而得到的極小點的極小點, ,作為作為下一輪下一輪迭代的迭代的始點始點。4 4）從）從新的始點新的始點出發(fā)出發(fā), ,沿著沿著新的方向組新的方向組做一維搜索。做一維搜索。 如此反復進行如此反復進行n n輪輪搜索后搜索后, ,可找到可找到n n個共軛方向個共軛方向, ,若目標函數(shù)是若目標函數(shù)是正正定二次定二次型函數(shù)型函數(shù), ,則經(jīng)過則經(jīng)過n n輪后就可以找到極小點。輪后就可以找到極小點。機械優(yōu)化設計2021/3/2346改進改進POWELLPOWELL法法: : 獲得新方向構成新方向組時獲得新方向構成新方向組時, ,