【文章內(nèi)容簡(jiǎn)介】 12(a)中有則單峰區(qū)間為 對(duì)于圖 112(b)，有則單峰區(qū)間為 利用進(jìn)退法，一般總可找到單峰區(qū)間中的 3個(gè)點(diǎn)，即 2個(gè)端點(diǎn)和中間某一個(gè)點(diǎn)。對(duì)于后面要介紹的二次插值法中要利用 3個(gè)點(diǎn)的信息，其他方法只要利用 2個(gè)端點(diǎn)信息。 黃金分割法 黃金分割法也稱 ，是通過對(duì)黃金分割點(diǎn)函數(shù)值的計(jì)算和比較，將初始區(qū)間逐次進(jìn)行縮小，直到滿足給定的精度要求，即求得一維極小點(diǎn)的近似解 已知 的單峰區(qū)間為 為了縮小區(qū)間，在 內(nèi)按一定規(guī)則對(duì)稱地取 2個(gè)內(nèi)部點(diǎn) 和 ，并計(jì)算 和 可能有三種情況，如圖 113所示。圖 113黃金分割法圖 113(a)經(jīng)過一次函數(shù)比較，區(qū)間縮小一次為 [a， x2]。在新的區(qū)間內(nèi)，保留一個(gè)好點(diǎn) 和 ，下一次只需再按一定規(guī)則，在新區(qū)間內(nèi)找另一個(gè)與 對(duì)稱的點(diǎn) ，計(jì)算 ，與 比較，如此反復(fù)。 圖 113(b)淘汰 ，產(chǎn)生新的單峰區(qū)間 [x， b]。 圖 113(c)可歸納入上面任一種情況處理。黃金分割法的關(guān)鍵是如何不斷找出區(qū)間內(nèi)的 2個(gè)對(duì)稱點(diǎn)，保證極小點(diǎn)不會(huì)丟掉，且收斂快。 設(shè)初始區(qū)間長(zhǎng)度為 l，第一次區(qū)間縮短率為 ，則縮短后的區(qū)間長(zhǎng)度為 第二次區(qū)間縮短時(shí)，在區(qū)間 中取點(diǎn) ，經(jīng)比較后又得新區(qū)間 由對(duì)稱性可知，區(qū)間 的長(zhǎng)度為 ，則本次區(qū)間縮短率為 令這兩次縮短率相等，即 ，使方程 （ 126）解方程，得合理的根為 由此可知，黃金分割法的均勻縮短率為 ，即每經(jīng)過一次函數(shù)值比較，都是淘汰本次區(qū)間的 。根據(jù)上式，黃金分割法的取點(diǎn)規(guī)則是 （ 127）（ 128） 為了使最終區(qū)間收斂到給定收斂精度 內(nèi)，區(qū)間的縮短次數(shù) N必需滿足 （ 129）即 （ 130） 由于實(shí)際問題的需要和函數(shù)形態(tài)的不同，常常需要不同的收斂準(zhǔn)則確定最優(yōu)點(diǎn)。對(duì)于直接法，有以下幾種收斂準(zhǔn)則： （ 1） 區(qū)間絕對(duì)精度 ； （ 2）區(qū)間相對(duì)精度 ； （ 3） 函數(shù)值絕對(duì)精度 ； （ 4） 函數(shù)值相對(duì)精度 黃金分割法特點(diǎn)：（ 1） 不必要求 可微，只要利用函數(shù)值大小的比較，即可很快地找到 ； （ 2） 除了第一次縮小區(qū)間要計(jì)算兩個(gè)點(diǎn)及其函數(shù)值以外，其余每次只要計(jì)算一個(gè)點(diǎn)及其函數(shù)值； （ 3） 可靠性好。黃金分割法可應(yīng)用到染色等眾多過程中，例如在其它條件不變的情況下，優(yōu)選乳化劑的加入量或水的合適加入量等。 例 16 假設(shè)某廠為生產(chǎn)一種含有特殊香味得毛織物，現(xiàn)決定在原毛染色中加入某種香型材料，假設(shè)其參考添加量為 ％～ ％，現(xiàn)通過試驗(yàn)確定其最佳添加量。 解 按黃金分割法安排試驗(yàn)，先在含優(yōu)區(qū)間[%,%]的 0. 618處取值做第一試驗(yàn)點(diǎn)，則該試驗(yàn)得第一次試驗(yàn)點(diǎn)為 第二試驗(yàn)點(diǎn)為 比較 兩次試驗(yàn)效果，若 好于 ，則舍去不包括 點(diǎn)的以外部分，在留下部分再找出 點(diǎn)的對(duì)稱點(diǎn) ， ，上述試驗(yàn)點(diǎn)的過程如圖 114所示。圖 114第一、第二、第三試驗(yàn)點(diǎn)確定的示意圖比較第二次和第一次試驗(yàn)的結(jié)果，如果仍是第一次的試驗(yàn)效果好，則去掉 以外的部分。在留下的 至 區(qū)間內(nèi)繼續(xù)找出 的對(duì)稱點(diǎn) 作為第四試驗(yàn)點(diǎn)。如果 點(diǎn)比 點(diǎn)的試驗(yàn)效果好，則舍去 到 這一段，在留下的部分內(nèi)繼續(xù)找出 的對(duì)稱點(diǎn) ,為第五試驗(yàn)點(diǎn)，見圖 115。圖 115第四、第五試驗(yàn)點(diǎn)確定的示意圖按同樣的方法繼續(xù)下去，直到獲得滿意的試驗(yàn)效果為止。如果在上述試驗(yàn)中 的效果比 還好，并且比較滿意，則可確定香料的添加量為 ％是最優(yōu)添加量。 對(duì)分法1中心對(duì)分法中心對(duì)分法是利用目標(biāo)函數(shù)的一階導(dǎo)數(shù)來判別最優(yōu)點(diǎn)的存在區(qū)間，利用目標(biāo)函數(shù)的一階導(dǎo)數(shù)，取中心對(duì)分點(diǎn) ，由目標(biāo)函數(shù)的正負(fù)，淘汰區(qū)間的一半，如圖 116所示。 已知 ，而 故淘汰區(qū)間 [a， x1]，留下區(qū)間 [x1， b]，令 趨于 再取 ，求 ，直至 ，則有 圖 116中心對(duì)分法求解圖對(duì)分法特點(diǎn)：一階可微，且每計(jì)算一次 ，可淘汰區(qū)間的一半，收斂很快；當(dāng)用于無目標(biāo)函數(shù)式的優(yōu)化試驗(yàn)時(shí)，每試驗(yàn)一次要判別下一次試驗(yàn)應(yīng)淘汰的區(qū)間。 2兩點(diǎn)對(duì)分法已知極小點(diǎn)區(qū)間 [a， b]，在其中點(diǎn)左右取 2個(gè)對(duì)稱點(diǎn) x1和 x2（ 見圖 117） ，且有 圖 117兩點(diǎn)對(duì)分法求解圖（ 131）（ 132） 其中 為一個(gè)小的正值，應(yīng)使 有明顯差異。如圖情況， ，淘汰區(qū)間，留下區(qū)間 ，即 ，令 重復(fù)上述過程，直至 方法特點(diǎn)：不要求 一階可微，但每淘汰一次區(qū)間需計(jì)算 2個(gè)點(diǎn)及其目標(biāo)函數(shù)值；每次可淘汰本次區(qū)間的將近一半，其大小取決于 值?？捎糜谟心繕?biāo)函數(shù)的設(shè)計(jì)和無目標(biāo)函數(shù)的優(yōu)化試驗(yàn)中。例 17 ，已知初始極限值 區(qū)間 [a， b]＝ [， ]，收斂精度要求在初始區(qū)間的 10％以內(nèi)，即 解法一 用古典極值法 （ 即求導(dǎo)方法 ） 。由 解得 故 x*為極大點(diǎn) 解法二 用中心對(duì)分法。 已知 由 x1=(a+b)/2=， 可淘汰區(qū)間 [0,]，留下區(qū)間 [,1]。 計(jì)算 x2=(+)/2=， 故精確解 x*＝ ， f (x*)=。 解法三 用兩點(diǎn)對(duì)分法。 已知 L0=，取 δ＝ ，計(jì)算 x1和 x2因?yàn)?f2 f1，淘汰 [0,]，留下新區(qū)間[,]。 第二次計(jì)算點(diǎn)為： 因?yàn)?，淘?[, x3]，留下新區(qū)間 [x3,]。 第三次計(jì)算點(diǎn)為： 因?yàn)? ，淘汰 ，留下新區(qū)間 ，此時(shí)， 已接近要求精度。取最終區(qū)間的中點(diǎn)x*＝ (+)/2=大點(diǎn)， f(x*)=。 方法比較 ：解法一僅需計(jì)算一次導(dǎo)數(shù)，即可求得精確解。解法二計(jì)算了 2次導(dǎo)數(shù)，求得了精確解。解法三計(jì)算了 6次目標(biāo)函數(shù)，取最后區(qū)間的中點(diǎn)作為近似極大點(diǎn)，與精確解比較，尚有較大誤差?？梢娊夥ㄈ挠?jì)算次數(shù)多，但不要求可微。 二次插值法 二次插值法是多項(xiàng)式逼近法的一種，利用目標(biāo)函數(shù)在若干點(diǎn)的信息和函數(shù)值，構(gòu)成一個(gè)與目標(biāo)函數(shù)相接近的低次插值多項(xiàng)式，然后求該多項(xiàng)式的最優(yōu)解作為原函數(shù)的近似最優(yōu)解。隨著區(qū)間的逐次縮小，多項(xiàng)式的最優(yōu)點(diǎn)與原函數(shù)最優(yōu)點(diǎn)之間的距離逐漸縮小，直到滿足一定精度要求時(shí)終止迭代。 設(shè)目標(biāo)函數(shù) f(x)在三點(diǎn) 上的函數(shù)值分別為 ，二次插值多項(xiàng)式為 多項(xiàng)式在插值點(diǎn)的函數(shù)值應(yīng)與目標(biāo)函數(shù)的函數(shù)值相等，滿足： （ 133）求得 （ 134） 為求極小點(diǎn)，將 3個(gè)系數(shù)代入插值多項(xiàng)式，令一階導(dǎo)數(shù)為零，有（ 135） 將 （ 134） 中的 b、 c代入式 （ 135） （ 136）式中 由于初始區(qū)間較大，第一次構(gòu)造的多項(xiàng)式 極小點(diǎn) 的近似解是達(dá)不到預(yù)期精度的，需要通過幾次逼近計(jì)算來縮小區(qū)間，使構(gòu)造的 點(diǎn)列不斷接近目標(biāo)函數(shù)的極小點(diǎn)。區(qū)間縮小的原則如圖 118所示。 圖 118二次插值區(qū)間縮小的四種情況（ 1） ，以 為新區(qū)間，令 x x2不變； （ 2） ，以 為新區(qū)間，令 ， x3不變； （ 3） ，以 為新區(qū)間，令 ， x1不變； （ 4） ，以 為新區(qū)間，令 ， x x3不變。 二次插值法收斂準(zhǔn)則：（ 1） 相繼兩次的二次插值函數(shù)極小點(diǎn) 、 之間距離小于給定精度 時(shí)，即： 及（ 2） 及上述兩種形式實(shí)際上是絕對(duì)精度和相對(duì)精度。二次插值法特點(diǎn)：（ 1） 二次插值法只要求連續(xù)，不要求其一階可微。 （ 2） 收斂速度比黃金分割法快，但可靠性不如黃金分割法好，程序也較長(zhǎng)。 （ 3） 如 p(x)的相鄰兩個(gè)迭代點(diǎn)重合，則產(chǎn)生死循環(huán)。 167。 無約束最優(yōu)化方法和約束最優(yōu)化方法 無約束最優(yōu)化方法概述 1研究無約束優(yōu)化方法的意義對(duì)于一個(gè) n維目標(biāo)函數(shù)，如果在沒有任何限制條件下尋求它的極小點(diǎn)，稱無約束極小化問題或無約束優(yōu)化問題。數(shù)學(xué)上表達(dá)為 大量實(shí)際問題都是有約束的，研究無約束優(yōu)化方法的意義在于： （ 1） 一類功能很強(qiáng)、使用方便的有約束優(yōu)化方法，往往能將有約束問題轉(zhuǎn)化成無約束問題，易于采用無約束優(yōu)化方法求解。 （ 2） 有些問題在不很接近最優(yōu)解時(shí)可先作無約束問題求解，然后采用有約束方法求出最優(yōu)解。 （ 3） 有些實(shí)際問題本身是無約束的，或把有些約束問題經(jīng)過模型變換可以轉(zhuǎn)化為無約束問題求解。 （ 4） 對(duì)于多維無約束問題來說，古典極值理論中令一階導(dǎo)數(shù)為零，但要求二階可微，且要判斷 Hessian矩陣為正定才能求得極小點(diǎn)，這種方法有理論意義，但無實(shí)用價(jià)值。和一維問題一樣，若多元函數(shù) F(X)不可微，亦無法求解。但古典極值理論是無約束優(yōu)化方法發(fā)展的基礎(chǔ)。 2多維無約束優(yōu)化方法的分類目前已研究出很多種無約束優(yōu)化方法，它們的主要不同點(diǎn)在于構(gòu)造搜索方向上的差別。概括起來，可分為直接法和間接法兩大類，其詳細(xì)分類如表 11所示。 坐標(biāo)輪換法1方法概述坐標(biāo)輪換法的基本構(gòu)思是將一個(gè) n維優(yōu)化問題轉(zhuǎn)化為依次沿 n個(gè)坐標(biāo)方向反復(fù)進(jìn)行一維搜索問題。這種方法的實(shí)質(zhì)是把 n維問題的求優(yōu)過程轉(zhuǎn)化為對(duì)每個(gè)變量逐次進(jìn)行一維求優(yōu)的循環(huán)過程。每次一維搜索時(shí)，只允許個(gè)變量的一次改動(dòng)，其余(n1)個(gè)變量固定不變。故坐標(biāo)輪換法也常稱單變量法或變量交錯(cuò)法。 2迭代過程（ 1） 任選初始點(diǎn) ，搜索方向 （ 2） 以 為初始點(diǎn)，沿 e1作正向試探性移步，步長(zhǎng)取 若試探成功，沿此方向一維搜索；否則，沿坐標(biāo)的負(fù)方向試探。若正負(fù)方向試探均失敗，則迭代點(diǎn)不動(dòng)，轉(zhuǎn)入下一步。 （ 3） 以 為沿 e2方向作為一維搜索的新起點(diǎn)，按步驟 （ 2） 進(jìn)行，得點(diǎn) 。以此類推，進(jìn)行完一輪一維搜索后，得 （ 4） 以 作為第二輪的初始點(diǎn)，重復(fù)步驟 （ 2） 和 （ 3）， 得第二輪搜索的終點(diǎn) ，相繼進(jìn)行第三、第四輪等的搜索。 16