機(jī)械優(yōu)化設(shè)計(jì)無(wú)約束方法2

機(jī)械優(yōu)化設(shè)計(jì)無(wú)約束方法演示文稿當(dāng)前1頁(yè)，總共94頁(yè)。（優(yōu)選）機(jī)械優(yōu)化設(shè)計(jì)無(wú)約束方法當(dāng)前2頁(yè)，總共94頁(yè)。第1章所列舉的機(jī)械優(yōu)化設(shè)計(jì)問(wèn)題，都是在一定的限制條件下追求某一指標(biāo)為最小，它們都屬于約束優(yōu)化問(wèn)題。工程問(wèn)題大都如此。

為什么要研究無(wú)約束優(yōu)化問(wèn)題?(1)有些實(shí)際問(wèn)題，其數(shù)學(xué)模型本身就是一個(gè)無(wú)約束優(yōu)化問(wèn)題。

(2)通過(guò)熟悉它的解法可以為研究約束優(yōu)化問(wèn)題打下良好的基礎(chǔ)。

(3)約束優(yōu)化問(wèn)題的求解可以通過(guò)一系列無(wú)約束優(yōu)化方法來(lái)達(dá)到。所以無(wú)約束優(yōu)化問(wèn)題的解法是優(yōu)化設(shè)計(jì)方法的基本組成部分，也是優(yōu)化方法的基礎(chǔ)。當(dāng)前3頁(yè)，總共94頁(yè)。（4）對(duì)于多維無(wú)約束問(wèn)題來(lái)說(shuō)，古典極值理論中令一階導(dǎo)數(shù)為零，但要求二階可微，且要判斷海賽矩陣為正定才能求得極小點(diǎn)，這種方法有理論意義，但在實(shí)際應(yīng)用中受到限制。和一維問(wèn)題一樣，若多元函數(shù)F(X)不可微，亦無(wú)法求解。但古典極值理論是無(wú)約束優(yōu)化方法發(fā)展的基礎(chǔ)。當(dāng)前4頁(yè)，總共94頁(yè)。一）無(wú)約束優(yōu)化問(wèn)題描述§4-1概述

若F(X)存在一階導(dǎo)數(shù)，則可按照如前所述的極值條件來(lái)確定其極值點(diǎn)可能的位置(稱為駐點(diǎn))。即求方程

的解。也就是求X，使其滿足特點(diǎn)：1.n個(gè)未知量n個(gè)方程的方程組，一般是非線性的2.求解該方程組與求無(wú)約束極值一樣困難，甚至更困難。當(dāng)前5頁(yè)，總共94頁(yè)。二）無(wú)約束優(yōu)化問(wèn)題求解概述

若用數(shù)值計(jì)算方法求解問(wèn)題4-1，按照尋優(yōu)思路不同，可分為：搜索類方法和單純形類方法。1.若給定方向Sk，多維無(wú)約束優(yōu)化問(wèn)題一維優(yōu)化設(shè)計(jì)問(wèn)題2.若未給定方向Sk，不同搜索類無(wú)約束優(yōu)化方法的區(qū)別在于確定其搜索方向Sk的方法不同爬山類方法。搜索方向的構(gòu)成問(wèn)題是無(wú)約束優(yōu)化方法的關(guān)鍵

搜索類基本思想是從某一給定的初始點(diǎn)X0開(kāi)始，沿給定的搜索方向S0進(jìn)行搜索，確定步長(zhǎng)a0使函數(shù)值沿S0下降最大(或達(dá)到給定的值)。其迭代格式如下：當(dāng)前6頁(yè)，總共94頁(yè)。開(kāi)始給定x0和S0以及ε，k=1最小化F(Xk+akSk)結(jié)束收斂？形成新Sk，k=k+1爬山類方法的尋優(yōu)思想當(dāng)前7頁(yè)，總共94頁(yè)。步長(zhǎng)和方向的形成和確定方法不同就派生出不同的n維無(wú)約束優(yōu)化方法，按照是否用到函數(shù)的導(dǎo)數(shù)三）求解方法分類1.直接法(不用導(dǎo)數(shù)的信息)2.間接法(用到導(dǎo)數(shù)的信息)坐標(biāo)輪換法單形替換法鮑威爾(Powell)最速下降法共軛梯度法牛頓法當(dāng)前8頁(yè)，總共94頁(yè)?！?-2最速下降法(梯度法)一）梯度方向*可取最優(yōu)步長(zhǎng)或下降步長(zhǎng)二）基本思想

梯度方向是目標(biāo)函數(shù)上升最快的方向，負(fù)梯度方向則是最速下降方向；2）迭代公式1）沿負(fù)梯度方向搜索：三）終止判別條件當(dāng)前9頁(yè)，總共94頁(yè)。為了使目標(biāo)函數(shù)值沿搜索方向能夠獲得最大的下降值，其步長(zhǎng)因子應(yīng)取一維搜索的最佳步長(zhǎng)。即有根據(jù)一元函數(shù)極值的必要條件和多元復(fù)合函數(shù)求導(dǎo)公式，得當(dāng)前10頁(yè)，總共94頁(yè)。在最速下降法中，相鄰兩個(gè)迭代點(diǎn)上的函數(shù)梯度相互垂直。而搜索方向就是負(fù)梯度方向，因此相鄰兩個(gè)搜索方向互相垂直。這就是說(shuō)在迭代點(diǎn)向函數(shù)極小點(diǎn)靠近的過(guò)程，走的是曲折的路線。形成“之”字形的鋸齒現(xiàn)象，而且越接近極小點(diǎn)鋸齒越細(xì)。

最速下降法的搜索路徑當(dāng)前11頁(yè)，總共94頁(yè)。當(dāng)前12頁(yè)，總共94頁(yè)。給定

X0

，εK=0，X（K）=X0K=K+1X(k)=X△X*=X（K）F*=F（X*）結(jié)束NY計(jì)算

從

出發(fā)，沿

搜索得*“最速下降性”只是迭代點(diǎn)鄰域的局部性質(zhì)。從全局看，并非最速下降方向。四.迭代步驟當(dāng)前13頁(yè)，總共94頁(yè)。特點(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)變得很小，越走越慢。當(dāng)前14頁(yè)，總共94頁(yè)。4.例4-1

解：沿負(fù)梯度方向進(jìn)行一維搜索，有a0為一維搜索最佳步長(zhǎng)，應(yīng)滿足極值必要條件

取初始點(diǎn)X0=[2，2]T，則初始點(diǎn)處函數(shù)值及梯度分別為當(dāng)前15頁(yè)，總共94頁(yè)。及第一次迭代設(shè)計(jì)點(diǎn)位置和函數(shù)值完成了最速下降法的第一輪迭代。經(jīng)10次迭代后，得到最優(yōu)解

從而得到一維搜索的最佳步長(zhǎng)為當(dāng)前16頁(yè)，總共94頁(yè)。

若引入變換，令

這個(gè)問(wèn)題的目標(biāo)函數(shù)F(X)的等值線為一簇橢圓，迭代點(diǎn)從X0走的是一段鋸齒形路線，如圖所示

則函數(shù)F(x1,x2)變?yōu)?/p>

其等值線就從橢圓族變?yōu)閳A族。仍從X0=[2，2]T，即Y0=[2，10]T出發(fā)進(jìn)行最速下降法尋優(yōu)。此時(shí)有當(dāng)前17頁(yè)，總共94頁(yè)。沿負(fù)梯度方向進(jìn)行一維搜索，有a’0為一維搜索最佳步長(zhǎng)，應(yīng)滿足極值必要條件當(dāng)前18頁(yè)，總共94頁(yè)。從而得出第一次迭代設(shè)計(jì)點(diǎn)位置和函數(shù)值可見(jiàn)經(jīng)過(guò)坐標(biāo)變換后，只需經(jīng)1次迭代后，得到最優(yōu)解

從而得到一維搜索的最佳步長(zhǎng)為當(dāng)前19頁(yè)，總共94頁(yè)。M是f(x)的海賽矩陣最大特征值的上界當(dāng)相鄰兩個(gè)迭代點(diǎn)之間滿足上述關(guān)系時(shí)，我們稱相應(yīng)的迭代方法具有線性收斂速度的迭代法。

二次型函數(shù)的對(duì)角形矩陣刻畫(huà)了橢圓長(zhǎng)短軸，表示度量的矩陣或者是表示尺度的矩陣。最速下降法的收斂速度和變量的尺度關(guān)系很大。最速下降法收斂速度的估計(jì)式m是f(x)的海賽矩陣最小特征值的下界當(dāng)前20頁(yè)，總共94頁(yè)。5.方法評(píng)價(jià)：迭代過(guò)程簡(jiǎn)單，對(duì)初始點(diǎn)的選擇，要求不高。梯度方向目標(biāo)函數(shù)值下降迅速只是個(gè)局部性質(zhì)，從整體來(lái)看，不一定是收斂最快的方向。以二維二次函數(shù)為例，相鄰兩次的搜索方向是正交的，所以搜索路徑是曲折的鋸齒形的；對(duì)于高維的非線性函數(shù)，接近極值點(diǎn)處，容易陷入穩(wěn)定的鋸齒形搜索路徑。梯度法的收斂速度與目標(biāo)函數(shù)的性質(zhì)密切相關(guān)。對(duì)于等值線(面)為同心圓（球）的目標(biāo)函數(shù)，一次搜索即可達(dá)到極小點(diǎn)。當(dāng)前21頁(yè)，總共94頁(yè)。§4-3牛頓法（牛頓方向）1）迭代方向：**最速下降法只利用了函數(shù)一階導(dǎo)數(shù)的信息，在極值點(diǎn)附近收斂較慢，從函數(shù)等值線特性分析可知，在極值點(diǎn)附近，函數(shù)具有二次函數(shù)的特性，如果利用二次導(dǎo)數(shù)的信息，在極值點(diǎn)附近進(jìn)行尋優(yōu)，應(yīng)該具有較快的收斂速度？一.原始牛頓法一）基本思路用目標(biāo)函數(shù)的近似二次函數(shù)的極小點(diǎn)來(lái)近似原函數(shù)的極小點(diǎn)；二）原始牛頓法的迭代公式原函數(shù):近似二次函數(shù):令2）步長(zhǎng)因子：當(dāng)前22頁(yè)，總共94頁(yè)。對(duì)于二次函數(shù)，f（x）的泰勒展開(kāi)式不是近似的，而是精確的。海賽矩陣是一個(gè)常矩陣，其中各元素為常數(shù)。因此，無(wú)論從任何點(diǎn)出發(fā)，只需一步就可找到極小點(diǎn)。二次收斂：若某一迭代方法能使二次函數(shù)在有限次迭代內(nèi)達(dá)到極小點(diǎn)。牛頓方法是二次收斂的當(dāng)前23頁(yè)，總共94頁(yè)。求逆矩陣？解，設(shè)B是A的逆矩陣，根據(jù)定義得解得：b1=1,b2=-2,b3=0,b4=1,即

設(shè)A是n階方陣，如果存在n階方陣B,滿足AB=BA=E則稱A是可逆矩陣，B是A的逆矩陣。E是n階單位矩陣逆矩陣的求法：定義法；公式法(伴隨矩陣法)求矩陣的逆矩陣當(dāng)前24頁(yè)，總共94頁(yè)。

例4-2

解：代入牛頓法迭代公式，得從而經(jīng)過(guò)一次迭代即求得極小點(diǎn)和函數(shù)值

取初始點(diǎn)X0=[2，2]T，則初始點(diǎn)處梯度，海賽矩陣及其逆陣分別為當(dāng)前25頁(yè)，總共94頁(yè)。二）阻尼牛頓法*具有二次收斂性，但用到二階導(dǎo)數(shù)矩陣求逆仍取牛頓方向，但改用最優(yōu)步長(zhǎng)因子，在牛頓方向上進(jìn)行一維搜索，避免了迭代后函數(shù)值上升的現(xiàn)象：從牛頓法迭代公式的推演中可以看到，迭代點(diǎn)的位置是按照極值條件確定的，其中并未含有沿下降方向搜尋的概念。因此對(duì)于非二次函數(shù)，如果采用上述牛頓迭代公式，有時(shí)會(huì)使函數(shù)值上升?；九ｎD法的步長(zhǎng)因子恒為1，有時(shí)會(huì)導(dǎo)致迭代發(fā)散而失效。1.問(wèn)題的提出2.改進(jìn)方法在Hk正定時(shí)可保證收斂性。當(dāng)前26頁(yè)，總共94頁(yè)。K=0，X（K）=X0K=K+1NX*=X（K）F*=F（X*）結(jié)束Y3.阻尼牛頓法的迭代步驟計(jì)算計(jì)算

，由

出發(fā)，沿

方向搜索得

給定

X0

，ε當(dāng)前27頁(yè)，總共94頁(yè)。方法特點(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)，但在特定條件下它具有收斂最快的優(yōu)點(diǎn)，并為其他的算法提供了思路和理論依據(jù)。當(dāng)前28頁(yè)，總共94頁(yè)。一般迭代式：梯度法：牛頓法：阻尼牛頓法：梯度法與牛頓法：當(dāng)前29頁(yè)，總共94頁(yè)。4-3

變尺度法

DFP變尺度法首先有戴維頓（Davidon）與1959年提出，又于1963年由弗萊徹（Fletcher）和鮑維爾加以發(fā)展和完善，成為現(xiàn)代公認(rèn)的較好的算法之一。

DFP法是基于牛頓法的思想又作了重要改進(jìn)。這種算法僅用到梯度，不必計(jì)算海賽陣及其逆矩陣，但又能使搜索方向逐漸逼近牛頓方向，具有較快的收斂速度。

當(dāng)前30頁(yè)，總共94頁(yè)。變量的尺度變換是放大或縮小各個(gè)坐標(biāo)。通過(guò)尺度變換可以把函數(shù)的偏心程度降低到最低限度。尺度變換技巧能顯著地改進(jìn)幾乎所有極小化方法的收斂性質(zhì)。值時(shí),需要進(jìn)行10次迭代才能達(dá)到極小點(diǎn)

如作變換y1=x1,y2=5x2把的尺度放大5倍，則目標(biāo)函數(shù)等值線由一簇橢圓變成一簇同心圓。x2例如在用最速下降法求極小當(dāng)前31頁(yè)，總共94頁(yè)。消除了函數(shù)的偏心，用最速下降法只需一次迭代即可求得極小點(diǎn)。梯度法構(gòu)造簡(jiǎn)單，只用到一階偏導(dǎo)數(shù)，計(jì)算量小，初始點(diǎn)可任選，且開(kāi)始幾次迭代，目標(biāo)函數(shù)值下降很快；其主要缺點(diǎn)是迭代點(diǎn)接近X*時(shí)，即使對(duì)二次正定函數(shù)收斂也非常慢。牛頓法收斂很快，對(duì)于二次函數(shù)只需迭代一次便達(dá)到最優(yōu)點(diǎn)，對(duì)非二次函數(shù)也能較快迭代到最優(yōu)點(diǎn)，但要計(jì)算二階偏導(dǎo)數(shù)矩陣及其逆陣，對(duì)維數(shù)較高的優(yōu)化問(wèn)題，其計(jì)算工作和存儲(chǔ)量都太大。能不能將兩種算法的優(yōu)點(diǎn)綜合起來(lái)，揚(yáng)長(zhǎng)避短？當(dāng)前32頁(yè)，總共94頁(yè)。Ak

是需要構(gòu)造n×n的一個(gè)對(duì)稱方陣，如Ak=I,則得到梯度法；則得到阻尼牛頓法；如當(dāng)矩陣Ak

不斷地迭代而能很好地逼近

時(shí)，就可以不再需要計(jì)算二階導(dǎo)數(shù)。

變尺度法的關(guān)鍵在于尺度矩陣Ak的產(chǎn)生。對(duì)于二次函數(shù):當(dāng)前33頁(yè)，總共94頁(yè)。進(jìn)行尺度變換在新的坐標(biāo)系中，函數(shù)f(x)的二次項(xiàng)變?yōu)椋耗康模簻p少二次項(xiàng)的偏心如G是正定，則總存在矩陣Q，使得：用矩陣Q-1右乘等式兩邊，得：用矩陣Q左乘等式兩邊，得：所以上式說(shuō)明：二次函數(shù)矩陣G的逆陣，可以通過(guò)尺度變換矩陣Q來(lái)求得。當(dāng)前34頁(yè)，總共94頁(yè)。牛頓迭代公式：記：搜索方向：迭代公式：A稱為變尺度矩陣當(dāng)前35頁(yè)，總共94頁(yè)。在例4－2中如取當(dāng)前36頁(yè)，總共94頁(yè)。當(dāng)前37頁(yè)，總共94頁(yè)。當(dāng)前38頁(yè)，總共94頁(yè)。牛頓法就可看成是經(jīng)過(guò)尺度變換后的梯度法。經(jīng)過(guò)尺度變換，使函數(shù)偏心率減小到零，函數(shù)的等值面變?yōu)榍蛎?或超球面)，使設(shè)計(jì)空間中任意點(diǎn)處函數(shù)的梯度都通過(guò)極小點(diǎn)，用最速下降法只需一次迭代就可達(dá)到極小點(diǎn)。這就是對(duì)變換前的二次函數(shù)，在使用牛頓方法時(shí)，由于其牛頓方向直接指向極小點(diǎn)，因此只需一次迭代就能找到極小點(diǎn)。當(dāng)前39頁(yè)，總共94頁(yè)。構(gòu)造尺度矩陣Ak從初始矩陣A0=I(單位矩陣)開(kāi)始，通過(guò)對(duì)公式

因此，一旦達(dá)到最優(yōu)點(diǎn)附近，就可望達(dá)到牛頓法的收斂速度。1）DFP法（Davidon-Fletcher-Powell)式中中修正矩陣的不斷修正，在迭代中逐步逼近于

。當(dāng)前40頁(yè)，總共94頁(yè)。2）BFGS算法(Broyden-Fletcher-Goldfrob-Shanno)

DFP算法由于舍入誤差和一維搜索不精確，有可能導(dǎo)致構(gòu)造矩陣的正定性遭到破壞，以至算法不穩(wěn)定。BFGS算法對(duì)于維數(shù)較高問(wèn)題具有更好的穩(wěn)定性。

當(dāng)前41頁(yè)，總共94頁(yè)。當(dāng)前42頁(yè)，總共94頁(yè)。例4-3：

用DFP算法求下列問(wèn)題的極值：取初始變尺度矩陣為單位矩陣A0=I，則第一次搜尋方向?yàn)?/p>

解：1）取初始點(diǎn)，為了按DFP法構(gòu)造第一次搜尋方向d0，需計(jì)算初始點(diǎn)處的梯度當(dāng)前43頁(yè)，總共94頁(yè)。沿d0方向進(jìn)行一維搜索，得為一維搜索最佳步長(zhǎng)，應(yīng)滿足得:,2）再按DFP法構(gòu)造點(diǎn)x1處的搜尋方向d1，需計(jì)算當(dāng)前44頁(yè)，總共94頁(yè)。代入校正公式=當(dāng)前45頁(yè)，總共94頁(yè)。=第二次搜尋方向?yàn)樵傺豥1進(jìn)行一維搜索，得當(dāng)前46頁(yè)，總共94頁(yè)。為一維搜索最佳步長(zhǎng)，應(yīng)滿足,得3）判斷x2是否為極值點(diǎn)梯度:

海賽矩陣

:當(dāng)前47頁(yè)，總共94頁(yè)。梯度為零向量,海賽矩陣正定?？梢?jiàn)點(diǎn)滿足極值充要條件，因此為極小點(diǎn)。

當(dāng)前48頁(yè)，總共94頁(yè)。針對(duì)牛頓法，提出了變尺度法

收斂速度比較慢每次迭代需要計(jì)算二階導(dǎo)數(shù)矩陣，矩陣求逆計(jì)算量大，存儲(chǔ)量大1.牛頓型方法2.最速下降法針對(duì)最速下降法，提出了只用梯度信息，但收斂速度更快的共軛梯度法當(dāng)前49頁(yè)，總共94頁(yè)。1.基本思想：

每次以一個(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)，若未收斂，則開(kāi)始第k+1次迭代，直至收斂到最優(yōu)點(diǎn)x*?！?-5坐標(biāo)輪換法當(dāng)前50頁(yè)，總共94頁(yè)。1)幾何描述(以二維問(wèn)題為例）二）迭代步驟依次沿個(gè)n個(gè)正交坐標(biāo)軸的方向搜索：一）搜索方向當(dāng)前51頁(yè)，總共94頁(yè)。2)坐標(biāo)輪換法流程圖從

出發(fā)沿

方向進(jìn)行一維搜索得：給定結(jié)束當(dāng)前52頁(yè)，總共94頁(yè)。2.算法特點(diǎn)

等值線為橢圓,且長(zhǎng)短軸分別平行于坐標(biāo)軸時(shí)--高效一般情況--低效方法簡(jiǎn)單，容易實(shí)現(xiàn)。當(dāng)維數(shù)增加時(shí)，效率明顯下降。收斂慢，以振蕩方式逼近最優(yōu)點(diǎn)。受目標(biāo)函數(shù)的性態(tài)影響很大。如圖a)所示，二次就收斂到極值點(diǎn)；如圖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ò)誤。當(dāng)前53頁(yè)，總共94頁(yè)?！?/p>

4-6

共軛方向法

1.共軛方向：設(shè)G為n×n階實(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作一維搜索，得x1當(dāng)前54頁(yè)，總共94頁(yè)。因?yàn)槭茄豥0方向搜索的最佳步長(zhǎng)，即在點(diǎn)x1處函數(shù)f（x）沿方向d0的方向?qū)?shù)為零?？紤]到點(diǎn)x1處方向?qū)?shù)與梯度之間的關(guān)系，故有如果按最速下降法，選擇負(fù)梯度方向?yàn)樗阉鞣较?，則將發(fā)生鋸齒現(xiàn)象。取下一次的迭代搜索方向d1直指極小點(diǎn)x*。α0d0x0x1x*11α1d1d1當(dāng)前55頁(yè)，總共94頁(yè)。如果能夠選定這樣的搜索方向，那么對(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í)左乘得：有當(dāng)前56頁(yè)，總共94頁(yè)。就是使d1直指極小點(diǎn)x*

，d1所必須滿足的條件。兩個(gè)向量d0和d1稱為G的共軛向量，或稱d0和d1對(duì)G是共軛方向。

2.共軛方向的性質(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)行一維搜索，最多經(jīng)過(guò)n次迭代就可以找到的二次函數(shù)f(x)極小點(diǎn)。

當(dāng)前57頁(yè)，總共94頁(yè)。關(guān)鍵：新的共軛方向確定在無(wú)約束方法中許多算法都是以共軛方向作為搜索方向，它們具有許多特點(diǎn)。根據(jù)構(gòu)造共軛方向的原理不同，可以形成不同的共軛方向法。當(dāng)前58頁(yè)，總共94頁(yè)。3.共軛梯度法共軛梯度法是共軛方向法中的一種，該方法中每一個(gè)共軛向量都是依賴于迭代點(diǎn)處的負(fù)梯度而構(gòu)造出來(lái)。從xk出發(fā)，沿負(fù)梯度方向作一維搜索:設(shè)與dk共軛的下一個(gè)方向dk+1由dk和點(diǎn)xk+1的負(fù)梯度的線性組合構(gòu)成，即：共軛條件：當(dāng)前59頁(yè)，總共94頁(yè)。則：解得：令為函數(shù)的泰勒二次展開(kāi)式則上兩式相減，并代入當(dāng)前60頁(yè)，總共94頁(yè)。將式與式轉(zhuǎn)置兩邊相乘，應(yīng)用共軛條件得：因此當(dāng)前61頁(yè)，總共94頁(yè)。當(dāng)前62頁(yè)，總共94頁(yè)。，已知初始點(diǎn)[1,1]T求下列問(wèn)題的極值解：1）第一次沿負(fù)梯度方向搜尋計(jì)算初始點(diǎn)處的梯度為一維搜索最佳步長(zhǎng)，應(yīng)滿足迭代精度。當(dāng)前63頁(yè)，總共94頁(yè)。得:2）第二次迭代：代入目標(biāo)函數(shù)當(dāng)前64頁(yè)，總共94頁(yè)。得因收斂。由從而有：當(dāng)前65頁(yè)，總共94頁(yè)。鮑威爾法是以共軛方向?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)?！?.7鮑威爾(Poweel)法當(dāng)前66頁(yè)，總共94頁(yè)。一.Poweel法（共軛方向法、方向加速法）：1.基本思想：直接利用函數(shù)值來(lái)構(gòu)造共軛方向

若沿連接相鄰兩輪搜索末端的向量S方向搜索，收斂速度加快。

因?yàn)閮蓷l平行線S1,S2與同心橢圓族相切，兩個(gè)切點(diǎn)的連線S直指中心。稱S1,S2與S為共軛方向。

目的：以共軛方向打破振蕩，加速收斂。

這種方法是在研究具有正定矩陣A的二次函數(shù)極小化的基礎(chǔ)上形成。當(dāng)前67頁(yè)，總共94頁(yè)。2.共軛方向生成

設(shè)Xk，Xk+1為從不同點(diǎn)出發(fā)，沿同一方向Sj進(jìn)行一維搜索得到兩個(gè)極小點(diǎn)，如圖所示。根據(jù)梯度與等值面垂直的性質(zhì)，Sj與Xk，Xk+1兩點(diǎn)處的梯度gk，gk+1存在關(guān)系

對(duì)于上述二次函數(shù)，其Xk，Xk+1兩點(diǎn)處梯度可表示為

相減得

因而有

若取方向則Sk和Sj共軛

只要沿Sj方向分別對(duì)函數(shù)作兩次一維搜索，得到兩個(gè)極小點(diǎn)Xk，Xk+1，兩個(gè)切點(diǎn)(極小點(diǎn))的連線所給的方向，就是與Sj

一起對(duì)H為共軛方向。當(dāng)前68頁(yè)，總共94頁(yè)。3.共軛方向的定義：當(dāng)前69頁(yè)，總共94頁(yè)。4.共軛方向的性質(zhì)：當(dāng)前70頁(yè)，總共94頁(yè)。5.步驟：當(dāng)前71頁(yè)，總共94頁(yè)。3）若目標(biāo)函數(shù)為正定二次函數(shù)，n輪結(jié)束后即可到達(dá)最優(yōu)點(diǎn)。2）每輪迭代產(chǎn)生一個(gè)新方向取代原來(lái)的第一方向，替換原則是去掉原方向組的第一個(gè)方向而將新方向排在原方向的最后；n輪迭代后可產(chǎn)生n個(gè)彼此共軛的方向；1）開(kāi)始采用坐標(biāo)軸方向；順次沿n個(gè)方向做一維搜索得到一個(gè)終點(diǎn)，由始點(diǎn)和終點(diǎn)構(gòu)成一個(gè)新的方向。要點(diǎn)當(dāng)前72頁(yè)，總共94頁(yè)。2）在改進(jìn)的算法中首先要判斷原向量組是否需要替換。若需要替換，還要進(jìn)一步判斷原向量組哪個(gè)向量最壞，然后在用新的方向替換這個(gè)最壞的方向或向量，以保證逐次生成共軛方向；1）每一輪迭代都用由始點(diǎn)和終點(diǎn)構(gòu)成一個(gè)新的搜索方向代替原方向組的第一個(gè)向量，而不管它的“好壞”。向量組線性相關(guān)改進(jìn)鮑威爾算法3）每輪迭代中始點(diǎn)X0k，終點(diǎn)Xnk和反射點(diǎn)Xn+1k沿方向移動(dòng)一個(gè)距離令當(dāng)前73頁(yè)，總共94頁(yè)。a）若不滿足判別條件，則下輪迭代仍用原方向組，并以Xnk和Xn+1k中函數(shù)值小者作為下輪迭代的始點(diǎn)。4）根據(jù)是否滿足判別條件

確定是否要對(duì)原方向組進(jìn)行替換b）若滿足判別條件，則下輪迭代對(duì)方向組進(jìn)行替換，將Sk補(bǔ)充到原方向組的最后位，而除掉Snk。即新方向組為S1k，S2k，…，Sm-1k，Sm+1k,…,Snk，Sn+1k作為下輪迭代的搜索方向。下一輪迭代的始點(diǎn)取為Sn+1k方向進(jìn)行一維搜索的極小點(diǎn)X0k＋15）判斷是否滿足收斂準(zhǔn)則當(dāng)前74頁(yè)，總共94頁(yè)。這樣重復(fù)迭代的結(jié)果，后面加進(jìn)去的向量都彼此對(duì)G共軛，經(jīng)n輪迭代即可得到一個(gè)由n個(gè)共軛方向所組成的方向組。對(duì)于二次函次，最多n次就可找到極小點(diǎn)，而對(duì)一般函數(shù)，往往要超過(guò)n次才能找到極小點(diǎn)（這里“n”表示設(shè)計(jì)空間的維數(shù)）。

當(dāng)前75頁(yè)，總共94頁(yè)。Powell修正算法F3<F1Q<DSi=Si+1i=m,m+1,…ni=n輸出X*=XnF*=F（X*）結(jié)束給定X0,Si=eii=1,2,…n,εK=0i=1自Xi-1始，沿Si方向搜索得一維最優(yōu)點(diǎn)Xii=i+1Xn+1=2Xn-X0Sn+1=Xn-X0自Xn始，沿Sn+1方向搜索得一維最優(yōu)點(diǎn)X*K=K+1F1=F(X0),F2=F(Xn),F3=F(Xn+1)求Δ及方向標(biāo)號(hào)mYYYYNNNX0=X*NXn-X0

≤ε當(dāng)前76頁(yè)，總共94頁(yè)。6.例4-3

解：1）沿S10方向進(jìn)行一維搜索，有a1為一維搜索最佳步長(zhǎng)，可通過(guò)

取初始點(diǎn)X00=[0，0]T，取初始搜索方向S10＝e1＝[10]T,S20＝e2＝[01]T,初始點(diǎn)處函數(shù)值得當(dāng)前77頁(yè)，總共94頁(yè)。

從而得到X10點(diǎn)處的函數(shù)值及沿S10走一步長(zhǎng)后函數(shù)值的增量2）沿S20方向進(jìn)行一維搜索，有a2為一維搜索最佳步長(zhǎng)，可通過(guò)得當(dāng)前78頁(yè)，總共94頁(yè)。

從第一輪終點(diǎn)X20處出發(fā)，沿S20走一步長(zhǎng)后函數(shù)值的增量

沿S10，

S20方向?qū)?yōu)后函數(shù)值增量的最大者為終點(diǎn)X20的反射點(diǎn)及其函數(shù)值為當(dāng)前79頁(yè)，總共94頁(yè)。3）為確定下一輪迭代的搜索方向和起始點(diǎn)，需檢查判別條件是否滿足

因?yàn)镚3>G0,不滿足判別條件，因而下一輪迭代中繼續(xù)使用原來(lái)的搜索方向

因?yàn)镚3>G2,所以取X20作為下一輪迭代起始點(diǎn)第二輪迭代：第二輪迭代初始點(diǎn)及其函數(shù)值當(dāng)前80頁(yè)，總共94頁(yè)。7.方法評(píng)價(jià)：

計(jì)算步驟復(fù)雜;

是二次收斂方法，收斂快。對(duì)非正定函數(shù)，也很有效;

是比較穩(wěn)定的方法。6.說(shuō)明：

若是正定二次函數(shù)，n輪迭代后收斂于最優(yōu)點(diǎn)x*。若是非正定二次函數(shù)，則迭代次數(shù)增加。

若是n維問(wèn)題，步驟相同。搜索方向：第一輪迭代，沿初始方向組Si(1)(i=1,2,…,n)的n個(gè)方向和共軛方向S(1)，搜索n+1次得極值點(diǎn)xn+1(1)

；第二輪迭代，沿方向組Si(2)(i=1,2,…,n；i≠m)的n-1個(gè)方向和共軛方向S(1)，構(gòu)筑共軛方向S(2)搜索n+1次得極值點(diǎn)xn+1(2)

。其中，為保證搜索方向的線性無(wú)關(guān)，去除了Sm(2)方向。

在第k輪迭代中，為避免產(chǎn)生線性相關(guān)或近似線性相關(guān)，需要去除前一輪中的某個(gè)方向Sm(k)。——去除的原則請(qǐng)自學(xué)。當(dāng)前81頁(yè)，總共94頁(yè)。前面介紹的許多優(yōu)化方法，除鮑威爾（Powell）法和坐標(biāo)輪換法外，都需要計(jì)算目標(biāo)函數(shù)的導(dǎo)數(shù)，而在實(shí)際工程的最優(yōu)化問(wèn)題中，目標(biāo)函數(shù)的導(dǎo)數(shù)往往很難求出或者根本無(wú)法求出。下面所介紹的方法只需要計(jì)算目標(biāo)函數(shù)值，無(wú)需求其導(dǎo)數(shù)，因此計(jì)算比較簡(jiǎn)單，其幾何概念也比較清晰，屬于直接法的無(wú)約束最優(yōu)化方法。這類方法適用于不知道目標(biāo)函數(shù)的數(shù)學(xué)表達(dá)式而僅知其具體算法的情況。這也是直接法的一個(gè)優(yōu)點(diǎn)。當(dāng)前82頁(yè)，總共94頁(yè)?！?-8單純形方法一、基本思想單純形替換法也是一種不使用導(dǎo)數(shù)的求解無(wú)約束極小化問(wèn)題的直接搜索方法，與前面幾種方法不同的是，單純形替換法不是利用搜索方向從一個(gè)點(diǎn)迭代到另一個(gè)更優(yōu)的點(diǎn)，而是從一個(gè)單純形迭代到