一維無約束優(yōu)化_第1頁
一維無約束優(yōu)化_第2頁
一維無約束優(yōu)化_第3頁
一維無約束優(yōu)化_第4頁
一維無約束優(yōu)化_第5頁
已閱讀5頁,還剩51頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)

文檔簡介

2023/2/111.約束極值存在的條件:(K—T條件)

2.迭代算法迭代格式:使得

3.收斂準則①點距準則②目標函數(shù)下降量準則③

梯度準則④K-T條件準則知識點回顧2023/2/12第4章一維無約束優(yōu)化方法2023/2/134.二次插值法(拋物線法)

1.確定初始區(qū)間的進退法2.黃金分割法(0.618法)3.牛頓法掌握其基本思想、特點2023/2/14

工程實際中,所有設(shè)計問題幾乎都是約束問題。

約束優(yōu)化設(shè)計問題→無約束問題來求解。此外,有些約束優(yōu)化設(shè)計方法,也可以借助于無約束優(yōu)化方法的策略思想來構(gòu)造。

引言第4章一維無約束優(yōu)化方法2023/2/15引言數(shù)值迭代格式給定求一個變量一維函數(shù)的極值問題機械最優(yōu)化設(shè)計雖大都為多維問題,但在數(shù)值迭代計算中要進行一維搜索,即把多維問題轉(zhuǎn)化為一維問題來處理,一維搜索是優(yōu)化方法的基礎(chǔ)。第4章一維無約束優(yōu)化方法2023/2/16一維搜索方法分兩步:(1)確定初始搜索區(qū)間;(2)求出該區(qū)間內(nèi)的最優(yōu)步長因子。第4章一維無約束優(yōu)化方法2023/2/17一維優(yōu)化方法分為兩類:(1)直接法——按照某種規(guī)律取若干點計算其函數(shù)值,然后通過直接比較函數(shù)值的大小來確定最優(yōu)解,常用的有黃金分割法,Fibonaui(分數(shù)法)(2)間接法——利用函數(shù)的一階導(dǎo)數(shù)、二階導(dǎo)數(shù)來求解,故又稱解析法,常用的有牛頓法和二次插值法等。第4章一維無約束優(yōu)化方法2023/2/184.1確定初始區(qū)間的進退法探索區(qū)間的確定方法有外推法及進退法,常用的是進退法。2023/2/194.1確定初始區(qū)間的進退法搜索區(qū)間內(nèi)函數(shù)具有單峰性,也就是在區(qū)間[a,b]中函數(shù)是凸函數(shù),具有高—低—高的特性。在區(qū)間上具有唯一的極小值。即當時,有2023/2/1104.1確定初始區(qū)間的進退法4.1.1方法的建立給定初始點和初始步長步驟:(1)令??計算,(2)比較、函數(shù)值大小。

2023/2/1114.1確定初始區(qū)間的進退法4.1.1方法的建立前進運算a.前進運算:

方向正確,作前進運算。計算三點的函數(shù)值滿足高—低—高的特性若則搜索區(qū)間為

否則,將步長再加倍,重復(fù)上述運算,直至函數(shù)值滿足高—低—高的特性。2023/2/1124.1確定初始區(qū)間的進退法4.1.1方法的建立b.后退運算:方向不正確,作后退運算,即反向搜索。否則,將步長再加倍繼續(xù)后退,直至函數(shù)值滿足高—低—高的特性。若計算三點的函數(shù)值滿足高—低—高的特性搜索區(qū)間為2023/2/1134.1確定初始區(qū)間的進退法4.1.2程序框圖①前進運算

③②前進運算

2023/2/1144.1確定初始區(qū)間的進退法4.1.2程序框圖前進運算

和依次往右趕,始終比較和作代換,計算2023/2/1154.1確定初始區(qū)間的進退法4.1.2程序框圖后退運算

①②③2023/2/1164.1確定初始區(qū)間的進退法4.1.2程序框圖后退運算計算作代換無論前進還是后退運算,都是左邊的點為,右邊的點為和依次往左趕,2023/2/1174.2黃金分割法Fibonaui(分數(shù)法)和黃金分割法都是應(yīng)用序列消去原理的直接搜索方法。2023/2/1184.2黃金分割法4.2.1序列消去原理基本思想:在搜索區(qū)間內(nèi)選取計算點并比較其函數(shù)值,消去部分區(qū)間,以縮短搜索區(qū)間。消去在縮短了的探索區(qū)間內(nèi)保留了一個點,再取一個新點,比較此兩點的函數(shù)值大小,進一步將新區(qū)間縮短,直至區(qū)間長度小于某一給定的精度ε,則認為找到了極值點。探索區(qū)間

2023/2/1194.2黃金分割法4.2.1序列消去原理消去

探索區(qū)間在縮短的區(qū)間內(nèi)取兩個點,比較其函數(shù)值,才能進一步縮短搜索區(qū)間,為了與前兩種情況一至,便簡化迭代程序,將第(3)種情況和(1)、(2)種情況合并,只按以下兩種情況考慮:為縮短后的探索區(qū)間。為縮短后的探索區(qū)間。消去

消去

2023/2/1204.2.2黃金分割法的基本思想通過計算和比較單峰區(qū)間內(nèi)兩點的函數(shù)值,不斷舍棄單峰區(qū)間的左端或右端的一部分,使探索區(qū)間按等比例等速縮小,直至極小點所在區(qū)間縮小到某一給定的精度ε,而得到近似最優(yōu)解,又稱它為0.618法。2023/2/1214.2.2黃金分割法的基本思想黃金分割法在探索區(qū)間的插入點有以下規(guī)律:(1)首輪在區(qū)間內(nèi)插入的兩個點與區(qū)間兩端點的距離相等,即相距兩端點具有對稱性。2023/2/1224.2.2黃金分割法的基本思想黃金分割法在探索區(qū)間的插入點有以下規(guī)律:(2)在縮短后的區(qū)間內(nèi)插入一個點,新區(qū)間的三段和原區(qū)間的三段具有相同的比例分布。如果把區(qū)間長度看作是1,則有:解上式得:最長段與較長段之比相等2023/2/1234.2.3黃金分割法的迭代過程①在初始區(qū)間取兩個試點

②計算函數(shù)值③比較

迭代過程2023/2/1244.2.3黃金分割法的迭代過程③比較求新區(qū)間增加一個新點

(a)

2023/2/1254.2.3黃金分割法的迭代過程③比較(b)求(b)新區(qū)間增加一個新點

④新區(qū)間小于給定的精度ε時,終止迭代,所求的最優(yōu)點

否則轉(zhuǎn)第3步繼續(xù)迭代。2023/2/1264.2.4程序框圖開始結(jié)束TTFF給定a,b,ε2023/2/1272023/2/1282023/2/1296次迭代達最優(yōu)點2023/2/130練習(xí)

1.試用黃金分割法求函數(shù)的最優(yōu)解。初始區(qū)間[a,b]=[1,7],精度ε=0.01.最優(yōu)解:2023/2/131重點內(nèi)容1、搜索區(qū)間內(nèi)函數(shù)應(yīng)具有什么性質(zhì)?2、黃金分割法的基本思想是什么?3、黃金分割法的區(qū)間縮短實質(zhì)上采用的是什么原理?4、黃金分割法首輪搜索區(qū)間插入點具有什么特點?2023/2/132知識點回顧1.用進退法確定初始區(qū)間時,搜索區(qū)間內(nèi)函數(shù)具有什么性質(zhì)?2.用進退法確定初始區(qū)間,直至函數(shù)滿足什么特性時停止搜索?

3.黃金分割法的基本思想是什么?4.黃金分割法中的0.618的含義是什么?本次課的內(nèi)容一維牛頓法(切線法)二次插值法(拋物線法)1、基本思想

2、迭代公式和迭代步驟3、程序框圖4、特點2023/2/1344.3一維牛頓法(1)牛頓法的基本思想

用二次函數(shù)逐點近似原目標函數(shù),以二次函數(shù)的極小點來近似原目標函數(shù)的極小點,用切線代替弧線逐漸逼近函數(shù)的根值。2023/2/135(1)牛頓法的基本思想

當目標函數(shù)有一階連續(xù)導(dǎo)數(shù),且二階導(dǎo)數(shù)大于零時,函數(shù)的極小值點應(yīng)滿足極值存在的必要條件,所以求函數(shù)的極小值點也就是求解方程的根。在曲線上作一系列切線,使之與軸的交點逐漸逼近方程的根。4.3一維牛頓法2023/2/136(2)牛頓法的迭代公式與軸的交點為推廣到k步得迭代公式過點的切線方程為

4.3一維牛頓法2023/2/137(2)牛頓法的迭代公式迭代公式也可由Taylor公式展開得到:

在點附近用二次函數(shù)來逼近原目標函數(shù),故在點用Taylor公式展開,保留到二次項。令4.3一維牛頓法2023/2/1384.3一維牛頓法(3)牛頓法的迭代步驟給定搜索區(qū)間,初始點,迭代精度ε,令1)計算

2)求

3)終止條件判斷

若滿足條件,則得近似解停止計算,否則轉(zhuǎn)步驟4)4)令轉(zhuǎn)步驟1)。自己列出程序框圖2023/2/139(4)牛頓法的程序框圖

給定x(0),a,b,εk=0TF結(jié)束開始4.3一維牛頓法2023/2/1402023/2/1412次迭代達最優(yōu)點2023/2/1424.3牛頓法1)

優(yōu)點是收斂速度快,2)缺點是需要計算函數(shù)的一階和二階導(dǎo)數(shù),增加了每次迭代的工作量。如果用數(shù)值微分計算函數(shù)的二階導(dǎo)數(shù),其舍入誤差將嚴重影響牛頓法的收斂速度,的值越小問題越嚴重。3)牛頓法要求初始點離極值點不太遠,否則有可能使極小化序列發(fā)散或收斂到非極小點。(5)牛頓法的特點2023/2/1434.4二次插值法(拋物線法)4.4.1二次插值法基本思想利用目標函數(shù)在三個點的信息:

構(gòu)造一個與目標函數(shù)值相接近的插值多項式,用該多項式的最優(yōu)解作為原目標函數(shù)的近似最優(yōu)解,隨著搜索區(qū)間的逐次縮短,多項式的最優(yōu)點與原函數(shù)最優(yōu)點的距離逐漸減小,直至滿足精度要求。2023/2/1444.4.2二次插值法的公式推導(dǎo)設(shè)函數(shù)極值點所在區(qū)間內(nèi)有三個點其函數(shù)值為滿足,即滿足高—低—高特性。構(gòu)造二次插值多項式多項式的最優(yōu)解(x2,f2)作為原目標函數(shù)的近似最優(yōu)解2023/2/1454.4.2二次插值法的公式推導(dǎo)構(gòu)造二次插值多項式:(4-3)——待定系數(shù)對(4-3)式求導(dǎo),令導(dǎo)數(shù)等于零,得插值多項式的極小點:極小點:2023/2/1464.4.2二次插值法的公式推導(dǎo)構(gòu)造二次插值多項式:(4-3)將三點的值代入(4-3)即可求待定系數(shù)(4-4)2023/2/1474.4.2二次插值法的公式推導(dǎo)由(4-4)可以求得(4-6)

(4-7)將代入得極小點(4-8)2023/2/1484.4.3二次插值法的迭代過程

①確定初始搜索區(qū)間給定初始插值點迭代精度ε。②計算

③計算插值多項式的極小點2023/2/1494.4.3二次插值法的迭代過程④終止判斷a.若便可得到極小點

b.若

必須縮小搜索區(qū)間根據(jù)區(qū)間消去原理,先比較和的大小,然后確定從四點中舍去得到新三點,然后再轉(zhuǎn)步驟③。2023/2/150

4.4.4二次插值法的程序框圖A=0停(失?。㏕FFTFT必須縮短搜索區(qū)間2023/2/151

4.4.4二次插值法的程序框圖求2023/2/152

4.4.4二次插值法的程序框圖求xm2023/2/153

4.4.4二次插值法的程序框圖A=0停(失?。㏕FFTFT采用序列消去原理縮短探索區(qū)間2023/2/1544.4.5二次插值法的特點

拋物線法充分利用了函數(shù)的性態(tài)。對于二次函數(shù)用二次插值法求解,在理論上一次迭代可達到最優(yōu)點。對于非二次函數(shù),在極值點附近函數(shù)呈現(xiàn)二次性態(tài),因而收斂速度也較快。4.4.6各種一維優(yōu)化方法的比較

牛頓法收斂快,但

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論