1

第五章約束優化方法

5.1約束優化問題的最優解5.2約束優化問題極小點的條件

5.3常用的約束優化方法

5.3.1約束坐標輪換法5.3.2約束隨機方向法5.3.3復合形法5.3.5懲罰函數法1

第五章約束優化方法5.1約束優化問題的最優解2概述約束優化問題最優解最優值最優點約束最優解和無約束最優解無論是在數學模型上還是幾何意義上均是不同的概念2概述約束優化問題最優解最優值最優點約束最優解和無約束最優解3等值線等值線族的中心無約束最優解解：等值線的共同中心.數學模型:3等值線等值線族的中心無約束最優解解：等值線的共同中心.數學4數學模型:可行域約束最優解

4數學模型:可行域約束最優解

5無約束最優點約束最優點5無約束最優點約束最優點6約束優化問題的類型

1.不等式約束優化問題(IP型)2.等式約束優化問題(EP型)3.一般約束優化問題(GP型)6約束優化問題的類型1.不等式約束優化問題(IP型)2.7約束優化方法分類約束優化方法

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

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

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

α0←0.5α0

繼續迭代終止準則:

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

無約束:最優步長

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

無約束:檢查適用性

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

無約束:點距準則

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

避免輸出偽最優點的辦法:1、輸入不同的初始點2、用不同的不長多次計算13特點:約束坐標輪換法具有算法明了、迭代簡單、便于設計者掌14基本原理：典型的“瞎子爬山”式的數值選代解法。在可行域內，任選初始點x(0)，以給定的步長a=a0

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

5.3.2約束隨機方向法14基本原理：典型的“瞎子爬山”式的數值選代解法。在可行域內155.3.2約束隨機方向法任取一個初始點取初始步長α0利用隨機函數構成隨機方向S(1)

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

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

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

(bi–ai)

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

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

132X0X(R)n+l≤k≤2n195.3.3復合形法基本思想：在可行域中選取K個點作為20[引例]

設有一約束優化問題的數學模型20[引例]設有一約束優化問題的數學模型21一、復合形法的基本思想步驟：第一步：初始復合形的構成

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

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

F1>F2>F3

↓↓

X(H)

X(L)

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

X(R)132X0X(R)21一、復合形法的基本思想步驟：132X0X(R)22步驟：第一步：初始復合形的構成

第二步：對復合形進行調優迭代計算

形心點X0

映射點

X(R)

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

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

(i＝l，2，…，n)(2)將非可行點調入可行域123423二、初始復合形的構成方法一:試湊法隨機數24終止條件:24終止條件:25例:用復合形法求解下例約束最優化問題，迭代精度取

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

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

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

取，求壞點的映射點

在可行域內

26(2)迭代計算獲得新復合形計算復合形各頂點目標函數值27計算并與比較：

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

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

（3）檢驗迭代終止條件

27計算并與比較：用替換282829復合形法的特點:

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

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

懲罰函數法等.305.3.5懲罰函數法將約束優化問題通過一定形式的變換31minφ(x，r(k)，m(k)) (5.56)x∈Rn式中，φ(x，r(k)，m(k))為增廣函數，稱為懲罰函數，簡稱罰函數

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

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

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

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

0＜C＜1

(k)=0

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

:例:用內點法求解

的約束最優化問題。

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

36解：若用內點法求解此約束最優化問題，由式知懲罰函數為將函373738序列極小點都在可行域內38序列極小點都在可行域內39初始點x(0)的確定

自定法:搜索法

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

重復數次，直到所有的約束條件都得到滿足，最終可取得在可行域內部的初始點x(0)。39初始點x(0)的確定若：構造：按照該數學模型解出的最優40

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

通常建議取C＝0.1~0.540關于幾個參數的選擇一般可取初始罰因子r(0)＝1~5041內點懲罰函數法的特點:在給定一個可行初始方案后，能求出一系列逐步得到改進的可行的設計方案。但只適用于解不等式約束優化問題，且初始點須在可行域內。41內點懲罰函數法的特點:42=

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

x=[x1x2]T∈

43例：桁架設計問題：minF(x)=1.57x144設有不等式約束優化問題：構造外點法懲罰函數的常見形式如下：懲罰因子r(k)規定取正。且在優化過程中r(k)取為遞增數列

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

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

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

求懲罰函數極小點:

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

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

49對幾個問題的討論50約束容差帶。50約束容差帶。51外點法不但可以解不等式約束優化問題，而且還可以解等式約束優化問題

用外點法求解二維等式約束優化問題：按外點法的基本思想，構造懲罰函數51外點法不但可以解不等式約束優化問題，而且還可以解等式約束52

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

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

一般約束優化問題的數學模型

minf(x)x∈DD:gu(x)≥0(u=12……p)hv(x)=0(v=12……q,q<n)54三、混合法

用罰函數法解決有等式約束和不等式約束的一般約55內點形式的混合型懲罰函數法r(k)---遞減m(k)---遞增初始點必須是嚴格的內點為了統一用一個內點法懲罰因子,上式也可寫成:不等式約束部分按內點法形式處理r(k)---遞減55內點形式的混合型懲罰函數法r(k)---遞減不等式約束56r(k)---遞增外點形式的混合型懲罰函數法不等式約束部分按外點法形式處理56外點形式的混合型懲罰函數法不等式約束部分按外點法形式處理57如何判斷優化結果的正確性:1、約束優化問題，最優點大多位于邊界上。2、輸入不同的初始點多次計算。3、用不同的方法解。作業：1、了解各種方法的基本思想和特點2、P130題23757如何判斷優化結果的正確性:58機械優化舉例：已知給定軌跡曲線，其上１２個主要點的坐標見下表，并給定

（該機構主要傳遞運動，對動力特性要求不高）。試設計一曲柄搖桿機構，使其連桿上點Ｍ的連桿曲線最佳逼近已知