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

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

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

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

4、個(gè)被保留下來(lái)作新的試點(diǎn)用，可大大節(jié)省計(jì)算工作量2022-4-21SOUTHEAST UNIVERSITY 東南大學(xué)94.2.3 算法步驟選擇數(shù)據(jù)，確定搜索區(qū)間選擇數(shù)據(jù)，確定搜索區(qū)間 確定新試點(diǎn)，重新搜索確定新試點(diǎn)，重新搜索計(jì)算試點(diǎn)及目標(biāo)函數(shù)值計(jì)算試點(diǎn)及目標(biāo)函數(shù)值搜索區(qū)間縮小為搜索區(qū)間縮小為 比較比較目標(biāo)函數(shù)值目標(biāo)函數(shù)值11kkxxa ,kkb搜索區(qū)間縮小為搜索區(qū)間縮小為 YN若若 則停止迭代則停止迭代1100kkbaba2022-4-21SOUTHEAST UNIVERSITY 東南大學(xué)104.2.4 計(jì)算舉例確定試點(diǎn)及目標(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確定試點(diǎn)及目標(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確定試點(diǎn)及目標(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確定試點(diǎn)及目標(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ū)間長(zhǎng)度的0.618倍。若做了 次迭代，第 次迭代區(qū)間長(zhǎng)為 ，此時(shí)共計(jì)點(diǎn)的個(gè)

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

9、3.1 算法原理原理2022-4-21SOUTHEAST UNIVERSITY 東南大學(xué)184.3.2 算法步驟Step 1 給定初始點(diǎn) ，初始步長(zhǎng) Step 2 用加倍步長(zhǎng)的外推法找出初始區(qū)間Step 3 進(jìn)一步縮小搜索區(qū)間1x00h 2022-4-21SOUTHEAST UNIVERSITY 東南大學(xué)19如何確定初始點(diǎn)及步長(zhǎng)？2022-4-21SOUTHEAST UNIVERSITY 東南大學(xué)20如何用加倍步長(zhǎng)的外推法找出初始區(qū)間？由初始點(diǎn) 向某個(gè)方向，比如向 增大方向走一步，步長(zhǎng)為 ，得 計(jì)算 和 ，并比較函數(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 計(jì)算舉例 2022-4-21SOUTHEAST UNIVERSITY 東南大學(xué)24牛頓法是一種函數(shù)逼近法，它的基本思想是：在極小點(diǎn)附近用二階泰勒多項(xiàng)式近似代替目標(biāo)函數(shù) ，從而求出 極小點(diǎn)的估計(jì)值。 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 計(jì)算舉例 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 計(jì)算舉例2022-4-21SOUTHEAST UNIVERSITY 東南