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

機械優(yōu)化設(shè)計中的問題，大多數(shù)屬于約束優(yōu)化設(shè)計問題，其數(shù)學(xué)模型為§6.1概述目前一頁\總數(shù)一百零一頁\編于三點§6.1概述

直接解法：隨機方向搜索法、復(fù)合形法、可行方向法等

間接解法：內(nèi)點懲罰函數(shù)法、外點懲罰函數(shù)法、混合懲罰函數(shù)法增廣乘子法等一.有約束問題解法分類：二.直接解法的基本思想：

合理選擇初始點，確定搜索方向，在可行域中尋優(yōu)，經(jīng)過若干次迭代，收斂至最優(yōu)點。

Xk+1=Xk+αkdkdk::

可行搜索方向。即設(shè)計點沿該方向作微量移動時,目標函數(shù)值將下降,且不會超出可行域直接解法通常適用于僅含不等式約束的問題目前二頁\總數(shù)一百零一頁\編于三點§6.1概述特點：①由于求解過程在可行域內(nèi)進行；無論迭代計算何時終止,都可以獲得一個比初始點好的設(shè)計點;②若可行域是凸集，目標函數(shù)是定義在凸集上的凸函數(shù)，則收斂到全局最優(yōu)點；否則，結(jié)果與初始點有關(guān)。凸可行域x1x20X(0)X(0)X(0)X(0)非凸可行域x1x20X1*X2*目前三頁\總數(shù)一百零一頁\編于三點§6.1概述原理：將有約束優(yōu)化問題轉(zhuǎn)化為無約束優(yōu)化問題來解決。方法：以原目標函數(shù)和加權(quán)的約束函數(shù)共同構(gòu)成一個新的

目標函數(shù)Φ(X,r1,r2)，成為無約束優(yōu)化問題。通

過不斷調(diào)整加權(quán)因子，產(chǎn)生一系列Φ函數(shù)的極小點

序列X(k)*(r1(k),r2(k))k=0,1,2…，逐漸收斂到原目

標函數(shù)的約束最優(yōu)解。

其中：新目標函數(shù)：三.間接解法的基本思想：

懲罰因子：r1,r2目前四頁\總數(shù)一百零一頁\編于三點§6.2隨機方向法一.基本思想：隨機產(chǎn)生初始點，隨機產(chǎn)生若干個搜索方向dk，并從中選擇一個能使目標函數(shù)值下降最快的方向作為可行搜索方向進行搜索。確保：①新迭代點在可行域中②目標函數(shù)值的下降性。X(0)X(L)X(1)X*x1x20目前五頁\總數(shù)一百零一頁\編于三點二.初始點的選擇

隨機方向法的初始點X0必須是一個可行點，既滿足全部

不等式約束條件。初始點可以通過隨機選擇的方法產(chǎn)生。1）輸入設(shè)計變量的上限值和下限值，即ai≤xi≤bi2）在區(qū)間（0，1）內(nèi)產(chǎn)生n個偽隨機數(shù)qi3）計算隨機點x的各分量xi=ai+qi(bi-ai)4）判別隨機點X是否可行，若隨機點可行，用X0←X

為初始點；若非可行點，轉(zhuǎn)到步驟2）重新產(chǎn)生隨

機點，直到可行為止?！?.2隨機方向法目前六頁\總數(shù)一百零一頁\編于三點三.可行搜索方向的產(chǎn)生從k個隨機方向中，選取一個較好的方向。1）在(-1,1)區(qū)間內(nèi)產(chǎn)生偽隨機數(shù)rij，得隨機單位向量ej

2)取一試驗步長a0，按下式計算k個隨機點§6.2隨機方向法目前七頁\總數(shù)一百零一頁\編于三點3）檢驗k個隨機點是否為可行點，除去非可行點，計算余下的可行點的目標函數(shù)值，比較其大小，選出目標

函數(shù)最小的點XL

。4)比較XL

和X0兩點的目標函數(shù)值:①若f(XL)<f(X0)，則取XL

和X0連線方向為可行搜索方向；

②若f(XL)≥f(X0)，則縮小步長α0

，轉(zhuǎn)步驟2）重新計算，

直至f(XL)<f(X0)為止。③α0

縮小到很小仍然找不到一個XL，使f(XL)<f(X0),則

說明X0是一個局部極小點，更換初始點轉(zhuǎn)步驟1）。§6.2隨機方向法目前八頁\總數(shù)一百零一頁\編于三點產(chǎn)生可行搜索方向的條件為：則可行搜索方向為：四、搜索步長的確定步長由加速步長法確定：τ為步長加速系數(shù)，一般取1.3§6.2隨機方向法目前九頁\總數(shù)一百零一頁\編于三點五.計算步驟1)選擇一個可行的初始點X0;2)產(chǎn)生k個n維隨機單位向量ej(j=1,2,…,k);3)取試驗步長0，計算出k個隨機點X

j;4)在k個隨機點中，找出可行的的隨機點XL,產(chǎn)生可行搜索方向d=XLX0.5)從初始點X0出發(fā)，沿可行搜索方向d以步長進行迭代

計算，直到搜索到一個滿足全部約束條件，且目標函數(shù)

值不再下降的新點X。6)若收斂條件滿足，停止迭代。否則，令X0X轉(zhuǎn)步驟2。目前十頁\總數(shù)一百零一頁\編于三點例6-1求下列約束優(yōu)化問題的最優(yōu)解

解：用隨機方向法程序，在計算機上運行，迭代13次，求得約束最優(yōu)解：X*=[0.00273.0]T,f(X*)=3

迭代次數(shù)設(shè)計變量x1設(shè)計變量x2目標函數(shù)值0-2.02.06.01-0.01681.1171.1964-0.0331.0241.0257-0.1140.7170.73010-0.077-2.998-2.99713-0.0027-3.0-3.0X0X*-3-2-1012312-2-1x1目前十一頁\總數(shù)一百零一頁\編于三點§6.3復(fù)合形法一.單純形法：基本思想：以一個目標函數(shù)值較小的新點，代替原單純形中目標函數(shù)值最大的頂點，組成新的單純形，不斷地迭代，逐漸逼近最優(yōu)點。

二維空間中映射法比較單純形X(1)X(2)X(3)的頂點，f(X(1))>f(X(2))>f(X(3)),X(1)為最壞點，稱為X(H)，通過映射得到新點X(R)，X(R)＝X(S)＋a(X(S)-X(H))以X(R)來代替X(H)，組成新的單純形X(R)X(2)X(3)。其中f(X(R))<f(X(H));

a>1；稱為映射因子；X(1)=X(H)X(2)X(3)X(S)X(R)=X(4)X(5)X(6)定義：在n維空間中，由n+1個點組成的圖形稱單純形。X*除X(H)外，其它頂點的幾何中心目前十二頁\總數(shù)一百零一頁\編于三點二.復(fù)合形法：定義：

在n維空間中，由k≥n+1個點組成的多面體稱為復(fù)合形?；舅枷耄?/p>

以一個較好的新點，代替原復(fù)合形中的最壞點，組成新的復(fù)合形，以不斷的迭代，使新復(fù)合形逐漸逼近最優(yōu)點。說明：

單純形是無約束優(yōu)化方法，復(fù)合形用于約束優(yōu)化的方法。因為頂點數(shù)較多，所以比單純形更靈活易變。復(fù)合形只能解決不等式約束問題。因為迭代過程始終在可行域內(nèi)進行，運行結(jié)果可靠。目前十三頁\總數(shù)一百零一頁\編于三點三.迭代方法：1.映射法：

例：二維空間中，k=4，復(fù)合形是四面體X(1)X(2)X(3)X(4)，計算得：f(X(1))<f(X(2))<f(X(3))<f(X(4)),確定最壞點X(H)=X(4)，次壞點X(G)=X(3)，最好點X(L)=X(1)。X(S)為除X(H)以外，各點的幾何中心。映射迭代公式：X(R)=X(S)+α(X(S)-X(H))搜索方向：沿X(H)→X(S)的方向。步長因子（映射系數(shù)）α：α>1，建議先取1.3。若求得的X(R)在可行域內(nèi)，且f(X(R))<f(X(H))，則以X(R)代替X(H)組成新復(fù)合形，再進行下輪迭代?！?/p>

X(S)X(R)

X(H)X(1)X(4)X(3)X(2)目前十四頁\總數(shù)一百零一頁\編于三點變形法一

——擴張：若f(X(R))<f(X(L))，則可沿此方向擴張取若f(X(E))<f(X(L))，則擴張成功，以X(E)代替X(H)組成新復(fù)合形若f(X(E))>f(X(L))，則擴張失敗，以X(R)代替X(H)組成新復(fù)合形●

X(S)X(R)

X(H)X(E)X(1)X(4)X(3)X(2)目前十五頁\總數(shù)一百零一頁\編于三點變形法二

——收縮：

若在映射法中f(X(R))>f(X(H)),則以a＝0.5a重復(fù)采用映射法若直至a<10-5仍不成功，考慮采用收縮法

取

若f(X(K))<f(X(H)),則成功，以X(K)代替X(H)組成新復(fù)合形。●

X(S)X(R)

X(H)X(K)X(1)X(4)X(3)X(2)目前十六頁\總數(shù)一百零一頁\編于三點4.變形法三

——壓縮：

如采用上述方法均無效，還可以將復(fù)合形各頂點向最好點

X(L)靠攏，即采用壓縮的方法改變復(fù)合形的形狀。

取

X(L)X(1)X(4)X(3)X(2)目前十七頁\總數(shù)一百零一頁\編于三點四.初始復(fù)合形的形成：人工選擇初始復(fù)合形2.隨機產(chǎn)生初始復(fù)合形：

①先在可行域內(nèi)確定一個初始頂點；②確定xi的上下界：ai、bi；③產(chǎn)生區(qū)間[0,1]中的k-1組偽隨機數(shù)ri(j)；④產(chǎn)生k-1個頂點，xi(j)=αi+ri(j)

(bi-ai)⑤檢查k-1個頂點的可行性，求出在可行域內(nèi)的

q個頂點的幾何中心：

⑥以X(q+1)=X(s)+α(X(q+1)-X(s)),a=0.5將不滿

足約束的頂點移向可行域若可行域是非凸集，可能失敗，需減小上、下界再進行。目前十八頁\總數(shù)一百零一頁\編于三點凸集

X(S)x(1)x(3)x(2)原X(q+1)新X(q+1)X(S)x(1)x(3)x(2)原X(q+1)新X(q+1)非凸集目前十九頁\總數(shù)一百零一頁\編于三點步驟：

1.形成初始復(fù)合形

2.計算各頂點的函數(shù)值,找到最壞點X(H)

、次壞點X(G)和最好點X(L)

3.計算除最壞點外，其余頂點的形心:

檢查形心是否在可行域內(nèi)

4.則可行域為非凸集，取ai＝xi

(L),

bi＝xi(S)作為上下界；

轉(zhuǎn)步驟1

5.計算映射點：

X(R)=X(S)+a(X(S)-X(H)),a=1.3

檢查是否在可行域內(nèi)是，轉(zhuǎn)步驟5否，轉(zhuǎn)步驟4是，轉(zhuǎn)步驟6否，a=0.5a,重新計算反射點目前二十頁\總數(shù)一百零一頁\編于三點6.計算f(X(R))，若

7.若a>

:

檢查終止準則

若f(X(R))<f(X(H))，以x(R)代替x(H)重構(gòu)復(fù)合形后轉(zhuǎn)步驟8f(X(R))≥f(X(H))，轉(zhuǎn)步驟7是，則a=0.5a，轉(zhuǎn)步驟5否，則調(diào)用收縮法或壓縮法，重構(gòu)復(fù)合形后轉(zhuǎn)步驟3是，則迭代結(jié)束，以此復(fù)合形的x(L)為X＊否，則以重構(gòu)的復(fù)合形轉(zhuǎn)步驟2目前二十一頁\總數(shù)一百零一頁\編于三點例用復(fù)合形法求解解:1)產(chǎn)生初始復(fù)合形的頂點。取復(fù)合形頂點的數(shù)目為k

=2n=4,初始復(fù)合形的四個頂點為以上四點均滿足約束條件2）四點的函數(shù)值:由此可知最壞點為X10,最好點為X40.24602468x1x2X10X40X20X30目前二十二頁\總數(shù)一百零一頁\編于三點3)計算除去壞點后，各點的中心點4）檢查XC0點的可行性，由于

所以Xc0是可行點。24602468x1x2X10X40X20X30Xc0目前二十三頁\總數(shù)一百零一頁\編于三點5)求反射點Xr0并檢查其可行性取反射系數(shù)

=1.3，可得反射點也是可行的。6）比較反射點與最壞點的目標函數(shù)值用Xr0代替XH0，與其余3點構(gòu)成新的復(fù)合形。第二輪迭代，k=1新復(fù)合形的四個頂點為其對應(yīng)的函數(shù)值為24602468x1x2X10X40X20X30Xr0目前二十四頁\總數(shù)一百零一頁\編于三點Xr124602468x1x2X41X21X31

由此可見，XH1=X21=[1,4]T，除去壞點后其余各點的中心為XC1=[2.77,4.46]T,滿足所有約束條件，是可行點。進行反射計算，得Xr1=[5.071,5.058]T,經(jīng)檢驗Xr1也是可行點，其f(Xr1)=14.71<47=f(Xh1),故可重新組成復(fù)合形，再計算，直至達到精度要求停機，最后所求得的X1k

和f(X1k)接近理論最優(yōu)解X*=[6,5]T,f(X*)=11.X11目前二十五頁\總數(shù)一百零一頁\編于三點六.方法評價：

計算簡單，不必求導(dǎo)，占內(nèi)存?。?/p>

隨著維數(shù)的增加，效率大大下降；

不能解含等式約束的問題；建議：

①初始α取1.3。②n+1≤k≤2n，當(dāng)n≤5時，k取值接近2n；當(dāng)n>5時，k取值可小些。目前二十六頁\總數(shù)一百零一頁\編于三點§6.4可行方向法一.基本思想：在可行域內(nèi)選擇一個初始點X(0)，確定了一個可行方向和適當(dāng)?shù)牟介L后，按照下式進行迭代計算：

X(k+1)=X(k)+ad通過不斷的調(diào)整可行方向，使迭代點逐步逼近約束最優(yōu)點。該方法是求解大型約束優(yōu)化問題的主要方法之一。目前二十七頁\總數(shù)一百零一頁\編于三點§6.4可行方向法二.搜索策略：

根據(jù)目標函數(shù)和約束函數(shù)的不同性態(tài)，選擇不同的搜索策略。

1)

邊界反彈法：第一次搜索為負梯度方向，終止于邊

界。以后各次搜索方向均為適用可行方向，以最大

步長從一個邊界反彈到另一個邊界，直至滿足收斂

條件。f(X)X(0)X(1)X(2)X*X(3)目前二十八頁\總數(shù)一百零一頁\編于三點§6.4可行方向法

2)最優(yōu)步長法：第一次搜索為負梯度方向，終止于邊

界。第二次搜索沿適用可行方向作一維搜索以最優(yōu)

步長因子求得最優(yōu)點。反復(fù)以上兩步，直至得到最

優(yōu)點X*。X(1)X(0)X(2)X(3)X*f(X)目前二十九頁\總數(shù)一百零一頁\編于三點§6.4可行方向法

3)貼邊搜索法：

第一次搜索為負梯度方向，終止于邊界。以后各次搜索貼邊（約束面）進行。若適時約束面是線性約束，每次搜索到約束面的交集時，移至另一個約束面，經(jīng)過有限的幾步就可以收斂到最優(yōu)點。X(1)X(0)X(2)X*目前三十頁\總數(shù)一百零一頁\編于三點§6.4可行方向法

若約束面是非線性時，從X(k)點沿切線（面）方向d(k)

搜索，會進入非可行域。容差帶δ：

建立約束面的容差帶+δ，從X(k)

出發(fā)，沿d(k)方向搜索到d(k)方向與g(X)+δ=0的交點X'后，再沿適時約束的負梯度方向返回約束面的X(k+1)點。

X(k)g(X)g(X)+

δX'-▽g(X)d(k)X(k+1)目前三十一頁\總數(shù)一百零一頁\編于三點§6.4可行方向法調(diào)整步長因子α1

：

X(k+1)=X'-a1▽g(X')將g(X)在X'點泰勒展開，取一階近似式：

g(X)≈g(X')+[▽g(X')]T(X-X')進而得到：g(X(k+1))≈g(X')+[▽g(X')]T(X'-a1▽g(X')-X')≈g(X')+[▽g(X')]T[-a1▽g(X')]為了讓X(k+1)到達約束面，令g(X(k+1))=0得:X(k)X(k+1)g(X)g(X)+

δ=0X’-▽g(X)d(k)目前三十二頁\總數(shù)一百零一頁\編于三點§6.4可行方向法三.可行方向的確定可行方向應(yīng)該滿足設(shè)計點可行及目標函數(shù)值下降兩個條件

1)可行條件:

[▽gj(Xk)]T

dk≤0

j=1,2,…J(起作用約束的個數(shù))▽g(Xk)dk▽g1(Xk)▽g2(Xk)dkXkg1(X)=0g2(X)=0目前三十三頁\總數(shù)一百零一頁\編于三點§6.4可行方向法三.可行方向的確定

2)目標函數(shù)值下降條件:

[▽f(Xk)]T

dk<0

▽f(Xk)dkg1(X)=0g2(X)=0目前三十四頁\總數(shù)一百零一頁\編于三點§6.4可行方向法三.可行方向的確定[▽gj(Xk)]T

dk≤0

保證在可行域內(nèi)[▽f(Xk)]T

dk<0

保證目標函數(shù)值下降

可行方向▽f(Xk)g1(X)=0g2(X)=0▽g1(Xk)dkXk可行下降方向區(qū)▽g2(Xk)目前三十五頁\總數(shù)一百零一頁\編于三點§6.4可行方向法1）優(yōu)選方向法四.可行方向產(chǎn)生方法式中：d為求解變量，[▽gj(Xk)]T

、[▽f(Xk)]T為定值目前三十六頁\總數(shù)一百零一頁\編于三點§6.4可行方向法2）梯度投影法：

可行方向:

其中:p為投影算子,J-起作用的約束個數(shù)-▽f(Xk)g1(X)=0g4(X)=0g3(X)=0g2(X)=0Xkdk目前三十七頁\總數(shù)一百零一頁\編于三點§6.4可行方向法1）取最優(yōu)步長五.步長的確定若X(k+1)為可行點，a＊作為本次迭代步長

X(k+1)=X(k)+a＊da*dX(k+1)

x1x20X(k)

dk目前三十八頁\總數(shù)一百零一頁\編于三點§6.4可行方向法2）取最大步長aM五.步長的確定a＊daMdX(k+1)

X(k+1)=X(k)+aMdx1x20X(k)

dk

目前三十九頁\總數(shù)一百零一頁\編于三點①試驗步長因子at將F(X)在X(k)

處作泰勒展開,僅取到線性項:目標函數(shù)相對下降量:迭代公式X(k+1)=X(k)+atd(k)

整理得:目前四十頁\總數(shù)一百零一頁\編于三點約束邊界容差帶

在實際計算中,應(yīng)給約束邊界一個允許的誤差限:式中,通常取0.01-0.001;只要迭代點進入容差帶,即認為達到了邊界.然后在迭代中當(dāng)滿足一定的收斂條件時，在將容差值逐漸縮小，直至當(dāng)

=105時，則認為該點已經(jīng)位于約束面上。目前四十一頁\總數(shù)一百零一頁\編于三點②將位于非可行域的試驗點xt調(diào)整到約束面上。在Xt點處，g1(Xt)>0,g2(Xt)>0。應(yīng)將Xt點調(diào)整到g1(Xt)=0的約束面上，因為對于Xt點來說，g1(Xt)的約束違反量比g2(Xt)大。若設(shè)gk(Xt)為約束違反量最大的約束條件，則應(yīng)滿足

x1x20XkXk+1Xtg1(X)=0g2(X)=0目前四十二頁\總數(shù)一百零一頁\編于三點將試驗點Xt調(diào)整到gk(Xt)=0的約束面上的方法:試探法：當(dāng)試驗點位于非可行域時，將試驗步長t縮短；當(dāng)位于可行域時，將試驗步長t加倍，直至滿足gj(X)0(j=1,2,,J)，即認為試驗點已經(jīng)被調(diào)整到約束面上了。at=at+a0Xt=Xk

+atdk

gk(Xt)≤0?a0=0.7a0

at=at-a0否a0=0.7a0

否

gk(Xt)≤

?是

結(jié)束aM=at是目前四十三頁\總數(shù)一百零一頁\編于三點若考慮約束允差，并按允差中心/2做線性內(nèi)插，可以得到將Xt1調(diào)整到約束面上的步長s。本次迭代步長取為(b)插值法：利用線性插值將位于非可行域的試驗點Xt調(diào)整到約束面上。設(shè)試驗步長t，求得可行試驗點:當(dāng)試驗步長為t+0時，求得非可行試驗點:并設(shè)在該兩點的約束函數(shù)分別為gk(Xt1)<0和gk(Xt2)＞0asagk

(X)a0gk

(Xt2)atgk

(Xt1)δ目前四十四頁\總數(shù)一百零一頁\編于三點收斂條件2）設(shè)計點Xk滿足庫恩-塔克條件1）設(shè)計點Xk及約束允差滿足目前四十五頁\總數(shù)一百零一頁\編于三點可行方向法的計算步驟1）在可行域內(nèi)選一個初始點X0，給出約束允差及收斂精度值。2）令迭代次數(shù)k=0,第一次迭代的搜索方向取d0=f(X0)估算試驗步長t，計算試驗點Xt①若試驗點Xt滿足gj(Xt)0，Xt點必位于第j個約束面上，則轉(zhuǎn)步驟6）；②若試驗點Xt

位于可行域內(nèi)，則加大試驗步長t，重新計算新的試驗點，直至Xt

越出可行域，再轉(zhuǎn)步驟5）；③若試驗點位于非可行域，則直接轉(zhuǎn)步驟5）目前四十六頁\總數(shù)一百零一頁\編于三點

5）確定約束違反量最大的約束函數(shù)gk(Xt)。用試探法或插值法計算調(diào)整步長t，使試驗點xt返回到約束面上，則完成一次迭代。再令kk+1,Xk=Xt,轉(zhuǎn)步驟6）6）在新的設(shè)計點Xk處產(chǎn)生新的可行方向dk7)在Xk點滿足收斂條件，停止迭代。約束最優(yōu)解為X*=Xk,f(X*)=f(Xk)。否則，改變允差的值，令目前四十七頁\總數(shù)一百零一頁\編于三點例用可行方向法求約束優(yōu)化問題的約束最優(yōu)解。Minf(X)=x12+2x22-10x1-x1x2-4x2+60s.t.g1(X)=x10

g2(X)=x20g3(X)=x160g4(X)=x280g5(X)=x1+x2110解：取初始點X0=[01]T，為約束邊界g1(X)=0上的一點。第一次迭代用優(yōu)選方向法確定可行方向。首先計算X0點的目標函數(shù)f(X0)和約束函數(shù)g1(X0)的梯度目前四十八頁\總數(shù)一百零一頁\編于三點為在可行下降扇形區(qū)內(nèi)尋找最優(yōu)方向，需求解一個以可行方向d=[d1d2]T為設(shè)計變量的優(yōu)化問題，其數(shù)學(xué)模型為：目前四十九頁\總數(shù)一百零一頁\編于三點最優(yōu)方向是d*=[0.984，0.179]T，它是目標函數(shù)等值線（直線束）和約束函數(shù)d12+d22=1（半徑為1的圓）的切點。第一次迭代的可行方向為d0=d*。d1d*-1101-1d2目標函數(shù)減小方向目前五十頁\總數(shù)一百零一頁\編于三點第一次迭代的可行方向為d0=d*。若步長取0=6.098，則

可見第一次迭代點X1

在約束邊界g3(X1)=0上。

x1x2g1(X)=0g4(X)=0g2(X)=0g3(X)=0g5(X)=0XkX1X0d00246810264810-▽f(X1)目前五十一頁\總數(shù)一百零一頁\編于三點第二次迭代用梯度投影法來確定可行方向。迭代點x1的目標函數(shù)負梯度-f(X1)=[0.0925.818]T，不滿足方向的可行條件。現(xiàn)將f(X1)投影到約束邊界g3(X)=0上，

計算投影算子P本次迭代的可行方向為目前五十二頁\總數(shù)一百零一頁\編于三點顯然，d1為沿約束邊界g3(X)=0的方向。若取1=2.909，則本次迭代點即為該問題的約束最優(yōu)點X*則得約束最優(yōu)解

x1x2g1(X)=0g4(X)=0g2(X)=0g3(X)=0g5(X)=0-▽f(X1)XkX1X0d00246810264810目前五十三頁\總數(shù)一百零一頁\編于三點將有約束的優(yōu)化問題轉(zhuǎn)化為無約束優(yōu)化問題來求解。保證：轉(zhuǎn)化后的無約束優(yōu)化問題與原約束問題具有同一最優(yōu)解。

構(gòu)成一個新的目標函數(shù)：§6.5懲罰函數(shù)法懲罰項懲罰因子懲罰函數(shù)目前五十四頁\總數(shù)一百零一頁\編于三點從而保證懲罰項必須具有以下極限性質(zhì)：根據(jù)懲罰項的不同構(gòu)成形式，懲罰函數(shù)法又可分為內(nèi)點懲罰函數(shù)法、外點懲罰函數(shù)法和混合懲罰函數(shù)法§6.5懲罰函數(shù)法目前五十五頁\總數(shù)一百零一頁\編于三點一.內(nèi)點懲罰函數(shù)法基本思想內(nèi)點法將新目標函數(shù)Φ(X,r)構(gòu)筑在可行域D內(nèi)，隨著懲罰因子r(k)的不斷遞減，生成一系列新目標函數(shù)Φ(Xk,

r(k))，在可行域內(nèi)逐步迭代，產(chǎn)生的極值點Xk*(r(k))序列從可行域內(nèi)部趨向原目標函數(shù)的約束最優(yōu)點X*。例：min.f(X)=x

s.t.g(X)=1-x≤0新目標函數(shù):?(X,r(k))?(X*,r(k))=2x*-1r=0.1r=0.01?(X,r(k))f(X)=xxf(X)1220g(x)=1-xX1*X2*r=0.001X*目前五十六頁\總數(shù)一百零一頁\編于三點2.懲罰函數(shù)的形式

①

②其中：懲罰（加權(quán)）因子

降低系數(shù)c：0<c<1當(dāng)x在可行域內(nèi)遠離約束邊界時：當(dāng)x由可行城內(nèi)靠近約束邊界時：障礙項目前五十七頁\總數(shù)一百零一頁\編于三點3.幾個參數(shù)的選擇懲罰因子初始值r(0)

的選擇：

過大、過小均不好，建議考慮選擇r(0)=1或者：2.

降低系數(shù)c的選擇：c的典型值為0.1～0.7。3.

初始點X(0)

的選擇：要求：

①在可行域內(nèi)；②不要離約束邊界太近。方法：

①人工估算，需要校核可行性；

②計算機隨機產(chǎn)生，也需校核可行性。X1*X2*X*xf(X)?(X,r(k))?(X*,r(k))=2x*-1r=0.1r=0.01r=0.001g(x)=1-x?(X,r(k))122f(X)=x0目前五十八頁\總數(shù)一百零一頁\編于三點

③初始點確定方法：

任意給出一個初始點；判斷其可行性，若違反了S個約束，求出不滿足約束中的最大值：

應(yīng)用優(yōu)化方法減少違反約束：

以求得的設(shè)計點作為新初始點，繼續(xù)其判斷可行性，若仍有不滿足的約束，則重復(fù)上述過程，直至初始點可行。目前五十九頁\總數(shù)一百零一頁\編于三點④

判斷是否收斂：4.內(nèi)點懲罰函數(shù)法步驟：①選取合適的初始點X(0)

，以及r(0)、c、計算精度ε1、ε2

，令k=0；

②

構(gòu)造懲罰（新目標）函數(shù)；③調(diào)用無約束優(yōu)化方法，求新目標函數(shù)的最優(yōu)解Xk*和

Φ(Xk,r(k))；若均滿足，停止迭代，有約束優(yōu)化問題的最優(yōu)點為X*=Xk*；若有一個準則不滿足，則令并轉(zhuǎn)入第3步，繼續(xù)計算。目前六十頁\總數(shù)一百零一頁\編于三點例：用內(nèi)點法求下列問題的最優(yōu)解：構(gòu)造懲罰函數(shù)目前六十一頁\總數(shù)一百零一頁\編于三點目前六十二頁\總數(shù)一百零一頁\編于三點112目前六十三頁\總數(shù)一百零一頁\編于三點二.外點懲罰函數(shù)法1.基本原理外點法將新目標函數(shù)Φ(X,r)構(gòu)筑在可行域D外，隨著懲罰因子r(k)的不斷遞增，生成一系列新目標函數(shù)Φ(Xk,r(k))，在可行域外逐步迭代，產(chǎn)生的極值點Xk*(r(k))序列從可行域外部趨向原目標函數(shù)的約束最優(yōu)點X*。新目標函數(shù)：例：求下述約束優(yōu)化問題的最優(yōu)點。

min.f(X)=x

x∈R1s.tg(X)=1-x≤0(X*,?(X*,r∞))可行域g(X)=1-x=0f(X)=x?(X,r(k))f(X)12x120?(X,r(k))X*(r(0))r(0)=0.25r(1)=0.5r(2)=1r(3)=2目前六十四頁\總數(shù)一百零一頁\編于三點懲罰函數(shù)可取為2)懲罰因子r(k)

1)當(dāng)設(shè)計點在可行域內(nèi)時,懲罰項為0,不懲罰;當(dāng)設(shè)計點在可行域外

時,懲罰項大于0,有懲罰作用。外點法可以用來求解含不等式和等式約束的優(yōu)化問題。衰減項目前六十五頁\總數(shù)一百零一頁\編于三點3.幾個參數(shù)的選擇①r(0)

的選擇:r(0)

過大，會使懲罰函數(shù)的等值線變形或偏心，求極

值困難。r(0)

過小，迭代次數(shù)太多。

一般取r(0)

＝1

或者②X(0)

的選擇：基本上可以在可行域內(nèi)外，任意選擇。③遞增系數(shù)c的選擇：r(k)=cr(k-1)

通常選擇5～10，可根據(jù)具體題目，進行試算調(diào)整。目前六十六頁\總數(shù)一百零一頁\編于三點例：用外點法求解下列有約束優(yōu)化問題解：懲罰函數(shù)為：

目前六十七頁\總數(shù)一百零一頁\編于三點無約束目標函數(shù)極小化問題的最優(yōu)解系列為：求偏導(dǎo)，得

目前六十八頁\總數(shù)一百零一頁\編于三點rx1*x2*φ*(r)f*(r)0.01-0.8098-50.0000-24.965-49.99770.1-0.4597-5.0000-2.2344-4.947410.2361-0.5000.96310.1295100.8322-0.05002.30682.000110000.9980-0.00052.66242.6582∞108/38/3優(yōu)化過程收斂情況目前六十九頁\總數(shù)一百零一頁\編于三點內(nèi)、外點法不同g(X)=0f(X)=123x1x20112f(X)=1012231g(X)=0x1x2012231g(X)=0x2f(X)=1x10122-11g(X)=0x1x23-2-3-1-20122-11g(X)=0x1x23-2-3-1-2330122-11g(X)=0x1x23-2-3-1-23目前七十頁\總數(shù)一百零一頁\編于三點內(nèi)點法特點：

（1）初始點必須為嚴格的可行點

（2）不適于具有等式約束的數(shù)學(xué)模型

（3）迭代過程中各個點均為可行設(shè)計方案

（4）一般收斂較慢

（5）初始懲罰因子要選擇得當(dāng)

（6）懲罰因子為遞減，遞減率c有0<c<1

外點法特點：

（1）初始點可以任選

（2）對等式約束和不等式約束均可適用

（3）僅最優(yōu)解為可行設(shè)計方案

（4）一般收斂較快

（5）初始罰因子要選擇得當(dāng)

（6）懲罰因子為遞增，遞增率c有c>1目前七十一頁\總數(shù)一百零一頁\編于三點三.

混合懲罰函數(shù)法1.基本思想采用內(nèi)點法和外點法相結(jié)合的混合懲罰函數(shù)法，發(fā)揮內(nèi)點法和外點法的特點，處理既有等式約束，又有不等式約束的優(yōu)化設(shè)計問題。2.懲罰函數(shù)的形式一般既包括障礙項，也包括衰減項。目前七十二頁\總數(shù)一百零一頁\編于三點懲罰函數(shù)法優(yōu)點：原理簡單，算法易行，適應(yīng)范圍廣，可利用無約束最優(yōu)化方法資源。缺點：（1）初始懲罰因子r(0)取值不當(dāng)可導(dǎo)致懲罰函數(shù)變得病態(tài)，

使無約束優(yōu)化計算困難。（2）理論上講，只有懲罰因子r

(k)

0（內(nèi)點法）或

r(k)

趨于無窮（外點法）時，算法才收斂，因此序

列迭代過程收斂速度慢。增廣乘子法外點懲罰函數(shù)＋拉格朗日函數(shù)

計算過程穩(wěn)定，計算效率超過懲罰函數(shù)法目前七十三頁\總數(shù)一百零一頁\編于三點拉格朗日函數(shù)一、拉格朗日乘子法（升維法）§6.6增廣乘子法l+n個方程l+n個未知變量具有相同的最優(yōu)解X*目前七十四頁\總數(shù)一百零一頁\編于三點例:用拉格朗日乘子法求下列問題的最優(yōu)解解構(gòu)造拉格朗日函數(shù)令▽L=0,得到求解得：目前七十五頁\總數(shù)一百零一頁\編于三點構(gòu)造拉格朗日函數(shù)構(gòu)造外點懲罰函數(shù)目前七十六頁\總數(shù)一百零一頁\編于三點二、等式約束的增廣乘子法

采用拉格朗日乘子法時求解有難度,而罰函數(shù)法當(dāng)?shù)c接近邊界時函數(shù)常有病態(tài),此法的思路是把兩者結(jié)合起來。其增廣拉格朗日函數(shù)為:目前七十七頁\總數(shù)一百零一頁\編于三點不論r(k)取何值，增廣乘子函數(shù)與原函數(shù)具有相同的約束極值點X*，與拉格朗日函數(shù)有相同的拉格朗日乘子向量。二、等式約束的增廣乘子法目前七十八頁\總數(shù)一百零一頁\編于三點例:求下列優(yōu)化問題的最優(yōu)解構(gòu)造拉格朗日函數(shù):求解可得:對應(yīng)海賽矩陣:非正定目前七十九頁\總數(shù)一百零一頁\編于三點構(gòu)造增廣乘子函數(shù):對應(yīng)海賽矩陣:r不需要趨于無窮大，只要取一個足夠大的定值，且恰好選取了一個λ=λ*,

X*就是函數(shù)M(X，λ，r)的極小點目前八十頁\總數(shù)一百零一頁\編于三點二、等式約束的增廣乘子法目前八十一頁\總數(shù)一百零一頁\編于三點增廣乘子法中的乘子迭代二、等式約束的增廣乘子法校正量近似牛頓法得到的校正量目前八十二頁\總數(shù)一百零一頁\編于三點參數(shù)選取沒有其它信息情況下，初始乘子向量

增廣乘子函數(shù)和外點懲罰函數(shù)形式相同；從第二次迭代開始，乘子向量按公式進行校正。懲罰因子初始值r(0)按照外點法取。從第二次迭代開始，懲罰因子按下式遞增：懲罰因子遞增系數(shù)，

β

=10判別數(shù)，通常取0.25二、等式約束的增廣乘子法目前八十三頁\總數(shù)一百零一頁\編于三點等式約束增廣乘子法計算步驟：

選取設(shè)計變量的初始點X0，懲罰因子初值r0，增長系數(shù)β，判別數(shù)δ，收斂精度ε，乘子向量λp0=0

(p=1,2,…l),迭代次數(shù)k=0；構(gòu)造增廣乘子函數(shù)M(X,λ,r)，并用無約束方法求

min

M(X,λ,r)，得無約束最優(yōu)解Xk=X*(λk,rk)計算校正乘子向量如果，迭代終止，約束最優(yōu)解為X*=Xk，λ*=λk+1;否則轉(zhuǎn)步驟6計算懲罰因子再令k=k+1，轉(zhuǎn)步驟2目前八十四頁\總數(shù)一百零一頁\編于三點例:用增廣乘子法求下列問題的最優(yōu)解解構(gòu)造增廣乘子函數(shù)確定初始參數(shù)：

β＝2,

λ0=0,

r0=0.1，目前八十五頁\總數(shù)一百零一頁\編于三點利用解析法求min

M(X,λ,r)，令▽M(X,λ,r)＝0，可得最優(yōu)解：

目前八十六頁\總數(shù)一百零一頁\編于三點krkλkxk10.10(0.0714,0,