第五章約束優(yōu)化方法

1

第五章約束優(yōu)化方法

5.1約束優(yōu)化問題的最優(yōu)解5.2約束優(yōu)化問題極小點的條件

5.3常用的約束優(yōu)化方法

5.3.1約束坐標輪換法5.3.2約束隨機方向法5.3.3復合形法5.3.5懲罰函數法2概述約束優(yōu)化問題最優(yōu)解最優(yōu)值最優(yōu)點約束最優(yōu)解和無約束最優(yōu)解無論是在數學模型上還是幾何意義上均是不同的概念3等值線等值線族的中心無約束最優(yōu)解解：等值線的共同中心.數學模型:4數學模型:可行域約束最優(yōu)解

5無約束最優(yōu)點約束最優(yōu)點6約束優(yōu)化問題的類型

1.不等式約束優(yōu)化問題(IP型)2.等式約束優(yōu)化問題(EP型)3.一般約束優(yōu)化問題(GP型)7約束優(yōu)化方法分類約束優(yōu)化方法

約束坐標輪換法直接法：約束隨機方向法

復合形法間接法：懲罰函數法

直接法：設法使每一次迭代產生的新迭代點限制在可行域內，且一步一步的降低目標函數值，直至最后獲得一個可行域內的約束最優(yōu)解。間接法：將約束優(yōu)化問題通過一定形式的變換，轉化為無約束優(yōu)化問題，然后采用約束優(yōu)化方法進行求解。85.3.1約束坐標輪換法基本思想:與無約束坐標輪換法類似,依此沿坐標軸方向尋優(yōu),逐步逼近最優(yōu)點。9任取一個初始點取初始步長α0沿e1方向檢查可行性:適用性:檢查......加速步長檢查可行性:適用性:10沿e2方向檢查可行性:適用性:檢查可行性:適用性:檢查可行性:適用性:檢查可行性:適用性:11沿e1方向檢查可行性:適用性:檢查可行性:適用性:沿e2方向檢查可行性:適用性:檢查......12沿坐標軸方向找不到合適的點:縮減初始步長

α0←0.5α0

繼續(xù)迭代終止準則:

α0≤ε約束坐標輪換法與無約束坐標輪換法的區(qū)別：①步長

無約束:最優(yōu)步長

約束:加速步長②對每一個迭代點的檢查

無約束:檢查適用性

約束:檢查適用性和可行性③終止準則

無約束:點距準則

約束:步長準則13特點:約束坐標輪換法具有算法明了、迭代簡單、便于設計者掌握運用等優(yōu)點。但是，它的收斂速度較慢，對于維數較高的優(yōu)化問題(例如10維以上)很費機時。另外，這種方法在某些情況下還會出現“死點”的病態(tài)，導致輸出偽最優(yōu)點。

避免輸出偽最優(yōu)點的辦法:1、輸入不同的初始點2、用不同的不長多次計算14基本原理：典型的“瞎子爬山”式的數值選代解法。在可行域內，任選初始點x(0)，以給定的步長a=a0

，沿按某方法產生的隨機方向S(1)取探索點x=x(0)+aS(1），若該點同時符合下降性（F(x)<F(x(0)))和可行性（x∈D)則表示x點探索成功。并以它為新的起始點，繼續(xù)按上面的迭代公式在S(1）方向上獲取新的成功探索點……..

5.3.2約束隨機方向法155.3.2約束隨機方向法任取一個初始點取初始步長α0利用隨機函數構成隨機方向S(1)

檢查可行性:適用性:檢查若m個方向都不行,則減小步長:α0←0.5α0終止準則:

α0≤ε16說明當在某個轉折點處沿m個(預先限定的次數)隨機方向試探均失敗，則說明以此點為中心，α0為半徑的圓周上各點都不是適用、可行點。此時，可將初始步長α0縮半后繼續(xù)試探。直到α0≤ε，且沿m個隨機方向都試探失敗時，則最后一個成功點(如圖中的x(3))就是達到預定精度ε要求的約束最優(yōu)點，迭代即可結束。m是預先規(guī)定在某轉折點處產生隨機方向所允許的最大數目。一般可在50~500范圍內選取。約束隨機方向法的搜索方向比坐標輪換法要靈活得多。當預定的隨機方向限定數m足夠大時，它不會像約束坐標輪換法那樣出現“病態(tài)”而導致輸出偽最優(yōu)點。

17隨機搜索方向的產生在（a,b）之間的隨機數：yi=ai+

(bi–ai)

（-1,1）之間的隨機數：yi=2-1設是在區(qū)間(一l，1)上的兩個隨機數。將它們分別作為坐標軸上的分量所構成的向量即為相應的二維隨機向量，其單位向量：同理，n維問題,隨機方向的單位向量：在算法語言所使用的函數庫中，有一種隨機函數RND(X)。利用這一隨機函數可在程序運行過程中產生一個0到1之間的隨機數。

(i＝l，2，…，n)18約束隨機方向搜索法的特點：對目標函數的性態(tài)無特殊要求，程序設計簡單，使用方便。在維數較少的情況下是一種十分有效的方法，適用于小型問題。195.3.3復合形法基本思想：在可行域中選取K個點作為一復合形（多面體）的K個頂點。比較各點函數值的大小，去掉函數值最大所對應的最壞點，而代之最壞點的映射點構成新的復合形。不斷重復上述過程，使復合形不斷向最優(yōu)點移動和收縮，直至滿足選代精度為止。

132X0X(R)n+l≤k≤2n20[引例]

設有一約束優(yōu)化問題的數學模型21一、復合形法的基本思想步驟：第一步：初始復合形的構成

頂點X(1)、X(2)、X(3)第二步：對復合形進行

調優(yōu)迭代計算頂點X(1)、X(2)、X(3)

F1>F2>F3

↓↓

X(H)

X(L)

壞點好點先求出除壞點外，其余各點構成的圖形的形心點X0再求壞點X(H)相對于形心點X0的映射點

X(R)132X0X(R)22步驟：第一步：初始復合形的構成

第二步：對復合形進行調優(yōu)迭代計算

形心點X0

映射點

X(R)

α:反射系數，一般開始是取α=1.3132檢查可行性:適用性:新復合形4點的映射復合形的收縮23二、初始復合形的構成

方法一:試湊法方法二:隨機產生(1)產生K個隨機點隨機數

(i＝l，2，…，n)(2)將非可行點調入可行域123424終止條件:25例:用復合形法求解下例約束最優(yōu)化問題，迭代精度取

解：取復合形的頂點數:(1)獲得初始復合形:本例采用人為給定四個點檢驗各點是否可行：將各點的坐標值代入以上三個約束方程，均滿足約束要求，這四個點為可行點，用作初始復合形的四個頂點26(2)迭代計算獲得新復合形計算復合形各頂點目標函數值，

定出最壞點最好點計算除壞點外其余各頂點的中心

將代入諸約束條件均滿足，可知在可行城內。

取，求壞點的映射點

在可行域內

27計算并與比較：

用替換，亦即替換構成新的復合形：

比較各點目標函數值，定出最壞點:最好點:

（3）檢驗迭代終止條件

2829復合形法的特點:

對目標函數及約束函數無特殊要求，適應性強，計算量一般，收斂較快，適用中小型問題。是現有解不等式約束優(yōu)化問題的一種重要的直接法。305.3.5懲罰函數法將約束優(yōu)化問題通過一定形式的變換，轉化為無約束優(yōu)化問題，然后采用約束優(yōu)化方法進行求解轉化必須滿足條件：1、不破壞原約束問題的約束條件，

2、最優(yōu)解必須歸結到原約束問題的最優(yōu)解上去。約束優(yōu)化問題的間接法有:消元法、拉格朗日乘子法、

懲罰函數法等.31minφ(x，r(k)，m(k)) (5.56)x∈Rn式中，φ(x，r(k)，m(k))為增廣函數，稱為懲罰函數，簡稱罰函數

將一般約束優(yōu)化問題數學模型minF(x)x∈Rn：gu(x)≥0，u＝l，2，…，phv(x)=0，v=1，2，…，q轉化成為一個如下的無約束優(yōu)化問題構造的新目標函數一般形式為懲罰函數法懲罰項32按照懲罰函數構成的形式不同，懲罰函數法又分為三種：1、內點懲罰函數法2、外點懲罰函數法3、混合懲罰函數法33一、內點懲罰函數法基本思想：將新目標函數定義于可行域內，序列迭代點在可行域內逐步逼近原目標函數約束邊界上的最優(yōu)點。將約束優(yōu)化問題：

minF(x)x∈:gu(x)≥0(u=12……m)轉化為無約束優(yōu)化問題

其中：r(1)>r(2)>r(3)…>r(k)…>0是一個遞減的正值數列：

r(k)＝Cr(k-1)，

0＜C＜1

(k)=0

34內點懲罰函數法的思路:當X由可行域內靠近任一約束邊界時,懲罰項值趨于無窮大,所以它就像圍墻一樣阻止迭代點越出約束邊界.條件1：不破壞原約束問題的約束條件35minф(x,r(k))=min{F(x)+r(k)∑（1/gu(x)）}條件2：最優(yōu)解必須歸結到原約束問題的最優(yōu)解上去36解：若用內點法求解此約束最優(yōu)化問題，由式知懲罰函數為將函數對求導，得:令:解得無約束極小值的點列為

:例:用內點法求解

的約束最優(yōu)化問題。

無約束極小值點列相應的懲罰函數值為

3738序列極小點都在可行域內39初始點x(0)的確定

自定法:搜索法

先任取一個設計點x(k)；計算x(k)點的諸約束函數值gu(x(k))，u＝1，2，…，p若：構造：按照該數學模型解出的最優(yōu)點x*，至少比原設計點x(k)多滿足一個約束條件

重復數次，直到所有的約束條件都得到滿足，最終可取得在可行域內部的初始點x(0)。40

關于幾個參數的選擇(1)初始罰因子r(0)的選取一般可取初始罰因子r(0)＝1~50也有建議?。?2)遞減系數C的選擇

通常建議取C＝0.1~0.541內點懲罰函數法的特點:在給定一個可行初始方案后，能求出一系列逐步得到改進的可行的設計方案。但只適用于解不等式約束優(yōu)化問題，且初始點須在可行域內。42=

已知約束優(yōu)化問題:試寫出內點罰函數,并選出初始迭代點.內點罰函數:例：43例：桁架設計問題：minF(x)=1.57x1

x=[x1x2]T∈

44設有不等式約束優(yōu)化問題：構造外點法懲罰函數的常見形式如下：懲罰因子r(k)規(guī)定取正。且在優(yōu)化過程中r(k)取為遞增數列

r(k)=Cr(k-1)，C＞1則將保證(k)=∞二、外點懲罰函數法基本思想：將新目標函數定義于可行域外，序列迭代點在可行域外逐步逼近原目標函數約束邊界上的最優(yōu)點。45式中:外點懲罰函數法的思路：可行域內時,新目標函數就是原目標函數,當X位于可行域外時,懲罰項為正值,新目標函數值增大,就構成了對不滿足約束條件時的一種”懲罰”.且離可行域越遠,懲罰就越嚴厲.當r(k）不夠大時，罰函數（新目標函數）的極小值在可行域外，即懲罰不夠，可加大r(k），隨著r(k）的增大，使新目標函數）的極小點越來越逼近原目標函數極小點?？尚杏蛲饪尚杏騼?6對于解不等式約束優(yōu)化問題minF(x)＝xx∈R1

：g1(x)=x－1≥0用外點法構造懲罰函數，具體構造形式如下：寫成另一種形式例47令:解得無約束極小值的點列為

:無約束極小值點列相應的懲罰函數值為

求懲罰函數極小點:

48由此可見，當懲罰因子為一遞增正值數列時，其極值點離約束最優(yōu)點愈來愈近，的差值與愈來愈小。當時，，亦即逼近于真正的約束最優(yōu)解。無約束極值點列隨值遞增從可行域外向最優(yōu)點收斂。

49對幾個問題的討論初始點x(0)的選取:外點法的初始點x(0)可以任選，即在可行域與非可行域選取均可。(2)初始罰因子r(0)和遞增系數C的選取初始罰因子r(0)選得是否恰當，對算法的成敗和計算速度仍有著顯著的影響。因此，選取時要謹慎。遞增系數C的取值，一般影響不太顯著，但也不宜取得過大。通常取C＝5~10。(3)約束容差帶用外點法求解時，由于罰函數的無約束最優(yōu)點列是從可行域外部向約束最優(yōu)點逼近的，所以最終取得的最優(yōu)點一定是在邊界的非可行域一側。嚴格地說，它是一個非可行點。這對某些工程問題可能是不允許的。為了解決這一問題?？稍诩s束邊界的可行域一側加一條容差帶，如圖5.21。這就相當于將約束條件改為gu(x)－δu≥0，u=1，2，…，p式中的δu是容差量，一般可取δu=10－3~10－4。

50約束容差帶。51外點法不但可以解不等式約束優(yōu)化問題，而且還可以解等式約束優(yōu)化問題

用外點法求解二維等式約束優(yōu)化問題：按外點法的基本思想，構造懲罰函數52

外點法的特點外點法既可解不等式約束優(yōu)化問題，也能解等式約束優(yōu)化問題，且其初始點x(0)可任選，即在可行域中或非可行域中均可。其缺點是序列無約束最優(yōu)點是一系列的非可行點，對于工程設計一般是不可取的。為使最終的迭代點能落入可行域，必須設置約束容差帶。53例：已知約束優(yōu)化問題:試寫出外點罰函數,并選出初始迭代點.外點罰函數:54三、混合法

用罰函數法解決有等式約束和不等式約束的一般約束（GP型）優(yōu)化問題的方法，把它稱為混合懲罰函數法，簡稱混合法。

一般約束優(yōu)化問題的數學模型

minf(x)x∈DD:gu(x)≥0(u=12……p)hv(x)=0(v=12……q,q<n)55內點形式的混合型懲罰函數法r(k)---遞減m(k)---遞增初始點必須是嚴格的內點為了統(tǒng)一用一個內點法懲罰因子,上式也可寫成:不等式約束部分按內點法形式處理r(k)---遞減56r(k)---遞增外點形式的混合型懲罰函數法不等式約束部分按外點法形式處理57如何判斷優(yōu)化結果的正確性:1、約束優(yōu)化問題，最優(yōu)點大多位于邊界上。2、輸入不同的初始點多次計算。3、用不同的方法解。上機：第七周周一和周三晚上18:00-21：001、了解各種方法的基本思想和特點2、P130題237應用實例一、機械優(yōu)化設計的一般過程機械優(yōu)化設計的全過程一般可分為如下幾個步驟:1)建立優(yōu)化設計的數學模型。

2)選擇適當的優(yōu)化方法。

3)編寫計算機程序。

4)準備必要的初始數據并上機計算。

5)對計算機求得的結果進行必要的分析。其中建立優(yōu)化設計數學模型是首要的和關鍵的一步，它是取得正確結果的前提，優(yōu)化方法的選擇取決于數學模型的特點，例如優(yōu)化問題規(guī)模的大小，目標函數和約束函數的性態(tài)以及計算精度等。在比較各種可供選用的優(yōu)化方法時，需要考慮的一個重要因素是計算機執(zhí)行這些程序所花費的時間和費用，也即計算效率。正確地選擇優(yōu)化方法，至今還沒有一定的原則。通常認為，對于目標函數和約束函數均為顯函數且設計變量個數不太多的回題，懲罰函數法較好;對函數易于求導的問題，以可利用導數信息的方法為好;對求導非常困難的問題則應選用直接解法，例如復合形法;對于高度非線性的函數，則應選用計算穩(wěn)定性較好的方法，例如BFGS變尺度法和內點懲罰函數法相結合的方法。編寫計算機程序對于使用者來說，已經沒有多少工作要做了，因為已有許多成熟的優(yōu)化方法程序可供選擇。使用者只需要將數學模型按要求編寫成子程序嵌入已有的優(yōu)化程序即可。步驟4)和5)對機械設計工作者來說，通常不存在原則上的困難。建立數學模型的基本原則建立數學模型的基本原則是優(yōu)化設計中的一個重要組成部分。優(yōu)化結果是否可用，主要取決于所建立數學模型是否能夠確切而又簡潔地反映工程問題的客觀實際。在建立數學模型時，片面地強調確切，往往會使數學模型十分冗長、復雜，增加求解問題的困難程度，有時甚至會使問題無法求解;片面強調簡潔，則可能使數學模型過份失真，以致失去了求解的意義。合理的做法是在能夠確切反映工程實際問題的基礎上力求簡潔。設計變量、目標函數和約束條件是組成優(yōu)化設計數學模型的三要素，下面分別予以討論。1.設計變量的選擇機械設計中的所有參數都是可變的，但是將所有的設計參數都列為設計變量不僅會使問題復雜化，而且是沒有必要的。例如材料的機械性能由材料的種類決定，在機械設計中常用材料的種類有限，通?？筛鶕枰徒涷炇孪冗x定，因此諸如彈性模量、泊松比、許用應力等參數按選定材料賦以常量更為合理;另一類狀態(tài)參數，如功率、溫度、應力、應變、撓度、壓力、速度、加速度等則通?？捎稍O計對象的尺寸、載荷以及各構件間的運動關系等計算得出，多數情況下也沒有必要作為設計變量。因此，在充分了解設計要求的基礎上，應根據各設計參數對目標函數的影響程度認真分析其主次，盡量減少設計變量的數目，以簡化優(yōu)化設計問題。另外還應注意設計變量應當相互獨立，否則會使目標函數出現“山脊”或“溝谷”，給優(yōu)化帶來困難。2.目標函數的確定目標函數是一項設計所追求的指標的數學反映，因此對它最基本的要求是能夠用來評價設計的優(yōu)劣，同時必須是設計變量的可計算函數。選擇目標函數是整個優(yōu)化設計過程中最重要的決策之一。有些問題存在著明顯的目標函數，例如一個沒有特殊要求的承受靜載的梁，自然希望它越輕越好，因此選擇其自重作為目標函數是沒有異議的。但設計一臺復雜的機器，追求的目標往往較多，就目前使用較成熟的優(yōu)化方法來說，還不能把所有要追求的指標都列為目標函數，因為這樣做并不一定能有效地求解。因此應當對所追求的各項指標進行細致的分析，從中選擇最重要最具有代表性的指標作為設計追求的目標。例如一架好的飛機，應該具有自重輕、凈載重量大，航程長，使用經濟，價格便宜，跑道長度合理等性能，顯然這些都是設計時追求的指標。但并不需要把它們都列為目標函數，在這些指標中最重要的指標是飛機的自重。因為采用輕的零部件建造的自身重量最輕的飛機只會促進其它幾項指標，而不會損害其中任何一項。因此選擇飛機自重作為優(yōu)化設計的目標函數應該是最合適的了。若一項工程設計中追求的目標是相互矛盾的，這時常常取其中最主要的指標作為目標函數，而其余的指標列為約束條件。也就是說，不指望這些次要的指標都達到最優(yōu)，只要它們不致于過劣就可以了。在工程實際中，應根據不同的設計對象，不同的設計要求靈活地選擇某項指標作為目標函數。以下的意見可作為選擇時的參考。對于一般的機械，可按重量最輕或體積最小的要求建立目標函數;對應力集中現象尤其突出的構件，則以應力集中系數最小作為追求的目標，對于精密儀器，應按其精度最高或誤差最小的要求建立目標函數。在機構設計中，當對所設計的機構的運動規(guī)律有明確的要求時，可針對其運動學參數建立目標函數;若對機構的動態(tài)特性有專門要求，則應針對其動力學參數建立目標函數;而對于要求再現運動軌跡的機構設計，則應根據機構的軌跡誤差最小的要求建立目標函數。3.約束條件的確定約束條件是就工程設計本身而提出的對設計變量取值范圍的限制條件。和目標函數一樣，它們也是設計變量的可計算函數。如前所述，約束條件可分為性能約束和邊界約束兩大類。性能約束通常與設計原理有關，有時非常簡單，如設計曲柄連桿機構時，按曲柄存在條件而寫出的約束函數均為設計變量的線性顯函數;有時卻相當復雜，如對一個復雜的結構系統(tǒng)，要計算其中各構件的應力和位移，常采用有限元法，這時相應的約束函數為設計變量的隱函數，計算這樣的約束函數往往要花費很大的計算量。3.約束條件的確定在選取約束條件時應當特別注意避免出現相互矛盾的約束。因為相互矛盾的約束必然導致可行域