第四章一維搜索(補(bǔ)充)(2)

1、一維搜索湯奕湯奕2022-4-21SOUTHEAST UNIVERSITY 東南大學(xué)4.1 一維搜索問題2022-4-21SOUTHEAST UNIVERSITY 東南大學(xué)2 單變量函數(shù)的最優(yōu)化問題 迭代關(guān)鍵是構(gòu)造搜索方向和步長因子 minkkkkkf xpf xp使函數(shù)值最小使函數(shù)值最小的步長因子的步長因子步長因子步長因子搜索方向搜索方向2022-4-21SOUTHEAST UNIVERSITY 東南大學(xué)3 ,0,maxkkkkpfxpfxkpkkf xpkkkf xpkkkfxpk 沿當(dāng)時，函數(shù)是下降的；當(dāng)時，函數(shù)是上升的。稱這樣搜索方向，任一 都能使，即是下降方向。若記，則的函數(shù)為單谷函

2、數(shù)。是一元函數(shù)的極小點。2022-4-21SOUTHEAST UNIVERSITY 東南大學(xué)4 概念：又稱試探法，按某種方式找試探點，通過一系列試探點來確定極小點。區(qū)間收縮法 概念：又稱插值法，用某種較簡單的曲線逼近本來的函數(shù)曲線，通過求逼近函數(shù)的極小點來估計目標(biāo)函數(shù)的極小點。 方法：牛頓法、割線法、拋物線法、三次插值法、有理插值法函數(shù)逼近法 方法：黃金分割法、Fibonacci法、進(jìn)退法。4.1.1 求解步長因子的方法2022-4-21SOUTHEAST UNIVERSITY 東南大學(xué)54.2 黃金分割法 找到包含極小點的初始搜索區(qū)間，然后按黃金分割點通過對函數(shù)值的比較不斷縮小區(qū)間。 保證極

3、小點始終在搜索區(qū)間內(nèi)，當(dāng)區(qū)間長度小到精度范圍之內(nèi)時，可以粗略地認(rèn)為區(qū)間端點的平均值即為極小點的近似值。 適用于單谷函數(shù)。概述4.2.1 單谷函數(shù)2022-4-21SOUTHEAST UNIVERSITY 東南大學(xué)6性質(zhì) *00111*1101*1110,12a ba bababa baba b 若是單谷區(qū)間上的單谷函數(shù)，極小點為 ，在中任取兩點，且，則：（）當(dāng)時，。（）當(dāng)時，。2022-4-21SOUTHEAST UNIVERSITY 東南大學(xué)74.2.2 基本原理原理2022-4-21SOUTHEAST UNIVERSITY 東南大學(xué)8可以證明，不論新搜索區(qū)間是哪一段區(qū)間，總有上一對試點中一

4、個被保留下來作新的試點用，可大大節(jié)省計算工作量2022-4-21SOUTHEAST UNIVERSITY 東南大學(xué)94.2.3 算法步驟選擇數(shù)據(jù)，確定搜索區(qū)間選擇數(shù)據(jù)，確定搜索區(qū)間 確定新試點，重新搜索確定新試點，重新搜索計算試點及目標(biāo)函數(shù)值計算試點及目標(biāo)函數(shù)值搜索區(qū)間縮小為搜索區(qū)間縮小為 比較比較目標(biāo)函數(shù)值目標(biāo)函數(shù)值11kkxxa ,kkb搜索區(qū)間縮小為搜索區(qū)間縮小為 YN若若 則停止迭代則停止迭代1100kkbaba2022-4-21SOUTHEAST UNIVERSITY 東南大學(xué)104.2.4 計算舉例確定試點及目標(biāo)函數(shù)值：比較目標(biāo)函數(shù)值：縮小收縮區(qū)間：判斷是否繼續(xù)迭代：進(jìn)入下一輪迭代

5、。111100.618 301.854 3.664800.382 301.146 0.2131xxxx11xx 10110 1.854aabx11001.8540.6180.153baba2022-4-21SOUTHEAST UNIVERSITY 東南大學(xué)11第一輪迭代000 3ab確定試點及目標(biāo)函數(shù)值：比較目標(biāo)函數(shù)值：縮小收縮區(qū)間：判斷是否繼續(xù)迭代：進(jìn)入下一輪迭代。22211.146 0.213100.382 1.85400.708 0.0611xxxxx 22xx 21220 1.146aabx22001.1460.3820.153baba2022-4-21SOUTHEAST UNIVER

6、SITY 東南大學(xué)12第二輪迭代110 1.854ab確定試點及目標(biāo)函數(shù)值：比較目標(biāo)函數(shù)值：縮小收縮區(qū)間：判斷是否繼續(xù)迭代：進(jìn)入下一輪迭代。323330.708 0.061100.382 300.438 0.2080 xxxxx 33xx 33320.438 1.146axbb33001.1460.4380.2360.153baba2022-4-21SOUTHEAST UNIVERSITY 東南大學(xué)13第三輪迭代220 1.146ab確定試點及目標(biāo)函數(shù)值：比較目標(biāo)函數(shù)值：縮小收縮區(qū)間：判斷是否繼續(xù)迭代：迭代結(jié)束，輸出最有近似解：434330.4380.618 1.1460.4380.876 0

7、.07980.708 0.0611xxxxx 44xx 44430.708 1.146axbb44001.1460.7080.1460.153baba*4410.9272ba2022-4-21SOUTHEAST UNIVERSITY 東南大學(xué)14第四輪迭代330.438 1.146ab2022-4-21SOUTHEAST UNIVERSITY 東南大學(xué)154.2.5 算法小結(jié)0.618法最多做9次迭代如果一旦不滿足，只能將黃金分割比的近似值取得比0.618更接近精確值的數(shù)。用0.618法每迭代一次，搜索區(qū)間就縮短為初始區(qū)間長度的0.618倍。若做了 次迭代，第 次迭代區(qū)間長為 ，此時共計點的個

8、數(shù)為 個。kk000.618kkkbaba1k 4.3 加步探索法（進(jìn)退法）2022-4-21SOUTHEAST UNIVERSITY 東南大學(xué)16一維搜索方法都要事先給定一個包含極小點的初始搜索區(qū)間，加步探索法就是解決這個問題的關(guān)鍵。概述加步探索法本身是一種區(qū)間試探法。主要思路就是從一點出發(fā)，按一定的步長，試圖確定出函數(shù)值呈現(xiàn)“高低高”的3點。首先從一個方向去找，若不成功，就退回來，再沿相反方向?qū)ふ?，若方向正確，則加大步長進(jìn)行探索，最終找到 3點，使其滿足下列條件為止。 1231223,xxxf xf xf xf x2022-4-21SOUTHEAST UNIVERSITY 東南大學(xué)174.

9、3.1 算法原理原理2022-4-21SOUTHEAST UNIVERSITY 東南大學(xué)184.3.2 算法步驟Step 1 給定初始點 ，初始步長 Step 2 用加倍步長的外推法找出初始區(qū)間Step 3 進(jìn)一步縮小搜索區(qū)間1x00h 2022-4-21SOUTHEAST UNIVERSITY 東南大學(xué)19如何確定初始點及步長？2022-4-21SOUTHEAST UNIVERSITY 東南大學(xué)20如何用加倍步長的外推法找出初始區(qū)間？由初始點 向某個方向，比如向 增大方向走一步，步長為 ，得 計算 和 ，并比較函數(shù)值大小。1x0h210 xxh1fx2fxx 21f xf x 2022-4-

10、21SOUTHEAST UNIVERSITY 東南大學(xué)22如何進(jìn)一步縮小搜索區(qū)間？Step 32022-4-21SOUTHEAST UNIVERSITY 東南大學(xué)234.3.3 計算舉例 2022-4-21SOUTHEAST UNIVERSITY 東南大學(xué)24牛頓法是一種函數(shù)逼近法，它的基本思想是：在極小點附近用二階泰勒多項式近似代替目標(biāo)函數(shù) ，從而求出 極小點的估計值。 f x f x2022-4-21SOUTHEAST UNIVERSITY 東南大學(xué)254.4 牛頓法概述 2022-4-21SOUTHEAST UNIVERSITY 東南大學(xué)264.4.1 算法原理原理 2022-4-21S

11、OUTHEAST UNIVERSITY 東南大學(xué)272022-4-21SOUTHEAST UNIVERSITY 東南大學(xué)284.3.2 算法步驟Step 1Step 2Step 32022-4-21SOUTHEAST UNIVERSITY 東南大學(xué)294.3.3 計算舉例 2022-4-21SOUTHEAST UNIVERSITY 東南大學(xué)302022-4-21SOUTHEAST UNIVERSITY 東南大學(xué)314.4.4 算法小結(jié)2022-4-21SOUTHEAST UNIVERSITY 東南大學(xué)324.5 拋物線法概述 2022-4-21SOUTHEAST UNIVERSITY 東南大學(xué)334.4.1 算法原理原理 2022-4-21SOUTHEAST UNIVERSITY 東南大學(xué)34 2022-4-21SOUTHEAST UNIVERSITY 東南大學(xué)35 2022-4-21SOUTHEAST UNIVERSITY 東南大學(xué)36ATTENTION !4.5.2 計算舉例2022-4-21SOUTHEAST UNIVERSITY 東南