版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
最優(yōu)化理論與算法§9,一維搜索第九章一維搜索一維搜索的基本概念試探法函數(shù)逼近法9.一維搜索-概念1
最優(yōu)化方法的基本結(jié)構(gòu):給定初始點(diǎn)x0
確定搜索方向dk,即按照一定規(guī)則,構(gòu)造f在xk點(diǎn)處的下降方向作為搜索方向;(b)確定步長(zhǎng)因子k,使目標(biāo)函數(shù)值有某種意義下的下降;(c)令xk+1=xk+kdk
若xk+1滿足某種終止條件則停止迭代,得到近似最優(yōu)解xk+1,否則,重復(fù)上述步驟。9.1一維搜索概念9.一維搜索-概念2
9.一維搜索-概念3函數(shù)逼近法/插值法試探法一維搜索{一維搜索算法的閉性假設(shè)一維搜索是以x為起點(diǎn),沿方向?yàn)閐的進(jìn)行的,并定義為算法映射m9.一維搜索-概念4
th9.1.1設(shè)f是定義在rn的連續(xù)函數(shù),d0,則(9.1.4)定義的算法映射m在(x,d)處是閉的9.一維搜索-概念5
9.一維搜索-試探法1
9.2.1,0.618法9.一維搜索-試探法2
單峰函數(shù)具有一些很有用的性質(zhì):如果f是[a,b]上單峰函數(shù),則可通過(guò)計(jì)算此區(qū)間內(nèi)兩不同點(diǎn)的函數(shù)值,就能確定一個(gè)包含極小點(diǎn)的子區(qū)間,從而縮小了搜索區(qū)間.
單峰函數(shù)的一個(gè)等價(jià)定義:9.一維搜索-試探法3
9.一維搜索-試探法4
證明:僅證(1),反證,如若不然,存在點(diǎn)x*[a,x(1)],使9.一維搜索-試探法50.618法的基本思想:通過(guò)取試探點(diǎn)使包含極小點(diǎn)的區(qū)間(不確定區(qū)間)不斷縮小,當(dāng)區(qū)間長(zhǎng)度小到一定程度時(shí),區(qū)間上各點(diǎn)的函數(shù)值均接近極小值,此時(shí)該區(qū)間內(nèi)任一點(diǎn)都可以作為極小點(diǎn)的近似值.
9.一維搜索-試探法6由(2.3)和(2.4)得到9.一維搜索-試探法7
今考慮(2.1)的情形,此時(shí)新的搜索區(qū)間為9.一維搜索-試探法8
9.一維搜索-試探法9這樣,計(jì)算公式(2.5)(2.6)可寫(xiě)為
9.一維搜索-試探法10其幾何意義:黃金分割率對(duì)應(yīng)的點(diǎn)在單位長(zhǎng)區(qū)間[0,1]中的位置相當(dāng)于其對(duì)稱(chēng)點(diǎn)1-在區(qū)間[0,]中的位置
ak+lbk+lk+lk+lk+lk+lbk+lak+lakbkkkstep2step39.一維搜索-試探法11算法(0.618法)
9.一維搜索-試探法12
9.一維搜索-試探法132.2fibonacci法
fibonacci法是與0.618法類(lèi)似的一種分割方法。它與0.618法的主要區(qū)別之一在于:搜索區(qū)間長(zhǎng)度的縮短率不是采用黃金分割數(shù),而是采用
fibonacci數(shù):
9.一維搜索-試探法14顯然,這里fn-k/fn-k+1相當(dāng)于0.618法(1.5)-(1.6)中的,每次的縮短率滿足
9.一維搜索-試探法15
9.一維搜索-試探法16算法(fibonacci法)
上式表明當(dāng)n趨于無(wú)窮時(shí),finonacci法與0.618法的區(qū)間縮短率相同,因而也是以收斂比r線性收斂??梢宰C明fibonacci法是分割方法求一維極小化問(wèn)題的最優(yōu)策略,而0.618法是近似最優(yōu)的。9.一維搜索-試探法17計(jì)算函數(shù)值(1),(1).置k=1
9.一維搜索-試探法18step5,
置k:=k+1,轉(zhuǎn)2.
9.一維搜索-試探法192.3進(jìn)退法
9.一維搜索-試探法20算法(進(jìn)退法)
輸出[a,b]9.一維搜索-函數(shù)逼近法11.牛頓法
考慮問(wèn)題minf(x),xr1(3.1)令又令得到(x)的駐點(diǎn),記做x(k+1),則9.一維搜索-函數(shù)逼近法2在點(diǎn)x(k)附近,f(x)(x),因此可用(x)的極小點(diǎn)作為目標(biāo)函數(shù)f(x)的極小點(diǎn)的估計(jì)。如果x(k)是f(x)的極小點(diǎn),則利用(3.2)可以得到極小點(diǎn)的一個(gè)進(jìn)一步的估計(jì).于是得到一個(gè)序列{x(k)}.
9.一維搜索-函數(shù)逼近法39.一維搜索-函數(shù)逼近法49.一維搜索-函數(shù)逼近法59.一維搜索-函數(shù)逼近法6算法(牛頓法)9.一維搜索-函數(shù)逼近法7基本思想:用割線逼近目標(biāo)函數(shù)的導(dǎo)函數(shù)的曲線y=f‘(x)把割線的零點(diǎn)作為目標(biāo)函數(shù)的駐點(diǎn)的估計(jì)。3.2.割線法9.一維搜索-函數(shù)逼近法8在一定的條件下,這個(gè)序列收斂于解:9.一維搜索-函數(shù)逼近法9由(3.11)和(3.12)得到9.一維搜索-函數(shù)逼近法10上式兩端取絕對(duì)值,則9.一維搜索-函數(shù)逼近法11下面考慮收斂速率,考慮k取充分大的情形。根據(jù)(3.14)9.一維搜索-函數(shù)逼近法129.一維搜索-函數(shù)逼近法139.一維搜索-函數(shù)逼近法14基本思想:在極小點(diǎn)附近用二次三項(xiàng)式x逼近目標(biāo)函數(shù)f(x),令x與f(x)在三點(diǎn)x
(1)<x(2)<x(3)處有相同的函數(shù)值,并假設(shè)
f(x
(1))
>f(x(2)),f(x(2))<f(x(3))令x=a+bx+cx2(9.3.21)又令x(1)=a+bx(1)+c(x
(1))2=
fx
(1)
(9.3.22)x(2)=a+bx(2)+c(x
(2))2=f(x(2))
(9.3.23)x(3)=a+bx(3)+c(x
(3))2=
f((3))(9.3.24)解方程組(9.3.22-24),求二次逼近函數(shù)x的系數(shù)a,b,c為書(shū)寫(xiě)方便,記3.3拋物線法9.一維搜索-函數(shù)逼近法159.一維搜索-函數(shù)逼近法163.4
三次插值法9.一維搜索-函數(shù)逼近法17令9.一維搜索-函數(shù)逼近法18將(3.30)-(33)依次代入(3.29)得(3.34)9.一維搜索-函數(shù)逼近法19
我們目的是求(x)的極小點(diǎn),期望用它來(lái)逼近極小點(diǎn),或者基于此再確定新的迭代,為此,求出滿足極值條件的點(diǎn),即滿足‘(x)=0,“(x)>0的點(diǎn).
9.一維搜索-函數(shù)逼近法20
9.一維搜索-函數(shù)逼近法21注意到當(dāng)a=0時(shí),b>0,故當(dāng)a=0時(shí)由(3.40)得
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 山東省臨沭縣2025屆中考生物對(duì)點(diǎn)突破模擬試卷含解析
- 二零二五年度節(jié)能減排環(huán)保產(chǎn)業(yè)投資合作協(xié)議3篇
- 2025年版鋼材貿(mào)易代理及分銷(xiāo)渠道建設(shè)合同4篇
- 2025年物業(yè)管理公司員工安全責(zé)任與應(yīng)急疏散通道維護(hù)合同3篇
- 2025年度鋁材產(chǎn)品質(zhì)量檢測(cè)與認(rèn)證服務(wù)合同4篇
- 二零二五年度旅游車(chē)輛租賃與景區(qū)景點(diǎn)講解合同4篇
- 2025年度洗滌房租賃與洗滌技術(shù)培訓(xùn)合同3篇
- 二零二五年度城市綠化工程臨時(shí)工派遣服務(wù)合同模板4篇
- 2025年昌月離婚協(xié)議書(shū)全新版本2篇
- 2025年度鋁合金模板工程安裝與綠色認(rèn)證合同4篇
- GB/T 11072-1989銻化銦多晶、單晶及切割片
- GB 15831-2006鋼管腳手架扣件
- 有機(jī)化學(xué)機(jī)理題(福山)
- 醫(yī)學(xué)會(huì)自律規(guī)范
- 商務(wù)溝通第二版第4章書(shū)面溝通
- 950項(xiàng)機(jī)電安裝施工工藝標(biāo)準(zhǔn)合集(含管線套管、支吊架、風(fēng)口安裝)
- 微生物學(xué)與免疫學(xué)-11免疫分子課件
- 《動(dòng)物遺傳育種學(xué)》動(dòng)物醫(yī)學(xué)全套教學(xué)課件
- 弱電工程自檢報(bào)告
- 民法案例分析教程(第五版)完整版課件全套ppt教學(xué)教程最全電子教案
- 7.6用銳角三角函數(shù)解決問(wèn)題 (2)
評(píng)論
0/150
提交評(píng)論