改進(jìn)的黃金分割法

《改進(jìn)的黃金分割法》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫(kù)。

1、實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)項(xiàng)目名稱改進(jìn)的黃金分割法所屬課程名稱最優(yōu)化實(shí)驗(yàn)類型算法編程實(shí)驗(yàn)日期2015年12月25日班級(jí)學(xué)號(hào)姓名成績(jī)6一、實(shí)驗(yàn)概述：【實(shí)驗(yàn)?zāi)康摹?：了解黃金分割法所存在的缺點(diǎn)并對(duì)它進(jìn)行改進(jìn)。3：熟悉應(yīng)用Matlab求解無(wú)約束最優(yōu)化問(wèn)題的編程方法.【實(shí)驗(yàn)原理】黃金分割法的基本思想是：通過(guò)取試探點(diǎn)和進(jìn)行函數(shù)值的比較,使包含極小點(diǎn)的搜索區(qū)間不斷縮短,當(dāng)區(qū)間長(zhǎng)度縮短到一定程度時(shí),區(qū)間上各點(diǎn)的函數(shù)值均接近極小值,從而各點(diǎn)可以看作為極小點(diǎn)的近似；也即是，依照“去壞留好”原則，對(duì)稱原則，以及等比收縮原則來(lái)逐步縮小搜索范圍。當(dāng)函數(shù)是凸函數(shù)時(shí)，

2、我們可以利用函數(shù)的凸性,得到函數(shù)值的上界和下界，進(jìn)而利用這些信息，縮短函數(shù)不確定區(qū)間，達(dá)到優(yōu)化算法的效果。很多人認(rèn)為黃金分割法是搜索速度最快的方法，從程序編寫角度來(lái)說(shuō)，黃金分割法每次只需要插入一個(gè)點(diǎn)，每次只需要計(jì)算一次函數(shù)值，易于理解。就對(duì)區(qū)間縮短率來(lái)講，黃金分割法的縮短率是0.618，舍棄的區(qū)間是0.382。但是，如果一個(gè)函數(shù)是凸函數(shù)，根據(jù)已知的函數(shù)值，可以找到它的最大值和最小值，這些信息有利于得到最優(yōu)解的位置，進(jìn)而大大縮減不確定區(qū)間。假設(shè)f(x)是定義在區(qū)間S上的連續(xù)的，單變量可微的凸函數(shù)，給點(diǎn)初始不確定區(qū)間[l,u]。下

3、面介紹兩種利用函數(shù)的凸性優(yōu)化黃金分割的方法。利用凸函數(shù)的一階特征改進(jìn)算法。通過(guò)凸函數(shù)的一階特征，定理1.3.11[5]：設(shè)S?Rn為非空開(kāi)凸集，f是定義在S上的可微函數(shù)，則f為凸函數(shù)的充分必要條件是：f(y)≥f(x)+?f(x)T(y?x),?x,y∈S（1）證明：必要性設(shè)f是凸函數(shù)，于是對(duì)所有α，0≤α≤1，有f(αy+(1?α)x≤αf(y)+(1?α)f(x)因此，對(duì)于0<α≤1，f(x+α(y?x))?f(x)≤f(y)?f(x)α6令α→0，得?f(x)T(y?x)≤f(y)?f(x)充分性假設(shè)（1）成立，任取x1

4、,x2∈S，0≤α≤1。令x=αx1+(1?α)x2，我們有f(x1)≥f(x)+?f(x)T(x1?x),f(x2)≥f(x)+?f(x)T(x2?x)于是得到：αf(x1)+(1?α)f(x2)≥f(x)+?f(x)T[αx1+(1?α)x2?x]=f(αx1+(1?α)x2)所以f(x)是凸函數(shù)。這個(gè)定理表明了根據(jù)局部導(dǎo)數(shù)的線性近似是函數(shù)的低估，即凸函數(shù)圖形位于圖形上任一點(diǎn)切線的上方。根據(jù)這個(gè)定理，所以函數(shù)的最小值一定在切線的上方。利用凸函數(shù)的一階特征以及已知的最小函數(shù)值就可以確定不確定區(qū)間。函數(shù)兩個(gè)端點(diǎn)處的切線和最小函

5、數(shù)值的交點(diǎn)，即為縮小的不確定區(qū)間?！緦?shí)驗(yàn)環(huán)境】Windowsxp,matlab2007二、實(shí)驗(yàn)內(nèi)容：【實(shí)驗(yàn)方案】該算法的基本思想是：已知函數(shù)f(x)在區(qū)間端點(diǎn)l,u兩點(diǎn)的函數(shù)值f(l),f(u)，并比較兩點(diǎn)函數(shù)值的大小，如果f(l)≤f(u)，最小值點(diǎn)為x=u?0.618(u?l)。否則，就取x=l+0.618(u?l)，并給該點(diǎn)的函數(shù)賦值f(x)；下一步求出函數(shù)在l,u兩點(diǎn)處的切線函數(shù)；最小函數(shù)f(x)與兩切線的交點(diǎn)l′,u′，即是新的迭代區(qū)間[l,u]。由定理1.3.11，我們知道函數(shù)值一定在切線的上方，所以最小值也在新的

6、迭代區(qū)間內(nèi)，如圖1所示：6【實(shí)驗(yàn)過(guò)程】（實(shí)驗(yàn)步驟、記錄、數(shù)據(jù)、分析）Step0:確定，l,u。Step1；函數(shù)在l,u兩點(diǎn)處賦值f(l),f(u)；Step2:比較f(l),f(u)兩點(diǎn)函數(shù)值的大小，如果f(l)≤f(u)，x=u?0.618(u?l)，否則：x=l+0.618(u?l)，并給x點(diǎn)賦值f(x)；Step3:計(jì)算出f在l,u點(diǎn)的切線方程tl,tu；Step4:函數(shù)f(x)與直線tl,tu的交點(diǎn)l′,u′，即是新的迭代區(qū)間[l,u]Step5:循環(huán)，直到滿足精度要求【實(shí)驗(yàn)結(jié)論】（結(jié)果）數(shù)值檢驗(yàn)及結(jié)果分析對(duì)改進(jìn)的黃金

7、分割法，我們使用matlab2007進(jìn)行了數(shù)值試驗(yàn)選用了以下數(shù)學(xué)函數(shù)：檢驗(yàn)函數(shù)多項(xiàng)式函數(shù)：，其中a=0.5,1,1.5,L,9.5,10；b=1,2,L,10；c=?5,?4,L,5數(shù)值結(jié)果見(jiàn)表1；表1是多項(xiàng)式函數(shù)檢驗(yàn)結(jié)果，其中a,it,Value表示最優(yōu)解，迭代步數(shù)和最優(yōu)值。表中列出黃金分割法與算法2.1的結(jié)果，所有算法均使用如下終止條件：jd=10^(?4)，迭代區(qū)間為[?10,10]。6算法函數(shù)黃金分割法改進(jìn)你的黃金分割法citavalueitavalue1271.999982.6897e-10181.999952.18

8、857e-92271.999987.23451e-20431.999956.71866e-183271.999981.94587e-29671.999944.40785e-264271.999985.23381e-39921.999948.94081e-355271.9999