重慶科創(chuàng)學院-現代設計方法之24 無約束設計的最優(yōu)化方法

1、主講人：魏良慶主講人：魏良慶1 1、PowellPowell法的應用計算法的應用計算2 2、梯度法的應用計算、梯度法的應用計算3 3、共軛梯度法的應用計算、共軛梯度法的應用計算4 4、變尺度法的應用計算、變尺度法的應用計算2.4 2.4 多維無約束優(yōu)化方法多維無約束優(yōu)化方法 l共軛與共軛方向的概念共軛與共軛方向的概念l共軛方向的形成共軛方向的形成l常用的無約束優(yōu)化設計方法的基本步常用的無約束優(yōu)化設計方法的基本步驟與幾何解釋驟與幾何解釋2.4 2.4 多維無約束優(yōu)化方法多維無約束優(yōu)化方法 l第第2 2章第一節(jié)所列舉的機械優(yōu)化設計問題，章第一節(jié)所列舉的機械優(yōu)化設計問題，都是在一定的限制條件下追求某

2、一指標為都是在一定的限制條件下追求某一指標為最小，它們都屬于多維約束優(yōu)化問題。工最小，它們都屬于多維約束優(yōu)化問題。工程問題大都如此。程問題大都如此。 為什么要研究多維無約束優(yōu)化問題為什么要研究多維無約束優(yōu)化問題? 2.4 2.4 多維無約束優(yōu)化方法多維無約束優(yōu)化方法 (1) (1)有些實際問題，其數學模型本身就是一個多有些實際問題，其數學模型本身就是一個多維無約束優(yōu)化問題。維無約束優(yōu)化問題。 (2)(2)通過熟悉它的解法可以為研究多維約束優(yōu)化通過熟悉它的解法可以為研究多維約束優(yōu)化問題打下良好的基礎。問題打下良好的基礎。 (3)(3)多維約束優(yōu)化問題的求解可以通過一系列多多維約束優(yōu)化問題的求解可

3、以通過一系列多維無約束優(yōu)化方法來達到。維無約束優(yōu)化方法來達到。所以多維無約束優(yōu)化所以多維無約束優(yōu)化問題的解法是優(yōu)化設計方法的基本組成部分，也問題的解法是優(yōu)化設計方法的基本組成部分，也是優(yōu)化方法的基礎。是優(yōu)化方法的基礎。2.4 2.4 多維無約束優(yōu)化方法多維無約束優(yōu)化方法 多維無約束優(yōu)化問題是：多維無約束優(yōu)化問題是：求求n n維設計變量維設計變量使目標函數：使目標函數： 12Tnx xxx( )minfxmin( )nfRxx各種多維無約束優(yōu)化解法的區(qū)別：各種多維無約束優(yōu)化解法的區(qū)別：搜索方向的不同搜索方向的不同2.4 2.4 多維無約束優(yōu)化方法多維無約束優(yōu)化方法 分類：分類：（1 1）直接解法

4、）直接解法-不使用導數信息，如不使用導數信息，如坐標輪換坐標輪換 法、法、PowellPowell法、隨機搜索法、單純形法法、隨機搜索法、單純形法等等（2 2）間接解法）間接解法( (解析法解析法) )-要使用導數，要使用導數，二階有二階有 梯度法、共軛梯度法、二階以上用牛頓法梯度法、共軛梯度法、二階以上用牛頓法1(0,1,2,)kkkkSkxx搜索方向的構成問題是多維無約束優(yōu)化方法的關鍵搜索方向的構成問題是多維無約束優(yōu)化方法的關鍵2.4 2.4 多維無約束優(yōu)化方法多維無約束優(yōu)化方法 從選定的某初始點從選定的某初始點x x(k(k) )出發(fā)，沿著以一出發(fā)，沿著以一定規(guī)律產生的搜索方向定規(guī)律產生

5、的搜索方向S S(k(k) )，取適當的步長，取適當的步長a a(k(k) ), ,逐次搜尋函數值下降的新迭代點逐次搜尋函數值下降的新迭代點x x(k+1)(k+1), ,使之逐步通近最優(yōu)點使之逐步通近最優(yōu)點x x* *。 2.4 2.4 多維無約束優(yōu)化方法多維無約束優(yōu)化方法 可以把可以把初始點初始點x x(k(k) )、搜索方向搜索方向S S(k(k) )、迭代步長迭代步長a a(k(k) )稱為優(yōu)化方法算法的三要素。其中以稱為優(yōu)化方法算法的三要素。其中以搜索方向搜索方向S S(k(k) )更為突出和重要更為突出和重要，它從根本上決定一個算法的，它從根本上決定一個算法的成敗、收斂速率的快慢等

6、。成敗、收斂速率的快慢等。 一個算法的搜索方向成為該優(yōu)化方法的基本一個算法的搜索方向成為該優(yōu)化方法的基本標志，標志，分析、確定搜索方向分析、確定搜索方向S S(k(k) )是研究優(yōu)化方法的是研究優(yōu)化方法的最根本的任務之一最根本的任務之一。2.4 2.4 多維無約束優(yōu)化方法多維無約束優(yōu)化方法 函數的函數的負梯度方向負梯度方向是函數值下降最快的方向是函數值下降最快的方向搜索方向搜索方向S S取該點的負梯度方向取該點的負梯度方向 ( (最速下降最速下降方向方向) )，使函數值在該點附近的范圍內下降最快。，使函數值在該點附近的范圍內下降最快。( )fx1(0,1,2,)kkkkSkxx1() (0,1

7、,2, )kkkka fk xxx2.4 2.4 多維無約束優(yōu)化方法多維無約束優(yōu)化方法 為了使目標函數值沿搜索方向為了使目標函數值沿搜索方向 能夠能夠獲得最大的下降值，其步長因子獲得最大的下降值，其步長因子 應取一應取一維搜索的最佳步長。即有維搜索的最佳步長。即有()kfxk1()() min ()min ( )kkkkkkaaffa ffa f xxxxx2.4 2.4 多維無約束優(yōu)化方法多維無約束優(yōu)化方法 l根據一元函數極值的必要條件和多元復根據一元函數極值的必要條件和多元復合函數求導公式，得合函數求導公式，得 ( )()()0Tkkkkfff xxx1()()0kTkffxx1()0kT

8、kSS2.4 2.4 多維無約束優(yōu)化方法多維無約束優(yōu)化方法 在最速下降在最速下降( (梯度梯度) )法中，相鄰兩個迭代點上法中，相鄰兩個迭代點上的函數梯度的函數梯度相互垂直相互垂直。而搜索方向就是負梯度方。而搜索方向就是負梯度方向，因此向，因此相鄰兩個搜索方向互相垂直相鄰兩個搜索方向互相垂直。這就是說。這就是說在迭代點向函數極小點靠近的過程，走的是曲折在迭代點向函數極小點靠近的過程，走的是曲折的路線。形成的路線。形成“之之”字形的鋸齒現象，而且字形的鋸齒現象，而且越接越接近極小點鋸齒越細。近極小點鋸齒越細。 2.4 2.4 多維無約束優(yōu)化方法多維無約束優(yōu)化方法 開始給定結束0,x()kkf d

9、x1:min()kkkkkkkfxxdxd1kkxx*1kxx否是1kk0k 2.4 2.4 多維無約束優(yōu)化方法多維無約束優(yōu)化方法 例例2.4-1 2.4-1 求目標函數求目標函數 的極小點。的極小點。初始點初始點解：初始點處函數值及梯度分別為解：初始點處函數值及梯度分別為02,2Tx00102()10424()50100 xfxfxxx2212( )25fxxx2.4 2.4 多維無約束優(yōu)化方法多維無約束優(yōu)化方法 沿負梯度方向進行一維搜索，有沿負梯度方向進行一維搜索，有0100002 4()2 100fxxx0為一維搜索最佳步長，應滿足極值必要條件為一維搜索最佳步長，應滿足極值必要條件 12

10、2( )min (2 4 )25(2 100 )min ( )f x2.4 2.4 多維無約束優(yōu)化方法多維無約束優(yōu)化方法 00( )8(2 4) 5000(2 100)0 算出一維搜索最佳步長算出一維搜索最佳步長 06260.020 030 7231252第一次迭代設計點位置和函數值第一次迭代設計點位置和函數值 01202 41.9198772 1000.307178 5 10 x1( ) 3.686164fx繼續(xù)作下去，經繼續(xù)作下去，經1010次迭代后，得到最優(yōu)解次迭代后，得到最優(yōu)解 0 0Tx()0fx2.4 2.4 多維無約束優(yōu)化方法多維無約束優(yōu)化方法 這一問題的目標函數這一問題的目標函

11、數f f( (x x) )的等值線為一簇橢圓。的等值線為一簇橢圓。將上例中目標函數將上例中目標函數 引入變換引入變換 y1=x1,y2=5x2則函數則函數f(x)f(x)變?yōu)椋鹤優(yōu)椋?212( )25fxxx221212(,)y yyy其等值線由橢圓變成一簇同心圓。其等值線由橢圓變成一簇同心圓。2.4 2.4 多維無約束優(yōu)化方法多維無約束優(yōu)化方法 仍從仍從 即即 出發(fā)進行最速下降法出發(fā)進行最速下降法尋優(yōu)。此時：尋優(yōu)。此時：02,2Tx02,10Ty00102()10424()220yyyyy沿負梯度方向進行一維搜索沿負梯度方向進行一維搜索：1000000()2 42410 201020 yyy

12、2.4 2.4 多維無約束優(yōu)化方法多維無約束優(yōu)化方法 為一維搜索最佳步長，可由極值條件：為一維搜索最佳步長，可由極值條件：10022()min ()min( )( )(24 )(1020 ) yyy0()0由由0260.552從而算得一步計算后設計點的位置及其目標函數：從而算得一步計算后設計點的位置及其目標函數：2.4 2.4 多維無約束優(yōu)化方法多維無約束優(yōu)化方法 010124010200()0 yy經變換后，只需一次迭代，就可找到最優(yōu)解。經變換后，只需一次迭代，就可找到最優(yōu)解。這是因為經過尺度變換：這是因為經過尺度變換：11225yxyx等值線由橢圓變成圓。等值線由橢圓變成圓。1 12.4

13、2.4 多維無約束優(yōu)化方法多維無約束優(yōu)化方法 （1）理論明確，程序簡單，理論明確，程序簡單，對初始點要求不嚴格。對初始點要求不嚴格。（2）對一般函數而言，收對一般函數而言，收斂速度并不快，因為最速斂速度并不快，因為最速下降方向僅是指某點的一下降方向僅是指某點的一個個局部局部性質。性質。2.4 2.4 多維無約束優(yōu)化方法多維無約束優(yōu)化方法 （4）梯度法的收斂速度與目標函數的性質密切相梯度法的收斂速度與目標函數的性質密切相關。對于關。對于等值線等值線( (面面) )為同心圓（球）的目標函數，為同心圓（球）的目標函數，一次搜索即可達到極小點。一次搜索即可達到極小點。（3）相鄰兩次搜索方向的正交性決定

14、了迭代過程相鄰兩次搜索方向的正交性決定了迭代過程的的路線呈鋸齒狀路線呈鋸齒狀，在，在遠離極小點時逼近速度較快，遠離極小點時逼近速度較快，而在接近極小點時逼近速度較慢。而在接近極小點時逼近速度較慢。2.4 2.4 多維無約束優(yōu)化方法多維無約束優(yōu)化方法 設設G G為為n nn n階階實對稱正定矩陣實對稱正定矩陣，如果有兩個，如果有兩個n n維維向量向量S S0 0和和S S1 1滿足滿足 ，則稱向量，則稱向量S S0 0與與S S1 1 關于矩陣關于矩陣G G共軛共軛。01()0TSS G2.4 2.4 多維無約束優(yōu)化方法多維無約束優(yōu)化方法 01()0TSS G當當G為單位矩陣時為單位矩陣時，01

15、()0TSS 假設目標函數假設目標函數f(x)在極值點附近的二次近似函數為在極值點附近的二次近似函數為1( )2TfTxx Gxb xc對二維情況對二維情況任選取初始點任選取初始點x0沿某個下降方向沿某個下降方向S0作一維搜索，得作一維搜索，得x11000Sxx2.4 2.4 多維無約束優(yōu)化方法多維無約束優(yōu)化方法 因為因為 是沿是沿S0方向搜索的最佳步長，即在方向搜索的最佳步長，即在點點x1處函數處函數f（x）沿方向沿方向S0的方向導數為零的方向導數為零?？紤]到點?？紤]到點x1處方向導數與梯度之間的關系，故有處方向導數與梯度之間的關系，故有01100()0TffSS xx如果按最速下降法，選擇

16、負梯度方向如果按最速下降法，選擇負梯度方向 為搜為搜索方向，則將發(fā)生索方向，則將發(fā)生鋸齒鋸齒現象現象 。1( )f x2.4 2.4 多維無約束優(yōu)化方法多維無約束優(yōu)化方法 2.4 2.4 多維無約束優(yōu)化方法多維無約束優(yōu)化方法 0S0 x0 x1x*1 11S11()fx0取下一次的迭代搜索方向取下一次的迭代搜索方向S1直指極小點直指極小點x* S12.4 2.4 多維無約束優(yōu)化方法多維無約束優(yōu)化方法 l如果能夠選定這樣的搜索方向，那么對于二元如果能夠選定這樣的搜索方向，那么對于二元二次函數二次函數只需順次進行只需順次進行S0、S1兩次直線搜索就兩次直線搜索就可以求到極小點可以求到極小點x*，即

17、有，即有111Sxx那么這樣的那么這樣的S1方向應該滿足什么條件呢方向應該滿足什么條件呢 ? ?01()0TSS G2.4 2.4 多維無約束優(yōu)化方法多維無約束優(yōu)化方法 對于前述的二次函數對于前述的二次函數: :有有11( )fxGxb1( )2TfTxx Gxb xc當當 時時 。1xx10 x* *是是f( (x) )極小點，極小點，應滿足極值必要條件，故有應滿足極值必要條件，故有( )0f xG x b1111111( )()( )fSfxSb xG xbxG0將等式兩邊同時左乘將等式兩邊同時左乘 得：得：0()TS01()0TSS G2.4 2.4 多維無約束優(yōu)化方法多維無約束優(yōu)化方法

18、 01()0TSS G就是使就是使S1直指極小點直指極小點x*，S S1 1所必須滿足的條件。所必須滿足的條件。兩個向量兩個向量S S0 0和和S S1 1稱為稱為G的共軛向量，或稱的共軛向量，或稱SO和和S S1 1對對G是共軛方向。是共軛方向。 021()( )0TSfSx2.4 2.4 多維無約束優(yōu)化方法多維無約束優(yōu)化方法 性質性質1 1 若非零向量系若非零向量系S0, ,S1, ,S2,Sm-1是是對對G共軛共軛，則這則這m個向量是線性無關個向量是線性無關的的。性質性質2 2 在在n維空間中維空間中互相共軛的非零向量的個數互相共軛的非零向量的個數不超過不超過n。 性質性質3 3 從任意

19、初始點出發(fā)，順次沿從任意初始點出發(fā)，順次沿n個個G的共軛方的共軛方向向S0, ,S1, , S2,進行一維搜索，進行一維搜索，最多經過最多經過n次迭代次迭代就可以找到的就可以找到的二次二次函數函數f( (x) )極小點。極小點。 2.4 2.4 多維無約束優(yōu)化方法多維無約束優(yōu)化方法 開始給定結束00,xd1:min()kkkkkkkfxxdxd1kkxx*1kxx否是1kk0k 提供新的共軛方向關鍵：新的共關鍵：新的共軛方向軛方向確定確定2.4 2.4 多維無約束優(yōu)化方法多維無約束優(yōu)化方法 l共軛梯度法是共軛方向法中的一種共軛梯度法是共軛方向法中的一種，該方法中，該方法中每一個共軛向量都是每一

20、個共軛向量都是依賴于迭代點處的負梯度依賴于迭代點處的負梯度而構造出來而構造出來。l從從xk出發(fā)，沿負梯度方向作一維搜索出發(fā)，沿負梯度方向作一維搜索: :2.4 2.4 多維無約束優(yōu)化方法多維無約束優(yōu)化方法 1(0,1,2, )kkkkSkxx()kkSf x設與設與Sk共共軛的下一個方向軛的下一個方向Sk+1由由Sk和點和點xk+1的負的負梯度的線形組合構成，即：梯度的線形組合構成，即：11()kkkkSfS x21()( )0kTkSfSx共軛條件：共軛條件：2.4 2.4 多維無約束優(yōu)化方法多維無約束優(yōu)化方法 則：則：21()( )() 0kTkkkfffSxxx解得：解得：212()()

21、()()()()kTkkkkTkkffffffxxxxxx2.4 2.4 多維無約束優(yōu)化方法多維無約束優(yōu)化方法 ()kkfxGxb則則11()kkfxGxb上兩式相減，并代入上兩式相減，并代入1kkkkSxx1()()kkkkSff Gxx令令1( )2TfTxx Gxb xc為函數的泰勒二次展開式為函數的泰勒二次展開式2.4 2.4 多維無約束優(yōu)化方法多維無約束優(yōu)化方法 11()kkkkSfSx1()()kkkkSffGxx將式將式與式與式兩邊相乘，并應用兩邊相乘，并應用共軛條件共軛條件得：得：11()()()()0kkkkkffffxxxx21112()()()()()()kkTkkkTk

22、kffffffxxxxxx2.4 2.4 多維無約束優(yōu)化方法多維無約束優(yōu)化方法 因此因此11()kkkkSfS x212()()kkkffxx1(0,1,2,)kkkkSkxx2.4 2.4 多維無約束優(yōu)化方法多維無約束優(yōu)化方法 2.4 2.4 多維無約束優(yōu)化方法多維無約束優(yōu)化方法 迭代精度迭代精度 。 2212112( )242fxxxxxx ，已知初始點已知初始點1,11,1T T解：解：1 1）第一次沿負梯度方向搜尋）第一次沿負梯度方向搜尋計算初始點處的梯度計算初始點處的梯度0120212244( )422xxfxxxx0.0012.4 2.4 多維無約束優(yōu)化方法多維無約束優(yōu)化方法 01

23、20212244()422xxfxxxx01000001 4141 212S xx為一維搜索最佳步長，應滿足為一維搜索最佳步長，應滿足1002()min()min(40203)ffSxx2.4 2.4 多維無約束優(yōu)化方法多維無約束優(yōu)化方法 得:00.25120.5x2 2）第二次迭代：）第二次迭代：21200()50.2520()ffxx11()2fx11002()1.5SfS x2.4 2.4 多維無約束優(yōu)化方法多維無約束優(yōu)化方法 得:211222 20.51.50.5 1.5Sxx代入目標函數代入目標函數22( ) (2 2 )2(0.5 1.5 )2(2 2 )(0.5 1.5 ) 4(

24、2 2 )( )f x 2.4 2.4 多維無約束優(yōu)化方法多維無約束優(yōu)化方法 ( )0 得得122240,( )8,( )20ff xxx因因2()0fx收斂。收斂。由由從而有：從而有：2.4 2.4 多維無約束優(yōu)化方法多維無約束優(yōu)化方法 共軛梯度法特點共軛梯度法特點1 1）每步迭代只需存儲若干向量（適用于大）每步迭代只需存儲若干向量（適用于大規(guī)模問題）；規(guī)模問題）；2 2）有二次終結性（對于正定二次函數，至）有二次終結性（對于正定二次函數，至多多n n次迭代可達次迭代可達opt.opt.） 2.4 2.4 多維無約束優(yōu)化方法多維無約束優(yōu)化方法 1 1、梯度法：、梯度法：搜索方向為目標函數負梯

25、度方向，搜索方向為目標函數負梯度方向，計算速度開始搜索下降快，愈接近極值點下降愈計算速度開始搜索下降快，愈接近極值點下降愈慢。對初始點的選擇要求不高，適合與其它方法慢。對初始點的選擇要求不高，適合與其它方法結合使用。結合使用。2 2、共軛梯度法：、共軛梯度法：第一步搜索沿負梯度方向，然第一步搜索沿負梯度方向，然后沿負梯度的共軛方向搜索。后沿負梯度的共軛方向搜索。計算效率優(yōu)于梯度計算效率優(yōu)于梯度法。法。對初始點沒有特殊的要求，不需要計算二階對初始點沒有特殊的要求，不需要計算二階偏導數矩陣及其逆矩陣，計算量與梯度法相當。偏導數矩陣及其逆矩陣，計算量與梯度法相當。適用于各種大規(guī)模的問題適用于各種大規(guī)

26、模的問題。2.4 2.4 多維無約束優(yōu)化方法多維無約束優(yōu)化方法 鮑威爾（鮑威爾（PowellPowell）法是）法是直接利用函數值來構造共直接利用函數值來構造共軛方向的一種方法軛方向的一種方法 1( )2TfTxx Gxb xc對函數：對函數：基本思想：基本思想：在不用導數的前提下，在迭代中逐在不用導數的前提下，在迭代中逐次構造次構造G的共軛方向的共軛方向2.4 2.4 多維無約束優(yōu)化方法多維無約束優(yōu)化方法 jjk kkkSd dgg gk+1k+1xxk+1設設xk, xk+1為從不同點出發(fā)，沿同一方向為從不同點出發(fā)，沿同一方向Sj進行一維進行一維搜索而得到的兩個極小點。搜索而得到的兩個極小

27、點。 jS2.4 2.4 多維無約束優(yōu)化方法多維無約束優(yōu)化方法 根據梯度和等值面相垂直的性質，根據梯度和等值面相垂直的性質，Sj和和xk, ,xk+1兩兩點處的梯度點處的梯度gk，gk+1之間存在關系之間存在關系: :1()0,()0jTkjTkSSgg另一方面，對于上述二次函數，其另一方面，對于上述二次函數，其xk，xk+1兩點處兩點處的梯度可表示為的梯度可表示為: :11,kkkkgGxbgGxb2.4 2.4 多維無約束優(yōu)化方法多維無約束優(yōu)化方法 因而有因而有11() ()()()0j Tkkj TkkSSggG xx1kkkSxx取取這說明只要沿這說明只要沿Sj方向分別對函作兩次一維搜

28、索，方向分別對函作兩次一維搜索，得到兩個極小點得到兩個極小點xk和和xk+1，那么這兩點的，那么這兩點的連線所連線所給出的方向給出的方向Sk就是與就是與Sj一起一起對對G共軛共軛的方向。的方向。2.4 2.4 多維無約束優(yōu)化方法多維無約束優(yōu)化方法 1 1）任選一初始點）任選一初始點x0，再，再選兩個線性無關的向量，選兩個線性無關的向量，如 坐 標 軸 單 位 向 量如 坐 標 軸 單 位 向 量e1=1,0T和和e2=0,1T作為作為初始搜索方向。初始搜索方向。2 2）從）從x0出發(fā)，順次沿出發(fā)，順次沿e1，e2作一維搜索，得作一維搜索，得 點，兩點連線點，兩點連線得一新方向得一新方向S100

29、12,xxx1x2x0o oe1e2d1d2x*102x10 x11x12x01x11002S xx2.4 2.4 多維無約束優(yōu)化方法多維無約束優(yōu)化方法 用用S1代替代替e1形成兩個線形成兩個線性無關向量性無關向量S1, e2 ，作，作為下一輪迭代的搜索方為下一輪迭代的搜索方向。再從向。再從 出發(fā)，沿出發(fā)，沿S S1 1作一維搜索得點作一維搜索得點 ，作為下一輪迭代的初始作為下一輪迭代的初始點。點。 02x10 xx1x2x0o oe1e2d1d2x*102x10 x11x12x01x2.4 2.4 多維無約束優(yōu)化方法多維無約束優(yōu)化方法 x1x2x0o oe1e2d1d2x*102x10 x1

30、1x12x01x3 3）從出發(fā)）從出發(fā) ，順次，順次沿沿e2,S1作一維搜索，作一維搜索，得到點得到點 ，兩點，兩點連線得一新方向連線得一新方向: :1112,x x21120S xx10 x2.4 2.4 多維無約束優(yōu)化方法多維無約束優(yōu)化方法 沿沿S S2 2作一維搜索得點作一維搜索得點x2 即是二維問題的極即是二維問題的極小點小點x* 方法的基本迭代格式方法的基本迭代格式包括包括共共軛方向產生和軛方向產生和方向替換兩主要步驟。方向替換兩主要步驟。x1x2x0o oe1e2d1d2x*102x10 x11x12x01x2.4 2.4 多維無約束優(yōu)化方法多維無約束優(yōu)化方法 把二維情況的基本算法

31、擴展到把二維情況的基本算法擴展到n維，則鮑維，則鮑威爾基本算法的要點是：威爾基本算法的要點是： 在每一輪迭代中總有一個始點（第一輪的在每一輪迭代中總有一個始點（第一輪的始點是任選的初始點）和始點是任選的初始點）和n個線性獨立的搜索個線性獨立的搜索方向。從始點出發(fā)順次沿方向。從始點出發(fā)順次沿n個方向作一維搜索個方向作一維搜索得一終點，由得一終點，由始點和終點決定了一個新的搜索始點和終點決定了一個新的搜索方向。方向。 2.4 2.4 多維無約束優(yōu)化方法多維無約束優(yōu)化方法 l用這個方向替換原來用這個方向替換原來n n個方向中的一個，于是個方向中的一個，于是形成新的搜索方向組。替換的原則是形成新的搜索

32、方向組。替換的原則是去掉原方去掉原方向組的第一個方向而將新方向排在原方向的最向組的第一個方向而將新方向排在原方向的最后。后。此外規(guī)定，從這一輪的搜索終點出發(fā)沿新此外規(guī)定，從這一輪的搜索終點出發(fā)沿新的搜索方向作一維搜索而得到的極小點，作為的搜索方向作一維搜索而得到的極小點，作為下一輪迭代的始點。這樣就形成算法的循環(huán)。下一輪迭代的始點。這樣就形成算法的循環(huán)。 上述基本算法僅具有理論意義上述基本算法僅具有理論意義 。2.4 2.4 多維無約束優(yōu)化方法多維無約束優(yōu)化方法 因為在迭代中的因為在迭代中的n個搜索方向有時會變成線個搜索方向有時會變成線性相關而不能形成共軛方向的情況性相關而不能形成共軛方向的情

33、況。從而。從而導致可能求不到極小點，所以上述基本算導致可能求不到極小點，所以上述基本算法有待改進。法有待改進。 2.4 2.4 多維無約束優(yōu)化方法多維無約束優(yōu)化方法 在鮑威爾基本算法中，每一輪迭代都用連結始點在鮑威爾基本算法中，每一輪迭代都用連結始點和終點所產生出的搜索方向去替換原向量組中的和終點所產生出的搜索方向去替換原向量組中的第一個向量，而不管它的第一個向量，而不管它的“好壞好壞”，這是產生向，這是產生向量組線性相關的原因所在。量組線性相關的原因所在。 2.4 2.4 多維無約束優(yōu)化方法多維無約束優(yōu)化方法 在改進的算法中在改進的算法中首先判斷原向量組是否需要替首先判斷原向量組是否需要替換

34、。換。如果需要替換，還要如果需要替換，還要進一步判斷原向量組進一步判斷原向量組中哪個向量最壞，中哪個向量最壞，然后然后再用新產生的向量替換再用新產生的向量替換這個最壞的向量，這個最壞的向量，以保證逐次生成共軛方向。以保證逐次生成共軛方向。2.4 2.4 多維無約束優(yōu)化方法多維無約束優(yōu)化方法 l為此，要解決兩個關鍵問題為此，要解決兩個關鍵問題： （1）Sk1是否較好？是否應該進入新的方向組？是否較好？是否應該進入新的方向組？即方向組是否進行更新？即方向組是否進行更新？ （2 2）如果應該更新方向組，）如果應該更新方向組， Sk1不一定替換方不一定替換方向向 ，而是有選擇地替換某一方向而是有選擇地

35、替換某一方向 。1kSkmS2.4 2.4 多維無約束優(yōu)化方法多維無約束優(yōu)化方法 令在令在k次循環(huán)中次循環(huán)中00231()()()kknknFfFfFfxxx01,kkknnx x x100()2kkkkkknnnnxxxxxx（）分別稱為一輪迭代的分別稱為一輪迭代的始點、終點和反射點始點、終點和反射點。2.4 2.4 多維無約束優(yōu)化方法多維無約束優(yōu)化方法 則在循環(huán)中函數下降最多的第則在循環(huán)中函數下降最多的第m次迭代是次迭代是() (0,1,2, )kiiffinx1(1,2, )iiiffin 記記：11maxmimmi nff 相應的方向為相應的方向為 。kmS002,nFfFf因此因此2

36、.4 2.4 多維無約束優(yōu)化方法多維無約束優(yōu)化方法 為了構成共為了構成共軛性好的方向組，須遵循下列準則：軛性好的方向組，須遵循下列準則：在在k次循環(huán)中，若次循環(huán)中，若滿足條件滿足條件：30FF202302(2)()mFFF FF2030.5()mFF則選用新方向則選用新方向Sk，并在第并在第k+1迭代中用迭代中用Sk替換對應于替換對應于 的方向的方向 。否則，仍然用原方向組進行第。否則，仍然用原方向組進行第k+1迭代。迭代。mkmS2.4 2.4 多維無約束優(yōu)化方法多維無約束優(yōu)化方法 這樣重復迭代的結果，后面加進去的向量都彼此對這樣重復迭代的結果，后面加進去的向量都彼此對G共軛，共軛，經經n輪

37、迭代即可得到一個由輪迭代即可得到一個由n個共軛方向所組成的方向組。對個共軛方向所組成的方向組。對于于n次函次，最多次函次，最多n次就可找到極小點，而對一般函數，往往次就可找到極小點，而對一般函數，往往要超過要超過n n次才能找到極小點（這里次才能找到極小點（這里“n”表示設計空間的維表示設計空間的維數）。數）。 2.4 2.4 多維無約束優(yōu)化方法多維無約束優(yōu)化方法 例例2.4-5 2.4-5 用改進的鮑威爾法求目標函數用改進的鮑威爾法求目標函數的最優(yōu)解。已知初始點的最優(yōu)解。已知初始點1,1T，迭代精度，迭代精度221211 2( )242fxxxxxx0.001解：（解：（1 1）第）第1 1

38、輪迭代計算輪迭代計算0011 x0000()3Fff x2.4 2.4 多維無約束優(yōu)化方法多維無約束優(yōu)化方法 沿沿e1方向進行一維搜索方向進行一維搜索0201min()43fxe12得得00101 11132101 xxe011( )7ffx2.4 2.4 多維無約束優(yōu)化方法多維無約束優(yōu)化方法 以以 為起點，沿第二坐標軸方向為起點，沿第二坐標軸方向e2進行一維搜索進行一維搜索01x0212min ()227fxe20.5得得0021213030.5111.5 xxe022()7.5ff x2.4 2.4 多維無約束優(yōu)化方法多維無約束優(yōu)化方法 確定此輪中的最大下降量及其相應方向確定此輪中的最大下

39、降量及其相應方向0010101()()4ffff xx0021212()()0.5ffff xx12max,4m 2.4 2.4 多維無約束優(yōu)化方法多維無約束優(yōu)化方法 反射點及其函數值反射點及其函數值000320315221.512 xxx033( )7Ffx檢驗檢驗PowellPowell條件條件202302(2)()1.25mFFF FF2030.5()32mFF2.4 2.4 多維無約束優(yōu)化方法多維無約束優(yōu)化方法 l由于滿足由于滿足PowellPowell條件，則淘汰函數值下降量最條件，則淘汰函數值下降量最大的方向大的方向e1，下一輪的基本方向組為下一輪的基本方向組為e2， 。03S構成

40、新的方向構成新的方向 0003203121.510.5S xx2.4 2.4 多維無約束優(yōu)化方法多維無約束優(yōu)化方法 沿沿 方向一維搜索得極小點和極小值方向一維搜索得極小點和極小值03S13.81.7x1()7.9f x此點為下輪迭代初始點。此點為下輪迭代初始點。 按點距準則檢驗終止條件按點距準則檢驗終止條件 11220(3.8 1)(1.7 1)2.886xx需進行第二輪迭代計算。需進行第二輪迭代計算。2.4 2.4 多維無約束優(yōu)化方法多維無約束優(yōu)化方法 （2 2）第）第2 2輪迭代計算輪迭代計算此輪基本方向組為此輪基本方向組為e2， ，分別相當于分別相當于 ， ，起始點為起始點為 = 03S

41、11S12S10 x1x沿沿e2方向進行一維搜索得方向進行一維搜索得 113.81.9x11()7.98f x2.4 2.4 多維無約束優(yōu)化方法多維無約束優(yōu)化方法 以以 為起點沿為起點沿 方向一維搜索得方向一維搜索得11x03S123.961.9x122()7.996ffx確定此輪中函數值最大下降量及其相應方向確定此輪中函數值最大下降量及其相應方向10.08 20.016 12max,0.08m 2.4 2.4 多維無約束優(yōu)化方法多維無約束優(yōu)化方法 l反射點及其函數值反射點及其函數值1113203.963.84.12221.941.72.18 xxx133()7.964Ff x檢驗檢驗Powe

42、llPowell條件，淘汰函數值下降量最大的方向條件，淘汰函數值下降量最大的方向e2，下一輪的基本方向組應為下一輪的基本方向組應為 ， 。 03S13S2.4 2.4 多維無約束優(yōu)化方法多維無約束優(yōu)化方法 構成新的方向構成新的方向1113203.963.80.161.941.70.24Sxx沿沿 方向進行一維搜索得方向進行一維搜索得13S242 x2()8f x2.4 2.4 多維無約束優(yōu)化方法多維無約束優(yōu)化方法 檢驗終止條件檢驗終止條件 22220(4 3.8)(2 1.7)0.36xx（3 3）第）第3 3輪迭代計算輪迭代計算此輪基本方向組為此輪基本方向組為 ， ，起始點為起始點為 ，先先

43、后沿后沿 ， 方向方向，進行一維搜索，得進行一維搜索，得03S13S20 x2x03S13S2142 x2242 x2.4 2.4 多維無約束優(yōu)化方法多維無約束優(yōu)化方法 檢驗終止條件檢驗終止條件 故最優(yōu)解故最優(yōu)解 22200 xx*42 x*()8f x2.4 2.4 多維無約束優(yōu)化方法多維無約束優(yōu)化方法 實際上，前兩輪迭代的實際上，前兩輪迭代的 ， 為共軛方向，由于本例目為共軛方向，由于本例目標函數是二次函數，按共軛方向的二次收斂性，故前兩標函數是二次函數，按共軛方向的二次收斂性，故前兩輪的結果就是問題的最優(yōu)解，但每一輪迭代都需要進行輪的結果就是問題的最優(yōu)解，但每一輪迭代都需要進行n n+1

44、+1次迭代。次迭代。13S23S2.4 2.4 多維無約束優(yōu)化方法多維無約束優(yōu)化方法 補充知識：補充知識：牛頓法牛頓法( )x( )x( )f x1kx( )f x2( )( )()() ()1()()()2kkTkkTkkffffxxxxxxxxxxx設設 為為 的極小點的極小點 1kx( )x1() 0kx21()()()0kkkkffxxxx2.4 2.4 多維無約束優(yōu)化方法多維無約束優(yōu)化方法 121()() (0,1,2, )kkkkffk xxxx這就是多元函數求極值的這就是多元函數求極值的牛頓法迭代公式牛頓法迭代公式。 對于二次函數，海賽矩陣是一個常矩陣，其中對于二次函數，海賽矩陣

45、是一個常矩陣，其中各元素均為常數。因此，無論從任何點出發(fā)，只各元素均為常數。因此，無論從任何點出發(fā)，只需一步就可找到極小點。需一步就可找到極小點。2.4 2.4 多維無約束優(yōu)化方法多維無約束優(yōu)化方法 例例2 24 4 求目標函數求目標函數 的極小點的極小點。初始點初始點2212( )25fxxx02,2Tx102010102402( )( )121000050ff xxxx經過一次迭代即求得極小點經過一次迭代即求得極小點 ，函數極小值函數極小值 。00 x()0fx2.4 2.4 多維無約束優(yōu)化方法多維無約束優(yōu)化方法 開始給定結束0,x21()()kkkff dxx1:min()kkkkkkk

46、fxxdxd1kkxx*1kxx否是1kk0k 2.4 2.4 多維無約束優(yōu)化方法多維無約束優(yōu)化方法 l 牛頓法的主要缺點牛頓法的主要缺點是每次迭代都要計是每次迭代都要計算函數的二階導數矩陣，并對該矩陣求逆。算函數的二階導數矩陣，并對該矩陣求逆。這樣工作量很大。特別是矩陣求逆，當維這樣工作量很大。特別是矩陣求逆，當維數高時工作量更大數高時工作量更大 。 2.4 2.4 多維無約束優(yōu)化方法多維無約束優(yōu)化方法 變尺度法是在牛頓法的思想上進行了重大改進變尺度法是在牛頓法的思想上進行了重大改進的一類方法。的一類方法。 1.1.基本思想基本思想 變量的尺度變換是放大或縮小各個坐標。通過變量的尺度變換是放

47、大或縮小各個坐標。通過尺度變換可以把函數的偏心程度降到最低限度。尺度變換可以把函數的偏心程度降到最低限度。 2.4 2.4 多維無約束優(yōu)化方法多維無約束優(yōu)化方法 把把 的尺度放大的尺度放大5 5倍，則目標函數等值線由一簇倍，則目標函數等值線由一簇橢圓變成一簇同心圓。橢圓變成一簇同心圓。例如在用最速下降法求例如在用最速下降法求 的極小的極小2212( )25fxxx值時值時, ,需要進行需要進行1010次迭代才能達到極小點次迭代才能達到極小點0,0Tx如作變換如作變換 y1=x1, y2=5x2x2221212(,)y yyy消除了函數的偏心，用最速下降法只需一次迭代即消除了函數的偏心，用最速下

48、降法只需一次迭代即可求得極小點?？汕蟮脴O小點。2.4 2.4 多維無約束優(yōu)化方法多維無約束優(yōu)化方法 Ak 是需要構造是需要構造nn的一個對稱方陣，稱為的一個對稱方陣，稱為變尺度矩陣變尺度矩陣如如Ak=I, 則得到梯度法則得到梯度法 ；21()kkf Ax 則得到阻尼牛頓法則得到阻尼牛頓法 ；如如迭代方向：迭代方向：1()(0,1,2, )kkkSfkAx迭代公式：迭代公式：1()(0,1,2, )kkkkkfkxxAx變尺度法的關鍵在于尺度矩陣變尺度法的關鍵在于尺度矩陣A Ak k的產生。的產生。2.4 2.4 多維無約束優(yōu)化方法多維無約束優(yōu)化方法 從初始矩陣從初始矩陣A0=I( (單位矩陣單

49、位矩陣) )開始，通過對公式開始，通過對公式 1kkkAAA中修正矩陣中修正矩陣 的不斷修正，在迭代中逐步逼近于的不斷修正，在迭代中逐步逼近于 kA1()kGx因此，一旦達到最優(yōu)點附近，就可望達到牛頓法的因此，一旦達到最優(yōu)點附近，就可望達到牛頓法的收斂速度收斂速度。2.4 2.4 多維無約束優(yōu)化方法多維無約束優(yōu)化方法 1 1）DFPDFP法（法（DavidonDavidon-Fletcher-Powell)-Fletcher-Powell)TkkkkkTkkkTkkTkkxxAggAAxggAg111()( )kkkkkkkkff gggxxxxx式中式中2.4 2.4 多維無約束優(yōu)化方法多維

50、無約束優(yōu)化方法 DFPDFP算法由于舍入誤差和一維搜索不精確，有可能算法由于舍入誤差和一維搜索不精確，有可能導致構造矩陣的正定性遭到破壞，以至算法不穩(wěn)定。導致構造矩陣的正定性遭到破壞，以至算法不穩(wěn)定。BFGSBFGS算法對于維數較高問題具有更好的穩(wěn)定性。算法對于維數較高問題具有更好的穩(wěn)定性。 1 kk Tk Tkkkkk Tk Tkk TkkkkTkk TxxgAgAxxxgxgAgxxgA2.4 2.4 多維無約束優(yōu)化方法多維無約束優(yōu)化方法 開始給定結束0,x000()f gxAI1:min()kkkkkkkfxxdxd1kkxx*1kxx否是1kkkn11111()kkkkkkkkf gx

51、gggxxx11kkk AAA01kxx0k kkk dA g是否2.4 2.4 多維無約束優(yōu)化方法多維無約束優(yōu)化方法 l解：解： 1）取初始點取初始點 ，為了按為了按DFPDFP法構法構造第一次搜尋方向造第一次搜尋方向S0，需計算初始點處的梯度，需計算初始點處的梯度221212112( ,)242f x xxxxxx01 1Tx01200212244( )422xxfxx xgx2.4 2.4 多維無約束優(yōu)化方法多維無約束優(yōu)化方法 取初始變尺度矩陣為單位矩陣取初始變尺度矩陣為單位矩陣A0=I，則第一，則第一次搜尋方向為次搜尋方向為 00010440122S A g2.4 2.4 多維無約束優(yōu)化方法多維無約束優(yōu)化方法 沿沿S0方向進行一維搜索，得