數(shù)值解單變量最優(yōu)化

4.5.2無約束最優(yōu)化問題的數(shù)值解法

4.5.2.1單變量最優(yōu)化問題的數(shù)值解法〔一維搜索〕一、消去法的根本概念1消去法的根本思想利用單峰函數(shù)在可行域內(nèi)只有一個極值點(diǎn)的特點(diǎn)，設(shè)法逐步縮小搜索最優(yōu)點(diǎn)的區(qū)間，直至找到最優(yōu)點(diǎn)，并到達(dá)允許的精度為止。消去法分為：1整理ppt同時消去法：同時計算一批點(diǎn)的函數(shù)值，然后比較各函數(shù)值的大小，再消去一局部區(qū)間，直至到達(dá)精度要求。序貫消去法：從第二個點(diǎn)起，每計算一個點(diǎn)的函數(shù)值，就與前一個點(diǎn)的函數(shù)值進(jìn)行比較，消去局部區(qū)間后再安排下一個計算點(diǎn)，如此序貫進(jìn)行，直至到達(dá)精度要求。2整理ppt2序貫法縮小搜索區(qū)間設(shè)：一元函數(shù)y(x)在區(qū)間[a0,b0]內(nèi)為單峰函數(shù)，假設(shè)首先在[a0,b0]內(nèi)任取兩點(diǎn)x1，x2(x1<x2)，并計算函數(shù)值y(x1)，y(x2)，這時可能的三種情況為：3整理ppt〔1〕

y(x1)<y(x2)那么x*在[a0,x2]之內(nèi)4整理ppt〔2〕

y(x1)>y(x2)那么x*在[x1,b0]之內(nèi)5整理ppt〔3〕y(x1)=y(x2)那么x*在[x1,x2]之內(nèi)6整理ppt根據(jù)上面分析，可將搜索區(qū)間縮小。在余下的區(qū)間內(nèi)繼續(xù)選擇新點(diǎn)，比較新點(diǎn)的函數(shù)值，直至區(qū)間縮小到精度要求，找到最優(yōu)點(diǎn)。a0b0091011121334567812X1’x17整理ppt3不定區(qū)間當(dāng)進(jìn)行n次函數(shù)值的計算與比較后，可以得出這n個函數(shù)值中的最小值，f(xm)及最小點(diǎn)xm以及其左右的鄰點(diǎn)xk、xr，而真正的最小點(diǎn)x*必落在xr與xk之內(nèi)。將xr與xk之間的區(qū)間稱為不定區(qū)間ln，且ln=xr–xk8整理ppt不定區(qū)間的影響因素：①

與計算次數(shù)n有關(guān)；l0=b0–a0一定時，n↑ln↓②與計算點(diǎn)的分布方式有關(guān)，即與xi確實定方法有關(guān)顯然，ln越小，那么xm與x*越接近，用xm近似x*越可靠，即精度越高。ln=xr–xk9整理ppt4區(qū)間縮短率n次函數(shù)值的計算與比較后，不定區(qū)間與原始區(qū)間的比值①當(dāng)l0一定時，En↓ln↓②相同計算次數(shù)下，En越小的方案越好10整理ppt二對無約束函數(shù)的搜索——求單峰所在區(qū)間的進(jìn)退算法

消去法的應(yīng)用根底是目標(biāo)函數(shù)f(x)在[a0,b0]內(nèi)為單峰函數(shù)。問題：〔1〕怎樣確定f(x)為單峰函數(shù)〔2〕怎樣確定f(x)的單峰所在區(qū)間[a0,b0]一般采用進(jìn)退算法解決這兩個問題。11整理ppt1、進(jìn)退算法的根本思想由單峰函數(shù)的性質(zhì)可知，對于存在極小值的單峰函數(shù)，在極小點(diǎn)左邊，函數(shù)值嚴(yán)格下降，而在極小點(diǎn)右邊，函數(shù)值應(yīng)嚴(yán)格上升。12整理ppt據(jù)此，可以從某個給定的初始點(diǎn)出發(fā)，沿著函數(shù)值下降的方向逐步前進(jìn)〔或后退〕直至發(fā)現(xiàn)函數(shù)值開始上升為止。由兩邊高中間低的三點(diǎn)函數(shù)值，就可以確定極小值所在的初始區(qū)間[a0，b0]13整理ppt2、進(jìn)退算法

(1)選定初始點(diǎn)a0與步長h(2)計算并比較y〔a0〕和y〔a0+h〕，根據(jù)比較結(jié)果有前進(jìn)和后退兩種可能：①

前進(jìn)計算：②后退運(yùn)算：14整理ppt前進(jìn)計算：假設(shè)y〔a0〕≥y〔a0+h〕，那么步長加倍，計算y〔a0+3h〕。

假設(shè)y〔a0+h〕≤y〔a0+3h〕，那么令a0=a0，b0=a0+3h15整理ppt假設(shè)y〔a0+h〕≥y〔a0+3h〕，令a0=a0+h，h=2h，重復(fù)上述前進(jìn)運(yùn)算。

16整理ppt后退運(yùn)算：假設(shè)y〔a0〕≤y〔a0+h〕,那么后退計算y〔a0-h〕;假設(shè)y〔a0-h〕≥y〔a0〕，那么令a0=a0-h，b0=a0+h，停止運(yùn)算。否那么繼續(xù)后退。17整理ppt例：求函數(shù)的極小所在區(qū)間初始點(diǎn)a0=1，步長h=1解：h=a0=118整理ppt所以應(yīng)后退19整理ppt應(yīng)繼續(xù)后退，后退時步長加倍，所以計算后退，計算20整理ppt找到了函數(shù)值大〔〕、小〔