第三章無(wú)約束問(wèn)題的最優(yōu)化方法.pptx

1、第三章無(wú)約束問(wèn)題的最優(yōu)化方法13.1 引言一. 目的：求一組 n 維設(shè)計(jì)變量 X= x1, x2 ,x n T, 使目標(biāo)函數(shù)達(dá)到 min. f(x) XRn即求目標(biāo)函數(shù)的最優(yōu)解：最優(yōu)點(diǎn) x* 和最優(yōu)值 f(x*) 。二. 意義： 為有約束優(yōu)化方法的研究提供了策略思想、概念基礎(chǔ)和基本方法； 為有約束優(yōu)化問(wèn)題的間接解法提供了有效而方便的方法； 對(duì)于某些工程問(wèn)題，進(jìn)行分析后，便于提供解決的有效方法； 不可避免地還存在無(wú)約束優(yōu)化的設(shè)計(jì)問(wèn)題。23.1 引言三. 內(nèi)容：一維搜索： 求最優(yōu)步長(zhǎng)因子(k)多維（變量）優(yōu)化：確定搜索方向 S (k)黃金分割插值法 坐標(biāo)輪換法共軛方向法梯度法共軛梯度法牛頓法DFP

2、變尺度法 33.2 一維搜索方法一. 一維搜索：定義: 在第K次迭代時(shí)，從已知點(diǎn) X(k)出發(fā)，沿給定方向求最優(yōu)步長(zhǎng)因子(k)，使 f (X(k) + S(k) )達(dá)到最小值的過(guò)程，稱為一維搜索。方法：1. 解析法： f (x (k+1) ) = min. f (x (k) + S (k) ) = f (x (k) + (k) S ( k) ) 步驟: f(X(k) + S(k) ) 沿S(k) 方向x(k) 臺(tái)勞展開(kāi)； 取二次近似： 43.2 一維搜索方法對(duì)求導(dǎo)，令其為零。 2. 數(shù)值迭代法：直接法應(yīng)用區(qū)間消去原理： 分?jǐn)?shù)法、黃金分割法近似法利用多項(xiàng)式函數(shù)逼近（曲線擬合）原理： 二次插值法、

3、 三次插值法 一維搜索也稱直線搜索。這種方法不僅對(duì)于解決一維最優(yōu)化本身具有實(shí)際意義，而且也是解多維最優(yōu)化問(wèn)題的重要支柱。 求得最優(yōu)步長(zhǎng)因子：53.2 一維搜索方法單峰區(qū)間： 在區(qū)間 1，3 內(nèi)，函數(shù)只有一個(gè)峰值，則此區(qū)間為單峰區(qū)間。單峰區(qū)間內(nèi)，一定存在一點(diǎn)*，當(dāng)任意一點(diǎn)2*時(shí)，f(2)f(*)，說(shuō)明： 單峰區(qū)間內(nèi)，函數(shù)可以有不可微點(diǎn)，也可以是不連續(xù)函數(shù)；二. 搜索區(qū)間的確定：f (x)0130f (x)31f ()32*10當(dāng)2*時(shí)，仍有f (2 ) f(*) ，則*是最優(yōu)點(diǎn)，也即為最優(yōu)步長(zhǎng)因子(k)。2確定的搜索區(qū)間必定是一個(gè)含有最優(yōu)點(diǎn)*的單峰區(qū)間。62、確定初始單谷區(qū)間的進(jìn)退法基本思想：

4、對(duì)f(x)任選一個(gè)初始點(diǎn)a1及初始步長(zhǎng)h， 通過(guò)比較這兩點(diǎn)函數(shù)值的大小，確定第三點(diǎn)位置，比較這三點(diǎn)的函數(shù)值大小，確定是否為 “高低高” 形態(tài)。步驟：（1）選定初始點(diǎn)a, 初始步長(zhǎng)hh0，計(jì)算 y1f(a1)，y2f(a1h)。（2）比較y1和y2。 （a）如y1y2, 向右前進(jìn)；加大步長(zhǎng) h2 h ，轉(zhuǎn)（3）向前； （b）如y1y3, 加大步長(zhǎng) h2 h ，a1=a2, a2=a3,轉(zhuǎn)（3）繼續(xù)探測(cè)。 （b）如y2y3, 則初始區(qū)間得到： a=mina1,a3， b=maxa3,a1，函數(shù)最小值所在的區(qū)間為a， b 。8y1y3y2y2y1a3a2a2a1a1Oaa3h0h02h0y1y2a2

5、a3a1a2a1Oaa32h0h0h0y3y1y2y1y2y3a1a2 確定初始單谷區(qū)間進(jìn)退法示意圖9進(jìn)退法程序框圖 103.2 一維搜索方法3.一維搜索的區(qū)間消去方法： 基本原理： 搜索區(qū)間確定之后，采用區(qū)間消去法逐步縮短搜索區(qū) 間，從而找到極小點(diǎn)的數(shù)值近似解。在搜索區(qū)間內(nèi)a,b 任取兩點(diǎn)a1、b1，令f1f（a1）， f2f（b1）f(a1)f(b1)f(a1)f(b1)f(a1)f(b1)a1a1 a1 b1baabab b1b1(1)如f1f2, 則縮小的新區(qū)間為a1,b;(3)如f1=f2, 則縮小的新區(qū)間為a1,b1113.2 一維搜索方法 黃金分割法： 黃金分割法適用于a,b區(qū)間

6、上的任何單谷函數(shù)求極小值問(wèn)題。對(duì)函數(shù)除要求“單谷”外不作其他要求，甚至可以不連續(xù)。因此，這種方法的適應(yīng)面相當(dāng)廣。 黃金分割法也是建立在區(qū)間消去法原理基礎(chǔ)上的試探方法。 在搜索區(qū)間內(nèi)a,b適當(dāng)插入兩點(diǎn)，將區(qū)間分成三段；利用區(qū)間消去法，使搜索區(qū)間縮小，通過(guò)迭代計(jì)算，使搜索區(qū)間無(wú)限縮小，從而得到極小點(diǎn)的數(shù)值近似解。 黃金分割法還要求在保留下來(lái)的區(qū)間內(nèi)再插入一點(diǎn)所形成的區(qū)間新三段，與原來(lái)區(qū)間的三段具有相同的比例分布 。123.2 一維搜索方法黃金分割法要求插入兩點(diǎn)：13黃金分割法的搜索過(guò)程：1）給出初始搜索區(qū)間及收斂精度 ，將 賦以0.618。2）按坐標(biāo)點(diǎn)計(jì)算公式計(jì)算 , ；并計(jì)算其對(duì)應(yīng)的函數(shù)值。3）

7、根據(jù)區(qū)間消去法原理縮短搜索區(qū)間。為了能用原來(lái)的坐標(biāo)點(diǎn)計(jì)算公式，需進(jìn)行區(qū)間名稱的代換，并在保留區(qū)間中計(jì)算一個(gè)新的試驗(yàn)點(diǎn)及其函數(shù)值。如果 ，則新區(qū)間 令 記N0=0； 如果 ，則新區(qū)間 ，令 ，記N0=1； 4）檢查區(qū)間是否縮短到足夠小和函數(shù)值收斂到足夠精度，如果收斂條件滿足，則取最后兩試驗(yàn)點(diǎn)的平均值作為極小點(diǎn)的數(shù)值近似解。如果條件不滿足則轉(zhuǎn)向步驟5）。14f(a1)f(a2)f(a1)f(a2)a1(a) a1(a2) a2(b)abab a2(a1)a1a2如N0=0，則取如N0=1，則取5）產(chǎn)生新的插入點(diǎn)：轉(zhuǎn)向3）進(jìn)行新的區(qū)間縮小。15黃金分割法程序框圖例 ：用黃金分割法求函數(shù)f(x)=3x

8、3-4x+2的極小點(diǎn)，給定 x0=0, h=1, =0.2。16例 ：用黃金分割法求函數(shù)f(x)=3x3-4x+2的極小點(diǎn)，給定 x0=0, h=1, =0.2。解：1）確定初始區(qū)間x1=x0=0, f1=f(x1)=2x2=x0+h=0+1=1, f2=f(x2)=1由于f1f2, 應(yīng)加大步長(zhǎng)繼續(xù)向前探測(cè)。x3= x0+2h=0+2=2, f3=f(x3)=18由于f2f3,可知初始區(qū)間已經(jīng)找到，即a,b=x1,x2=0,22）用黃金分割法縮小區(qū)間 第一次縮小區(qū)間： x1=0+0.382X(2-0)=0.764, f1=0.282 x2=0+0.618 X(2-0)=1.236, f2=2.

9、72 f10.2 第二次縮小區(qū)間： 令 x2=x1=0.764, f2=f1=0.282 x1=0+0.382X(1.236-0)=0.472, f1=0.317 由于f1f2, 故新區(qū)間a,b=x1,b=0.472, 1.236因?yàn)?b-a=1.236-0.472=0.7640.2, 應(yīng)繼續(xù)縮小區(qū)間。173.2 一維搜索方法四.一維搜索的插值類方法1.牛頓法 設(shè)f(x)為一個(gè)連續(xù)可微的函數(shù)，則在x0附近，該函數(shù)應(yīng)該與一個(gè)二次函數(shù)接近，即可在點(diǎn)x0附近用一個(gè)二次函數(shù)(x)來(lái)逼近函數(shù)f(x) ，即：用二次函數(shù)的(x)極小點(diǎn)x1作為f(x)極小點(diǎn)的一個(gè)近似點(diǎn)。根據(jù)極值必要條件: 得到：依次繼續(xù)下去

10、，可得牛頓迭代公式：18 牛頓法的優(yōu)點(diǎn)是收斂速度快。缺點(diǎn)是要計(jì)算函數(shù)的一階和二階導(dǎo)數(shù)，因而增加了每次迭代的工作量。如果用數(shù)值微分計(jì)算函數(shù)的二階導(dǎo)數(shù)，其舍入誤差將嚴(yán)重影響牛頓法的收斂速度， f(x)的值越小，這個(gè)問(wèn)題就越嚴(yán)重。另外，牛頓法要求初始點(diǎn)選的比較好，也就是說(shuō)應(yīng)離極小點(diǎn)不太遠(yuǎn)，否則有可能使極小化序列發(fā)散或收斂到非極小點(diǎn)。193.2 一維搜索方法二次插值法. 基本原理：步驟：203.2 一維搜索方法 縮短區(qū)間若f(x)本身為二次函數(shù)，則在理論上按前式一次求值就可找到最優(yōu)點(diǎn) ；若f(x)為高于二次的函數(shù)或?yàn)槠渌瘮?shù) ,可采用區(qū)間消去法逐步縮小區(qū)間 。 根據(jù)xp* ，x2，f(xp* )和f(

11、x2)的相互關(guān)系，分4種情況進(jìn)行區(qū)間縮小。 在已有的四x1,x2,x3,xp* 中選擇新的三個(gè)點(diǎn)x1,x2,x3，再進(jìn)行二次插值。 213.2 一維搜索方法 方法評(píng)價(jià)：與黃金分割法相比，二次插值法充分利用函數(shù)值的信息；收斂快；調(diào)用函數(shù)次數(shù)少。二次插值法的程序框圖22例 ： 用二次插值法求函數(shù)f(x)=3x3-4x+2的極小點(diǎn)，給定 x0=0, =0.2。解： 1）確定初始區(qū)間初始區(qū)間a,b=0,2, 中間點(diǎn)x2=1。2）用二次插值法逼近極小點(diǎn)相鄰三點(diǎn)的函數(shù)值: x1=0, x2=1, x3=2; f1=2, f2=1, f3=18. 代入公式：xp*0.555, fp=0.292由于fpf2,

12、 xp * 0.2, 應(yīng)繼續(xù)迭代。在新區(qū)間，相鄰三點(diǎn)的函數(shù)值: x1=0, x2=0.555, x3=1; f1=2, f2=0.292, f3=1.xp*0.607, fp=0.243 由于fpx2, 新區(qū)間a,b=x2, b=0.555,1 |x2-xp * |=0.0520.2, 迭代終止。 xp*0.607, f*=0.243233.3 多維優(yōu)化算法無(wú)約束優(yōu)化問(wèn)題的概念和數(shù)學(xué)模型： 求n維設(shè)計(jì)變量x=x1，x2， ，xnT使目標(biāo)函數(shù)為minf（x），而對(duì)x沒(méi)有任何限制；如果存在x*，使minf（x）=f（x*），則稱x*為最優(yōu)點(diǎn)，f（x*）為最優(yōu)值。 數(shù)學(xué)模型: minF(x) x=x

13、1，x2， ，xnTRn 求上述問(wèn)題最優(yōu)解的方法，稱為無(wú)約束優(yōu)化方法。24 無(wú)約束優(yōu)化的地位： 1、有些實(shí)際問(wèn)題，其數(shù)學(xué)模型本身就是無(wú)約束優(yōu)化問(wèn)題，或者除了在非常接近極小點(diǎn)的情況下，都可以按無(wú)約束問(wèn)題來(lái)處理。 2、通過(guò)熟悉無(wú)約束優(yōu)化問(wèn)題的解法，可以為研究約束優(yōu)化問(wèn)題打下良好的基礎(chǔ)。 3、約束優(yōu)化問(wèn)題的求解往往可以通過(guò)一系列無(wú)約束優(yōu)化方法來(lái)實(shí)現(xiàn)。 所以，無(wú)約束優(yōu)化問(wèn)題的解法是優(yōu)化設(shè)計(jì)方法的基本組成部分，也是優(yōu)化方法的基礎(chǔ)。25無(wú)約束優(yōu)化方法數(shù)值計(jì)算方法的步驟： 1、選擇一個(gè)初始點(diǎn)x（0），這一點(diǎn)越靠近極小點(diǎn)x*越好。 2、若已經(jīng)取得某設(shè)計(jì)點(diǎn)x（k），并且該點(diǎn)不是近似極小點(diǎn)，則在x（k）點(diǎn)根據(jù)函數(shù)

14、f（x）的性質(zhì)，選擇一個(gè)方向S（k），并且沿此方向搜索函數(shù)值是下降的，稱下降方向。 3、當(dāng)搜索方向S（k）確定后，由 x（k） 點(diǎn)出發(fā)，沿S（k）方向進(jìn)行搜索， 定出步長(zhǎng)因子 （k） ， 得到新的設(shè)計(jì)點(diǎn) x（k+1）=x（k）+（k）S（k），并滿足f（x（k+1）f（x（k） 4、若x（k+1）滿足迭代計(jì)算終止條件， x（k+1）點(diǎn)作為x*；否則從該點(diǎn)出發(fā)，返回第二步繼續(xù)搜索迭代。26 無(wú)約束優(yōu)化數(shù)值計(jì)算方法的關(guān)鍵問(wèn)題： 無(wú)約束優(yōu)化數(shù)值計(jì)算方法采用的是搜索方法，其基本思想是從給定的初始點(diǎn)出發(fā)，沿某一個(gè)搜索方向進(jìn)行不斷的搜索，確定最佳步長(zhǎng)使函數(shù)值沿搜索方向下降最大，其迭代公式為 x（k+1）=

15、x（k）+（k）S（k） 各種無(wú)約束優(yōu)化方法的區(qū)別在于確定其搜索方向的S（k）的方法不同。所以，搜索方向的構(gòu)成問(wèn)題使無(wú)約束優(yōu)化問(wèn)題的關(guān)鍵。27 用直接法尋找極小點(diǎn)時(shí)，不必求函數(shù)的導(dǎo)數(shù)，只要計(jì)算目標(biāo)函數(shù)值。這類方法較適用于解決變量個(gè)數(shù)較少的（n 20）問(wèn)題，一般情況下比間接法效率低。 間接法除要計(jì)算目標(biāo)函數(shù)值外，還要計(jì)算目標(biāo)函數(shù)的梯度，有的還要計(jì)算其海賽矩陣。 （1）間接法：要使用導(dǎo)數(shù)，如梯度法、（阻尼）牛頓法、變尺度法、共軛梯度法等。 （2）直接法：不使用導(dǎo)數(shù)信息，如坐標(biāo)輪換法、鮑威爾法單純形法等。無(wú)約束優(yōu)化方法的分類： 無(wú)約束優(yōu)化方法的分類依據(jù)就是根據(jù)（k）和S（k）的確定方法而定的。 若根

16、據(jù)構(gòu)成搜索方向所使用的信息性質(zhì)的不同，可以分為兩類。 281 、 梯度法基本思想： 函數(shù)的負(fù)梯度方向是函數(shù)值在該點(diǎn)下降最快的方向。將n 維問(wèn)題轉(zhuǎn)化為一系列沿負(fù)梯度方向用一維搜索方法尋優(yōu)的問(wèn)題，利用負(fù)梯度作為搜索方向，故稱最速下降法或梯度法。 搜索方向s取該點(diǎn)的負(fù)梯度方向 (最速下降方向) ，使函數(shù)值在該點(diǎn)附近的范圍內(nèi)下降最快 。29 為了使目標(biāo)函數(shù)值沿搜索方向 能夠獲得最大的下降值，其步長(zhǎng)因子 應(yīng)取一維搜索的最佳步長(zhǎng)。即有 根據(jù)一元函數(shù)極值的必要條件和多元復(fù)合函數(shù)求導(dǎo)公式，得： 30 在最速下降法中，相鄰兩個(gè)迭代點(diǎn)上的函數(shù)梯度相互垂直。而搜索方向就是負(fù)梯度方向，因此相鄰兩個(gè)搜索方向互相垂直。這

17、就是說(shuō)在迭代點(diǎn)向函數(shù)極小點(diǎn)靠近的過(guò)程，走的是曲折的路線。形成“之”字形的鋸齒現(xiàn)象，而且越接近極小點(diǎn)鋸齒越細(xì)。 31方法特點(diǎn)： （1）初始點(diǎn)可任選，每次迭代計(jì)算量小，存儲(chǔ)量少，程序簡(jiǎn)短。即使從一個(gè)不好的初始點(diǎn)出發(fā)，開(kāi)始的幾步迭代，目標(biāo)函數(shù)值下降很快，然后慢慢逼近局部極小點(diǎn)。 （2）任意相鄰兩點(diǎn)的搜索方向是正交的，它的迭代路徑為繞道逼近極小點(diǎn)。當(dāng)?shù)c(diǎn)接近極小點(diǎn)時(shí)，步長(zhǎng)變得很小，越走越慢。 3233沿負(fù)梯度方向進(jìn)行一維搜索，有為一維搜索最佳步長(zhǎng)，應(yīng)滿足極值必要條件 例： 求目標(biāo)函數(shù) 的極小點(diǎn)。解：取初始點(diǎn) 則初始點(diǎn)處函數(shù)值及梯度分別為 算出一維搜索最佳步長(zhǎng) 34繼續(xù)作下去，經(jīng)10次迭代后，得到最優(yōu)

18、解 第一次迭代設(shè)計(jì)點(diǎn)位置和函數(shù)值 這個(gè)問(wèn)題的目標(biāo)函數(shù)的等值線為一簇橢圓，迭代點(diǎn)從起點(diǎn)出發(fā)走的是鋸齒形路線。1135將上例中目標(biāo)函數(shù) 引入變換其等值線由橢圓變成一簇同心圓。 仍從 即 出發(fā)進(jìn)行最速下降法尋優(yōu)。則函數(shù)f(X)變?yōu)椋簓1=x1, y2=5x2 經(jīng)變換后，只需一次迭代，就可找到最優(yōu)解。這是因?yàn)榻?jīng)過(guò)尺度變換等值線由橢圓變成圓。36梯度法特點(diǎn)：（1）理論明確，程序簡(jiǎn)單，對(duì)初始點(diǎn)要求不嚴(yán)格。（2）對(duì)一般函數(shù)而言，梯度法的收斂速度并不快，因?yàn)樽钏傧陆捣较騼H僅是指某點(diǎn)的一個(gè)局部性質(zhì)。（3）梯度法相鄰兩次搜索方向的正交性，決定了迭代全過(guò)程的搜索路線呈鋸齒狀，在遠(yuǎn)離極小點(diǎn)時(shí)逼近速度較快，而在接近極小

19、點(diǎn)時(shí)逼近速度較慢。（4）梯度法的收斂速度與目標(biāo)函數(shù)的性質(zhì)密切相關(guān)。對(duì)于等值線(面)為同心圓（球）的目標(biāo)函數(shù)，一次搜索即可達(dá)到極小點(diǎn)。372、牛頓法及其改進(jìn)設(shè) 為 的極小點(diǎn)，則 基本思想 ： 將 f(x) 在 x(k) 點(diǎn)作臺(tái)勞展開(kāi)，取二次函數(shù)式(x)作為近似函數(shù),以(x) 的極小值點(diǎn)作為 f(x) 的近似極小值點(diǎn)。牛頓法是求函數(shù)極值的最古老算法之一。 這就是多元函數(shù)求極值的牛頓法迭代公式。 38 對(duì)于二次函數(shù) ，海賽矩陣H是一個(gè)常矩陣，其中各元素均為常數(shù)。因此，無(wú)論從任何點(diǎn)出發(fā)，只需一步就可找到極小點(diǎn)。 例：求目標(biāo)函數(shù) 的極小點(diǎn)。解：取初始點(diǎn)經(jīng)過(guò)一次迭代即求得極小點(diǎn)39 從牛頓法迭代公式的推演

20、中可以看到，迭代點(diǎn)的位置是按照極值條件確定的，其中并未含有沿下降方向搜尋的概念。因此對(duì)于非二次函數(shù)，如果采用上述牛頓迭代公式，有時(shí)會(huì)使函數(shù)值上升 。阻尼牛頓法： 阻尼因子 ，沿牛頓方向進(jìn)行一維搜索的最佳步長(zhǎng)，由下式求得： 40 阻尼牛頓法程序框圖41方法特點(diǎn)： （1） 初始點(diǎn)應(yīng)選在X*附近，有一定難度； （2） 盡管每次迭代都不會(huì)是函數(shù)值上升，但不能保證每次下降 ； （3） 若迭代點(diǎn)的海賽矩陣為奇異，則無(wú)法求逆矩陣，不能構(gòu)造牛頓法方向； （4）不僅要計(jì)算梯度，還要求海賽矩陣及其逆矩陣，計(jì)算量和存儲(chǔ)量大。此外，對(duì)于二階不可微的F(X)也不適用。 雖然阻尼牛頓法有上述缺點(diǎn)，但在特定條件下它具有收斂

21、最快的優(yōu)點(diǎn)，并為其他的算法提供了思路和理論依據(jù)。42一般迭代式：梯度法：牛頓法：阻尼牛頓法：433、 變尺度法 DFP變尺度法首先有戴維頓（Davidon）與1959年提出，又于1963年由弗萊徹（Fletcher）和鮑維爾加以發(fā)展和完善，成為現(xiàn)代公認(rèn)的較好的算法之一。 DFP法是基于牛頓法的思想又作了重要改進(jìn)。這種算法僅用到梯度，不必計(jì)算海賽陣及其逆矩陣，但又能使搜索方向逐漸逼近牛頓方向，具有較快的收斂速度。 44 基本思想： 變尺度法的基本思想與牛頓法和梯度法有密切聯(lián)系。觀察梯度法和牛頓法的迭代公式 x(k+1)=x(k)-(k)g(k)和 xk+1 = xk - (k)G(xk)-1 g

22、(k) 分析比較這兩種方法可知： 梯度法的搜索方向?yàn)?g(k) ，只需計(jì)算函數(shù)的一階偏導(dǎo)數(shù)，計(jì)算量小，當(dāng)?shù)c(diǎn)遠(yuǎn)離最優(yōu)點(diǎn)時(shí)，函數(shù)值下降很快，但當(dāng)?shù)c(diǎn)接近最優(yōu)點(diǎn)時(shí)收斂速度極慢。 牛頓法的搜索方向?yàn)? G(xk)-1 g(k) ，不僅需要計(jì)算一階偏導(dǎo)數(shù)，而且要計(jì)算二階偏導(dǎo)數(shù)及其逆陣，計(jì)算量很大，但牛頓法具有二次收斂性，當(dāng)?shù)c(diǎn)接近最優(yōu)點(diǎn)時(shí)，收斂速度很快。 45 思考： 若迭代過(guò)程先用梯度法，后用牛頓法并避開(kāi)牛頓法的海賽矩陣的逆矩陣的煩瑣計(jì)算，則可以得到一種較好的優(yōu)化方法，這就是“變尺度法”產(chǎn)生的基本構(gòu)想。 為此，綜合梯度法和牛頓法的優(yōu)點(diǎn)，提出變尺度法的基本思想。 變尺度法的基本迭代公式寫(xiě)為下面的

23、形式： xk+1 = xk - kA(k) g(k) 式中的A(k)為構(gòu)造的n n階對(duì)稱矩陣，它是隨迭代點(diǎn)的位置的變化而變化的。 變尺度法的搜索方向- A(k) g(k) ，稱為擬牛頓方向。 若A(k) =I，上式為梯度法的迭代公式，若A(k) = G(xk)-1 ，上式為阻尼牛頓法的迭代公式。當(dāng)矩陣Ak 不斷地迭代而能很好地逼近A(k) = G(xk)-1 時(shí)，就可以不再需要計(jì)算二階導(dǎo)數(shù)。變尺度法的關(guān)鍵在于尺度矩陣Ak的產(chǎn)生 。46尺度矩陣的概念： 通過(guò)坐標(biāo)變換可以改變函數(shù)的偏心程度，我們也稱之為尺度變換。尺度變換能顯著地改進(jìn)幾乎所有極小化方法的收斂性質(zhì)。 如用梯度法求f(x)=x12+25

24、x22的極小值時(shí)，需要迭代10次才能到達(dá)極小點(diǎn)x*=0 0T。若作變換 y1=x1 y2=5x2則可以將函數(shù)的等值線由橢圓變?yōu)閳A，即(y)=y12+y22，從而消除了函數(shù)的偏心，用梯度法只需一次迭代即能求得極小點(diǎn)。47 用Q-1右乘等式兩邊，得 QTG=Q-1 再用Q左乘等式兩邊，得 QQTG=I 所以 QQT=G-1 這說(shuō)明二次函數(shù)矩陣G的逆陣，可以通過(guò)尺度變換矩陣Q求得。 QQT實(shí)際上是在空間內(nèi)測(cè)量距離大小的一種度量，稱為尺度矩陣，記作A，即 A= QQT 對(duì)于一般二次函數(shù) 為減低函數(shù)二次項(xiàng)的偏心程度，進(jìn)行尺度變換 xQx則在新的坐標(biāo)系中，函數(shù)的二次項(xiàng)變?yōu)?若矩陣是正定的，則總存在矩陣Q使

25、 QTGQ=I將函數(shù)的偏心變?yōu)榱恪?8 尺度變換矩陣的建立： 根據(jù)變尺度法的基本原理，需要構(gòu)造一個(gè)變尺度矩陣序列Ak來(lái)逼近海賽逆矩陣序列Gk-1，每迭代一次，尺度改變一次。 從初始矩陣A0=I(單位矩陣)開(kāi)始，通過(guò)對(duì)公式 中修正矩陣Ak 的不斷修正，在迭代中逐步逼近于Gk-1. 因此，一旦達(dá)到最優(yōu)點(diǎn)附近，就可望達(dá)到牛頓法的收斂速度。 49 尺度變換矩陣的建立： 根據(jù)變尺度法的基本原理，需要構(gòu)造一個(gè)變尺度矩陣序列Ak來(lái)逼近海賽逆矩陣序列Gk-1，每迭代一次，尺度改變一次。 為了建立變尺度矩陣Ak ，必須對(duì)其附加某些條件。 1、為保證迭代公式的下降性質(zhì)，要求Ak中的每一個(gè)矩陣都是對(duì)稱正定的。因?yàn)槿?/p>

26、要求搜索方向Sk= - Akgk 為下降方向，即要求gkT Sk 0，也就是 -gkT Akgk 0 ，即Ak應(yīng)為對(duì)稱正定。 2、要求Ak之間的迭代具有簡(jiǎn)單的形式，顯然Ak+1= Ak+ Ak 為最簡(jiǎn)單的形式，其中Ak為校正矩陣。 3、要求必須滿足擬牛頓條件。Ak+1 gk= xk其中： gk= gk+1-gk xk= xk+1-xk50一般步驟： 1、選定初始點(diǎn)和收斂精度； 2、計(jì)算初始點(diǎn)處的梯度，選取初始對(duì)稱正定矩陣A0，置k=0。 3、計(jì)算搜索方向Sk= - Akgk 4、沿Sk方向一維搜索，計(jì)算gk+1、 gk 、 xk 。 5、判斷是否滿足終止準(zhǔn)則，若滿足輸出最優(yōu)解，否則轉(zhuǎn)6。 6、

27、當(dāng)?shù)鷑次還未找到極小點(diǎn)，重置Ak為單位矩陣，并以當(dāng)前點(diǎn)為初始點(diǎn)返回2，否則轉(zhuǎn)7。 7、計(jì)算Ak+1= Ak+ Ak ，置k=k+1返回3。51 DFP算法由于舍入誤差和一維搜索的不精確，有可能導(dǎo)致Ak奇異，而使數(shù)值穩(wěn)定性方面不夠理想。所以1970年提出更穩(wěn)定的算法，稱為BFGS算法，其校正公式為5253方法評(píng)價(jià)： DEF變尺度法以逐次逼近的方法實(shí)現(xiàn) H-1 的計(jì)算，當(dāng)目標(biāo)函數(shù)的一階導(dǎo)數(shù)易求時(shí)，以一階代替二階導(dǎo)數(shù)的計(jì)算是有效的方法。 算法的第一步是梯度法，最速下降；接近 x* 時(shí)，又采用二次收斂的共軛方向，總的收斂速度較快。 H(k) 近似代表 x(k)點(diǎn)的二階導(dǎo)數(shù)，當(dāng)其為零時(shí)，可判斷 x(k

28、)為鞍點(diǎn)。 H(k) 的計(jì)算較復(fù)雜，存儲(chǔ)量較大。 算法穩(wěn)定性較差，由于計(jì)算機(jī)有舍入誤差，容易使 H (k) 的正定性破壞，趨于奇異。 54例： 用DFP算法求下列問(wèn)題的極值：解： 1）取初始點(diǎn) ，為了按DFP法構(gòu)造第一次搜尋方向d0，需計(jì)算初始點(diǎn)處的梯度取初始變尺度矩陣為單位矩陣A0=I，則第一次搜尋方向?yàn)?55沿d0方向進(jìn)行一維搜索，得為一維搜索最佳步長(zhǎng)，應(yīng)滿足得:,2）再按DFP法構(gòu)造點(diǎn)x1處的搜尋方向d1，需計(jì)算56代入校正公式=57=第二次搜尋方向?yàn)?再沿d1進(jìn)行一維搜索，得58為一維搜索最佳步長(zhǎng)，應(yīng)滿足,得3）判斷x2是否為極值點(diǎn)梯度: 海賽矩陣 : 梯度為零向量,海賽矩陣正定?？梢?jiàn)

29、點(diǎn)滿足極值充要條件，因此為極小點(diǎn)。594、 共軛方向法 1.共軛方向： 設(shè)G為nn階實(shí)對(duì)稱正定矩陣，如果有兩個(gè)n維向量d0和d1滿足 ，則稱向量d0與d1 關(guān)于矩陣G共軛。當(dāng)G為單位矩陣時(shí)，假設(shè)目標(biāo)函數(shù)f(x) 在極值點(diǎn)附近的二次近似函數(shù)為對(duì)二維情況：任選取初始點(diǎn)x0沿某個(gè)下降方向d0作一維搜索，得x160 因?yàn)?是沿d0方向搜索的最佳步長(zhǎng)，即在點(diǎn)x1處函數(shù)f（x）沿方向d0的方向?qū)?shù)為零?？紤]到點(diǎn)x1處方向?qū)?shù)與梯度之間的關(guān)系，故有 如果按最速下降法，選擇負(fù)梯度方向 為搜索方向，則將發(fā)生鋸齒現(xiàn)象 。 取下一次的迭代搜索方向d1直指極小點(diǎn)x*。0d0 x0 x1x*111d1d161 如果能夠

30、選定這樣的搜索方向，那么對(duì)于二元二次函數(shù)只需順次進(jìn)行d0、d1兩次直線搜索就可以求到極小點(diǎn)x* ，即有那么這樣的d1方向應(yīng)該滿足什么條件呢 ?對(duì)于前述的二次函數(shù):當(dāng) 時(shí)，x*是f(x)極小點(diǎn)，應(yīng)滿足極值必要條件，故有將等式兩邊同時(shí)左乘 得：有62 就是使d1直指極小點(diǎn)x* ， d1所必須滿足的條件 。 兩個(gè)向量d0和d1稱為G的共軛向量，或稱d0和d1對(duì)G是共軛方向。 共軛方向的性質(zhì)：性質(zhì)1 若非零向量系d0,d1,d2,dm-1是對(duì)G共軛，則這m個(gè)向量是線性無(wú)關(guān)的。性質(zhì)2 在n維空間中互相共軛的非零向量的個(gè)數(shù)不超過(guò)n。 性質(zhì)3 從任意初始點(diǎn)出發(fā)，順次沿n個(gè)G的共軛方向d0,d1, d2,進(jìn)行

31、一維搜索，最多經(jīng)過(guò)n次迭代就可以找到的二次函數(shù)f(x)極小點(diǎn)。 63關(guān)鍵：新的共軛方向確定？64 在無(wú)約束方法中許多算法都是以共軛方向作為搜索方向，它們具有許多特點(diǎn)。根據(jù)構(gòu)造共軛方向的原理不同，可以形成不同的共軛方向法。 65共軛梯度法： 共軛梯度法是共軛方向法中的一種，該方法中每一個(gè)共軛向量都是依賴于迭代點(diǎn)處的負(fù)梯度而構(gòu)造出來(lái)。 從xk出發(fā)，沿負(fù)梯度方向作一維搜索: 設(shè)與dk共軛的下一個(gè)方向dk+1由dk和點(diǎn)xk+1的負(fù)梯度的線形組合構(gòu)成，即：共軛條件：66則：解得：令為函數(shù)的泰勒二次展開(kāi)式則上兩式相減，并代入67將式與式兩邊相乘，并應(yīng)用共軛條件得：因此68算法步驟：69算法特點(diǎn)： 共軛梯度

32、法屬于解析法，其算法需求一階導(dǎo)數(shù)，所用公式及算法簡(jiǎn)單，所需存儲(chǔ)量少。該方法以正定二次函數(shù)的共軛方向理論為基礎(chǔ)，對(duì)二次型函數(shù)可以經(jīng)過(guò)有限步達(dá)到極小點(diǎn)，所以具有二次收斂性。但是對(duì)于非二次型函數(shù)，以及在實(shí)際計(jì)算中由于計(jì)算機(jī)舍入誤差的影響，雖然經(jīng)過(guò)n次迭代，仍不能達(dá)到極小點(diǎn)，則通常以重置負(fù)梯度方向開(kāi)始，搜索直至達(dá)到預(yù)定精度，其收斂速度也是較快的。70，已知初始點(diǎn)1,1T例： 求下列問(wèn)題的極值解： 1）第一次沿負(fù)梯度方向搜尋 計(jì)算初始點(diǎn)處的梯度為一維搜索最佳步長(zhǎng)，應(yīng)滿足迭代精度 。 得:712）第二次迭代：代入目標(biāo)函數(shù)由得從而有：因收斂。725、 坐標(biāo)輪換法 坐標(biāo)輪換法屬于直接法，既可以用于無(wú)約束優(yōu)化問(wèn)

33、題的求解，又可以經(jīng)過(guò)適當(dāng)處理用于約束優(yōu)化問(wèn)題求解。 坐標(biāo)輪換法是每次搜索只允許一個(gè)變量變化，其余變量保持不變，即沿坐標(biāo)方向輪流進(jìn)行搜索的尋優(yōu)方法。它把多變量的優(yōu)化問(wèn)題輪流地轉(zhuǎn)化成單變量（其余變量視為常量）的優(yōu)化問(wèn)題，因此又稱這種方法為變量輪換法。此種方法只需目標(biāo)函數(shù)的數(shù)值信息而不需要目標(biāo)函數(shù)的導(dǎo)數(shù)。73基本思想：搜索方向與步長(zhǎng)： 每次以一個(gè)變量坐標(biāo)軸作為搜索方向，將 n維的優(yōu)化問(wèn)題轉(zhuǎn)化為一維搜索問(wèn)題。例，第 k輪迭代的第 i 次搜索，是固定除 xi外的 n-1 個(gè)變量，沿 xi 變量坐標(biāo)軸作一維搜索，求得極值點(diǎn) xi(k) n 次搜索后獲得極值點(diǎn)序列 x1(k), x2(k）, xn(k)，若

34、未收斂，則開(kāi)始第 k+1 次迭代，直至收斂到最優(yōu)點(diǎn) x*。 74終止準(zhǔn)則： 可以采用點(diǎn)距準(zhǔn)則或者其它準(zhǔn)則。注意： 若采用點(diǎn)距準(zhǔn)則或函數(shù)值準(zhǔn)則，其中采用的點(diǎn)應(yīng)該是一輪迭代的始點(diǎn)和終點(diǎn)，而不是某搜索方向的前后迭代點(diǎn)。75流程圖:入口給定：x0，K=1i=1Xik=x0沿ei方向一維搜索求ixik=xi-1k+ ikeix=xk f=f(x)i=n?|xnk-x0k|?x*=xf*=f(x*)出口i=i+1x0=x0kk=k+1NYNY76方法評(píng)價(jià)： 方法簡(jiǎn)單，容易實(shí)現(xiàn)。 當(dāng)維數(shù)增加時(shí)，效率明顯下降。 收斂慢，以振蕩方式逼近最優(yōu)點(diǎn)。 受目標(biāo)函數(shù)的性態(tài)影響很大。 如圖 a) 所示，二次就收斂到極值點(diǎn)；

35、 如圖 b) 所示，多次迭代后逼近極值點(diǎn)； 如圖 c) 所示，目標(biāo)函數(shù)等值線出現(xiàn)山脊（或稱陡谷），若搜索到 A 點(diǎn)，再沿兩個(gè)坐標(biāo)軸，以t0步長(zhǎng)測(cè)試，目標(biāo)函數(shù)值均上升，計(jì)算機(jī)判斷 A 點(diǎn)為最優(yōu)點(diǎn)。事實(shí)上發(fā)生錯(cuò)誤。776、 鮑威爾方法 鮑威爾法是以共軛方向?yàn)榛A(chǔ)的收斂較快的直接法之一，是一種十分有效的算法。 1964年，鮑維爾提出這種算法，其基本思想是直接利用迭代點(diǎn)的目標(biāo)函數(shù)值來(lái)構(gòu)造共軛方向，然后從任一初始點(diǎn)開(kāi)始，逐次沿共軛方向作一維搜索求極小點(diǎn)。并在以后的實(shí)踐中進(jìn)行了改進(jìn)。 78對(duì)函數(shù)：基本思想：在不用導(dǎo)數(shù)的前提下，在迭代中逐次構(gòu)造G的共軛方向。 共軛方向的生成：jjkkkdddjggk+1xx

36、k+1 設(shè)xk, xk+1為從不同點(diǎn)出發(fā)，沿同一方向dj進(jìn)行一維搜索而到的兩個(gè)極小點(diǎn)。 這種方法是在研究具有正定矩陣G的二次函數(shù)的極小化問(wèn)題時(shí)形成的。79 梯度和等值面相垂直的性質(zhì), dj和 xk, xk+1兩點(diǎn)處的梯度gk,gk+1之間存在關(guān)系:另一方面，對(duì)于上述二次函數(shù)，其xk, xk+1兩點(diǎn)處的梯度可表示為:因而有取 這說(shuō)明只要沿dj方向分別對(duì)函數(shù)作兩次一維搜索，得到兩個(gè)極小點(diǎn)xk和xk+1 ，那么這兩點(diǎn)的連線所給出的方向dk就是與dj一起對(duì)G共軛的方向。80算法步驟：（二維情況為例）81 方法的基本迭代格式包括共軛方向產(chǎn)生和方向替換兩主要步驟。 把二維情況的基本算法擴(kuò)展到n維，則鮑威爾

37、基本算法的要點(diǎn)是： 在每一輪迭代中總有一個(gè)始點(diǎn)（第一輪的始點(diǎn)是任選的初始點(diǎn)）和n個(gè)線性獨(dú)立的搜索方向。從始點(diǎn)出發(fā)順次沿n個(gè)方向作一維搜索得一終點(diǎn)，由始點(diǎn)和終點(diǎn)決定了一個(gè)新的搜索方向。 用這個(gè)方向替換原來(lái)n個(gè)方向中的一個(gè)，于是形成新的搜索方向組。替換的原則是去掉原方向組的第一個(gè)方向而將新方向排在原方向的最后。 此外規(guī)定，從這一輪的搜索終點(diǎn)出發(fā)沿新的搜索方向作一維搜索而得到的極小點(diǎn)，作為下一輪迭代的始點(diǎn)。這樣就形成算法的循環(huán)。 82 鮑威爾基本算法的缺陷： 可能在某一環(huán)迭代中出現(xiàn)基本方向組為線性相關(guān)的矢量系的情況。 如第k環(huán)中，產(chǎn)生新的方向： Sk=xnk-x0k=1kS1k+ 2kS2k + +

38、 nkSnk 式中， S1k、S2k 、 、 Snk為第k環(huán)基本方向組矢量， 1k 、 2k 、 、 nk為個(gè)方向的最優(yōu)步長(zhǎng)。 若在第k環(huán)的優(yōu)化搜索過(guò)程中出現(xiàn)1k =0，則方向Sk表示為S2k 、 S3k 、 、 Snk的線性組合，以后的各次搜索將在降維的空間進(jìn)行，無(wú)法得到n維空間的函數(shù)極小值，計(jì)算將失敗。83 如圖所示為一個(gè)三維優(yōu)化問(wèn)題的示例，設(shè)第一環(huán)中1 =0 ，則新生方向與e2 、e3共面，隨后的各環(huán)方向組中，各矢量必在該平面內(nèi)，使搜索局限于二維空間，不能得到最優(yōu)解。鮑威爾基本算法的退化x1x2x31=01e23e3S184 鮑威爾修正算法： 在某環(huán)已經(jīng)取得的n+1各方向中，選取n個(gè)線性無(wú)關(guān)的并且共軛程度盡可能高的方向作為下一環(huán)的基本方向組。