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

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

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

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

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

Xk+1=Xk+αkdkdk::

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

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

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

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

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

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

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

隨機(jī)方向法的初始點(diǎn)X0必須是一個(gè)可行點(diǎn)，既滿足全部

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

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

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

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

函數(shù)最小的點(diǎn)XL

。4)比較XL

和X0兩點(diǎn)的目標(biāo)函數(shù)值:①若f(XL)<f(X0)，則取XL

和X0連線方向?yàn)榭尚兴阉鞣较颍?/p>

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

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

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

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

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

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

計(jì)算，直到搜索到一個(gè)滿足全部約束條件，且目標(biāo)函數(shù)

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

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

迭代次數(shù)設(shè)計(jì)變量x1設(shè)計(jì)變量x2目標(biāo)函數(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ù)一百零一頁\編于三點(diǎn)§6.3復(fù)合形法一.單純形法：基本思想：以一個(gè)目標(biāo)函數(shù)值較小的新點(diǎn)，代替原單純形中目標(biāo)函數(shù)值最大的頂點(diǎn)，組成新的單純形，不斷地迭代，逐漸逼近最優(yōu)點(diǎn)。

二維空間中映射法比較單純形X(1)X(2)X(3)的頂點(diǎn)，f(X(1))>f(X(2))>f(X(3)),X(1)為最壞點(diǎn)，稱為X(H)，通過映射得到新點(diǎn)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個(gè)點(diǎn)組成的圖形稱單純形。X*除X(H)外，其它頂點(diǎn)的幾何中心目前十二頁\總數(shù)一百零一頁\編于三點(diǎn)二.復(fù)合形法：定義：

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

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

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

例：二維空間中，k=4，復(fù)合形是四面體X(1)X(2)X(3)X(4)，計(jì)算得：f(X(1))<f(X(2))<f(X(3))<f(X(4)),確定最壞點(diǎn)X(H)=X(4)，次壞點(diǎn)X(G)=X(3)，最好點(diǎn)X(L)=X(1)。X(S)為除X(H)以外，各點(diǎn)的幾何中心。映射迭代公式：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ù)合形，再進(jìn)行下輪迭代?！?/p>

X(S)X(R)

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

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

X(S)X(R)

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

——收縮：

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

取

若f(X(K))<f(X(H)),則成功，以X(K)代替X(H)組成新復(fù)合形?！?/p>

X(S)X(R)

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

——壓縮：

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

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

取

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

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

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

q個(gè)頂點(diǎn)的幾何中心：

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

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

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ù)一百零一頁\編于三點(diǎn)步驟：

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

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

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

3.計(jì)算除最壞點(diǎn)外，其余頂點(diǎn)的形心:

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

4.則可行域?yàn)榉峭辜?，取ai＝xi

(L),

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

轉(zhuǎn)步驟1

5.計(jì)算映射點(diǎn)：

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,重新計(jì)算反射點(diǎn)目前二十頁\總數(shù)一百零一頁\編于三點(diǎn)6.計(jì)算f(X(R))，若

7.若a>

:

檢查終止準(zhǔn)則

若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ù)一百零一頁\編于三點(diǎn)例用復(fù)合形法求解解:1)產(chǎn)生初始復(fù)合形的頂點(diǎn)。取復(fù)合形頂點(diǎn)的數(shù)目為k

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

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

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

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

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

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

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

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

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

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

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

1)

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

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

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

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

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

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

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

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

3)貼邊搜索法：

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

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

搜索，會(huì)進(jìn)入非可行域。容差帶δ：

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

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

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

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

：

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

g(X)≈g(X')+[▽g(X')]T(X-X')進(jìn)而得到：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)到達(dá)約束面，令g(X(k+1))=0得:X(k)X(k+1)g(X)g(X)+

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

1)可行條件:

[▽gj(Xk)]T

dk≤0

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

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

[▽f(Xk)]T

dk<0

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

dk≤0

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

dk<0

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

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

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

可行方向:

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

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

x1x20X(k)

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

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

dk

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

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

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

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

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

x1x20XkXk+1Xtg1(X)=0g2(X)=0目前四十二頁\總數(shù)一百零一頁\編于三點(diǎn)將試驗(yàn)點(diǎn)Xt調(diào)整到gk(Xt)=0的約束面上的方法:試探法：當(dāng)試驗(yàn)點(diǎn)位于非可行域時(shí)，將試驗(yàn)步長t縮短；當(dāng)位于可行域時(shí)，將試驗(yàn)步長t加倍，直至滿足gj(X)0(j=1,2,,J)，即認(rèn)為試驗(yàn)點(diǎn)已經(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ù)一百零一頁\編于三點(diǎn)若考慮約束允差，并按允差中心/2做線性內(nèi)插，可以得到將Xt1調(diào)整到約束面上的步長s。本次迭代步長取為(b)插值法：利用線性插值將位于非可行域的試驗(yàn)點(diǎn)Xt調(diào)整到約束面上。設(shè)試驗(yàn)步長t，求得可行試驗(yàn)點(diǎn):當(dāng)試驗(yàn)步長為t+0時(shí)，求得非可行試驗(yàn)點(diǎn):并設(shè)在該兩點(diǎn)的約束函數(shù)分別為gk(Xt1)<0和gk(Xt2)＞0asagk

(X)a0gk

(Xt2)atgk

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

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

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

5）確定約束違反量最大的約束函數(shù)gk(Xt)。用試探法或插值法計(jì)算調(diào)整步長t，使試驗(yàn)點(diǎn)xt返回到約束面上，則完成一次迭代。再令kk+1,Xk=Xt,轉(zhuǎn)步驟6）6）在新的設(shè)計(jì)點(diǎn)Xk處產(chǎn)生新的可行方向dk7)在Xk點(diǎn)滿足收斂條件，停止迭代。約束最優(yōu)解為X*=Xk,f(X*)=f(Xk)。否則，改變?cè)什畹闹?，令目前四十七頁\總數(shù)一百零一頁\編于三點(diǎn)例用可行方向法求約束優(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解：取初始點(diǎn)X0=[01]T，為約束邊界g1(X)=0上的一點(diǎn)。第一次迭代用優(yōu)選方向法確定可行方向。首先計(jì)算X0點(diǎn)的目標(biāo)函數(shù)f(X0)和約束函數(shù)g1(X0)的梯度目前四十八頁\總數(shù)一百零一頁\編于三點(diǎn)為在可行下降扇形區(qū)內(nèi)尋找最優(yōu)方向，需求解一個(gè)以可行方向d=[d1d2]T為設(shè)計(jì)變量的優(yōu)化問題，其數(shù)學(xué)模型為：目前四十九頁\總數(shù)一百零一頁\編于三點(diǎn)最優(yōu)方向是d*=[0.984，0.179]T，它是目標(biāo)函數(shù)等值線（直線束）和約束函數(shù)d12+d22=1（半徑為1的圓）的切點(diǎn)。第一次迭代的可行方向?yàn)閐0=d*。d1d*-1101-1d2目標(biāo)函數(shù)減小方向目前五十頁\總數(shù)一百零一頁\編于三點(diǎn)第一次迭代的可行方向?yàn)閐0=d*。若步長取0=6.098，則

可見第一次迭代點(diǎn)X1

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

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

計(jì)算投影算子P本次迭代的可行方向?yàn)槟壳拔迨揬總數(shù)一百零一頁\編于三點(diǎn)顯然，d1為沿約束邊界g3(X)=0的方向。若取1=2.909，則本次迭代點(diǎn)即為該問題的約束最優(yōu)點(diǎn)X*則得約束最優(yōu)解

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

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

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

s.t.g(X)=1-x≤0新目標(biāo)函數(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ù)一百零一頁\編于三點(diǎn)2.懲罰函數(shù)的形式

①

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

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

的選擇：

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

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

初始點(diǎn)X(0)

的選擇：要求：

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

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

②計(jì)算機(jī)隨機(jī)產(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ù)一百零一頁\編于三點(diǎn)

③初始點(diǎn)確定方法：

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

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

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

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

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

，令k=0；

②

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

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

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ù)一百零一頁\編于三點(diǎn)懲罰函數(shù)可取為2)懲罰因子r(k)

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

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

的選擇:r(0)

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

值困難。r(0)

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

一般取r(0)

＝1

或者②X(0)

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

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

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

目前六十八頁\總數(shù)一百零一頁\編于三點(diǎn)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ù)一百零一頁\編于三點(diǎn)內(nèi)、外點(diǎn)法不同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ù)一百零一頁\編于三點(diǎn)內(nèi)點(diǎn)法特點(diǎn)：

（1）初始點(diǎn)必須為嚴(yán)格的可行點(diǎn)

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

（3）迭代過程中各個(gè)點(diǎn)均為可行設(shè)計(jì)方案

（4）一般收斂較慢

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

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

外點(diǎn)法特點(diǎn)：

（1）初始點(diǎn)可以任選

（2）對(duì)等式約束和不等式約束均可適用

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

（4）一般收斂較快

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

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

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

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

(k)

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

r(k)

趨于無窮（外點(diǎn)法）時(shí)，算法才收斂，因此序

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

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

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

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

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

β

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

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

β＝2,

λ0=0,

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

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

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