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

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

4.5.2.1單變量最優(yōu)化問題的數(shù)值解法〔一維搜索〕一、消去法的根本概念1消去法的根本思想利用單峰函數(shù)在可行域內(nèi)只有一個極值點的特點，設法逐步縮小搜索最優(yōu)點的區(qū)間，直至找到最優(yōu)點，并到達允許的精度為止。消去法分為：1整理ppt同時消去法：同時計算一批點的函數(shù)值，然后比較各函數(shù)值的大小，再消去一局部區(qū)間，直至到達精度要求。序貫消去法：從第二個點起，每計算一個點的函數(shù)值，就與前一個點的函數(shù)值進行比較，消去局部區(qū)間后再安排下一個計算點，如此序貫進行，直至到達精度要求。2整理ppt2序貫法縮小搜索區(qū)間設：一元函數(shù)y(x)在區(qū)間[a0,b0]內(nèi)為單峰函數(shù)，假設首先在[a0,b0]內(nèi)任取兩點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ù)選擇新點，比較新點的函數(shù)值，直至區(qū)間縮小到精度要求，找到最優(yōu)點。a0b0091011121334567812X1’x17整理ppt3不定區(qū)間當進行n次函數(shù)值的計算與比較后，可以得出這n個函數(shù)值中的最小值，f(xm)及最小點xm以及其左右的鄰點xk、xr，而真正的最小點x*必落在xr與xk之內(nèi)。將xr與xk之間的區(qū)間稱為不定區(qū)間ln，且ln=xr–xk8整理ppt不定區(qū)間的影響因素：①

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

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

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

前進計算：②后退運算：14整理ppt前進計算：假設y〔a0〕≥y〔a0+h〕，那么步長加倍，計算y〔a0+3h〕。

假設y〔a0+h〕≤y〔a0+3h〕，那么令a0=a0，b0=a0+3h15整理ppt假設y〔a0+h〕≥y〔a0+3h〕，令a0=a0+h，h=2h，重復上述前進運算。

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