運籌學與最優(yōu)化方法 第4章最優(yōu)化搜索算法的結(jié)構(gòu)

《運籌學與最優(yōu)化方法 第4章最優(yōu)化搜索算法的結(jié)構(gòu)》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、第四章最優(yōu)化搜索算法的結(jié)構(gòu)與一維搜索4.1常用的搜索算法結(jié)構(gòu)一、收斂性概念：考慮（fs）設迭代算法產(chǎn)生點列{x(k)}?S.1.理想的收斂性：設x*∈S是g.opt.當x*∈{x(k)}或x(k)≠x*，?k，滿足時，稱算法收斂到最優(yōu)解x*。4.1常用的搜索算法結(jié)構(gòu)由于非線性規(guī)劃問題的復雜性，實用中建立下列收斂性概念：2.實用收斂性：定義解集S*={x

2、x具有某種性質(zhì)}例：S*={x

3、x---g.opt}S*={x

4、x---l.opt}S*={x

5、?f(x)=0}S*={x

6、f(x)≤β}(β為給定的實數(shù)，稱為閾值)4.1常用的搜索算法結(jié)構(gòu)一、收斂性概念：考慮（fs）2.實用收斂

7、性（續(xù)）▲收斂性：設解集S*≠，{x(k)}為算法產(chǎn)生的點列。下列情況之一成立時，稱算法收斂：1°?x(k)∈S*;2°x(k)S*，?k，{X(k)}任意極限點∈S*。▲全局收斂：對任意初始點x(1),算法均收斂。局部收斂：當x(1)充分接近解x*時，算法才收斂。4.1常用的搜索算法結(jié)構(gòu)二、收斂速度設算法產(chǎn)生點列{x(k)},收斂到解x*,且x(k)≠x*，?k，1.線性收斂：當k充分大時成立。2.超線性收斂：3.二階收斂：??﹥0，是使當k充分大時有4.1常用的搜索算法結(jié)構(gòu)二、收斂速度（續(xù)）定理：設算法點列{x(k)}超線性收斂于x*,且x(k)≠x*，?k，那么證明只需注意

8、

9、

10、

11、x(k+1)–x*

12、

13、-

14、

15、x(k)–x*

16、

17、

18、≤

19、

20、x(k+1)–x(k)

21、

22、≤

23、

24、x(k+1)–x*

25、

26、+

27、

28、x(k)–x*

29、

30、，除以

31、

32、x(k)–x*

33、

34、并令k→∞，利用超線性收斂定義可得結(jié)果。4.1常用的搜索算法結(jié)構(gòu)三、二次終結(jié)性▲一個算法用于解正定二次函數(shù)的無約束極小時，有限步迭代可達最優(yōu)解，則稱該算法具有二次終結(jié)性?！谓K結(jié)性=共軛方向+精確一維搜索?！曹椃较颉ざx：設An×n對稱正定，d(1),d(2)∈Rn,d(1)≠0，d(2)≠0，滿足d(1)TAd(2)=0,稱d(1),d(2)關(guān)于矩陣A共軛?！す曹椣蛄拷M：d(1),d(2),…,d(m)∈Rn均

35、非零，滿足d(i)TAd(j)=0,(i≠j).4.1常用的搜索算法結(jié)構(gòu)三、二次終結(jié)性（續(xù)）·當A=I(單位矩陣)時，d(1)TAd(2)=d(1)Td(2)=0，即正交關(guān)系?！ぎ攄(1),d(2),…,d(m)關(guān)于正定矩陣A兩兩共軛時，d(1),d(2),…,d(m)線性無關(guān)。proof:設d=?1d(1)+?2d(2)+…+?md(m)=0，?j=1,2,…,m，d(j)TAd=?jd(j)TAd(j)=0∵d(j)TAd(j)>0，故?j=0，即線性無關(guān)。超線性收斂和二次終結(jié)性常用來討論算法的優(yōu)點。正定4.1常用的搜索算法結(jié)構(gòu)四、下降算法模型考慮（fs）常用一種線性搜索的方

36、式來求解：迭代中從一點出發(fā)沿下降可行方向找一個新的、性質(zhì)有改善的點?！飨陆捣较颍涸O∈S，d∈Rn,d≠0,若存在，使，稱d為在點的下降方向。minf(x)s.t.x∈S4.1常用的搜索算法結(jié)構(gòu)四、下降算法模型（續(xù)）△可行方向：設∈S，d∈Rn,d≠0,若存在，使，稱d為點的可行方向。同時滿足上述兩個性質(zhì)的方向稱下降可行方向。4.1常用的搜索算法結(jié)構(gòu)模型算法線性搜索求，新點使x(k+1)∈S初始x(1)∈S,k=1對x(k)點選擇下降可行方向d(k)是否滿足停機條件？停k=k+1yesno4.2一維搜索一元函數(shù)求極小及線性搜索均為一維搜索。常用于求：minf(x(k)+?d(k))

37、=φ(λ)s.t.λ∈SS有3種情況（-∞，+∞）或（0，+∞）或[a,b]一、縮小區(qū)間的精確一維搜索：考慮問題(P)minφ(λ)s.t.λ∈[α,β]φ(λ):R→R1、不確定區(qū)間及單峰函數(shù)△不確定區(qū)間：[α,β]含φ(λ)的最小點，但不知其位置4.2一維搜索一、縮小區(qū)間的精確一維搜索（續(xù)）定義：設φ：[α,β]→R，?λ*∈[α,β]是φ在[α,β]上的最小點，若對任意λ1,λ2,α≤λ1<λ2≤β滿足：1o若λ2≤λ*，則φ(λ1)>φ(λ2);2o若λ1≥λ*，則φ(λ1)<φ(λ2).則稱φ(λ)在[α,β]上強單峰。若只有當φ(λ1)≠φ(λ*)，φ(λ2)≠φ(λ

38、*)時，上述1o,2o式才成立，則稱φ(λ)在[α,β]上單峰。4.2一維搜索一、縮小區(qū)間的精確一維搜索（續(xù)）若對任意λ1,λ2,α≤λ1<λ2≤β滿足：1o若λ2≤λ*，則φ(λ1)>φ(λ2);2o若λ1≥λ*，則φ(λ1)<φ(λ2).則稱φ(λ)在[α,β]上強單峰。若只有當φ(λ1)≠φ(λ*)，φ(λ2)≠φ(λ*)時，上述1o,2o式才成立，則稱φ(λ)在[α,β]上單峰。αλ*λ1λ2β強單峰αλ*β單峰4.2一維搜索一、縮小區(qū)間的精確一維搜索（續(xù)）定理：設Ф：R