常用的一維搜索方法.ppt

1、定理(必要條件) 設(shè) (1) 為D的一個(gè)內(nèi)點(diǎn); (2) 在 可微; (3) 為 的極值點(diǎn); 則 。,求無約束的某可微函數(shù)的最優(yōu)解， 根據(jù)一階必要條件， 可令函數(shù)的梯度等于零，由此求得駐點(diǎn)； 然后用充分條件進(jìn)行判別，求出所要的解,n元函數(shù),求解無約束優(yōu)化問題,定理(充分條件) 設(shè) (1) 為D的一個(gè)內(nèi)點(diǎn); (2) 在 二次連續(xù)可微; (3) ; (4) 正定; 則 為 的嚴(yán)格局部極小點(diǎn)。,第3章 常用的一維搜索方法,對某些較簡單的函數(shù)，這樣做有時(shí)是可行的； 但對一般n元函數(shù) f(x) 來說，由條件 得到的是一個(gè)非線性方程組，解它相當(dāng)困難。 對于不可微函數(shù)，當(dāng)然談不上使用這樣的方法。 為此，常直接

2、使用迭代法。,第3章 常用的一維搜索方法,為了求函數(shù)f(x)的最優(yōu)解，,然后按某種規(guī)劃(即算法)找出比,更好的解,再按此種規(guī)則找出比,更好的解,如此即可得到一個(gè)解的序列,若這個(gè)解序列有極限,則稱它收斂于x*。,若算法是有效的，則它產(chǎn)生的解序列收斂于該問題的最優(yōu)解。 計(jì)算機(jī)只能進(jìn)行有限次迭代，一般很難得到準(zhǔn)確解，而只能得到近似解。當(dāng)達(dá)到滿足的精度要求后，即可停止迭代。,迭代法的基本思想,首先給定一個(gè)初始估計(jì),理想的終止條件是,或者,問題是 x* 未知,停止迭代時(shí)要滿足的條件稱為終止條件。,迭代法的終止條件,實(shí)用的終止條件是根據(jù)相繼兩次迭代的結(jié)果,（1）根據(jù)相繼兩次迭代的絕對誤差,（2）根據(jù)相繼兩

3、次迭代的相對誤差,（3）根據(jù)目標(biāo)函數(shù)梯度的模足夠小,迭代法的終止條件,設(shè)序列 收斂于 ，若存在與迭代次數(shù) k 無關(guān)的數(shù),時(shí)，稱超線性收斂。,時(shí)，稱線性收斂或一階收斂。,成立，就稱 收斂的階為 ，或者稱 階收斂。,迭代法的收斂速度,和 ，使k從某個(gè)k0開始，都有,當(dāng),當(dāng) ，且,具有二階收斂速度。,當(dāng),時(shí)，稱為二階收斂，也可說,迭代法的一般框架,找初始點(diǎn),判斷當(dāng)前點(diǎn)是否滿足終止條件,找下一個(gè)迭代點(diǎn),最優(yōu)解,(a) 找初始點(diǎn),(b) 終止條件,(c) 迭代格式,從當(dāng)前點(diǎn)出發(fā)，按照某種規(guī)則找下一個(gè)迭代點(diǎn),注：迭代格式不同，對應(yīng)著不同的算法,是,否,循環(huán),迭代法的分類,初始點(diǎn)不好找,每一迭代點(diǎn)的目標(biāo)函數(shù)

4、值都在下降,整體下降，局部上升,初始點(diǎn)任意選取,迭代法的分類,僅利用函數(shù)值，簡單易用,利用導(dǎo)數(shù)信息，收斂性結(jié)果更強(qiáng),每次迭代沿某個(gè)方向搜索下個(gè)迭代點(diǎn)， 最常見研究最多的方法,每次迭代在某區(qū)域內(nèi)搜索下個(gè)迭代點(diǎn)，近30年來發(fā)展起來的一類方法,現(xiàn)假定已迭代到點(diǎn),則從,都不能使目標(biāo)函數(shù)值下降。,若 是一局部極小點(diǎn)，,若從 出發(fā)至少存在一個(gè)方向可使目標(biāo)函數(shù)值有所下降，,圖 1,線搜索迭代法的基本思想,出發(fā)沿任何方向移動(dòng),如圖1示,若從 出發(fā)至少存在一個(gè)方向 可使目標(biāo)函數(shù)值有所下降，可選定這個(gè)方向 ，,這相當(dāng)于在射線,其中，,稱為搜索方向；,稱為步長或步長因子。,圖 1,線搜索迭代法的基本思想,沿這個(gè)方向

5、邁進(jìn)適當(dāng)?shù)囊徊?，得到下一個(gè)迭代點(diǎn) ， 使 。,上選定新點(diǎn),(1) 選定某一初始點(diǎn),，并令,(2) 確定搜索方向,(3) 從,出發(fā)，沿方向,求步長,，以產(chǎn)生下一個(gè)迭代點(diǎn),(4) 檢查得到的新點(diǎn),是否為極小點(diǎn)或近似極小點(diǎn)。,，轉(zhuǎn)回(2)繼續(xù)進(jìn)行迭代。,在以上步驟中，選取搜索方向是最關(guān)鍵的一步。 各種算法的區(qū)分，主要在于搜索方向 的不同。,若是，則停止迭代。 否則，令,線搜索迭代法的步驟,找初始點(diǎn),判斷當(dāng)前點(diǎn)是否滿足終止條件,下一個(gè)迭代點(diǎn),最優(yōu)解,(a) 找初始點(diǎn),(b) 終止條件,(c) 迭代格式,找步長 和下降方向 ， 確定下一個(gè)迭代點(diǎn),不同的 對應(yīng)不同的算法,是,否,循環(huán),線搜索迭代法的框架分

6、析,不同的 對應(yīng)不同的算法,線搜索迭代法的框架分析,(c) 迭代格式：不同的 對應(yīng)不同的算法，各種算法的區(qū) 分，主要在于確定搜索方向的方法不同。 后面介紹各種 算法時(shí)會(huì)給出一個(gè)明確的選取 的方法。,在確定了迭代方向后，下一步就要確定迭代步長 ，常見的方法有3種。,(1) 令它等于某一常數(shù)(例如令,)，這樣做不能保證目標(biāo),函數(shù)值下降。,(2) 第二種稱為可接受點(diǎn)算法，只要能使目標(biāo)函數(shù)值下降，可 任意選取步長。,求目標(biāo)函數(shù) f(x) 的極小：,這項(xiàng)工作是求以 為變量的一元函數(shù),的極小點(diǎn),，故常稱這一過程為（精確）一維搜索或,線搜索迭代法的框架分析-一維搜索,（精確）線搜索或一維最優(yōu)化，確定的步長為

7、最佳步長。,(3) 第三種方法的思路是：沿搜索方向使目標(biāo)函數(shù)值下降最多， 即沿射線,在搜索方向上所得最優(yōu)點(diǎn)處的梯度和該搜索方向正交。,定理 設(shè)目標(biāo)函數(shù),具有一階連續(xù)偏導(dǎo)數(shù)，,規(guī)則產(chǎn)生,則有,（精確）一維搜索的一個(gè)重要性質(zhì),按下述,證明：構(gòu)造函數(shù) ，則得,即 是函數(shù) 的極小點(diǎn)，所以,精確的一維搜索 (1) 試探法：按某種方式找試探點(diǎn)，通過比較一系列試探點(diǎn)的函 數(shù)值的大小確定極小點(diǎn)。 (2) 區(qū)間收縮法：用某種分割技術(shù)縮小最優(yōu)解所在的區(qū)間(稱 為搜索區(qū)間)。 (3) 函數(shù)逼近法：用比較簡單函數(shù)的極小值點(diǎn)近似代替原函數(shù)的 極小值點(diǎn)。從幾何上看是用比較簡單的曲線近似代替原 來的曲線，用簡單曲線的極小值

8、點(diǎn)代替原曲線的極小點(diǎn)。 Newton法、二次插值法、三次插值法,常用的一維搜索方法,“成功-失敗”法,二分法、0.618法,非精確的一維搜索：通過計(jì)算少量的函數(shù)值，得到一步長 ，使得后續(xù)迭代點(diǎn) 滿足 ，即使目標(biāo)函數(shù)要“充分”下降。,常用的一維搜索方法,(1) Armiji-Goldstein準(zhǔn)則,其中,要滿足,非精確的一維搜索：通過計(jì)算少量的函數(shù)值，得到一步長 ，使得后續(xù)迭代點(diǎn) 滿足 ，即使目標(biāo)函數(shù)要“充分”下降。,常用的一維搜索方法,(2) Wolfe-Powell準(zhǔn)則,要滿足,其中,常用的一維搜索方法,我們主要介紹下面幾種方法,“成功失敗”法 0.618法（黃金分割法） 二分法 牛頓法（N

9、ewton）和插值法 Armiji-Goldstein 準(zhǔn)則 Wolfe-Powell 準(zhǔn)則,常用的一維搜索方法,對問題 令 則,僅考慮一維無約束優(yōu)化問題,注意：初始步長不能選得太小,“成功失敗”法（進(jìn)退法）,步驟1：選取初始點(diǎn) xR , 初始步長 h 0 及精度 0， 步驟2：計(jì)算 步驟3：若 搜索成功, 轉(zhuǎn)步驟4；否則，搜索失敗， 轉(zhuǎn)步驟5。 步驟4：令 x:= x + h, 轉(zhuǎn)步驟 2。 步驟5：判斷 若 停止迭代， ；否則令 轉(zhuǎn)步驟 2。 缺點(diǎn)：效率低。優(yōu)點(diǎn)：可以求搜索區(qū)間。,例1：設(shè)給定初始點(diǎn)為 a 及初始步長為 h, 求搜索區(qū)間c, d 1) 前進(jìn)運(yùn)算 首先計(jì)算 f (a), f

10、(a+h), 如果 f (a) f (a+h), 則步長加倍, 計(jì) 算f (a+3h). 若 f (a+h)= f (a+3h), 則c=a, d=a+3h; 否則將步 長再加倍，并重復(fù)上面運(yùn)算. 2) 后退運(yùn)算 如果 f (a) f (a+h), 則將步長縮為原來的1/4并改變符號(hào)，即 將步長改為-h/4, 如果 f (a) f (a-h/4),則c=a-h /4,d=a+h; 否則 將步長加倍，并繼續(xù)后退。,注意: 1. h 選擇要適當(dāng).(太大含多個(gè)單峰區(qū)間,太小迭代次數(shù)多)； 2. f (x)單調(diào)時(shí)無結(jié)果, (加迭代次數(shù)限制)；,“成功失敗”法（進(jìn)退法）,例 ：利用“成功-失敗”法求函數(shù)

11、 的搜索區(qū)間， 取初始點(diǎn) ，步長,解：取初始點(diǎn) ，步長,“成功失敗”法-算例,得到搜索區(qū)間為,0.618法（黃金分割法）,0.618法是求單峰函數(shù)極值的一種試探法，有的書上 也稱為區(qū)間收縮法。所謂的單峰函數(shù)是指只有一個(gè)峰值 的函數(shù)。 定義(單峰函數(shù))：設(shè) f(x) 是定義在a, b上的函數(shù)，若 1） x* a, b 是在a, b上的最小點(diǎn) ， 2） 若對任意 x1 , x2, a x1 f (x2); 2 若x1 x* ，則 f (x1) f (x2). 則稱 f(x) 為a, b上的單峰函數(shù)。,定理：設(shè) f：RR 在a, b 上是單峰函數(shù)， a x1 x2 b 。 那么 1若 f (x1)

12、f (x2)，則 x* x1 , b ,如左下圖 2若 f (x1) f (x2) ，則 x* a, x2 , 如右下圖,縮短區(qū)間的第一個(gè)原則-去壞留好原則,0.618法（黃金分割法）,證明： 1反證法：設(shè) x* a, b為最小點(diǎn)， 若x* a, x1，由定義 知 f (x1) f (x2 ), 矛盾（條件）； 結(jié)論成立。 注：上述定理為縮短區(qū)間的算法提供了理論根據(jù)。,0.618法（黃金分割法）,通過上述定理，選二點(diǎn) x1 x2 , 比較 f (x1 ) 與 f (x2 ) ,可去掉 a , x1 或者x2 , b. 考慮條件： 1對稱原則： x1 a = b- x2 (1) （使“壞”的情況

13、去掉，區(qū)間長度不小于“好”的情況） 2保持縮減比原則 t =(保留的區(qū)間長度原區(qū)間長度) 不變。 （使每次保留下來的節(jié)點(diǎn)， x1或 x2 ，在下一次的比較中成 為一個(gè)相應(yīng)比例位置的節(jié)點(diǎn) ）。 推導(dǎo)縮減比 t : 如圖設(shè)第一次保留a, x2 (去掉x2 , b), 第二次保留的長度為a, x1 , 則,0.618法（黃金分割法）,整理(2) ： x2 = a + t x1 = a + t ( x2 -a)= a + (1-t) ( b -a ) 結(jié)合(1)式： 故 t0.618 注意: 上式有 t 2 = 1-t , 故有 x1 = a+(1-t)(b-a)=a+0.328(b-a) x2 =

14、a+t(b-a)= a+0.618(b-a),0.618法（黃金分割法）,t 2 + t 1 = 0,當(dāng)區(qū)間的長度充分小時(shí)，可將區(qū)間中點(diǎn)取做極小點(diǎn)的近似點(diǎn)。,0.618 法-算法,優(yōu)點(diǎn)：不要求函數(shù)可微，且每次迭代只需計(jì)算一 個(gè)函數(shù)值，計(jì)算量小，程序簡單 缺點(diǎn)：收斂速度慢。,黃金分割法（0.618 法）的優(yōu)缺點(diǎn),0.618法（黃金分割法）,例 ：試用0.618法求目標(biāo)函數(shù) 的最優(yōu)解。 給定初始區(qū)間0,2，收斂精度,解：第一次區(qū)間縮短計(jì)算過程：,計(jì)算兩點(diǎn)及對應(yīng)函數(shù)值：,作數(shù)值比較，可見 ,再做置換：,0.618法-算例,第二次區(qū)間縮短計(jì)算過程：,作數(shù)值比較， ,再做置換：,第三次區(qū)間縮短計(jì)算過程：

15、,作數(shù)值比較， ,再做置換：,各次的迭代結(jié)果如下：,缺點(diǎn)：收斂速度慢 優(yōu)點(diǎn)：不要求函數(shù)可微，且每次迭代只需計(jì)算一個(gè)函數(shù) 值，計(jì)算量小,設(shè) f (x)在 a ,b上可微，求函數(shù)f在a,b的極小點(diǎn)，就是求 函數(shù)導(dǎo)數(shù)為零的點(diǎn)。 如果 則在(a,b)內(nèi)一定存在一點(diǎn) x，使得 。 為求極小點(diǎn)，可取 ， 若 , x 為最小點(diǎn), x0 = x* ; , x0 在上升段, x* x0，去掉a, x0 .,二分法-基本思想,用 或者 作新的區(qū)間a,b，繼續(xù)這個(gè)過程， 逐步將區(qū)間a,b縮小， 當(dāng)區(qū)間a,b的長度充分小時(shí)，可將a,b的中點(diǎn)取做極小 點(diǎn)的近似點(diǎn)。,二分法-基本思想,優(yōu)點(diǎn)：計(jì)算量較少，而且總能收斂到一個(gè)局部極小點(diǎn)。 缺點(diǎn)：收斂速度較慢,二分法-計(jì)算步驟,步驟1：計(jì)算 步驟2：若 ，令 ，轉(zhuǎn)步驟3； 若 ，令 ，轉(zhuǎn)步驟3