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

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

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

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

3、面介紹兩種利用函數(shù)的凸性優(yōu)化黃金分割的方法。利用凸函數(shù)的一階特征改進(jìn)算法。通過凸函數(shù)的一階特征，定理1.3.11[5]：設(shè)S?Rn為非空開凸集，f是定義在S上的可微函數(shù)，則f為凸函數(shù)的充分必要條件是：f(y)≥f(x)+?f(x)T(y?x),?x,y∈S（1）證明：必要性設(shè)f是凸函數(shù)，于是對所有α，0≤α≤1，有f(αy+(1?α)x≤αf(y)+(1?α)f(x)因此，對于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ù)。這個定理表明了根據(jù)局部導(dǎo)數(shù)的線性近似是函數(shù)的低估，即凸函數(shù)圖形位于圖形上任一點切線的上方。根據(jù)這個定理，所以函數(shù)的最小值一定在切線的上方。利用凸函數(shù)的一階特征以及已知的最小函數(shù)值就可以確定不確定區(qū)間。函數(shù)兩個端點處的切線和最小函

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

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

7、分割法，我們使用matlab2007進(jìn)行了數(shù)值試驗選用了以下數(shù)學(xué)函數(shù)：檢驗函數(shù)多項式函數(shù)：，其中a=0.5,1,1.5,L,9.5,10；b=1,2,L,10；c=?5,?4,L,5數(shù)值結(jié)果見表1；表1是多項式函數(shù)檢驗結(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