1、最優化方法最優化方法 Optimization第十一講第十一講第八章第八章 算法和算法復雜性算法和算法復雜性第九章第九章 一一 維維 搜搜 索索 主要內容主要內容 算法概念算法概念 算法收斂準則算法收斂準則 全局收斂全局收斂, , 局部收斂局部收斂, , 收斂速度收斂速度 算法二次終止性算法二次終止性 算法復雜性算法復雜性 內點法內點法: : 路徑跟蹤法路徑跟蹤法算法概念算法概念一下降迭代算法一下降迭代算法迭代：迭代：( )(1)( )( )1*lim*0*kkkkkxAxkkxxxxx從一點出發，按照某種規則 ，求出后繼點，用代替 ，重復以上過程，得到一個解的序列，若該序列有極限點，即則稱它

2、收斂于。下降下降：在每次迭代中，后繼點處的函數值要有所減少。在每次迭代中，后繼點處的函數值要有所減少。下降迭代算法的步驟下降迭代算法的步驟：。，置選定某一初始點0. 1)0(kx。確定搜索方向)(. 2kd。迭代點，以產生下一個求步長出發，沿方向從)1()()(. 3kkkkxdx。，返回止迭代；否則，令小點，若是，則停是否為極小點或近似極檢查21:. 4)1(kkxk 選取搜索方向選取搜索方向是最關鍵的一步，各種算法的區別，是最關鍵的一步，各種算法的區別， 主要在于確定搜索方向的方法不同。主要在于確定搜索方向的方法不同。 k確定步長 的主要方法令它等于某一常數。.12.k可接受點算法，即只要

3、能使目標函數值下降，可任意選取步長。( )( )( )( )( )( )3.( )()min().kkkkkkkxxdf xf xdf xd基于沿搜索方向使目標函數值下降最多，即沿射線求目標函數的極小由于這項工作是求以 為變量的一元函數的極小點，故常稱這一過程為（最優）一維搜索，這樣確定的步長為最佳步長。定理：定理：(1)( )( )(1)( )(1)( )()min()()0kkkkkkkkkkkTkf xxf xdf xdxxdf xd設目標函數具有一階偏導數，由下列規則產生：則有。證明：證明：0)()()(0)()()()()()()(kTkkkkTkkkkkkkkkddxfddxfdx

4、f而的駐點。為是最優步長，則若記二算法映射二算法映射定義：定義：,2:2nXXXEA X給定集合記其冪集（即所有子集構成的集合）為，稱集值映射為一個算法映射(algorithm mapping).例：例：(0)(1)()min|,0 ,|( )|()nnkkLPcx Axb xXxxLPA xyyLPyxxXxA x考慮標準形式的線性規劃令為的基本可行解 ，若定義算法映射為的基本可行解,并且 和 的基矩陣是相鄰的 ，那么對于任意一個基本可行解，迭代格式就生成一個相鄰的基本可行解序列。例：例：2min. .1.xstx考慮下列非線性規劃：11,(1)1;2( )1(1),11.2xxA xxx定

5、義算法映射：3 53 9 335 7 253, 2,3,3,2 42 8 323 6 24A利用算法 可以產生不同的點列：xy1y=(x+1)/2A(x(1,k)A(x(2,k)解集合解集合把滿足某些條件的點集定義為把滿足某些條件的點集定義為解集合解集合當迭代點屬當迭代點屬于該集合時，停止迭代于該集合時，停止迭代常用的解集合常用的解集合：|( )0|,( ),xf xx xKKTx xS f xbb 為點其中 是某個可接受的目標函數值。算法收斂問題算法收斂問題定義：定義：(1)( ):2XkA XYXxYAxAY設 為解集合，為算法映射。給定一個集合，若對于任意的初始點，算法映射 所產生的序列

6、中任一收斂子序列的極限都屬于 ，則稱算法映射 在 上收斂。().().Yglobal convergenceYlocal convergence若集合 是任意選取的（該集合不必限定在解集合的很小領域內），則相應的收斂性稱為若集合 只能取接近 的點集，則相應的收斂性稱為全局收斂性局部收斂性實用收斂準則實用收斂準則(1)( )(1)( )( )1.kkkkkxxxxx或者( )(1)( )(1)( )()()2.()().()kkkkkf xf xf xf xf x或者( )3.()().kf x無約束最優化中收斂速率收斂速率定義：定義：( )(1)_( )( )*lim*kkpkkkp 設序列收

7、斂于，定義滿足的非負數 的上確界為序列的收斂級。pp若序列的收斂級為 ，則序列是 級稱收斂的。11p序列是以收斂若且比 線性0，則稱收斂的。1,10pp若或者且，則序列是超線稱性收斂的。收斂級收斂級p越大，序列收斂得越快；當收斂級越大，序列收斂得越快；當收斂級p相同時，收斂比相同時，收斂比越小，越小，序列收斂得越快。序列收斂得越快。 例：例： 01kaa 11lim0lim1,lim(1)()0kkkkkkrkkkaaaaraaaa 又且當時 ，以收斂比 線性收斂于 。例：例：20 | 1kaa1111222222222lim0limlim1,lim(2)kkkkkkkkkrkkkaaaara

8、aaa 又且當時 ，是2級收斂的。例：例：1kk111(1)1lim0111limlim011111limlim(1)111kkkkkkkkkpkpkkkkkkkkkkkkkpkkkk 又是超線性收斂的。用二次終止性作為判斷算法優劣的原因用二次終止性作為判斷算法優劣的原因：(1)(1)正定二次函數具有某些較好的性質，因此一個好的算法應正定二次函數具有某些較好的性質，因此一個好的算法應能夠在有限步內達到其極小點。能夠在有限步內達到其極小點。(2)(2)對于一般的目標函數，若在其極小點處對于一般的目標函數，若在其極小點處HesseHesse矩陣正定，矩陣正定，因此可以猜想，對正定二次函數好的算法，

9、對于一般目標函因此可以猜想，對正定二次函數好的算法，對于一般目標函數也應具有較好的性質。數也應具有較好的性質。 2( )*1*|* |2TTfxfxfxxxxxfxxxoxx 若某個算法對任意的若某個算法對任意的正定二次函數正定二次函數，從任意的初始點出發，都，從任意的初始點出發，都能經能經有限步有限步迭代達到其極小點，則稱該算法具有迭代達到其極小點，則稱該算法具有二次終止性二次終止性。算法的二次終止性算法的二次終止性算法復雜性算法復雜性 描述算法的存儲要求和運行時間要求，分為描述算法的存儲要求和運行時間要求，分為算法的空間復雜性和算法的時間復雜性。算法的空間復雜性和算法的時間復雜性。利用算法

10、需要的利用算法需要的初等運算次數初等運算次數表示算法的表示算法的時間復雜性時間復雜性。算法復雜性算法復雜性求解實例求解實例I I的算法的的算法的基本計算總次數基本計算總次數C C( (I I) )是實例輸入長度是實例輸入長度d d( (I I) )的一個函數，該函數被另一個函數的一個函數，該函數被另一個函數g g( (x x) )控制，即存控制，即存在一個函數在一個函數g g( (x x) )和一個常數和一個常數a a，使得，使得 ( )CIag d I多項式時間算法與指數時間算法多項式時間算法與指數時間算法 輸入規模輸入規模(input size)：表示一個：表示一個實例實例所所需要的字符串

11、長度。需要的字符串長度。 一般的，使用一般的，使用 位二進制就可以位二進制就可以表示任意整數表示任意整數r。 線性規劃的輸入規模為：線性規劃的輸入規模為：21log r 22212211121 log1 log1 log |1 log |1 log |2log (|), ,njjmnmijjijiLmncabmnmnPmnPA b c為中所有非零數的乘積多項式時間算法與指數時間算法多項式時間算法與指數時間算法 ( ( )C Iag d I假設問題和解決該問題的一個算法已經給定，若給定該問題假設問題和解決該問題的一個算法已經給定，若給定該問題的一個實例的一個實例I I，存在，存在多項式函數多項式

12、函數g g( (x x) )，使得，使得成立，則稱該算法對成立，則稱該算法對實例實例I I是是多項式時間算法多項式時間算法. .若存在若存在g g( (x x) )為多項式函數且對該問題任意一個實例為多項式函數且對該問題任意一個實例I I ，都有，都有上式成立，則稱該算法為解決該問題的多項式時間算法。上式成立，則稱該算法為解決該問題的多項式時間算法。當當g g( (x x) )為指數函數時，稱相應的算法為為指數函數時，稱相應的算法為指數時間算法指數時間算法。（1 1）隨著問題輸入規模的增加，算法的計算量（即）隨著問題輸入規模的增加，算法的計算量（即算法復雜性）呈多項式增長算法復雜性）呈多項式增

13、長. .（2 2）一個多項式時間算法利用另一個多項式時間算）一個多項式時間算法利用另一個多項式時間算法作為其法作為其“子程序子程序”，構造一個新的復合型算法，構造一個新的復合型算法，則新算法仍是多項式時間算法。則新算法仍是多項式時間算法。多項式時間算法的優點多項式時間算法的優點122min10. .21010,2,0,1,2,nn iiiijiijj iixstxxinxin上例用單純形算法需要上例用單純形算法需要2n-1次迭代次迭代單純形算法的復雜性單純形算法的復雜性 精確線搜索精確線搜索 試探法試探法: 黃金分割法、黃金分割法、Fibonacci法、二分法法、二分法 函數逼近法函數逼近法:

14、 Newton法、割線法、拋物線法、法、割線法、拋物線法、 三次插值法三次插值法 非精確線搜索非精確線搜索 Armijo步長規則、步長規則、Goldstein步長規則、步長規則、 Wolfe步長規則步長規則一維搜索一維搜索( )( )0()min()kkLSf xd( )( )( )( )min(Exact Line Search).kkkkkkkf xdf xd如果求得的 ，使得則稱該一維搜索為稱為最精確一維索優步長搜( )( )( )(Inexact Line Search).kkkkkf xdf x如果存在 ，使得則稱該一維搜非精確一維搜索索為精確、非精確線搜索精確、非精確線搜索 函數逼

15、近法：牛頓法函數逼近法：牛頓法基本思想：基本思想：在極小點附近用二階在極小點附近用二階Taylor多項式近似。多項式近似。)(minxf2)()()()()()(21)()()(kkkkkxxxfxxxfxfx 令( )( )( )( )()()()0kkkxfxfxxx又令)()()()()()()1()1(kkkkkxfxfxxxx ，則的駐點，記作得定理：定理：(1)()( )()0()0kfxxfxfxxxxx設存在， 滿足，初點充分接近 ，則牛頓法產生的序列至少以二級收斂速度收連續三階導斂于數。證明：證明：f ( x)A( x)xf ( x)牛頓法可定義為算法映射|)(xxx定義函數

16、x設解集合為)(,)()1()(kkkxAxxx設(1)(1)( )( )( )( )( )( )( )( )( )( )( )( )( )2( )( )()|()1()()()()|()|1( )()()() |()|11() |( )|()|2kkkkkkkkkkkkkkkkkxxxfxxxxfxfxxfxfxfxfxfxxxfxfxxxfxxfx其中 在和 之間。21)(21)(| )(| ,| )(|0, 0)()()(kxfkxfxxxkkxxxfxfxfkk 處，有的閉區間上的每一點和使得在包含時，存在接近當連續，和(1)( )2( )21()2kkkkxxxxxk是二級收斂。12

17、)1(12)1( xxkkxx，使得充分接近取初點| |)()1()1()(xxxxxxxxxXxkkk且有。上連續在為緊集，是下降函數，且xxXxAXk)()(算法步驟算法步驟:(0)1.,0,0 xk給定初始點允許誤差置。. 3;,| )(|. 2)()(否則轉則停止計算，得點若kkxxf。，返回置計算點21,)(. 3)()()()1()1( kkxfxfxxxkkkkk缺點：缺點：初初始始點選擇十分重要。如果初始點靠近極小點，則點選擇十分重要。如果初始點靠近極小點，則可能很快收斂；如果初始點遠離極小點，迭代產生的點可能很快收斂；如果初始點遠離極小點，迭代產生的點列可能不收斂于極小點。列

18、可能不收斂于極小點。 例：例：.01. 0),21 (5minxxex2)0(x取初始點解：解：00002. 06096. 13012. 5012. 0612. 12349. 5349. 0677. 11388. 7388. 220)()()( kkkxfxfxk為近似解。6096. 1x0( )minarctg*0.xf xt dtx最優解例：例：用用Newton法求解：法求解：21( ),( )1fxarctg xfxx1110.7854220.57080.51781.325830.11690.11631.013740.001061kkkkxfxfx1121.1071523.53571.295213.50313.95kkkkxfxfx非精確搜索非精確搜索()()()()()00 1,()()()kmkkkmkkmkTkmfxdfxfxd設 ,( , ),(0,1). 取 步 長其 中是 滿 足 下 式 的 最 小 非 負 整 數 :Armijo步長規則步長規則根據目標函數的根據目標函數的Taylor展開式，展開式， 滿足這種規則的步長一定滿足這種規則的步長一定存在。存在。非精確搜索非精確搜索()()()()()()()()()()2()()(),()()(1)().0kkkkkTkkkkkTkfxdfxfxdfxdfx