第四章無約束優(yōu)化方法(編輯修改稿)
2025-08-28 13:40 本頁面
【文章內(nèi)容簡介】 檢查鮑威爾條件 于是可知 鮑威爾條件兩式均不成立。第二環(huán)取基本方向組和起始 點(diǎn)為 沿 e2方向作一維搜索得 以 為起點(diǎn)沿 S1方向一維搜索得 構(gòu)成新生方向 沿 S2方向一維搜索得 檢查迭代終止條件 需再作第三環(huán)迭代計(jì)算。 根據(jù)具體情況來分析， S1， S2實(shí)際上為共軛方向，見下圖。 本題又是二次函數(shù)，有共軛方向的二次收斂性，上面結(jié)果就 是問題的最優(yōu)解?？梢灶A(yù)料，如果做第三環(huán)迭代，則一定各 一維搜索的步長為零，必有 故得最優(yōu)解 梯度法 優(yōu)化設(shè)計(jì)是追求目標(biāo)函數(shù)值最小，因此，自然可以設(shè)想從某點(diǎn)出發(fā)，其搜索方向取該點(diǎn)的負(fù)梯度方向，使函數(shù)值在該點(diǎn)附近下降最快。這種方法也稱為最速下降法。 一、基本原理 梯度法的迭代公式為： x(k+1)=x(k)?(k)g(k) 其中 g(k)是函數(shù) F(x)在迭代點(diǎn) x(k)處的梯度 ?f(x(k)) ， ?(k)一般采用一維搜索的最優(yōu)步長，即 f(x(k+1))=f(x(k)?(k)g(k))=min f(x(k)?(k)g(k))=min?(?) 據(jù)一元函數(shù)極值條件和多元復(fù)合函數(shù)求導(dǎo)公式，得 ?’ (?)= (? f(x(k)?(k)g(k)))T g(k) =0 即 (? f(x(k+1)))T g(k) =0 或 (g(k+1))Tg(k)=0 此式表明，相鄰的兩個迭代點(diǎn)的梯度是彼此正交的。也即在梯度的迭代過程中，相鄰的搜索方向相互垂直。梯度法向極小點(diǎn)的逼近路徑是鋸齒形路線，越接近極小點(diǎn)，鋸齒越細(xì)，前進(jìn)速度越慢。 這是因?yàn)?梯度 是函數(shù)的局部性質(zhì)， 從局部上看，在該點(diǎn) 附近函數(shù)的下降最快， 但從總體上看則走了 許多彎路，因此函數(shù) 值的下降并不快。 二、迭代終止條件 采用梯度準(zhǔn)則： || g(k) ||? ? 三、迭代步驟 （ 1）任選初始迭代點(diǎn) x(0)，選收斂精度 ? 。 （ 2）確定 x(k)點(diǎn)的梯度（開始 k=0) （ 3）判斷是否滿足終止條件 || g(k) ||? ?？ 若滿足輸出最優(yōu)解，結(jié)束計(jì)算。否則轉(zhuǎn)下步。 （ 4）從 x(k)點(diǎn)出發(fā)，沿 g(k)方向作一維搜索求最優(yōu)步長 ?(k)。得下一迭代點(diǎn) x(k+1)=x(k)?(k)g(k) ,令 k=k+1 返回步驟 (2)。 四、梯度法流程圖 入口 給定： x(0)， ? k=0 ||g(k)||? ? ？ x*=x(k) f*=f(x(k)) 出口 x(k)= x(0) 計(jì)算： g(k) k=k+1 沿 g(k)方向一維搜索， 求最優(yōu)步長 ?(k)。 x(k+1)= x(k) ?(k) g(k)/ ||g(k)|| N Y 例題 的最優(yōu)解。 已知初始點(diǎn) 迭代精度 ε= 解： 函數(shù)的梯度 第一次迭代： 以 為起點(diǎn)沿一 方向作一維搜索 得第一個迭代點(diǎn) 繼續(xù)第二 次迭代 到第五次迭代結(jié)束時(shí)，有 故迭代可終止，最優(yōu)解為 迭代數(shù)據(jù)表見課本表 共軛梯度法 共軛梯度法是共軛方向法的一種，因?yàn)樵摲椒ㄖ忻恳粋€共軛向量都是依賴于迭代點(diǎn)處的負(fù)梯度而構(gòu)造出來的，所以稱作共軛梯度法。 一、共軛梯度法的搜索方向 共軛梯度法的搜索方向采用梯度法基礎(chǔ)上的共軛方向，如圖所示，目標(biāo)函數(shù) F(x)在迭代點(diǎn) xk+1處的負(fù)梯度為 ? f(xk+1)，該方向與前 一搜索方向 Sk互為正交，在此 基礎(chǔ)上構(gòu)造一種具有較高收斂 速度的算法，該算法的搜索方 向要滿足以下兩個條件： （ 1）以 xk+1點(diǎn)出發(fā)的搜索方 向 Sk+1是 ? f(xk+1)與 Sk的線性 組合。即 xk x* xk+1 ? f(xk+1) Sk+1 Sk Sk+1 = ? f(xk+1) + ?kSk （ 2）以與為基底的子空間中，矢量與相共軛，即滿足 [ Sk+1]T G Sk = 0 二、 ?k的確定 確定方法自學(xué)，不作要求。記住 三、 共軛梯度法的算法 （ 1）選初始點(diǎn) x0和收斂精度 ?。 （ 2）令 k=0，計(jì)算 S0 = ? f(x0) 。 （ 3）沿 Sk方向進(jìn)行一維搜索求 ?(k)，得 x(k+1)=x(k)+?(k)S(k) （ 4）計(jì)算 ? f(xk+1) ，若 ||? f(xk+1)||? ? ，則終止迭代，取x*=xk+1；否則進(jìn)行下一步。 （ 5）檢查搜索次數(shù)，若 k=n，則令 x0=xk+1，轉(zhuǎn)（ 2），否則，進(jìn)行下一步。 （ 6）構(gòu)造新的共軛方向 Sk+1 = ? f(xk+1) + ?kSk 令 k=k+1，轉(zhuǎn)（ 3） 四、共軛梯度法流程圖 入口 k=0， 計(jì)算 ： ? f(x0) || ? f(xk+1) ||? ? ？ 出口 求 ?(k) ， x(k+1)= x(k) +?(k)S(k) 計(jì)算 ： ? f(xk+1) x*=xk+1 f(x*)=f(xk+1) Y N 給定： x(0)， ? k? n ？ x0=xk+1 N Y Sk+1 = ? f(xk+1) + ?kSk K=K+1 五、共軛梯度法的特點(diǎn) 共軛梯度法屬于解析法，其算法需求一階導(dǎo)數(shù)，所用公式及算法簡單，所需存儲量少。 該方法以正定二次函數(shù)的共軛方向理論為基礎(chǔ)，對二次型函數(shù)可以經(jīng)過有限步達(dá)到極小點(diǎn)，所以具有二次收斂性。但是對于非二次型函數(shù)，以及在實(shí)際計(jì)算中由于計(jì)算機(jī)舍入誤差的影響，雖然經(jīng)過 n次迭代，仍不能達(dá)到極小點(diǎn)，則通常以重置負(fù)梯度方向開始，搜索直至達(dá)到預(yù)定精度，其收斂速度也是較快的。 六、例題 牛頓法 牛頓法是求無約束最優(yōu)解的一種古典解析算法 。 牛頓法可以分為 原始牛頓法 和 阻尼牛頓法 兩種。
畢業(yè)設(shè)計(jì)相關(guān)推薦
鄂ICP備17016276號-1