材料加工過程輔助優(yōu)化設(shè)計

《材料加工過程輔助優(yōu)化設(shè)計》由會員分享，可在線閱讀，更多相關(guān)《材料加工過程輔助優(yōu)化設(shè)計（85頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、 材料加工過程輔助優(yōu)化設(shè)計 第一章 優(yōu)化設(shè)計概論 優(yōu)化設(shè)計是近年來發(fā)展起來的一門新的科氏也是一項新的技術(shù)，它在工程設(shè)計的各個領(lǐng)域得到了廣泛的應(yīng)用。為什么人們?nèi)绱酥匾曔@項新技術(shù)呢?因為“最優(yōu)化”是每一個工程式產(chǎn)品設(shè)計者所追求的目標(biāo)。任何一項工程或一個產(chǎn)品的設(shè)計，部需要根據(jù)設(shè)計要求，合理選擇方案，確定各種參數(shù)，以期達到最佳的設(shè)計目標(biāo)，如重量輕、材料省、成本低、性能好、承載能力高等等。優(yōu)化設(shè)計正是根據(jù)這樣的客觀需求而產(chǎn)生并發(fā)展起來的。 優(yōu)化設(shè)計的理論基礎(chǔ)是數(shù)學(xué)規(guī)劃，采用的工具是電子計算機。主要表現(xiàn)在兩個方面： (1)優(yōu)化設(shè)計能使各種設(shè)計參數(shù)自動向更優(yōu)的方向進行

2、調(diào)整，宜至找到一個盡可能完善的或最合適的設(shè)計方案。常規(guī)設(shè)計雖然也希望找到最佳的設(shè)計方免但都是憑惜設(shè)計人員的試驗來進行的。它既不能保證沒計參數(shù)一定能夠向更優(yōu)的方向調(diào)整，同時也不可能保證一定能找到最合適的設(shè)計方案?！? (2)優(yōu)化設(shè)計的手段是采用電子計算機，在很短的時間內(nèi)就可以分析一個設(shè)計方案，并判斷方案的優(yōu)劣和是否可行，因此可以從大量的方案中選出更優(yōu)的設(shè)計方案，這是常規(guī)設(shè)計所不能相比的。 現(xiàn)著重論述以下三個問題： (1)如何把工程實際問題轉(zhuǎn)化成便于用數(shù)學(xué)方法求解的優(yōu)化數(shù)學(xué)模型。通過數(shù)學(xué)模型的建立，就可以從本質(zhì)上更深刻地理解什么是優(yōu)化設(shè)計。 u (2)優(yōu)化過程是如何進行的怎樣保證設(shè)計參

3、數(shù)能自動向更優(yōu)的方向調(diào)整。通過優(yōu)化過程的剖析，就可了解優(yōu)化過程包括田些主要內(nèi)容。 (3)優(yōu)化設(shè)計還存在四些局限性?今后應(yīng)從什么方向去研究解決。 第一節(jié) 工程中的優(yōu)化設(shè)計問題 例1：汽車駕駛空利雨授置汪任汗征戰(zhàn)凋四個角落不易擦到，刮雨范圍較小的缺點，因此視線達不到最優(yōu)。通過來用四連仔傳動裝置如圖1—1所而可以使刮雨范圍變成不是圓弧形，從而能克服上述缺點。優(yōu)化的目標(biāo)是，合理確定四連桿的幾何尺寸，使刮雨范圍盡可能大。 例2：圖1—3表示一個承強系統(tǒng)的重量最優(yōu)化問題。 例3圖1—4中所示例子，是一個沖壓件下料布置的最優(yōu)化問題。沖壓件是三塊不同大小的矩形板?，F(xiàn)征所提出的問題是，在下料時

4、應(yīng)如何布置這三塊不同大小的矩形板，使它們的包絡(luò)線在板材上所圍成的面積最小。我們可以把矩形仲壓件形心的坐標(biāo)作為設(shè)計參數(shù)，限制條件足沖壓件在扳材上不能重疊。這個例子的主要特點之一是設(shè)計參數(shù)和優(yōu)化目標(biāo)、限制條件之間的關(guān)系很難建立。 例4：是一個兩級齒輪減速箱酌優(yōu)化設(shè)計問題。齒輪箱的優(yōu)化設(shè)計問題具有較多的設(shè)計參數(shù)(這里有7個)和限制條件(通常多于20個)。 例5：是一個貨架底板的截面形狀優(yōu)化設(shè)計問題。本例的特點是設(shè)計參數(shù)彼此無關(guān)，目標(biāo)的改善常常是多個角度同時以適當(dāng)?shù)牧孔兓瘯r才能達到。 從上述例子我們可清楚地看到，優(yōu)化設(shè)計問題都具有一個明確的優(yōu)化目標(biāo)。最優(yōu)目標(biāo)的實現(xiàn)，可通過改變設(shè)計參數(shù)來達到。存在

5、兩個問題。 1) 首先必須確定設(shè)計方案的結(jié)構(gòu)型式。 2) 在一定的結(jié)構(gòu)型式下，建立設(shè)計參數(shù)與優(yōu)化目標(biāo)和約束條件之間的關(guān)系。 第一個問題實際上是結(jié)構(gòu)型式的優(yōu)選問題(也稱非數(shù)值優(yōu)化問題)。第二個問題實際上是在確定的結(jié)構(gòu)型式下的參數(shù)優(yōu)化問題。 第二節(jié) 優(yōu)化設(shè)計的數(shù)學(xué)模型 一、 引 例 目標(biāo)函數(shù)--管柱的質(zhì)量表達式為： 約束函數(shù)： (1) 壓桿的穩(wěn)定性條件 ： (2) 局部穩(wěn)定性條件： (3) 強度條件： (4) 工藝條件： 顯然，我們所需要找助最優(yōu)點一定是j點。管柱的昆優(yōu)方案為： 這時管柱的質(zhì)量w＝1.814kg為最小。

6、 二、 優(yōu)化設(shè)計的數(shù)學(xué)模型 1． 設(shè)計變量與設(shè)計空間 任何一個機械設(shè)計方案一般都是由若干個設(shè)計參數(shù)所決定的。這些設(shè)計參數(shù)可以是構(gòu)件的截面尺寸、零件的直徑和長度、齒輪的模數(shù)、機構(gòu)的工作速度等，也可以是彈性模量，許用應(yīng)力等與材料有關(guān)的參數(shù)。在這些設(shè)計參效中，一部分是按具體要求事先給定的，它們在優(yōu)化沒計過程中始終保持不變，故稱為預(yù)定參數(shù)。 先選定材料，因而彈性模量和許用應(yīng)力就是預(yù)定參數(shù)。另一部分參數(shù)在優(yōu)化設(shè)計過程中是可以變化的，如構(gòu)件截面尺寸大小等，這類設(shè)計參數(shù)就稱為設(shè)計變量。 以設(shè)計變量為坐標(biāo)軸所構(gòu)成的空間稱設(shè)計空間。一般情況下，設(shè)計變量的個數(shù)就是設(shè)計空間的維數(shù)。 2． 約束條件及可

7、行區(qū)與非可行區(qū) 在機械設(shè)計中，設(shè)計變量總要受到某些條件的限制，如強度、剛度條件等，這些條件稱為約束條件。約束條件一般都可用不等式或等式表示，其一般形式為， 不等號或等號左邊表示根據(jù)約束條件建立起來的設(shè)計變量x的函數(shù)式，又稱為約束函數(shù)。 可行區(qū)就是所有滿足約束條件設(shè)計點的集合R，即： 3． 目標(biāo)函數(shù) 優(yōu)化的目標(biāo)在數(shù)學(xué)上一般部可寫成設(shè)計變量的函數(shù)關(guān)系式。這個函數(shù)就稱為目標(biāo)函數(shù)： 4． 優(yōu)化設(shè)計的數(shù)學(xué)模型 優(yōu)化設(shè)計的任務(wù)就是要在可行區(qū)城內(nèi)找到一個點，便目標(biāo)函數(shù)值最?。虼藘?yōu)比設(shè)計可作如下數(shù)學(xué)描述： 三、 建立優(yōu)化設(shè)計數(shù)學(xué)模型的幾個實例 例1：圓柱形螺旋壓力彈簧的

8、優(yōu)化設(shè)計 試設(shè)計一受靜載荷的圓柱螺旋壓縮彈簧。已知當(dāng)彈簧受荷，P1＝178N時，其長度H1＝89mm；當(dāng)P2＝1160N時，H2＝54mm。該彈簧套有心棒，彈簧材科為普通碳素彈簧鋼絲。 目標(biāo)函數(shù)： 約束條件為： 1、強度條件： 最終為： 2、剛度條件 最終為： 3、工藝條件 4、幾何約束條件： 在這里應(yīng)保證設(shè)計變量為非負(fù)，即： 采用幾何規(guī)劃法解得： 例2：箱形截面梁的優(yōu)化設(shè)計 箱形梁的計算簡圖如圖1—10所示。設(shè)計變量為梁高x1，梁寬x2，腹板厚度x3和翼緣板厚度x4。 寫成向量形式； 目標(biāo)函數(shù)： 約

9、束函數(shù)： 1、 強度條件： 2、 剛度條件： 3、 翼緣板局部穩(wěn)定性條件： 4、 腹板局部穩(wěn)定性條件： 5、 幾何約束條件： 用可行方向法求得上述優(yōu)化設(shè)計數(shù)學(xué)模型的最優(yōu)解如表1—36所用數(shù)據(jù)為： 四、優(yōu)化設(shè)計數(shù)學(xué)模型的評價 模型的特性分析和評價，主要考慮以下幾方面； 1． 模型的可解性； 2． 線性與非線性程度； 3． 目標(biāo)函數(shù)的維致； 4． 連續(xù)性； 5． 凸性。 第三節(jié) 優(yōu)化過程概述 一、 優(yōu)化過程示例 圖1—12表示一個二級齒輪減速箱的優(yōu)化過程 圖1—13表示一個承載結(jié)構(gòu)的優(yōu)化過程 任何一個優(yōu)化過程均可視為由

10、綜合與分析、評價以及改變參數(shù)三部分組成。綜合與分析部分的主要功能是建立產(chǎn)品設(shè)計參數(shù)與產(chǎn)品性能、設(shè)計要求之間的關(guān)系，這實際上就是優(yōu)化設(shè)計數(shù)學(xué)模型。評價部分就是對產(chǎn)品的性能和設(shè)計要求進行評價，這實際上也就是評價目標(biāo)函數(shù)值是否得到改善或達到最優(yōu)，約束條件是否全部得到滿足。改變參數(shù)部分就是選擇優(yōu)化方法并根據(jù)該方法改變設(shè)計參數(shù)。 二、優(yōu)化過程的幾何描述 從數(shù)值計算角度而言，優(yōu)化過程是一個迭代過程。以第二節(jié)中管柱優(yōu)化設(shè)計為例，優(yōu)化過程如圖1—14所示。 一般要滿足兩條原則，一是參數(shù)改變后目標(biāo)函效應(yīng)有所下降，二是參數(shù)改變后仍滿足全部約束條件，即所形成的新點仍在可行區(qū)內(nèi)。 第四節(jié)

11、優(yōu)化設(shè)計存在的問題和某些發(fā)展趨勢 1) 優(yōu)化設(shè)計本身存在的問題和某些發(fā)展趨勢主要有以下幾方面： 2) 目前優(yōu)化設(shè)計多數(shù)還局限在解決參數(shù)最優(yōu)化這一類數(shù)值量優(yōu)化問題； 3) 優(yōu)化設(shè)計這門新技術(shù)在傳統(tǒng)產(chǎn)業(yè)中普及率還比較低。 4) 從理論上講，優(yōu)化設(shè)計希望能找到全局最優(yōu)方案，至少也是一個局部最優(yōu)的方案。由于工程實際問題的復(fù)雜性，目標(biāo)函數(shù)和約束函數(shù)的性態(tài)均比較復(fù)雜，要實現(xiàn)上述目標(biāo)不是花費大量的時間，就是無法達到。因此在實用上人們已經(jīng)把優(yōu)化的目標(biāo)擴大，并根據(jù)不同的優(yōu)化設(shè)計問由，考慮不同的優(yōu)化目標(biāo)。如果優(yōu)化數(shù)學(xué)模型比較簡單或者雖然較復(fù)雜函數(shù)性態(tài)較好，這時我們可以去追求局部最優(yōu)乃至全局最優(yōu)這樣的目

12、標(biāo)。 第五節(jié) 小節(jié) 第二章 極值理論簡介 在討論各種最優(yōu)化方法之前，我們先對古典極值理論作一簡單回顧。 第一節(jié) 一元函數(shù)的極值問題 如果函數(shù)f(x)在區(qū)間(a，b)內(nèi)處處有一階導(dǎo)數(shù),x為其極值點；則必須： 這就是極值存在的必要條件。這個條件為尋求函數(shù)的極值點提供了依據(jù)。 綜上所述．判斷極值點的條件是：設(shè)函數(shù)f(x)在點x0具有二階導(dǎo)數(shù)f’’(xo)。 (1)若f’(xo)=0, f’’(xo)<0，則f(x0)為函數(shù)的極大值； (2)若f’(xo)=0, f’’(xo)>0，則f(x0)為函數(shù)的極小值。 第二節(jié) 二元函數(shù)的

13、極值 二元函數(shù)極值點的必要條件： 必要條件成立并滿足： 則： 第三節(jié) 一般n元函數(shù)的極值 多元函數(shù)的性質(zhì)．能從二元函數(shù)得到很好的反映。二元函數(shù)極值問題所得結(jié)論很容易推廣于一般的多元函數(shù)。 一、 數(shù)的上升方向和下降方向 過x0點引入向量s，函數(shù)f(x)即f(x1，x2)沿s方向的變化率就是f(x)在x0點沿s方向的方向?qū)?shù)，其值為： 如果是n元函數(shù)，則其方向?qū)?shù)為: 用向量表示： 式中： 若s不是單位向量，則函數(shù)f(x)在x0點沿sk方向的變化率可寫成： 利用柯西不等式證明： 梯度方向F(Xo)為f(x

14、)在xo處的最速上升方向．而--F(Xo)為f(x)在xo處的最速下降方向。當(dāng)然，這里所說的最速上升或最速下降是對xo點附近而言的。 二、極值點的充分條件 若x*為f(x)的一個極小點，則函數(shù)在x*沿任何方向s均不減小，因此對任何方向的s恒有： 存在極值點的必要條件。 如何判斷駐點是否極小點呢?根據(jù)泰勒展開式可知，函數(shù)f(x)在x*附近可用矩陣近似表達成(略去高階微量．取到二次項)： 所以在x*附近有：f(x)>f(x*),故x*為f(x)的一個極小點。 綜上所述，函數(shù)f(x)在定義域上x*點存在極小點的充分條件是：

15、 　 　　　　　　　　　　　　　　A為正定 第四節(jié) 函數(shù)的凸性 1、 集合 具有某種性質(zhì)事物的全體稱為集合。事物就是集合成分，稱為集合的元素。 2、 凸集 若任意兩個點Xl和X2位于某集合之中，且連接這兩點的線段上所有點也在這個點集中，則這個點集便是凸集，如圖2—7所示。 3 凸函數(shù) 若函數(shù)f(x)的海賽矩陣處處為半正定，則函數(shù)為凸函數(shù)?？嗵幪帪檎ǎ畡t為嚴(yán)格的凸函數(shù)。 由于優(yōu)化設(shè)計是在可行區(qū)內(nèi)求目標(biāo)函數(shù)的極小點，所以要判斷極小點(局部最優(yōu))是否是最小點(全局最優(yōu))，就必須先看一看目標(biāo)函數(shù)是否是凸

16、函數(shù)，然后再判斷可行區(qū)是否是凸集。若目標(biāo)函數(shù)是凸函數(shù)，可行區(qū)又是凸集，則找到的極小點必為最小點。這時所找到的最優(yōu)點不僅是局部最優(yōu)，而且必須是全局最優(yōu)。這類優(yōu)化設(shè)計問題，我們稱為凸規(guī)劃問題。 由于可行區(qū)是由約束函數(shù)在設(shè)計空間中構(gòu)成，所以它的凸性與約束函數(shù)的凸性有密切關(guān)系。下面我們來研究圖2—11中的兩種情況。從圖中可以得出以下結(jié)論： 1、若約束函數(shù)gi(x)(i=l，2，…，m)為凸函數(shù)，則約束條件： 所構(gòu)成的可行區(qū)為凸集。 2、若約束函數(shù)gi(x)(i=l，2，…，m)為凹函數(shù)，則約束條件： 所構(gòu)成的可行區(qū)為凸集。

17、 第三章 無約束最優(yōu)化方法 第一節(jié) 概 述 當(dāng)建立了數(shù)學(xué)模型以后，我們可以根據(jù)這些數(shù)學(xué)模型有無約束條件將最優(yōu)化問題分解成無約束最優(yōu)化問題和有約束最優(yōu)化問題兩大類。雖然，工程實際中的最優(yōu)化設(shè)計問題絕大多數(shù)都是有約束的，但是，無約束最優(yōu)化問題是有約束最優(yōu)化方法的基礎(chǔ)。許多有約束的最優(yōu)化問題都可以通過一定的方法轉(zhuǎn)化成無約束最優(yōu)化問題，而且當(dāng)有約束問題的最優(yōu)點不在可行區(qū)的邊界上，而是在可行區(qū)的內(nèi)部時，也可以直接用無約束的方法來求解。另外，通過對無約束員優(yōu)化方法的研究，可以為研究有約束問題提供良好的概念基礎(chǔ)。

18、所以無約束最優(yōu)化問題在整個優(yōu)化設(shè)計問題的研究中仍占有很重要的地位。 無約束員優(yōu)化方法是基于古典極值理論的一種數(shù)值迭代方法，主要是用來求解非線性規(guī)劃問題。 關(guān)鍵要解決三個問題： 一是如何確定步長ak；二是如何選定迭代方向sk；三是如何判斷是否找到了最優(yōu)點；迭代應(yīng)終止。這三點就是我們這一章所要解決的問題，而前兩個問題，是我們這一章的重點。迭代方法有多種，它們之間的區(qū)別，就在于確定ak和sk的方式不同，持別是sk的確定，在各種方法中起著關(guān)鍵性的作用。下面首先來解決迭代終止問題。 第二節(jié) 迭代終止準(zhǔn)則 當(dāng)新得到一個迭代點Xk+1，后，我們就要檢驗這個點是否為最優(yōu)點或者最優(yōu)

19、點的近似點。檢驗的方法可因目標(biāo)函數(shù)的性質(zhì)及迭代方法的不同而不同。由圖3—1可以看到，當(dāng)?shù)^程已接近最優(yōu)點x*時，相鄰兩次迭代所得到的點Xk和Xk+1，已經(jīng)十分接近，而且它們所對應(yīng)的目標(biāo)函數(shù)值f（Xk）和f（Xk+1）也很接近。根據(jù)這一特點，目前常用的迭代終止準(zhǔn)則即停機準(zhǔn)則有以下幾種形式： 1)當(dāng)相鄰兩次迭代點Xk 和Xk+1，之間的距離已達到充分小時，則可認(rèn)為Xk+1，是極小值點，此時可以終止迭代。用空間向量的歐氏長度來表示，即為： n維空間中兩點Xk 和Xk+1之間的距離。 2）當(dāng)相鄰兩迭代點的目標(biāo)函數(shù)值已充分接近時。即目標(biāo)函數(shù)的下降量已達到足夠小時則認(rèn)為Xk+1為

20、極小值點，可以終止迭代。有數(shù)學(xué)式表示，即為： 3)當(dāng)?shù)c的目標(biāo)函數(shù)的梯度值達到充分小時，即滿足下式時，可以終止迭代過程。 只要滿足以上三點中之一，就可以認(rèn)為目標(biāo)函數(shù)值／(JL引)已收斂于其極小值。也可以聯(lián)合應(yīng)用以上幾式，進行綜合判斷。當(dāng)然，判斷迭代點是否為函數(shù)的極值點或近似極值點的方法還有很多。 上面各式中的ε是代表計算精度要求的一個足夠小的正數(shù)。它的大小應(yīng)根據(jù)不同的優(yōu)化方法和工程問題的實際要求適當(dāng)?shù)亟o出。ε值過大則達不到設(shè)計要求，過小又會給計算帶來許多不必要的麻煩。 另外必須注意全局最優(yōu)和局部最優(yōu)的問題。 第三節(jié) 常用的一維搜索方法 一維搜索方法只牽

21、涉到搜索步長的問題。 基本迭代公式： 數(shù)學(xué)描述： 首先確定搜索區(qū)間。 一、 搜索區(qū)間的確定 搜索區(qū)間首先應(yīng)滿足如下條件： 進退法確定搜索區(qū)間： 1、計算函數(shù)值 若： 則計算： 若： 則搜索區(qū)間為： 否則，將步長再加倍，重復(fù)前述步驟，最終可以找到搜索區(qū)間的上限即右端點b，其下限即左端點始終為a=a0 。該方法為前進計算法，反之為后退計算法，兩者結(jié)合為進退法。 導(dǎo)數(shù)法確定搜索區(qū)間： 取一點a0及步長Δa，計算f’（ a0），若： 再取一點a1= a0+Δa，計算f’（ a1），若： 則確定搜索區(qū)間為：[a=a0，b= a1]。 若：

22、 則將步長加倍，并計算f’（ a1+2Δa），如此繼續(xù)下去，總可以找到搜索區(qū)間的上限即右端點b。 進退法計算程序框圖： 有兩點值得注意，其一是我們事先已假設(shè)目標(biāo)函數(shù)在所考慮的區(qū)間是單峰的，如果目標(biāo)函數(shù)是多峰的，則應(yīng)一個峰一個峰地去尋查，尋查區(qū)間當(dāng)然也就有多個，應(yīng)該一個一個地確定。其二是對于韌始步長的選取Δa，不宜太大，特別是對于多蜂函數(shù)更應(yīng)注意。但也不宜太小，否則，費時太多。 二、0.618法 0．618法又稱為黃金分割法。假設(shè)我們通過進退法已經(jīng)求得搜索區(qū)間為[a0，b0]（為區(qū)別縮小后的區(qū)間，這里用a0 和b。表示縮小前的區(qū)間的上、下限)，按0．618的縮短率，逐次縮小搜

23、索區(qū)間，每次縮短后的區(qū)間長度均為前次區(qū)間長度的0618倍。具體步驟是這樣的：在區(qū)間[a0，b0]內(nèi)取兩個黃金分割點，如圖3—6所示： 若 則保留a1點， 可推出： 因而，a1又是新區(qū)間[a，b]內(nèi)的一個黃金分割點，相當(dāng)于前面的a2。因此我們在進行第二次縮短區(qū)間時，只用計算一個新的黃金分割點及其函數(shù)值即可。這樣就簡化了計算。 反之若： 保留a2： 如此反復(fù)進行下去，直到搜索區(qū)間縮小到足夠小，滿足不等式： 其中ε為一個事先給定的足夠小的正數(shù)。 程序框圖如下： 三、分?jǐn)?shù)法 在0.618法中，按索區(qū)間

24、每次都是以一個固定的縮短率0.618進行縮短的。而分?jǐn)?shù)法則是每一次縮短均取不等的比例數(shù)，同樣每次縮短后也可以保留上一次的一個點，而只需計算一個新的點。同時，分?jǐn)?shù)法還具有兩個優(yōu)點：一是在同樣的選代次數(shù)下，分?jǐn)?shù)法所求得的最佳步長6Z的精度是各種同類方法中員高的；另一個優(yōu)點則是在已知迭代精度時，可以預(yù)先計算出迭代的次數(shù)。 分?jǐn)?shù)法每次縮短的比例數(shù)是一個變化的量，這里要用到裴波那契數(shù)列： 與0.618法一樣，若： 則ak*應(yīng)在區(qū)間[a，a2]內(nèi)，那么去掉[a2，b]一段，a1點作為新區(qū)間進行下一輪縮短時的一個點。 若： 則應(yīng)在區(qū)間[a1，b]內(nèi)，那么去掉[a，a1]一段，a

25、2點作為新區(qū)間進行下一輪縮短時的一個點。 所以，不管f(a1)與f（a2）比較后的結(jié)果如何，我們在縮小區(qū)間后進行下一輪迭代時，都可以保留前—輪的一個點，只再計算一個新的點及其函數(shù)值就可以了。 現(xiàn)在我們再來看一看，最后一次縮短區(qū)間后ak*應(yīng)該等于什么? 通過一系列轉(zhuǎn)換推導(dǎo)可以得出： 得出最后區(qū)間的長度為： 因為 所以： 由此可求出n的大小和相應(yīng)的裴波那契數(shù)Fn的對應(yīng)關(guān)系可以根據(jù)表3—1所列的數(shù)據(jù)查得。 裴波那契數(shù)列可表示為： 不難證明： 因此當(dāng)n=7時，并且令的取值精確到三位小數(shù)時，F(xiàn)n-1/Fn都等于0．618，可見0．618法是分?jǐn)?shù)法的一個極限情況。

26、 第四節(jié) 梯度法(最速下降法) 一、 基本思想 梯度法又稱最速下降法，它是解析法的一種。在第二章里，我們已經(jīng)講過，函數(shù)在某一點的梯度方向即是函數(shù)值在此點的上升最快的方向。這也就是說，沿這一點的負(fù)梯度方向函數(shù)值下降最快。因此我們自然想到利用函數(shù)的負(fù)梯度方向作為搜索方向Sk。 設(shè)目標(biāo)函數(shù)f（x）在已知點Xk的梯度為： 則我們在設(shè)計空間中過Xk點選擇的搜索方向為： 最后提出： 問題轉(zhuǎn)化為求ak 值得到： 采用一維搜索求 ak。程序框圖如下： 二、 舉 例 例1：用梯度法求f（x）＝X21+25X22的極小點。 (1) 任選初始點x0＝(2，2)T (2)

27、 計算梯度 （3）求a0*使 最小。 a0* = 0.0200372 求得X1： （4）再從X1出發(fā)重復(fù)上述步驟。經(jīng)過若干次迭代即可求出極小點和極小值。 三、梯度法的討論 梯度法算法簡單，只用到目標(biāo)函數(shù)的一階導(dǎo)數(shù)．而且每次迭代計算工作量小，要求計算機的存貯量也較少。由于每次迭代都是沿函數(shù)值的最速下降方向，因而不管起始點x0取在何處，都能較快地接近極小值點，尤其是在開始的幾次選代時，函數(shù)值下降幅度很大?？墒窃诮咏鼧O小點時，目標(biāo)函數(shù)值卻下降很很慢，收斂也越來越慢。 改善梯度法的幾項措施： 1、

28、 選好初始點； 2、 進行變量轉(zhuǎn)換； 3、 改變迭代步長； 4、 采用平行切線法。 綜上所述，在工程設(shè)計中，單獨用梯度法來求解無約束最優(yōu)化問題是很少的。但是由于梯度法具有迭代過程簡單，計算工作量小，且韌始點可任選，收斂可靠等優(yōu)點，所以常將梯度法和其他方法結(jié)合使用，在開始階段用梯度法求得一個較優(yōu)的初始點，然后用其他收斂速度較快的方法來求得所需的極小點。 第五節(jié) 牛頓法 牛頓法也是解析法的一種，是最古老的求極值的方法之一。它的基本思想來源于用牛頓法求解方程的根。 設(shè)有—個一元函數(shù)φ(x)，要求φ(x)=0的根。 所得點的迭代公式為： 若求目標(biāo)函數(shù)f（x）的極小值，可

29、視為求方程f‘(x)＝o的根。設(shè)f(x)存在連續(xù)的一階、二階導(dǎo)數(shù)，則牛頓法求極值的迭代公式為： 經(jīng)過若干次迭代滿足： 則x*就是函數(shù)f（x）的極小點。 上述思想很容易推廣到求多元函數(shù)極值問題中。得迭代公式： 二、舉 例 求f（x）＝X21+25X22的極小點。 所以X1即為所求的極小點。 三、牛頓法討論 牛頓法的最大優(yōu)點是收斂速度快。也就是說．它的迭代次數(shù)相對其他方法來說，要少得多。特別是對于一些性態(tài)較好的目標(biāo)函數(shù)，例如二次函數(shù)，只需保證求梯度和海賽矩陣時的精度．不管初始點在何處，均可一步就找出最優(yōu)點。 可是牛頓法也有很大的缺點。首先，在每次迭代確定牛頓方向時，都要計

30、算目標(biāo)函數(shù)的一階導(dǎo)數(shù)和二階偏導(dǎo)數(shù)矩陣及其逆矩陣。這就使計算較為復(fù)雜，增加了每次選代的計算工作量。當(dāng)目標(biāo)函數(shù)維數(shù)較多時，計算量和存貯量都是以n2比例增加的。特別是在不易求導(dǎo)，用數(shù)值微分宋代替求導(dǎo)時，計算誤差會影響牛頓法的收斂速度。第二，從函數(shù)極值點的充分條件來看．為了保證牛頓方向Sk是目標(biāo)函數(shù)的下降方向，必須滿足： 要求：首先，H(xk)必須是可逆矩陣，即非奇異矩陣；其次，H(xk)必須是正定。第三，對于非二次函數(shù)，我們應(yīng)用泰勒級數(shù)展開．將函數(shù)簡化為—一個近似的二次函數(shù)。而在實際上，只有在函數(shù)極值點的很小的領(lǐng)域里，函數(shù)才能很接近于—個二次函數(shù)。在此范圍外用二次函數(shù)近似代替目標(biāo)因數(shù)，誤差是比

31、較大的， 也不能保證迭代—次就到達最優(yōu)點。更何況應(yīng)用牛頓選代公式時，步長是恒等于1的，這并不是最優(yōu)步長，也不能保證f（xk+1）< f（xk）。第四，對于非二次函數(shù)，采用牛頓法時初始點并不能任取，而是要求離極小點較近。否則，可能不收斂或是收斂到非極小點。 從下面的例子，我們可以看到初始點的選取對牛頓法的影響。 我們再求f(x)的二階導(dǎo)函數(shù)。 這兩點將函數(shù)劃分為三個區(qū)域： 討論一下當(dāng)初始點分別選在這三個區(qū)域內(nèi)時，用牛頓法的收斂情況。 為了克服上述這些缺點，人們又提出了一些改進的牛頓法。 1、 由于在極小值點附近，目標(biāo)函數(shù)總是趨近于一個二次函數(shù)

32、的，因此可以在一開始時．采用其他方法，例如梯度法，使xk處于極值點附近，然后再改用牛頓法，以加快收斂速度，達到較好的效果。 2、 我們還可以采用如下的迭代公式： 即阻尼牛頓法?？驁D如下： 第六節(jié) 共扼方向法 共扼方向法的最大特點是具有二次截止性。也就是說，在解決n維二次函數(shù)極小化問題時，最多只要做n次一維搜索即可求出極小值點。 一、 什么是共扼方向 滿足以下關(guān)系： 式中A為一個n ×n階對稱正定矩陣．則稱x和y是關(guān)于A共扼的。x及y兩個方向即稱為共扼方向。 如果有n個M維向量s1，s2，s3：，…，sn滿足以下條件: 則我們稱這n個向量是A共扼向量，它們的

33、方向稱共扼方向。 關(guān)于共扼方向的幾何概念可用圖3—16所示二維問題的幾何圖形來說明。 二、 共扼方向法的原理 設(shè)有一組m個n維向量s1，s2，s3：，…，sm彼此為Ａ共扼，即滿足： 則這m個向量一定是線性無關(guān)的。由于n維向量組最大的線性無關(guān)向量個數(shù)為n，所以n維向量空間最多可以找出n個彼此A共扼的向量，而其他任一方向均可由這n個向量的線性組合表示出來。 現(xiàn)在設(shè)有一個n維二次函數(shù)： 它的極小點為x*。若x。為任意給定的初始點，s1，s2，s3：，…，sn-1為關(guān)于A共扼的n個共扼方向，則有： 可見，只要求得了SK，a*k也就隨之可以求出．Xk+1也就可以求得了。

34、 第一個搜索方向為負(fù)梯度方向，沿這一方向搜索，X0 = (2,2)T得： 根據(jù)共扼方向的定義有： 任取a1= 1 則a2 =-625。得： 這就是所求極小值點。 三、如何構(gòu)造共扼方向 若在n維空間中．已知有n個單位向量： 第i個分量 則n個共扼方向是這樣來確定的： 通過S1和S2共扼得： 通過共扼關(guān)系得： 以此類推．可得： 且： 例： 經(jīng)過二次選代即收斂于極小點。 四、共扼梯度法 共扼梯度法的基本思想即是共扼方向法。任取一個起始點，經(jīng)過n次迭代，得到n個點，利用這n個點的梯度方向即構(gòu)成一組共扼方向。 具

35、體做法是這樣的，設(shè)有一個n維函數(shù)f(x)，用梯度法經(jīng)過n—1次迭代，即可得到n個選代點xo，xl，x2，…xn-1，這些點所對應(yīng)的函數(shù)的梯度為g1,g2, …gn-1。我們?nèi)∫唤M共扼方向如下： 經(jīng)過n次迭代后，如果目標(biāo)函數(shù)是二次型函數(shù)，則必然可收斂到極小點。采用這種方法構(gòu)成共扼方向，要用到函數(shù)的海賽矩陣，因此計算復(fù)雜，對A的要求也高，在實用上是存在困難的?，F(xiàn)在我們對以上公式作一些適當(dāng)?shù)暮喕?，得到求βk-1，的公式如下： 此廣中不合海賽矩陣A，因而免去了許多煩鎖的計算，而且不用擔(dān)心A的正定及非奇異問題,對初始點的選擇也就無任何限制了。 共扼梯度法的計算步驟及迭代公式如下

36、 (1)任選初始點Xo，則： 如此可構(gòu)造n個共扼方向s0，sl，s2，…，sn。 (3)對于每個迭代點及每個共扼方向，求a*，使： (4)按收斂判斷準(zhǔn)則判斷Xk+1，是否為極小點，若是，則可以停機，輸出結(jié)果；若不是，則應(yīng)繼續(xù)進行，直到滿足精度要求，求出極小值點為止。 對于n維二次函數(shù)，只用迭代n次，一定可以收斂到極小值點。若為非二次函數(shù)，則在迭代n次，得到x。點后，不一定就是極小值點。若經(jīng)過判斷不是，就應(yīng)令x0---xn，k--0重新構(gòu)造n個共扼方向，重復(fù)以上迭代過程。 第七節(jié) 變尺度法 變尺度法也是共扼方向法的一種。由于它避免了計算二階導(dǎo)數(shù)短陣及其求逆運

37、算，同時又具有較好的收斂性，對于計算高維的非線性問題還具有較好的穩(wěn)定性，因此是求最優(yōu)化問題的最有效方法之一。變尺度法的種類很多，這里我們只介紹其中最重要的兩種方法，DFP法和BFGS陽法。 一、基本原理 在尺度空間中，如果有—H為n x n階對稱正定矩陣，則定義： 為x的非歐氏范數(shù)，也稱X的尺度。 梯度法迭代公式為： 阻尼牛頓法迭代公式為： 梯度法和阻尼牛頓法的迭代公式可以統(tǒng)一寫成如下形式： Ak為變尺度矩陣(也稱近似矩陣)。Ak的構(gòu)成應(yīng)保證算法具有下降性、收斂性和計算的方便性。為此，必須做到以下四點： (1) 希望算法具有下降性，即滿足： (2)為使算法具有二次收斂性，必須

38、保證每次迭代的搜索方向Sk是關(guān)于H(xk)相互共扼的。 (3)為計算方便，我們希望變尺度矩陣具有以下的遞推形式： (4) Ak必須滿足擬牛頓條件。 二、DFP變尺度法 根據(jù)擬牛頓條件推出校正矩陣的計算公式為： 用此公式算出Ek后，即可按： 求出變尺度矩陣 Ak+1，并由此產(chǎn)生一個新的搜索方向： 然后可按一般步驟求得下一輪迭代點。 三、DFP變尺度法的計算步驟及算例 根據(jù)以上分析，DFP變尺度法的計算步驟如下： (1) 給定起始點Xo．精度ε，并令初始近似矩陣： (2) 計算vF(Xk )，并構(gòu)造搜索方向： (3) 過Xk點沿Sk進行一維搜索，求得ak*，則可得：

39、(4)檢驗迭代是否已滿足精度要求，即若： 則可停止迭代，最優(yōu)點即為： 否則，繼續(xù)執(zhí)行下一步。 (5)計算： (6)若在迭代了n次后仍達不到精度要求，為了加快收斂速度可重取Ak＝I：，再進行選代循環(huán)。也就是說，若A＝n，則令A(yù)k＝I，再轉(zhuǎn)到第二步，否則可進行下一步， (7)k＝k+1．轉(zhuǎn)到第二步。 四、BFGS變尺度法 DFP方法對于高維問題，由于收斂快，效果好，普遍被認(rèn)為是目前求解無約束最優(yōu)化問題最好的方法之一。但是它也存在數(shù)值穩(wěn)定性方面不夠理想的問題，對一維搜索的精度也要求較高。在70年代韌，又有人提出了另一種方法，稱為BFGS變尺度法，實際上，是對DFP方法的一種改進的方

40、法。 所改進之處是校正矩陣的計算： 其余和DFP方法完全一樣，計算校正矩陣復(fù)雜了，但對一維搜索的精度要求不高。 第八節(jié) 坐標(biāo)輪換法 直接解法。它們適用于以下場合： (1)目標(biāo)函數(shù)的導(dǎo)數(shù)很難求得它的解析式。 (2)目標(biāo)函數(shù)本身不是一個解析式或無法用解析式表達，例如目標(biāo)函數(shù)是一個二階常微分方程的解．而不是一個解析式； (3)對于維數(shù)不多的優(yōu)化設(shè)計問題，持別對于帶有離散變量的維數(shù)不多的問 題，有時用直接法較簡便。 一、坐標(biāo)輪換法的基本思想 坐標(biāo)輪換法的基本思想是把多維優(yōu)化問題轉(zhuǎn)化為一系列一維優(yōu)化問題。 二、算例 三、坐標(biāo)輪

41、換法的討論 第四章 線性規(guī)劃 工程中的最優(yōu)化設(shè)計問題絕大多數(shù)都是有約束的。有約束的最優(yōu)化設(shè)計問題可以分為兩類廣是目標(biāo)函數(shù)相約束函數(shù)均為線性函數(shù)，稱線性規(guī)劃問題；另一類是目標(biāo)函數(shù)和約束函數(shù)中至少有一個函數(shù)是非線性的，稱為非線性規(guī)劃問題。工程優(yōu)化設(shè)計多屬于后者。然而非線性規(guī)劃有時也可以用線性規(guī)劃在逐次逼近來求解，同時在生產(chǎn)管理領(lǐng)域內(nèi)(如制訂生產(chǎn)規(guī)劃、工藝方案等)也常常會遇到許多線性規(guī)劃問題，因此線性規(guī)劃在員優(yōu)化設(shè)計方法中仍占有雖要地位。 第一節(jié) 線性規(guī)劃的數(shù)學(xué)

42、模型 一、引 例 例1若有某水泥制品廠生產(chǎn)A、B兩種混合料。按照工廠的生產(chǎn)能力，每小時可生產(chǎn)A料14t，或B料7t，。從運輸眨離來講．每小時能運A科7t或B料12t，。按工廠的運輸能力，不論何種混合料，每小時只能運出物料8t已知生產(chǎn)4料所創(chuàng)造的經(jīng)濟價值為5元／t，B科為10元／t,試問該廠每小時能創(chuàng)造的最大經(jīng)濟價值為多少?這時每小時生產(chǎn)的A、B料各為多少? 設(shè)計變量： 目標(biāo)函數(shù)： 約束條件： 二、線性規(guī)劃的數(shù)學(xué)模型 為了得到線性規(guī)劃的數(shù)學(xué)模型，我們可以把上述引例的數(shù)學(xué)描述改寫為： 并滿足： 改寫后的數(shù)學(xué)表達式就是引例中線性規(guī)劃問題的數(shù)學(xué)模型。由此也就可以

43、寫出線性規(guī)劃數(shù)學(xué)模型的一般形式： 并滿足： 線性規(guī)劃的數(shù)學(xué)模型也可用矩陣的形式更簡潔地寫為： 并滿足： 第二節(jié) 線性規(guī)劃的基本原理 1． 可行解 滿足非負(fù)約束條件的約束方程的任何一個解都是可行解。 2． 基本解 若設(shè)計變量數(shù)為n．約束方程數(shù)為m，使n—m個變量值等于0，聯(lián)立解約束方程組所得到曲解稱為基本解。 3． 基本可行解 滿足非負(fù)條件的基本解稱基本可行解?；究尚薪饧仁腔窘猓彩强尚薪?。 4． 基本變量及基底 為得到基本解而使之不等于零的諸變量稱為基本變量?；咀兞康慕M合稱基底。 5． 最優(yōu)解及最優(yōu)基本解 目標(biāo)函數(shù)為最優(yōu)的可行解稱最優(yōu)解。目標(biāo)函數(shù)

44、為最優(yōu)的基本可行解稱最優(yōu)基本解。 第三節(jié) 單純形法 一、單純形法原理 首先找到一個基本可行解，作為迭代的初始頂點。然后從這個頂點移到另一個頂點，并判斷該頂點是否是員憂解，若是，則迭代結(jié)束，否則再移到另一個新頂點，再判斷，直到找到最優(yōu)點為止。這里關(guān)留要解決三個問題： (1)初始頂點(初始的基本可行解)如何確定? (2)怎樣使最優(yōu)搜索從一個頂點移到另一個頂點? (3)如何判斷所找到的頂點是不是最優(yōu)解? 首先讓我們來解決第一個問題。我們?nèi)杂蒙鲜鲆齺碚f明。 寫成向量形式： 令x1和x2為0，得初始可行基本解： 在求得初始基本可行解之后，我們就可以進一步去求新的基本

45、可行解，以實現(xiàn)從一個頂點轉(zhuǎn)移到另一個頂點。根據(jù)上述基變量所對應(yīng)的列向量所具有的特征，我們可以通過變換約束方程的系數(shù)和常數(shù)項，使一個非基本變量(X1或X2)和一個基本變量(X3、X4、X5)替換，從而找到新的基本可行解，即新的頂點。 已知初始基本可行解所對應(yīng)的增廣矩陣為： 既然是把X2，作為基本變量替換X3。增廣矩陣變成： 得新基本可行解： 可以證明在這里X2只能和第1個(即第1行)的基本變量X1（k）＝X3替換，而不能和其他基變量替換。 綜上所述，我們可以把求新頂點的方法歸納如下： 若己知具有m個線性獨立約束方程和n個變量的線性規(guī)劃的某個基本可行解(某個頂點)為

46、： 若想把非基本變量XQ去替換某個基本變量而進入基底必須按參數(shù)λl確定替換對象Xl(k)。 新的頂點(即新的基本可行解)所對應(yīng)的基本變量可用如下公式計算： 這時，增廣矩陣中的各個系數(shù)，應(yīng)按如下公式進行相應(yīng)的變化： 以上我們解決了怎樣從一個頂點轉(zhuǎn)移到另一個頂點。根據(jù)線性規(guī)劃的基本原理可知，最優(yōu)點必在可行區(qū)的頂點之中．因此每當(dāng)找到一個新的頂點，就需要判斷該頂點是不是最優(yōu)點。怎樣判斷一個頂點是否是優(yōu)點呢，若線性規(guī)劃問題為： 初始的基本可行解： 通過轉(zhuǎn)變新的基本解： 這時目標(biāo)函數(shù)為： 則說明任何一個新的可行解，其目標(biāo)函數(shù)值都比原來的大

47、(至少是相等)。所以原來的解x(k)(當(dāng)k＝0)時為初始基本可行解)就是最優(yōu)解。 且對某些i有a(k)iQ>0，則說明x(k)不是最優(yōu)解，必須進行頂點的轉(zhuǎn)移，也就是求新的基本可行解。用前面介紹過的方法，我們可以找到新的基本可行解： 且對所有i有a(k)iQ<0，則無最優(yōu)解。 二、單純形方法的計爵步驟及框圖 1、 將約束條件變換成等式，形成m階n維的線性規(guī)劃問題，求得起始基本可行解。 2、 對系數(shù)陣的每一列計算檢驗數(shù)： 對于初始基本可行解k=0。若每一列的檢驗數(shù)全部大于等于零．則x(k)即為最優(yōu)解，迭代結(jié)束。若某個檢驗數(shù)小于零且全部元素a(k)iQ<0，則此問題無

48、最優(yōu)解。 3、若某個檢驗數(shù)小于零且對于某些I有a(k)iQ>0，則選定Q列所對應(yīng)的變量xQ作為替換的非基本變量，求新的基本可行解。 4、再計算每一列的檢驗數(shù)，再判斷，如此迭代直至找到最優(yōu)解。 第四節(jié) 人造基變量 如果某線性規(guī)劃的約束條件為如下形式： 加入松弛變量后變?yōu)椋? 可見不能立即得到一個起始基本可行解。為了解決這個問題，我們可設(shè)法人工構(gòu)造一個基本可行解(稱人造基)作為已知的初始基本可行解。怎樣來構(gòu)成人造基呢? 若有n維m階的線性規(guī)劃問題： 現(xiàn)轉(zhuǎn)而求另一個線性規(guī)劃問題： 從而可找到起始基本可行解： 轉(zhuǎn)換后的線性規(guī)

49、劃問題的最優(yōu)解： 如果人造基變量始終不能從基底中替換出來，則說明原問題無最優(yōu)解。 第五章 非線性規(guī)劃 如果目標(biāo)函數(shù)和約束函數(shù)中至少有一個是非線性函數(shù)，那么這類優(yōu)化設(shè)計問題就稱為非線性規(guī)劃問題。 第一節(jié) SUMT方法(罰函數(shù)方法) 一、 SUMT方法的原理 SUMT方法即序列無約束極小化方法，亦稱罰函數(shù)法。它的基本思想是將原來的目標(biāo)函數(shù)相約束函數(shù)按一定的方式構(gòu)成一個新的函數(shù)。在這個新函數(shù)中，既包含目標(biāo)函數(shù)，又包臺全部約束條件及其一個可以變化的乘子。當(dāng)這個乘子按一定的方式改變時，就得到了一個新函數(shù)序列。顯然，求每一個新函數(shù)的最優(yōu)解都是一個無約束優(yōu)化問題。這樣我們就把一

50、個有約束的優(yōu)化問題轉(zhuǎn)化為一系列的無約束優(yōu)化問題。求解無約束優(yōu)化問題的最優(yōu)解可用第三章所介紹方法進行。所得到的最優(yōu)解序列將逐步逼近原問題的最優(yōu)解。 通過上面引例的分析，可以得到這樣一個啟示，約束非線性規(guī)劃問題可以通過構(gòu)造新目標(biāo)函數(shù)序列，用無約束優(yōu)化方法求解其極小點，并逐次逼近原問題的最優(yōu)點。即有約束的優(yōu)化設(shè)計問題可以轉(zhuǎn)化成一系列無約束極小化問題進行求解。在這里，關(guān)鍵是如何構(gòu)造這個新的目標(biāo)函數(shù)。對于上述內(nèi)點法所構(gòu)造的新目標(biāo)函數(shù)，它具有如下重要特征：當(dāng)在可行區(qū)內(nèi)某一點離開約束邊界較遠(yuǎn)時，其對應(yīng)的函數(shù)值是不很大的，而一旦某一點臨近約束邊界，其對應(yīng)的函數(shù)值就會陡然增大o這樣就可以保證在進行無約

51、束極小化時使每次找到的新點始終在可行區(qū)內(nèi)，而不會進入非可行區(qū)。因此這種函數(shù)就好像有個“圍墻”一樣，阻止最優(yōu)搜索進入非可行區(qū)．故有圍墻函數(shù)之稱，所引入的乘子rk常稱為障礙因子。根據(jù)這一特點，內(nèi)點法每次用無約束最優(yōu)化方法求極小點時，其初始點必須是可行區(qū)的內(nèi)點，而每次選定一個rk所找到的極小點也必然是內(nèi)點，即內(nèi)點法始終是在可行區(qū)的內(nèi)部進行最優(yōu)搜索。所以新目標(biāo)函數(shù)是圍墻函數(shù)的SUMT方法，又稱為別SUMT內(nèi)點法。 現(xiàn)在我們采用另一種方法對引例構(gòu)造新目標(biāo)函數(shù)： 由于是從非可行區(qū)通過求一系列的無約束極小點逐步逼近F(X)的最優(yōu)點，故稱此法為SUMT外點法。外點法的函數(shù)是一個懲罰函數(shù)，當(dāng)不滿足約

52、束條件時，其中的懲罰項將起作用。這就是用外點法構(gòu)造的新目標(biāo)函數(shù)的重要特點。 綜上所述，SUMT方法的基本原理可小結(jié)如下： 二、 內(nèi)點法例題及框圖 1、構(gòu)造圍墻函數(shù)： 2、rk＝r＝1，用無約束最優(yōu)化方法求圍墻函數(shù)由φ(X，rk)的極小點Xk*。 3、取rk+1=a*rk,a＝0.1求得φ(X，rk+1) 的極小點Xk+1。 4、 則Xk+1就是原問題的最優(yōu)點迭代停止，否則，轉(zhuǎn)步驟(3)，直到滿足控制精度要求為止。 三、外點法例題及框圖 例：二桿衍架的優(yōu)化設(shè)計 目標(biāo)函數(shù)： 約束函數(shù)： 懲罰函數(shù)：

53、 四、SUMT方法的討論 (1) 關(guān)于函數(shù)φ(X)的構(gòu)成 圍墻函數(shù)和罰函數(shù)的構(gòu)成可以是多種形式，但不管是什么形式，都必須滿足具有圍墻函數(shù)和罰函數(shù)的特征這一條件。 (2) 圍墻函數(shù)中障礙因子rk的起始值r0。選擇是否得當(dāng)．將顯著影響到SUMT內(nèi)點法的收斂速度。 (3) 在外點法中，初始懲罰因子R。和遞增系數(shù)β選得是否恰當(dāng)，對計算效率和 有效性同樣有顯著影響。 (4) 內(nèi)點法與外點法的比較 內(nèi)點法中用無約束優(yōu)化方法求解圍墻函數(shù)極小點時，初始點必須在可行區(qū)內(nèi)。 每次求得的極小點都是一個可行的設(shè)計方案，所以即使由于某種原因不易求得約束最優(yōu)點，也至少可以找到一個比較好的可行點

54、，這對工程優(yōu)化設(shè)計來說是具有現(xiàn)實意義的。外點法的初始點可以任意選擇，而且能夠處理等式約束，但它每次找到的極小點往往是不可行的，即使是最后按迭代收斂準(zhǔn)則所得到的最優(yōu)點也經(jīng)常是一個不可行點。因此，對于外點法所獲得的最優(yōu)點必須進行可行性檢查．必要時進行人工調(diào)整，以使其為可行點。 第二節(jié) 隨機方向搜索法 一、基本原理 隨機方向搜索法的迭代計算公式為： 1.隨機搜索方向的產(chǎn)生 隨機搜索方向的產(chǎn)生一般由下列步驟完成： 1、利用計算機產(chǎn)生偽隨機數(shù)的功能在[-1，1]區(qū)間內(nèi)得到均勻分布的隨機數(shù)，從而得到相應(yīng)的隨機單位向量。 2、個隨機單位向量計算m個隨機試驗點x(j)： 3、

55、 在m個隨機試驗點中選出目標(biāo)函數(shù)值最小的點x(L)，即： 4、 確定搜索方向 2.搜索步長的確定 確定搜索步長。的方法通常有兩種：一種是定步長，即按規(guī)定步長進行搜索。只要所得新點在可行域內(nèi)，并且其目標(biāo)函數(shù)是下降的，就按該步長繼續(xù)搜索，直到新點不滿足上述條件時才減小步長進行搜索。另一種方法是隨機變更步長，它是在搜索方向S上，根據(jù)目標(biāo)函數(shù)值的下降狀況和約束可行性條件，隨機調(diào)整步長大小進行搜索。這樣做可以充分利用S方向，減少計算工作量。 3.起始點的選擇 隨機方向搜索法的初始點x0必須是一個可行點。在選擇起始點時既可以憑經(jīng)驗人為地確定、也可以利用計算機產(chǎn)生的偽隨機效進行隨機選擇。隨

56、機選擇的具體步驟如下： 三、 算法和程序框圖 隨機方向法的算法如下： 1、選擇起始點x(0)．并檢驗其可行性。 2、產(chǎn)生m個隨機單位向量e(j)(j=1，2，…m)，選擇試驗步長因子H0， 由式(5—13)得到m個隨機點x(j)，并從中挑出最好的點X(l)，構(gòu)造搜索方向S(0)＝X(L)—X(O)。若選擇S(0)失敗則把試驗步長因子H0縮短到0.7H0，再重新確定。 3、由初始點x(0)出發(fā)，沿S(0方向搜索。步長因子H選為1.3H，若得到的新點是比x(0)更好的可行點，則繼續(xù)擴大步長，即H＝1.3H進行搜索，否則以縮小步長H=0.7H進行搜索。如此反復(fù)，直到得到目標(biāo)函數(shù)值不再下

57、降而又是可行的新點x，再將又作為下一次搜索的初始點x(0)，重復(fù)(2)，(3)步驟。 5、 收斂準(zhǔn)則： 三、隨機方向搜索法的討論 隨機方向搜索法的搜索過程僅僅需要提供目標(biāo)函數(shù)值和約束函數(shù)值的信息。因此它對函數(shù)的性態(tài)無特殊要求，使得程序結(jié)構(gòu)簡單，適應(yīng)面大。 另外，由于搜索方向是從許多方向中所選的使目標(biāo)函數(shù)值下降最快的最好的方向，因此它住往是比最速下降方向更好的方向(這一點可從圖5—9中明顯看出)。再加上在搜索道程中隨機變更步長因子，從而使得該法的收斂速度較快。 隨機方向搜索法的缺點是所得到的最擾解往往是局部最優(yōu)解。因此對于多峰函數(shù)，常需要多選擇幾個不同的初始點進行搜索．最后再

58、從它們的結(jié)果中選出最優(yōu)設(shè)計方案。 第三節(jié) 復(fù)合形法 一、復(fù)合形法的基本思路和步驟 1、 基本思路 復(fù)合形法的基本思路是在M維設(shè)計空間內(nèi)構(gòu)造由＆個可行點作為頂點的超多面體，該超多面體稱為復(fù)合形。顯然，復(fù)合形的每個頂點都代表一個設(shè)計方案。比較各個頂點所相應(yīng)的目標(biāo)函數(shù)值，判斷目標(biāo)函數(shù)值的下降方向，不斷地丟掉目標(biāo)函數(shù)值為最大的最差點，代之以既使目標(biāo)函數(shù)值有所改善又能滿足約束條件的新點，從而不斷地構(gòu)成新的復(fù)合形。如此重復(fù)計算，使新的復(fù)合形不斷地向員優(yōu)點移動和收縮，直到復(fù)合形本身小到一個預(yù)定的精度時，即可停止迭代，取得最優(yōu)解。 2．迭代步驟 (1) 確定復(fù)合形頂點。 (2) 計算各頂點的目標(biāo)

59、函數(shù)值，找出最差點，最好點和復(fù)合形中心。 (3) 求映像點。 (4) 檢查映像點的可行性。 (5) 比較映像點和最差點的目標(biāo)函數(shù)值。 (6) 檢查停機準(zhǔn)則。 三、 復(fù)合形法的例題 例3：用復(fù)合形法求極小化 第一輪搜索： (1)確定初始復(fù)合形頂點。 (2) 計算頂點的目標(biāo)函數(shù)值，找出最差點和次差點，并計算中心點及其目標(biāo)函數(shù)值，檢查停機準(zhǔn)則。 (3) 尋找映象點。 (4) 檢查x(a)的可行性： 可行。 (5) 比較映像點與最差點的目標(biāo)函數(shù)值。 用x(a)代替x(h)和其余3個頂點一起構(gòu)成新的復(fù)合形，從而進入新一輪搜索，程序?qū)⑥D(zhuǎn)向步驟(2)繼續(xù)進行。 三、復(fù)合

60、刑法討論 (I)復(fù)合形法僅僅依賴復(fù)合形頂點的目標(biāo)函數(shù)值和約束函數(shù)值所提供的信息來判斷尋優(yōu)方向和收斂淮則，不必計算目標(biāo)函數(shù)的一、二階導(dǎo)數(shù)和進行一維最優(yōu)化搜索，因此該法對目標(biāo)函數(shù)和約束函數(shù)的性態(tài)無特別的要求，程序也較簡單。但也正因為它所依賴的信息較少，而使其搜索的效率降低，并且不易收斂于最優(yōu)點。特別是當(dāng)設(shè)計變量相約束條件較多時，其搜索效率下降將更為顯著。 (2)起始復(fù)合形的頂點應(yīng)全部在可行區(qū)內(nèi)，人為地選定這些頂點在復(fù)雜的問題中是較為困難的。因此也注注采用上述隨機方向搜索按中所介紹的偽隨機數(shù)由計算機自動確定。 第四節(jié) 可行方向法 可行方向法也屬于一種直接搜索方法，但是其搜索方向的獲取

61、利用了目標(biāo)函數(shù)和約束函數(shù)的梯度信息。用目標(biāo)函數(shù)的梯度可以得到目標(biāo)函數(shù)值的下降方向，而利用約束函數(shù)的梯度則可以得到可行的搜索方向．因此，可行方向法的搜索方向?qū)嵸|(zhì)上是既使目標(biāo)函數(shù)值下降，同時又可行的方向，即可行下降方向。滿足這一條件的方法就稱為可行方向法。 一、可行方向法的基本原理 由于多數(shù)非線性規(guī)劃的最優(yōu)點都處在可行區(qū)的約束邊界上或者幾個約束邊界的交點上，因此最優(yōu)搜索如能沿著約束邊界附近進行，就有可能加速最優(yōu)化搜索的進程。按照這一基本思路，在任意選定一起始點后到最后得到最優(yōu)點必須解決三個問題：一是如何盡快使最優(yōu)搜索從起姑點到達約束邊界，二是到達邊界后怎樣判斷所找到的邊界點是否是最優(yōu)點；三是如

62、果邊界點經(jīng)判斷不是最優(yōu)點，那么下一步應(yīng)如何沿邊界進行最優(yōu)搜索。 1.如何從韌始點盡快到達邊界 搜索過程中可以確定為以下兩條原則：一是搜索方向由迭代點處于可行區(qū)還是非可行區(qū)而取負(fù)梯度方向或是梯度方向；二是搜索步長在第一次越過約束邊界前步長是逐次增加的，而此后不管迭代點是可行點還是非可行點都是逐次減小的。這兩條原則對于初始點為非可行點時也同樣適用。這種搜索方法的框圖如圖5—14所示。 2．如何判斷邊界點是否是最優(yōu)點 K—T條件： K7—T條件實際應(yīng)用時往往采用以下更方便的形式： 以此為基礎(chǔ)推出： 3．如何確定下一步的最優(yōu)搜索方向和步長 當(dāng)約束界面成上的設(shè)

63、計點經(jīng)判斷不符合K7—T條件而為非最優(yōu)點時，就必須繼續(xù)進行最優(yōu)搜索，確定最優(yōu)搜索方向。 把補償向量D的方向作為最優(yōu)搜索方向。D的方向總是指向最優(yōu)點而不會背離最優(yōu)點，所以沿這個方向進行搜索有可能向最優(yōu)點逼近。然而，由于沿D方向前進有可能進入非可行區(qū)，因此沿D方向走一步后，就應(yīng)該沿▽F方向再回到約束邊界面上，得到新的界面點，再判斷其是否為最優(yōu)點，如此反復(fù)，直到逼近最優(yōu)點正滿足預(yù)定精度要求為止。 步長的確定： 先任意給定S(為了不至于使計算機溢出，建議不要超過20)．找到XK+2后．若有： S減半，重找XK+2直到 確定了步長，搜索。如果經(jīng)過若干次最優(yōu)搜索，發(fā)現(xiàn)目標(biāo)函數(shù)雖然能夠逐步

64、減小，但下降速度很慢，那么可以自動加大步長S．使收斂速度加快。按上述方法反復(fù)迭代，就可以自動找到一系列合適的步長，使最優(yōu)搜索如圖5—16b)那樣一步一步逼近最優(yōu)點，并在給定的精度范圍內(nèi)收斂于最優(yōu)點x?？尚蟹较蚍ǖ目驁D如圖5—18所示。 三、可行方向法的討論 (1)從上面分析可看出，可行方向法的使用條件是最優(yōu)點必須在可行區(qū)的約束界面上。它既可以在一個約束的界面上，也可以在幾個約束界面的交點上。如果最優(yōu)點不在約束界面上，而在可行區(qū)的內(nèi)部，那么此方法將失效。 (2)由于可行方向法大致沿著約束界面向最優(yōu)點逼近．因此其收斂速度較快，效果較好。這使得該法適用于大中型約束優(yōu)化問題。 (3)可行

65、方向法的缺點是需要計算目標(biāo)函數(shù)和約束函數(shù)和一階偏導(dǎo)數(shù)來獲得梯度。這就增加了求解的困難度，特別是對于不易求導(dǎo)數(shù)的函數(shù)，還需要用差分法求偏導(dǎo)數(shù)的近似值，這不僅增加了程序上的復(fù)雜性，而且使計算精度也受到影響。 第六章 若干其他景優(yōu)化方法及應(yīng)用 第一節(jié) 幾何規(guī)劃 幾何規(guī)劃的特點： (1)有相當(dāng)一部分工程優(yōu)化問題都可描述成幾何規(guī)劃的形式。 (2)幾何規(guī)劃有兩個突出的優(yōu)點：一是能解非線性程度高的優(yōu)化數(shù)學(xué)模型；二是能解變量多的優(yōu)化問題。也就是說幾何規(guī)劃的解題規(guī)模和變量個數(shù)無直接的關(guān)系。 (3)在一般情況下可求得全局最優(yōu)解。 一、 何規(guī)劃的基本原理

66、 幾何規(guī)劃所依據(jù)的理論基礎(chǔ)是著名的算術(shù)幾何均值定理： 二、 正定幾何規(guī)劃 所謂正定幾何規(guī)劃，就是目標(biāo)函數(shù)和約束函數(shù)的各項均為正項這一類幾何規(guī)劃問題。 1． 無約束情況 無約束情況下正定幾何規(guī)劃描述為： 若假設(shè)目標(biāo)函數(shù)達到最優(yōu)值時，函數(shù)中的第j項在其中所占比例為： 規(guī)一性條件和正交性條件。 即f(x)的極小值等于d(W)的極大值。這樣，我們就把原問題轉(zhuǎn)化為求其對偶問題。求出了d(W)的極大值就間接等同于求出了f(x)的極小值，具體求解步驟如下: (1) 求解問題的對偶問題 (2) 根據(jù)最優(yōu)值f*和最優(yōu)分配W*求最優(yōu)點X。 2． 有約束情況 有約束情況下正定幾何規(guī)劃可描述為： 顯然有約束條件下的幾何規(guī)劃也有困難度問題，和無約束情況一樣，對偶問題的變量效也是多項式的總項效，所不同的是，總項數(shù)T應(yīng)包括目標(biāo)函數(shù)和約束函數(shù)項數(shù)之總和，即： 規(guī)一性和正交性條件產(chǎn)生的約束方程數(shù)仍為n+l，故困難度為： 三、廣義幾何規(guī)劃 正定幾何規(guī)劃要求目標(biāo)函數(shù)和約束函數(shù)均為正定多項式，但工程實際問題往往