非線性規(guī)劃一維搜索0506.ppt

第六章 非線性規(guī)劃 一維搜索,概述,當(dāng)用迭代法求函數(shù)的極小點(diǎn)時(shí)，常常要用到一維搜索，即沿某一已知方向求目標(biāo)函數(shù)的極小點(diǎn)。 一維搜索的方法很多，常用的有試探法、插值法和微積分中的求根法，下面我們首先給出一維搜索算法的基本思想，然后對(duì)一些經(jīng)典的算法進(jìn)行探討。,一維搜索的基本思想,一維搜索的基本方法,一維搜索的實(shí)施步驟,確定搜索區(qū)間,一維搜索的實(shí)施步驟,確定搜索區(qū)間,一維搜索的實(shí)施步驟,確定搜索區(qū)間,一維搜索的實(shí)施步驟,確定搜索區(qū)間的算法圖示,一維搜索的實(shí)施步驟,逐步縮小搜索區(qū)間,試探法黃金分割法,算法概述 0.618法又稱黃金分割法，它是一種等比例縮短區(qū)間的直接搜索方法 其基本思想是通過比較單峰區(qū)間內(nèi)兩點(diǎn)的函數(shù)值，不斷舍棄單峰區(qū)間的左端或右端的一部分，使區(qū)間按固定區(qū)間縮小率逐步縮小，直到極小點(diǎn)所在區(qū)間縮小到給定的誤差范圍內(nèi)而得到近似最優(yōu)解 由于前面的內(nèi)容已經(jīng)涉及了如何逐步縮小搜索區(qū)間，那么本方法的關(guān)鍵就是如何保證區(qū)間縮小率不變。,試探法黃金分割法,算法分析,試探法黃金分割法,算法分析,試探法黃金分割法,算法流程,試探法黃金分割法,算法流程圖,插值法牛頓法,黃金分割法的局限性 對(duì)于0.618法，對(duì)于所計(jì)算的各個(gè)探索點(diǎn)上的函數(shù)值，僅僅用來比較其大小，而在各試探點(diǎn)的具體函數(shù)值等這些非常有用的信息卻沒有被利用，因此算法收斂速度都較慢，為了充分利用有用的信息，我們有插值法或稱為多項(xiàng)式逼近法。 插值法的基本思想,插值法牛頓法,插值法的常用工具 多項(xiàng)式是函數(shù)逼近最常用的一種工具，在搜索區(qū)間內(nèi)利用若干探索點(diǎn)處的函數(shù)值來構(gòu)造低次多項(xiàng)式，用它作為函數(shù)的近似表達(dá)式，并用這個(gè)多項(xiàng)式的極小點(diǎn)作為原函數(shù)極小點(diǎn)的近似值。在這里介紹兩種用二次多項(xiàng)式函數(shù)逼近原函數(shù)的方法。一種方法是牛頓法，它是利用一點(diǎn)的函數(shù)值、一階導(dǎo)數(shù)值和二階導(dǎo)數(shù)值來構(gòu)造二次函數(shù)的。另一種方法是拋物線法，它是利用三個(gè)點(diǎn)的函數(shù)值來構(gòu)造二次函數(shù)的。在這里，我們只重點(diǎn)介紹牛頓法。然后在下一小節(jié)簡要介紹一下拋物線法的迭代公式。,插值法牛頓法,牛頓法算法思想,插值法牛頓法,牛頓法算法分析,插值法牛頓法,牛頓法算法流程,插值法牛頓法,牛頓法算法示意圖,插值法牛頓法,牛頓法的優(yōu)缺點(diǎn),拋物線法,拋物線法 當(dāng)函數(shù)具有比較好的解析性質(zhì)時(shí)，牛頓法與拋物線法通常比0.618法的效果更好,一維搜索的MATLAB求解,求解函數(shù),一維搜索的MATLAB求解,函數(shù)概要 fminbnd函數(shù)可以計(jì)算一元函數(shù)最小值優(yōu)化問題，它用于求解一維設(shè)計(jì)變量在固定區(qū)間內(nèi)的目標(biāo)函數(shù)的最小值，亦即最優(yōu)化問題的約束條件只有設(shè)計(jì)變量的上下界。其求解的算法是我們在前面小結(jié)中重點(diǎn)講述的基于黃金分割法和拋物線插值法。 在使用fminbnd進(jìn)行優(yōu)化的過程中，除非x1和x2十分接近，否則算法將不會(huì)在區(qū)間的端點(diǎn)評(píng)價(jià)目標(biāo)函數(shù)，因而設(shè)計(jì)變量的限制條件需要指定為開區(qū)間(x1,x2)，如果目標(biāo)函數(shù)的最小值恰好在x1處或者x2處取得，fminbnd將返回該區(qū)間的一個(gè)內(nèi)點(diǎn)，且其與端點(diǎn)x1或者x2的距離不超過2TolX，其中TolX為最優(yōu)解x處的誤差限。,一維搜索的MATLAB求解,輸入?yún)?shù)和輸出參數(shù),一維搜索的MATLAB求解,一維搜索的MATLAB求解,控制參數(shù)設(shè)置,一維搜索的MATLAB求解,命令詳解 x = fminbnd(fun,x1,x2) 返回標(biāo)量函數(shù)fun在滿足x1xx2條件下取最小值時(shí)設(shè)計(jì)變量x的值。 x = fminbnd(fun,x1,x2,options) 在求解問題的同時(shí)用options指定的優(yōu)化參數(shù)進(jìn)行目標(biāo)函數(shù)的最小化 x,fval = fminbnd(.) 返回最優(yōu)解x處的目標(biāo)函數(shù)值fval。 x,fval,exitflag = fminbnd(.) 在優(yōu)化計(jì)算結(jié)束之時(shí)返回exitflag值，描述函數(shù)計(jì)算的退出條件 x,fval,exitflag,output = fminbnd(.) 在優(yōu)化計(jì)算結(jié)束之時(shí)返回返回結(jié)構(gòu)變量output 命令分析 fminbnd只能解決設(shè)計(jì)變量為實(shí)變量的最優(yōu)化問題，所求解最優(yōu)化問題的目標(biāo)函數(shù)必須是連續(xù)的，且fminbnd給出的可能只是目標(biāo)函數(shù)的局部最優(yōu)解。 當(dāng)最優(yōu)化問題的解位于區(qū)間邊界附近時(shí)，fminbnd算法可能收斂的很慢，此時(shí)使用fmincon函數(shù)求解問題時(shí)的計(jì)算速度更快，計(jì)算精度更高，fmincon的用法我們將在之后講解。,一維搜索的MATLAB求解,例1 求解一維搜索問題 x,fval,exitflag,output = fminbnd(sin,0,2*pi) %最優(yōu)解 x = 4.7124 %最優(yōu)解x處的目標(biāo)函數(shù)值 fval = -1.0000 exitflag = 1 output = iterations: 8 funcCount: 9 algorithm: golden section search, parabolic interpolation message: 1x112 charTo find the minimum of the function,一維搜索的MATLAB求解,例2 求解一維搜索問題 首先用M-函數(shù)定義目標(biāo)函數(shù) function f=myfun(x) f=(x-5)2+7; 然后調(diào)用fminbnd函數(shù)求解