工程優(yōu)化設(shè)計(jì)約束間接法課件

1、工程優(yōu)化設(shè)計(jì)黃正東二0一二年九月內(nèi)容提要工程優(yōu)化問(wèn)題建模優(yōu)化數(shù)學(xué)理論一維搜索方法無(wú)約束問(wèn)題直接搜索方法無(wú)約束問(wèn)題間接接搜索方法約束問(wèn)題直接搜索方法線(xiàn)性規(guī)劃與二次規(guī)劃問(wèn)題求解約束問(wèn)題間接搜索方法啟發(fā)式算法優(yōu)化軟件系統(tǒng)約束問(wèn)題間接求解方法間接法: 將復(fù)雜的約束優(yōu)化問(wèn)題轉(zhuǎn)化為一系列簡(jiǎn)單的、容易解決的子問(wèn)題。例如，轉(zhuǎn)化為：（1）無(wú)約束問(wèn)題求解；（2）二次規(guī)劃子問(wèn)題求解；（3）線(xiàn)性規(guī)劃子問(wèn)題或線(xiàn)性約束優(yōu)化問(wèn)題。典型的方法有：懲罰函數(shù)法拉格朗日乘子法序列二次規(guī)劃方法序列線(xiàn)性規(guī)劃方法可行方向法簡(jiǎn)約梯度法約束問(wèn)題間接求解方法一。懲罰函數(shù)法-外點(diǎn)法min f(x)s.t. hi(x)=0, i=1,2,p gi

2、(x)0, i=1,2,q基本思想：允許迭代點(diǎn)在可行域外，但違反約束越大，就給出越大懲罰項(xiàng)的目標(biāo)函數(shù)值，這樣迫使搜索過(guò)程朝可行域方向進(jìn)行。0r0r1rk前一子問(wèn)題的結(jié)果作為后一子問(wèn)題的初始搜索點(diǎn)，xk*-x*約束問(wèn)題間接求解方法一。懲罰函數(shù)法-外點(diǎn)法性質(zhì)：當(dāng)rk+1rk時(shí)，G(xk+1*) G(xk*). 這里P(x,rk)=f(x)+rkG(x)。證明： 設(shè)P(x,rk)的最優(yōu)點(diǎn)為xk*, P(x,rk+1)的最優(yōu)點(diǎn)為xk+1*.那么， f(xk+1*)+rkG(xk+1*) f(xk*)+rkG(xk*) f(xk*)+rk+1G(xk*) f(xk+1*)+rk+1G(xk+1*)兩式相

3、加得， rk+1G(xk*)-G(xk+1*) rkG(xk*)-G(xk+1*)由于rk+1rk0, 故滿(mǎn)足上式須G(xk*)-G(xk+1*) 0，則有G(xk*) G(xk+1*) 。約束問(wèn)題間接求解方法一。懲罰函數(shù)法-外點(diǎn)法例子：min f(x)=x/2 s.t. 1-x0 xf,pf(x)x*P(x,r0)P(x,r1)P(x,r2)P(x,r3)P(x,rk)=x/2+rkmax(0,1-x)2考慮到此例子問(wèn)題解在可行域外，直接取：P(x,rk)=x/2+rk(1-x)2求導(dǎo)得：1/2-2rk(1-x)=0.xk*=1-1/4rk, P(x,rk)=1/2-1/(16rk)當(dāng)rk-

4、 時(shí)，xk*-1; P-1/2. 約束問(wèn)題間接求解方法一。懲罰函數(shù)法-外點(diǎn)法xf,pf(x)x*xf,pf(x)x*數(shù)值超大需適當(dāng)控制rk的初值和增加幅度約束問(wèn)題間接求解方法一。懲罰函數(shù)法-外點(diǎn)法算法：初始化k=0, xk,rk,eps,beta1.構(gòu)造無(wú)約束目標(biāo)函數(shù)解無(wú)約束極值子問(wèn)題,得xk*.判斷xk*是否滿(mǎn)足全部約束條件. 如果rkG(xk*)時(shí),才有min P(x,rk)-min f(x). 隨著rk增大,懲罰函數(shù)性態(tài)變壞(等值線(xiàn)扁平), P(x,rk)不可 避免出現(xiàn)病態(tài),以至子無(wú)約束問(wèn)題難以求解. (2). r0一開(kāi)始就取得太大, 過(guò)早出現(xiàn)性態(tài)差的P(x,rk),求極值 困難; r0

5、一開(kāi)始就取得太小,增加迭代次數(shù). 一般: r0=1, beta=5-10.g1(x)g2(x)x*P(x,r1)P(x,r2)P(x,r3)適用于中小型一般非線(xiàn)性約束優(yōu)化問(wèn)題，但較多用于等式約束優(yōu)化問(wèn)題。約束問(wèn)題間接求解方法一。懲罰函數(shù)法-內(nèi)點(diǎn)法min f(x)s.t. gi(x)0, i=1,2,q基本思想：內(nèi)點(diǎn)法的迭代過(guò)程在可行域內(nèi)，目標(biāo)函數(shù)懲罰項(xiàng)在可行域邊界筑起一道高墻,使迭代點(diǎn)不能越出可行域. 隨著懲罰項(xiàng)逐漸變化,高墻越來(lái)越陡, 從而接近真實(shí)約束邊界.只適用不等式約束問(wèn)題.r0r1rk-0前一子問(wèn)題的結(jié)果作為后一子問(wèn)題的初始搜索點(diǎn)，xk*-x*約束問(wèn)題間接求解方法一。懲罰函數(shù)法-內(nèi)點(diǎn)法

6、例子：min f(x)=x/2 s.t. 1-x0 xf,pf(x)x*P(x,r0)P(x,r1)P(x,r2)P(x,r3)P(x,rk)=x/2-rk/(1-x)求導(dǎo)得：1/2+rk/(1-x)2=0.xk*=1+2rk, P(x,rk)=(1+22rk) /2當(dāng)rk- 0時(shí)，xk*-1; P-1/2. 約束問(wèn)題間接求解方法一。懲罰函數(shù)法-內(nèi)點(diǎn)法算法：初始化k=0, xk,rk,eps,beta1.構(gòu)造無(wú)約束目標(biāo)函數(shù)解無(wú)約束極值子問(wèn)題,得xk*.判斷xk*是否滿(mǎn)足全部約束條件. 如果rkG(xk*)0,才有min P(x,rk)-min f(x). 隨著rk減小,懲罰函數(shù)變陡, 不可避免

7、出現(xiàn)1/g(x)-浮點(diǎn)溢出.r0與beta值對(duì)收斂性態(tài)有影響.一般取r0=1, beta=0.1-0.5.對(duì)于初始點(diǎn)為非可行時(shí),需要采用前處理過(guò)程,將它“拉入”可 行域內(nèi).適用于中小型不等式約束優(yōu)化問(wèn)題。約束問(wèn)題間接求解方法一。懲罰函數(shù)法-內(nèi)點(diǎn)法初始點(diǎn)生成過(guò)程：設(shè)I1= i | gi(x)0, I2= i | gi(x)0 k=0, 任取xk.計(jì)算I1和I2.如果I2為空, xk為可行,結(jié)束. 否則, 轉(zhuǎn)下步.內(nèi)點(diǎn)法解 , rk-0rk+1=beta*rk, 1beta0, k=k+1, xk+1=xk*, 轉(zhuǎn)步2. 拉入保持可行約束問(wèn)題間接求解方法一。懲罰函數(shù)法-混合法基本思想min f(x

8、)s.t. hi(x)=0, i=1,2,m gi(x)0, i=1,2,p外點(diǎn)拉入外點(diǎn)拉入內(nèi)點(diǎn)保持0r1r2rk2時(shí),半正定, M對(duì)x, 非嚴(yán)格極值存在.r2時(shí),正定, 對(duì)給定 M對(duì)x嚴(yán)格極值存在.約束問(wèn)題間接求解方法二。拉格朗日乘子法-增廣拉格朗日乘子法所以，當(dāng)r充分大時(shí)，Hesse矩陣正定或半正定。即，當(dāng)r充分大時(shí)，M對(duì)x, 的極值存在。M的極值點(diǎn)是否是原K-T方程的解呢?約束問(wèn)題間接求解方法二。拉格朗日乘子法-增廣拉格朗日乘子法當(dāng)hi(x)=0時(shí)，xM= xL.M的一階極值條件：因?yàn)槎加衕i(x)=0，所以，滿(mǎn)足M的一階極值條件的點(diǎn)與原問(wèn)題的K-T點(diǎn)完全相同等價(jià)。約束問(wèn)題間接求解方法二

9、。拉格朗日乘子法-增廣拉格朗日乘子法所以，如果存在充分大的r使M正定，它的一階極值條件的點(diǎn)也就是它的真正極值點(diǎn)；從而，求出它的所有極值點(diǎn)也就求出原約束優(yōu)化問(wèn)題所有的K-T點(diǎn)；反之，如果不存在充分大的r使M正定（此時(shí)，一般是K-T方程有多組解），M優(yōu)化方法就不一定能找到它的所有一階極值條件的點(diǎn)，也就不能找到所有K-T點(diǎn)。此時(shí)，M方法也可能失效。M方法只在第一種情況改進(jìn)了L方法，它的應(yīng)用前提是使M正定的r存在。約束問(wèn)題間接求解方法二。拉格朗日乘子法-增廣拉格朗日乘子法為了減少搜索變量，這里不直接采用針對(duì)x和的無(wú)約束搜索方法求解M的極值點(diǎn)。而是采用只針對(duì)x的無(wú)約束搜索方法求解極值點(diǎn)的x分量，同時(shí)利用

10、關(guān)系計(jì)算分量。即對(duì)x求極值min xM(x,), 對(duì)求解方程M(x,)=0 !約束問(wèn)題間接求解方法二。拉格朗日乘子法-增廣拉格朗日乘子法對(duì)于給定的和r,對(duì)M求極值xm* ，其條件是即xm*=xm*(, r)，但一般h(xm*)0.然而，一旦h(xm*)=0，就有=*和xm*=x*。這里x*是原問(wèn)題的解。選擇序列(1,r1), (2,r2), (k,rk), ,使h(xm*)-0,就有xm*-x*。由于同時(shí)需要k- *，根據(jù) 知，rh(x)-k比-k更接近-*，所以，取k+1= k-rh(x).一般來(lái)說(shuō)，rk也需要遞增，但并不需要趨向無(wú)窮大，只需要使Mxx正定就行。（克服罰函數(shù)法的病態(tài)問(wèn)題）約束

11、問(wèn)題間接求解方法二。拉格朗日乘子法-增廣拉格朗日乘子法算法1。初始化xk, k, rk, C, rb.2。解無(wú)約束問(wèn)題 min M(x, k, rk)。3。如果k+1=k, |f(xk+1)-f(xk)|eps, |h(xk+1)| rb, rk+1=rb. 轉(zhuǎn)步2。約束問(wèn)題間接求解方法二。拉格朗日乘子法-增廣拉格朗日乘子法算法分析1?？朔肆P函數(shù)法與普通拉格朗日乘子法的缺點(diǎn)。2。是目前最優(yōu)秀的約束優(yōu)化方法之一。3。對(duì)中小型、大型約束優(yōu)化問(wèn)題均適用，且計(jì)算穩(wěn)定性好。相同點(diǎn):都轉(zhuǎn)化為無(wú)約束子問(wèn)題,r為控制參數(shù);不同點(diǎn):子問(wèn)題目標(biāo)函數(shù)不同,克服了病態(tài)計(jì)算問(wèn)題;i=i-r*hi(x)約束問(wèn)題間接求解

12、方法三。序列二次規(guī)劃方法（Sequential Quadratic Programming, SQP）算法思想用牛頓法解L平穩(wěn)點(diǎn)方程，每一步迭代又轉(zhuǎn)化為求二次規(guī)劃問(wèn)題。min f(x)s.t. hi(x)=0, i=1,2,mL平穩(wěn)點(diǎn)方程約束問(wèn)題間接求解方法三。序列二次規(guī)劃方法L平穩(wěn)點(diǎn)方程的牛頓法即根據(jù)得：即為下列二次規(guī)劃問(wèn)題一階必要條件：約束問(wèn)題間接求解方法三。序列二次規(guī)劃方法這樣，解此二次規(guī)劃問(wèn)題可得d=dx, 進(jìn)而計(jì)算xk+1=xk+d.并由A(xk+1)T=g(xk+1)得k+1,從而完成一次牛頓迭代?？紤]到xk+1可能出可行域 (雖然前面考慮了約束,但近似過(guò)程使約束可能沒(méi)有精確滿(mǎn)足)

13、 ，可改換用罰函數(shù)法一維搜索確xk+1=xk+ad。算法：1。初始化，k=0, x0, 0.2。解（xk, k）處得二次規(guī)劃子問(wèn)題,得dk。3。一維搜索 min P(xk+adk), P(x)=f(x)+Mh(x)2, 得xk+1=xk+adk.4。解A(xk+1)T=g(xk+1)得k+1。5。如果收斂，停止；否則，k=k+1,轉(zhuǎn)步2。約束問(wèn)題間接求解方法約束問(wèn)題間接求解方法約束問(wèn)題間接求解方法三。序列二次規(guī)劃方法-不等式約束問(wèn)題min f(x)s.t. hi(x)=0, i=1,2,m gi(x)0, i=m+1,2,p一維搜索 min P(xk+ad ):k+1計(jì)算: A(xk+1)T=

14、g(xk+1)， A包含h和g（有效約束）的梯度。約束問(wèn)題間接求解方法三。序列二次規(guī)劃方法算法分析1。SQP是解非線(xiàn)性約束優(yōu)化問(wèn)題得最有效方法之一。2。L的Hesse矩陣可用擬牛頓法中BFGS公式迭代計(jì)算。3。方法需要一、二階導(dǎo)數(shù)信息。4。在每一步中，L的Hesse矩陣正定是保證迭代順利進(jìn)行的 重要條件。約束問(wèn)題間接求解方法三。序列二次規(guī)劃方法i=i-r*hi(x)無(wú)約束子問(wèn)題,r為控制參數(shù);病態(tài)計(jì)算問(wèn)題;整體漸近無(wú)約束子問(wèn)題,r為控制參數(shù);無(wú)病態(tài)計(jì)算問(wèn)題;整體漸近約束子問(wèn)題,無(wú)控制參數(shù);需要二階導(dǎo)數(shù);局部逼近約束問(wèn)題間接求解方法五。序列線(xiàn)性規(guī)劃法算法思想針對(duì)非線(xiàn)性約束優(yōu)化問(wèn)題，對(duì)目標(biāo)函數(shù)和約

15、束函數(shù)進(jìn)行線(xiàn)性化，求解線(xiàn)性規(guī)劃問(wèn)題確定每步移動(dòng)。min f(x)s.t. hi(x)=0, i=1,2,m gi(x)0, i=m+1,2,pk:=k+1約束問(wèn)題間接求解方法算法初始化 x=x0,k=0，dkl,dku, r1;計(jì)算f(xk)、hi(xk)和gi(xk);如果f(xk)、hi(xk)和gi(xk)滿(mǎn)足K-T條件, 結(jié)束.否則,用單純形法解上述線(xiàn)性規(guī)劃問(wèn)題,求d;xk+1=xk+d,更新move-limit dkl=r*dkl,dku=r*dku;k=k+1,轉(zhuǎn)步2.約束問(wèn)題間接求解方法五。序列線(xiàn)性規(guī)劃法Move Limit 根據(jù)線(xiàn)性化有效范圍限制最大移動(dòng)步長(zhǎng)約束問(wèn)題間接求解方法五。序列線(xiàn)性規(guī)劃法算法分析線(xiàn)性化范圍和此范圍隨迭代次數(shù)的縮小率與可行方向法相比，相同點(diǎn)是都為線(xiàn)性近似；不同點(diǎn)是這里直接確定下一點(diǎn)；那里只確定搜索方向，還需要一維搜索。等式約束： 簡(jiǎn)約梯度法 懲罰函數(shù)法 解KKT方程法（L乘子法、SQP(牛頓法)） 懲罰函數(shù)-KKT方程聯(lián)合法（增廣L乘子法、增廣SQP法）不等式約束 可行方向法 Active-set方法（局部轉(zhuǎn)化為等式約束） 松弛變量轉(zhuǎn)化為等式約束 障礙函數(shù)法（傳統(tǒng)內(nèi)點(diǎn)法） 混合約束： 受限梯度方向