青科大化工-最優(yōu)化方法

pse2009最優(yōu)化1/53第3章非線性規(guī)劃1、直接代入法SolutionbyDirectSubstitution2、罰函數(shù)法PenaltyFunction3、拉格朗日乘子法LagrangeMultiplierMethod4、二次規(guī)劃法和序列二次規(guī)劃法

5、幾何規(guī)劃法

6、復(fù)合形法

7、可變?nèi)莶罘╬se2009最優(yōu)化2/53§3非線性規(guī)劃策略：

1.消去約束條件，轉(zhuǎn)化為無(wú)約束優(yōu)化問(wèn)題，如直接代入法、經(jīng)典的拉格朗日法、罰函數(shù)法和序列無(wú)約束極小化方法（SUMT法）等實(shí)現(xiàn)這種轉(zhuǎn)化。

2.將非線性規(guī)劃問(wèn)題轉(zhuǎn)化為線性規(guī)劃問(wèn)題，如序列二次規(guī)劃法。

3.直接求解法：幾何規(guī)劃法、簡(jiǎn)約梯度法、單形法、復(fù)合形法、可變?nèi)莶罘ǖ?。非線性規(guī)劃的一般數(shù)學(xué)表達(dá)式：pse2009最優(yōu)化3/53一、直接代入法SolutionbyDirectSubstitution例1：pse2009最優(yōu)化4/53

直接代入法可用于求解較為簡(jiǎn)單的問(wèn)題。若約束條件為非線性，則該法處理起來(lái)較困難。思路：由約束方程組求得m個(gè)變量的表達(dá)式，代入目標(biāo)函數(shù)中，得到一新的目標(biāo)函數(shù)，此即為無(wú)約束條件的目標(biāo)函數(shù)。pse2009最優(yōu)化5/53圖解示意：x2x1若無(wú)約束條件，則pse2009最優(yōu)化6/53二、罰函數(shù)法PenaltyFunction罰因子，很大的正的常數(shù)求最小值時(shí)為+求最大值時(shí)為-當(dāng)時(shí)，不施加懲罰，當(dāng)時(shí)，施以罰因子ki。對(duì)于具有等式約束的問(wèn)題：思路：把約束條件用罰

因子連接到目標(biāo)

函數(shù)上去，使約

束問(wèn)題轉(zhuǎn)化為無(wú)約

束問(wèn)題。新的目標(biāo)函數(shù)具有這樣性質(zhì)：對(duì)于那些在求解過(guò)程中企圖違反約束的迭代點(diǎn)給以很大的罰因子，使得目標(biāo)函數(shù)變得很大（求最小問(wèn)題）。而且離約束條件愈遠(yuǎn)，則懲罰愈大。于是迫使迭代解無(wú)限地向可行域靠近，或者一直保持在可行域內(nèi)移動(dòng)，直到收斂于原問(wèn)題的最小點(diǎn)。pse2009最優(yōu)化7/53對(duì)于具有不等式約束的問(wèn)題：二、罰函數(shù)法PenaltyFunctionpse2009最優(yōu)化8/53例2：解：罰函數(shù)法pse2009最優(yōu)化9/53式4代入式3得：當(dāng)k時(shí)，要使上式成立，則解上述方程組式2、3：pse2009最優(yōu)化10/53此法是處理等式約束最優(yōu)化問(wèn)題最常用的方法之一。

三、拉格朗日乘子法LagrangeMultiplierMethod------Lagrangian其極值存在的必要條件為：思路：引進(jìn)待定的拉格朗日乘子，將有約束問(wèn)題轉(zhuǎn)化為無(wú)約束問(wèn)題。以兩變量、一等式約束的最優(yōu)化問(wèn)題為例：

聯(lián)立求解上述三個(gè)方程，解出、x1*、x2*，代入f后可得最優(yōu)值。pse2009最優(yōu)化11/53

事實(shí)上，如果f是無(wú)約束函數(shù)，則最優(yōu)化的必要條件為。但由于x1、x2受到約束，不能再任意規(guī)定函數(shù)f的兩個(gè)偏導(dǎo)數(shù)等于0。然而，在最優(yōu)點(diǎn)處f必定是一極值，即df=0仍然成立。又由于存在約束，必須滿足dh=0。所以，有約束的最優(yōu)化必要條件為：

三、拉格朗日乘子法LagrangeMultiplierMethodpse2009最優(yōu)化12/53代入式1得：拉格朗日乘子，常數(shù)，表示目標(biāo)函數(shù)隨約束條件h微小變化而變化的程度。

式3和原約束方程一起，三個(gè)方程解出、x1*、x2*，此x1*、x2*即為滿足約束條件的極值點(diǎn)。pse2009最優(yōu)化13/53一般地，對(duì)于多元等式約束最優(yōu)化問(wèn)題：可構(gòu)造Lagrangian函數(shù)：其極值的必要條件為：再推廣至多維的情況。pse2009最優(yōu)化14/53

以上共計(jì)n+m個(gè)方程，可解出x1、x2、……、xn；

1、1、…...m，共計(jì)n+m個(gè)變量。此解就是Lagrangian函數(shù)的駐點(diǎn)，而x1、x2、……、xn就有可能是上述問(wèn)題的最優(yōu)解。pse2009最優(yōu)化15/53例3：見前面例1：結(jié)果為解：構(gòu)造Lagrangian：pse2009最優(yōu)化16/53練習(xí)1：用拉格朗日乘子法解下列非線性規(guī)劃問(wèn)題。pse2009最優(yōu)化17/53練習(xí)2：用拉格朗日乘子法解下列非線性規(guī)劃問(wèn)題。X1=3.54,X2=-3.54,λ=-0.5X1=-3.54,X2=3.54,λ=-0.5pse2009最優(yōu)化18/53

如圖所示四臺(tái)換熱器系列。試選擇四臺(tái)換熱器的換熱面積，使冷流體出口溫度t4最高，而總換熱面積為200m2。各換熱器總傳熱系數(shù)Ki及熱流體入口溫度Ti給定，冷流體入口溫度t0為已知，冷熱流體流量給定。換熱為逆流。解：建模-----目標(biāo)函數(shù)-----約束條件1例4：熱交換器序列的最優(yōu)化設(shè)計(jì)pse2009最優(yōu)化19/53約束條件2：pse2009最優(yōu)化20/53又由式1得：式4代入式3得：pse2009最優(yōu)化21/53-----約束條件2構(gòu)造Lagrangian：-----共計(jì)13個(gè)方程pse2009最優(yōu)化22/53

四、二次規(guī)劃法和序列二次規(guī)劃法什么是二次規(guī)劃？所謂二次規(guī)劃是指目標(biāo)函數(shù)為二次函數(shù)，約束條件為線性函數(shù)的優(yōu)化問(wèn)題。其表達(dá)式為：（一）二次規(guī)劃法X為n維向量。（m個(gè)）（n個(gè)）例如：一元二次規(guī)劃問(wèn)題pse2009最優(yōu)化23/53

四、二次規(guī)劃法和序列二次規(guī)劃法二次規(guī)劃問(wèn)題處理方法：（1）引入松弛變量，將不等式約束化為等式約束：一元：多元：pse2009最優(yōu)化24/53

四、二次規(guī)劃法和序列二次規(guī)劃法（2）引入拉格朗日乘子：一元：多元：pse2009最優(yōu)化25/53

四、二次規(guī)劃法和序列二次規(guī)劃法（3）根據(jù)函數(shù)極值存在的必要條件有：一元：---線性代數(shù)方程組，未知數(shù)4個(gè)（x、y、、），方程4個(gè)，有唯一解，此解即為原二次規(guī)劃問(wèn)題的最優(yōu)解。pse2009最優(yōu)化26/53

四、二次規(guī)劃法和序列二次規(guī)劃法多元：------線性代數(shù)方程組，未知數(shù)2（n＋m）個(gè)，方程2（n＋m）個(gè)，有唯一解，此解即為原二次規(guī)劃問(wèn)題的最優(yōu)解。000202022111=+-=??=-+=??==??==??=-++=?????===jjjiinjjijijjjiiijmiiijjmiiijjtxLbsxaLttLssLacxdxLlmlmlmpse2009最優(yōu)化27/53

四、二次規(guī)劃法和序列二次規(guī)劃法（二）序列二次規(guī)劃法基本思路：將非線性規(guī)劃問(wèn)題在近似解xk處處理成二次規(guī)劃問(wèn)題。

由Wilson1963年首先提出，1977年形成一個(gè)快速、有效的算法WHP(又稱SQP)法。目前此法在化工領(lǐng)域優(yōu)化中起著舉足輕重的作用。

pse2009最優(yōu)化28/53

四、二次規(guī)劃法和序列二次規(guī)劃法（二）序列二次規(guī)劃法假設(shè)一個(gè)非線性規(guī)劃問(wèn)題：為n維向量。（1）引入拉格朗日乘子，構(gòu)造拉格朗日函數(shù)：pse2009最優(yōu)化29/53

四、二次規(guī)劃法和序列二次規(guī)劃法（二）序列二次規(guī)劃法（2）將上式在xk、k、k處泰勒展開，取至二階導(dǎo)數(shù)項(xiàng)：考慮到：pse2009最優(yōu)化30/53

四、二次規(guī)劃法和序列二次規(guī)劃法（二）序列二次規(guī)劃法于是，上式改寫為：對(duì)照：二次規(guī)劃上式等價(jià)于下述二次規(guī)劃問(wèn)題，即pse2009最優(yōu)化31/53

五、幾何規(guī)劃法

幾何規(guī)劃適宜解決用因次分析得出的設(shè)計(jì)關(guān)系式或由實(shí)驗(yàn)結(jié)果以冪函數(shù)擬合而得的關(guān)系式進(jìn)行最優(yōu)化的情形。它的優(yōu)點(diǎn)是可將一個(gè)復(fù)雜的優(yōu)化問(wèn)題簡(jiǎn)化為解一個(gè)線性代數(shù)方程組的問(wèn)題。下面先討論無(wú)約束幾何規(guī)劃問(wèn)題，然后再介紹有約束幾何規(guī)劃問(wèn)題。幾何規(guī)劃法要求目標(biāo)函數(shù)和約束條件均為正項(xiàng)式。所謂正項(xiàng)式（Posynomial）指系數(shù)、變量均為正數(shù)的多項(xiàng)式。無(wú)約束幾何規(guī)劃優(yōu)化問(wèn)題的一般表達(dá)式為：（1）（2）pse2009最優(yōu)化32/53

五、幾何規(guī)劃法根據(jù)“算術(shù)平均與幾何平均定理”有：只有a1＝a2＝…＝aN時(shí)，上式等式成立。將式3進(jìn)一步推廣，引入N個(gè)加權(quán)因子j>0，j＝1～N，有：（3）------正則條件（歸一化條件）pse2009最優(yōu)化33/53

五、幾何規(guī)劃法（4）將式4用于式1，得:原函數(shù)對(duì)偶函數(shù)（5）（6）正項(xiàng)式pse2009最優(yōu)化34/53

五、幾何規(guī)劃法將式2代入式5的右側(cè)得：pse2009最優(yōu)化35/53

五、幾何規(guī)劃法若使加權(quán)因子滿足以下正交條件：（7）（8）pse2009最優(yōu)化36/53

五、幾何規(guī)劃法將式8代入式7得：（9）將式9代入式5得：

可以證明，若f*是原目標(biāo)函數(shù)的最小值，*是對(duì)偶函數(shù)的最大值，則有---對(duì)偶函數(shù)pse2009最優(yōu)化37/53

五、幾何規(guī)劃法因此，應(yīng)用幾何規(guī)劃法的步驟為：（1）根據(jù)正定多項(xiàng)式的項(xiàng)數(shù)N引入N個(gè)加權(quán)因子；（2）根據(jù)正則條件和正交條件，求解加權(quán)因子的值j，i=1~n，j＝1～N；

（3）由j（j＝1～N）值求對(duì)偶函數(shù)的最大值*，再代入f*＝*中即可求出f*；（4）將f*值代入，可求出xi，i＝1～n。pse2009最優(yōu)化38/53例5

由管道、一個(gè)泵和容器組成的系統(tǒng)，其管道費(fèi)用為（100D+50D2）其中D為管徑，cm。容器的費(fèi)用可表示為20/Q，其中Q為流量，m3/s。泵的費(fèi)用為300Q2/D5。求使總費(fèi)用最少的管徑和流體處理量。解：總費(fèi)用pse2009最優(yōu)化39/53例5

由管道、一個(gè)泵和容器組成的系統(tǒng)，其管道費(fèi)用為（100D+50D2）其中D為管徑，cm。容器的費(fèi)用可表示為20/Q，其中Q為流量，m3/s。泵的費(fèi)用為300Q2/D5。求使總費(fèi)用最少的管徑和流體處理量。引入4個(gè)加權(quán)因子1、2

、3

、4pse2009最優(yōu)化40/53

根據(jù)正則條件和正交條件，求解加權(quán)因子的值j，i=1~2，j＝1～4:代入對(duì)偶函數(shù)中：pse2009最優(yōu)化41/53迭代求極值得：于是將j，j＝1～N的值代入f*＝*中即可求出f*將f*值代入可求出最優(yōu)值時(shí)的變量值：pse2009最優(yōu)化42/53解之得：pse2009最優(yōu)化43/53有約束幾何規(guī)劃優(yōu)化問(wèn)題的一般表達(dá)式為：pse2009最優(yōu)化44/53對(duì)目標(biāo)函數(shù)和約束條件分別應(yīng)用式4和正則條件，得：pse2009最優(yōu)化45/53將以上兩式相乘得：pse2009最優(yōu)化46/53-----正交條件pse2009最優(yōu)化47/53

六、復(fù)合形法基本思想：來(lái)源于無(wú)約束問(wèn)題最優(yōu)化的單純形法。此法只限于求解帶有不等式約束條件的極值問(wèn)題：步驟：（1）產(chǎn)生初始復(fù)合形n維空間中由n+2個(gè)頂點(diǎn)構(gòu)成的多面體，稱為復(fù)合形。之所以使用復(fù)合形，是為了避免單純形容易產(chǎn)生退化即降維的缺點(diǎn)。要求復(fù)合形的各個(gè)頂點(diǎn)必須在可行域內(nèi)。pse2009最優(yōu)化48/53

六、復(fù)合形法（2）計(jì)算中心點(diǎn)產(chǎn)生初始復(fù)合形的方法：方法一：用隨機(jī)數(shù)產(chǎn)生全部頂點(diǎn)；方法二：在可行域內(nèi)人為選定一個(gè)頂點(diǎn)，其余頂點(diǎn)用隨機(jī)數(shù)產(chǎn)生。；方法三：人為選定全部頂點(diǎn)。

先計(jì)算全部頂點(diǎn)的函數(shù)值，找出函數(shù)值最大的點(diǎn)xh（最差點(diǎn)），舍去，再用下式計(jì)算其余各頂點(diǎn)的中心點(diǎn)xc：pse2009最優(yōu)化49/53

六、復(fù)合形法檢查xc是否在可行域內(nèi)。若在，求xh的反射點(diǎn)；否則，聯(lián)結(jié)最好點(diǎn)xg（函數(shù)值最小的）與xc，在此區(qū)間內(nèi)利用隨機(jī)數(shù)構(gòu)成新的復(fù)合形。（3）計(jì)算反射點(diǎn)用下式計(jì)算反射點(diǎn)xr：反射系數(shù)通常取1.3

檢查xr是否在可行域內(nèi)。若不在，將反射系數(shù)減半，重新計(jì)算xr，如此反復(fù)，直至xr在可行域內(nèi)為止。由于采用了上述可變的反射系數(shù)，因此，復(fù)合形的延伸、收縮、壓縮的方法就沒必要采用了。pse2009最優(yōu)化50/53（4）判斷反射結(jié)果

六、復(fù)合形法

計(jì)算反射點(diǎn)的函數(shù)值，然后判斷：若有，則認(rèn)為反射成功，用xr代替xh，構(gòu)成新的復(fù)合形。

若有，則可將反射系數(shù)減半，求新的反射點(diǎn)。若反射系數(shù)已經(jīng)很小，則可用次壞點(diǎn)代替最壞點(diǎn)，重新計(jì)算中心點(diǎn)和反射點(diǎn)。（5）中止搜索給定收斂判據(jù)，計(jì)算精度要求，若有：中止搜索。pse2009最優(yōu)化51/53七、可變?nèi)莶罘ɑ舅枷耄簛?lái)源于無(wú)約束問(wèn)題最優(yōu)化的單純形法。此法適用于求解等式、不等式約束條件的極值問(wèn)題：步驟：（1）產(chǎn)生初始多面體

通常多面體頂點(diǎn)選r＋1個(gè)（r＝n－m），但當(dāng)r<2時(shí)，取r＝3。給定初始點(diǎn)和多面體邊長(zhǎng)。多面體邊長(zhǎng)的選取十分重要。邊長(zhǎng)大，易于進(jìn)入可行域（由不等式構(gòu)成的），但偏離梯度方向也大，不易收斂。為n維向量。pse2009最優(yōu)化52/53七、可變?nèi)莶罘ǎ?）計(jì)算多面體的形心點(diǎn)與復(fù)合形法相同：算出全部頂點(diǎn)的函數(shù)值，舍去最大值點(diǎn)