精確一維搜索2.Fibonacci與黃金分割法3.進退法

4.平分法1.一維最優(yōu)化問題

5.拋物線搜索法2021/10/101一維搜索的基本概念2021/10/102一.一維最優(yōu)化問題下降迭代算法中最優(yōu)步長的確定..一維最優(yōu)化問題：極值點的必要條件：2021/10/1031.下單峰函數(shù)定義：設是區(qū)間上的一元函數(shù)，是在上的極小點，且對任意的有（a）當時，（b）當.....則稱下是單峰函數(shù)。..有沒有特殊形式的下單峰函數(shù)2021/10/104性質(zhì)：通過計算區(qū)間內(nèi)兩個不同點的函數(shù)值，就可以確定一個包含極小點的子區(qū)間。定理

設是區(qū)間上的一元函數(shù)，是在上的極小點。任取點則有（1）如果，則（2）如果則.....如何確定一個下單峰函數(shù)呢？2021/10/105Fibonacci方法--試探點算法2021/10/106Fibonacci法的引入計算n次函數(shù)值，如何取點使最終區(qū)間最??？或者最終區(qū)間長度為1，計算n次函數(shù)值，初始區(qū)間最多為多長？2021/10/1072021/10/1082021/10/1092021/10/1010課堂練習2021/10/10112021/10/1012黃金分割法思想通過選取試探點使包含極小點的區(qū)間不斷縮短，直到區(qū)間長度小到一定程度，此時區(qū)間上各點的函數(shù)值均接近極小值。下面推導黃金分割法的計算公式。2021/10/10132021/10/1014通過確定的取值，使上一次迭代剩余的迭代點恰與下一次迭代的一個迭代點重合，從而減少算法的計算量。同理可得。2021/10/1015算法步驟：2021/10/1016一個以前很好的例子functionansw=goldsection(a,b,eps)%黃金分割法實現(xiàn)一維搜索%a----搜索區(qū)間左端點%b----搜索區(qū)間右端點%eps----搜索精度%CopyRight@XiaBo%Date:2008.3.20%%定義搜索函數(shù)funfunctionf=fun(x)%這里是一個簡單的函數(shù)定義，倘若在一個大型的優(yōu)化計算中，這個函數(shù)一般是和第k步的迭代點和下降方向有關(guān)的%是一個關(guān)于步長的函數(shù)%x---待求步長值f=x^2-x+2;2021/10/1017%尋找初始分割點x1=a+.382*(b-a);x2=a+.618*(b-a);%搜索主體while(abs(b-a)>eps)%計算分割點處的函數(shù)值

f1=fun(x1);f2=fun(x2);%比較判斷兩個分割點處的函數(shù)值，進而縮短區(qū)間長度

if(f1>f2)a=x1;x1=x2;x2=a+.618*(b-a);elseif(f1==f2)a=x1;b=x2;x1=a+.382*(b-a);x2=a+.618*(b-a);elseb=x2;x2=x1;x1=a+.382*(b-a);endend%返回搜索值answ=(a+b)/2;2021/10/1018黃金分割法的迭代效果：第k次后迭代后所得區(qū)間長度為初始區(qū)間長度的作業(yè)2021/10/10192021/10/1020作業(yè)如果換成了最終區(qū)間不大于0.08，如何做？為什么？2021/10/1021…….2021/10/1022…….2021/10/10233．進退法思想從一點出發(fā),按一定的步長,試圖確定出函數(shù)值呈現(xiàn)“高-低-高”的三點。一個方向不成功，就退回來，再沿相反方向?qū)ふ?。進退法的計算步驟（與教材的算法比較P20）如何確定包含極小點的一個區(qū)間？2021/10/1024例：2021/10/1025平分法

(優(yōu)點和缺點都突出的方法)能否看出優(yōu)點和缺點？2021/10/10262021/10/10275.拋物線插值思想在極小點附近，用二次三項式為什么非要是二次三項式？2021/10/1028如何計算函數(shù)令2021/10/1029拋物線插值算法步驟：解出2021/10/1030作業(yè)小結(jié)各種精確一維搜索算法2021/10/1031不精確一維線搜索2021/10/1032為什么不精確的搜索好？距離最優(yōu)解遠的時候，精度太大算法效率低有些算法的收斂速度不依賴與搜索的精度只要求有充分下降即可這種類似與“充分”、“足夠”等描述詞匯，在與計算相關(guān)的描述中，要特別在意，因為，這里的“充分”，已經(jīng)不再是理論上的要求，這里的“充分”必須與“可計算”相關(guān)（到底要多充分，就是這里的非精確搜索的準測）2021/10/1033Armijo準則Wolfe準則2021/10/1034Goldstein準則2021/10/10352021/10/1036Armijo準則2021/10/10372021/10/1038收斂性證明2021/10/10392021/10/1040懂數(shù)學、有能力、不神秘2021/10/10412021/10/1042主體證明開始(反證法)：2021/10/10432021/10/10442021/10/1045此引理給出了Wolfe準則單步中至少下降的界（略）2021/10/10462021/10/1047