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

1、工程優(yōu)化設(shè)計黃正東二0一二年九月內(nèi)容提要 工程優(yōu)化問題建模工程優(yōu)化問題建模 優(yōu)化數(shù)學(xué)理論優(yōu)化數(shù)學(xué)理論 一維搜索方法一維搜索方法 無約束問題直接搜索方法無約束問題直接搜索方法 無約束問題間接接搜索方法無約束問題間接接搜索方法 約束問題直接搜索方法約束問題直接搜索方法 線性規(guī)劃與二次規(guī)劃問題求解線性規(guī)劃與二次規(guī)劃問題求解 約束問題間接搜索方法約束問題間接搜索方法 啟發(fā)式算法啟發(fā)式算法 優(yōu)化軟件系統(tǒng)優(yōu)化軟件系統(tǒng)約束問題間接求解方法間接法間接法: : 將復(fù)雜的約束優(yōu)化問題轉(zhuǎn)化為一系列簡單的、容易將復(fù)雜的約束優(yōu)化問題轉(zhuǎn)化為一系列簡單的、容易解決的子問題。例如，轉(zhuǎn)化為：解決的子問題。例如，轉(zhuǎn)化為：（1 1

2、）無約束問題求解；）無約束問題求解；（2 2）二次規(guī)劃子問題求解；）二次規(guī)劃子問題求解；（3 3）線性規(guī)劃子問題或線性約束優(yōu)化問題。）線性規(guī)劃子問題或線性約束優(yōu)化問題。典型的方法有：典型的方法有：1.1. 懲罰函數(shù)法懲罰函數(shù)法2.2. 拉格朗日乘子法拉格朗日乘子法3.3. 序列二次規(guī)劃方法序列二次規(guī)劃方法4.4. 序列線性規(guī)劃方法序列線性規(guī)劃方法5.5. 可行方向法可行方向法6.6. 簡約梯度法簡約梯度法約束問題間接求解方法一。懲罰函數(shù)法一。懲罰函數(shù)法-外點法外點法min f(x)s.t. hi(x)=0, i=1,2,p gi(x) 0, i=1,2,q基本思想：基本思想：允許迭代點在可行域

3、外，但違反約束越大，就給出允許迭代點在可行域外，但違反約束越大，就給出越大懲罰項的目標(biāo)函數(shù)值，這樣迫使搜索過程朝可行域方向進越大懲罰項的目標(biāo)函數(shù)值，這樣迫使搜索過程朝可行域方向進行。行。piqiikikkxgrxhrxfrxP1122)(, 0max()()(),( min0r0r1rk 前一子問題的結(jié)果作為前一子問題的結(jié)果作為后一子問題的初始后一子問題的初始搜索點，搜索點，xk*-x*約束問題間接求解方法一。懲罰函數(shù)法一。懲罰函數(shù)法-外點法外點法性質(zhì)：性質(zhì)：當(dāng)當(dāng)rk+1rk時，時，G(xk+1*) G(xk*). 這里這里P(x,rk)=f(x)+rkG(x)。證明：證明： 設(shè)設(shè)P(x,rk

4、)的最優(yōu)點為的最優(yōu)點為xk*, P(x,rk+1)的最優(yōu)點為的最優(yōu)點為xk+1*.那么，那么， f(xk+1*)+rkG(xk+1*) f(xk*)+rkG(xk*) f(xk*)+rk+1G(xk*) f(xk+1*)+rk+1G(xk+1*)兩式相加得，兩式相加得， rk+1G(xk*)-G(xk+1*) rkG(xk*)-G(xk+1*)由于由于rk+1rk0, 故滿足上式須故滿足上式須G(xk*)-G(xk+1*) 0，則有則有G(xk*) G(xk+1*) 。約束問題間接求解方法一。懲罰函數(shù)法一。懲罰函數(shù)法-外點法外點法例子：例子：min f(x)=x/2 s.t. 1-x 0 xf

5、,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考慮到此例子問題解在可行考慮到此例子問題解在可行域外，直接取：域外，直接取：P(x,rk)=x/2+rk(1-x)2求導(dǎo)得：求導(dǎo)得：1/2-2rk(1-x)=0.xk*=1-1/4rk, P(x,rk)=1/2-1/(16rk)當(dāng)當(dāng)rk- 時，時，xk*-1; P-1/2. 約束問題間接求解方法一。懲罰函數(shù)法一。懲罰函數(shù)法-外點法外點法xf,pf(x)x*xf,pf(x)x*數(shù)值超大數(shù)值超大需適當(dāng)控制需適當(dāng)控制r rk k的的初值和初值和增加幅度增加幅度約束問題間接求解方法

6、一。懲罰函數(shù)法一。懲罰函數(shù)法-外點法外點法算法：算法：1. 初始化初始化k=0, xk,rk,eps,beta1.2. 構(gòu)造無約束目標(biāo)函數(shù)構(gòu)造無約束目標(biāo)函數(shù)3. 解無約束極值子問題解無約束極值子問題,得得xk*.4. 判斷判斷xk*是否滿足全部約束條件是否滿足全部約束條件. 如果如果rkG(xk*) 時時,才有才有min P(x,rk)-min f(x). 隨著隨著rk增大增大,懲罰函數(shù)性態(tài)變壞懲罰函數(shù)性態(tài)變壞(等值線扁平等值線扁平), P(x,rk)不可不可 避免出現(xiàn)病態(tài)避免出現(xiàn)病態(tài),以至子無約束問題難以求解以至子無約束問題難以求解. (2). r0一開始就取得太大一開始就取得太大, 過早出

7、現(xiàn)性態(tài)差的過早出現(xiàn)性態(tài)差的P(x,rk),求極值求極值 困難困難; r0一開始就取得太小一開始就取得太小,增加迭代次數(shù)增加迭代次數(shù). 一般一般: r0=1, beta=5-10.g1(x)g2(x)x*P(x,r1)P(x,r2)P(x,r3)適用于中小型一般非線性約束優(yōu)化問題，但較多用于等式約束優(yōu)化問題。適用于中小型一般非線性約束優(yōu)化問題，但較多用于等式約束優(yōu)化問題。約束問題間接求解方法一。懲罰函數(shù)法一。懲罰函數(shù)法-內(nèi)點法內(nèi)點法min f(x)s.t. gi(x) 0, i=1,2,q基本思想：基本思想：內(nèi)點法的迭代過程在可行域內(nèi)，目標(biāo)函數(shù)懲罰項內(nèi)點法的迭代過程在可行域內(nèi)，目標(biāo)函數(shù)懲罰項在可

8、行域邊界筑起一道高墻在可行域邊界筑起一道高墻,使迭代點不能越出可行域使迭代點不能越出可行域. 隨著隨著懲罰項逐漸變化懲罰項逐漸變化,高墻越來越陡高墻越來越陡, 從而接近真實約束邊界從而接近真實約束邊界.只適用不等式約束問題只適用不等式約束問題.qiikkxgrxfrxP1)(/1)(),( minr0r1rk-0前一子問題的結(jié)果作為前一子問題的結(jié)果作為后一子問題的初始后一子問題的初始搜索點，搜索點，xk*-x*約束問題間接求解方法一。懲罰函數(shù)法一。懲罰函數(shù)法-內(nèi)點法內(nèi)點法例子：例子：min f(x)=x/2 s.t. 1-x 0 xf,pf(x)x*P(x,r0)P(x,r1)P(x,r2)P

9、(x,r3)P(x,rk)=x/2-rk/(1-x)求導(dǎo)得：求導(dǎo)得：1/2+rk/(1-x)2=0.xk*=1+ 2rk, P(x,rk)=(1+2 2rk) /2當(dāng)當(dāng)rk- 0時，時，xk*-1; P-1/2. 約束問題間接求解方法一。懲罰函數(shù)法一。懲罰函數(shù)法-內(nèi)點法內(nèi)點法算法：算法：1. 初始化初始化k=0, xk,rk,eps,beta1.2. 構(gòu)造無約束目標(biāo)函數(shù)構(gòu)造無約束目標(biāo)函數(shù)3. 解無約束極值子問題解無約束極值子問題,得得xk*.4. 判斷判斷xk*是否滿足全部約束條件是否滿足全部約束條件. 如果如果rkG(xk*)0,才有才有min P(x,rk)-min f(x). 隨著隨著r

10、k減小減小,懲罰函數(shù)變陡懲罰函數(shù)變陡, 不可避免出現(xiàn)不可避免出現(xiàn)1/g(x)- 浮點溢出浮點溢出.5. r0與與beta值對收斂性態(tài)有影響值對收斂性態(tài)有影響.一般取一般取r0=1, beta=0.1-0.5.6. 對于初始點為非對于初始點為非可行時可行時,需要采用前處理過程需要采用前處理過程,將它將它“拉入拉入”可可 行域內(nèi)行域內(nèi).適用于中小型不等式約束優(yōu)化問題。適用于中小型不等式約束優(yōu)化問題。約束問題間接求解方法一。懲罰函數(shù)法一。懲罰函數(shù)法-內(nèi)點法內(nèi)點法初始點生成過程：初始點生成過程：設(shè)設(shè)I1= i | gi(x) 0, I2= i | gi(x)0 1. k=0, 任取任取xk.2. 計算

11、計算I1和和I2.3. 如果如果I2為空為空, xk為可行為可行,結(jié)束結(jié)束. 否則否則, 轉(zhuǎn)下步轉(zhuǎn)下步.4. 內(nèi)點法解內(nèi)點法解 , rk-05. rk+1=beta*rk, 1beta0, k=k+1, xk+1=xk*, 轉(zhuǎn)步轉(zhuǎn)步2. 12)(/ 1)(),(IiikIiikxgrxgrxP12)(/1)(),(IiikIiikxgrxgrxP拉入拉入保持可行保持可行約束問題間接求解方法一。懲罰函數(shù)法一。懲罰函數(shù)法-混合法混合法基本思想基本思想min f(x)s.t. hi(x)=0, i=1,2,m gi(x)0, i=1,2,p0)(|,0)(|,)()(, 0max()(11)(),(

12、2112212xgiIxgiIxhrxgrxgrxfrxPiimiikIiIiikikk外點拉入外點拉入外點拉入外點拉入內(nèi)點保持內(nèi)點保持0r1r2rk2r2時時, ,半正定半正定, M, M對對x, x, 非嚴格非嚴格極值存在極值存在. .r2r2時時, ,正定正定, , 對給定對給定 M M對對x x嚴格極值存在嚴格極值存在. .約束問題間接求解方法二。二。拉格朗日乘子法拉格朗日乘子法-增廣拉格朗日乘子法增廣拉格朗日乘子法所以，當(dāng)所以，當(dāng)r充分大時，充分大時，Hesse矩陣正定或半正定。矩陣正定或半正定。即，當(dāng)即，當(dāng)r充分大時，充分大時，M對對x, 的極值存在。的極值存在。M的極值點是否是原

13、的極值點是否是原K-T方程的解呢方程的解呢?約束問題間接求解方法miiiimiiimiiimiiixxxhxrhxfxhxhrxhxfxhxhrxLrxM1111)()()()()()()()()(),(),(二。二。拉格朗日乘子法拉格朗日乘子法-增廣拉格朗日乘子法增廣拉格朗日乘子法當(dāng)當(dāng)hi(x)=0時時，x xM= xL.M的一階極值條件：的一階極值條件： ,.,2 , 1, 0)(0mixhMMix因為都有因為都有hi(x)=0，所以，滿足所以，滿足M M的的一階極值條件的點一階極值條件的點與原問題與原問題的的K-TK-T點點完全相同等價。完全相同等價。約束問題間接求解方法二。二。拉格朗日

14、乘子法拉格朗日乘子法-增廣拉格朗日乘子法增廣拉格朗日乘子法所以，如果存在充分大的所以，如果存在充分大的r r使使M M正定，它的正定，它的一階極值條件的點一階極值條件的點也就是它的也就是它的真正極真正極值點值點；從而，求出它的；從而，求出它的所有所有極極值點值點也就求出也就求出原約束優(yōu)化問題原約束優(yōu)化問題所有的所有的K-T點點；反之，反之，如果不存在充分大的如果不存在充分大的r r使使M M正定（此時，一般是正定（此時，一般是K-T方程方程有多組解有多組解），），M M優(yōu)化方法就不一定能找到它的優(yōu)化方法就不一定能找到它的所有所有一階極值條一階極值條件的點，也就不能找到所有件的點，也就不能找到所

15、有K-TK-T點。此時，點。此時，M M方法也可能失效。方法也可能失效。M方法方法只在第一種情況改進了只在第一種情況改進了L方法方法，它的應(yīng)用前提是使，它的應(yīng)用前提是使M正定正定的的r存在。存在。約束問題間接求解方法二。二。拉格朗日乘子法拉格朗日乘子法-增廣拉格朗日乘子法增廣拉格朗日乘子法為了減少搜索變量，這里不直接采用針對為了減少搜索變量，這里不直接采用針對x和和的的無約束搜索方法求解無約束搜索方法求解M M的極值點。的極值點。而是采用只針對而是采用只針對x的無約束搜索方法求解極值點的的無約束搜索方法求解極值點的x分量，分量，同時利用關(guān)系同時利用關(guān)系計算計算分量分量。miiimiiiixxh

16、xfxhxrhxfrxM1*1)()()()()(),(即對x求極值min xM(x,), 對求解方程M(x,)=0 !約束問題間接求解方法0),(*rxMmx二。二。拉格朗日乘子法拉格朗日乘子法-增廣拉格朗日乘子法增廣拉格朗日乘子法對于對于給定的給定的和和r, ,對對M求極值求極值xm* ，其條件是，其條件是即即xm* *= =xm* *( (, r) )，但一般，但一般h(h(xm*) )0.然而，一旦然而，一旦h(xm*)=0，就有就有=*和和xm*=x*。這里這里x*是原問題的是原問題的解。解。選擇序列選擇序列(1,r1), (2,r2), (k,rk), ,使使h(xm*)-0,就有

17、就有xm*-x*。由于同時需要由于同時需要k- *，根據(jù)根據(jù) miiiixxhxrhxfrxM1)()()(),(知，知，rh(x)-k比比-k更接近更接近-*，所以，取所以，取k+1= k-rh(x).一般來說，一般來說，r rk k也需要遞增，但并不需要趨向無窮大，只需也需要遞增，但并不需要趨向無窮大，只需要使要使M Mxxxx正定就行。（克服罰函數(shù)法的病態(tài)問題）正定就行。（克服罰函數(shù)法的病態(tài)問題）約束問題間接求解方法二。二。拉格朗日乘子法拉格朗日乘子法-增廣拉格朗日乘子法增廣拉格朗日乘子法算法算法1 1。初始化。初始化x xk k, , k k, , r rk k, C, , C, r

18、rb b. .2 2。解無約束問題。解無約束問題 min M(x, min M(x, k k, , r rk k) )。3 3。如果。如果k+1k+1= =k k, |f(x, |f(xk+1k+1)-f(x)-f(xk k)|)|epseps, |h(x, |h(xk+1k+1)|)| r rb b, r, rk+1k+1= =r rb b. . 轉(zhuǎn)步轉(zhuǎn)步2 2。約束問題間接求解方法miiimiixhxhrxfrxM112)()(2)(),(二。二。拉格朗日乘子法拉格朗日乘子法-增廣拉格朗日乘子法增廣拉格朗日乘子法算法分析算法分析1 1。克服了罰函數(shù)法與普通。克服了罰函數(shù)法與普通拉格朗日乘子

19、法的缺點。拉格朗日乘子法的缺點。2 2。是目前最優(yōu)秀的約束優(yōu)化方法之一。是目前最優(yōu)秀的約束優(yōu)化方法之一。3 3。對中小型、大型約束優(yōu)化問題均適用，且計算穩(wěn)定性好。對中小型、大型約束優(yōu)化問題均適用，且計算穩(wěn)定性好。miixhrxfrxP12)(2)(),(相同點相同點: :都轉(zhuǎn)化為無約束子問題都轉(zhuǎn)化為無約束子問題,r,r為控制參數(shù)為控制參數(shù); ;不同點不同點: :子問題目標(biāo)函數(shù)不同子問題目標(biāo)函數(shù)不同, ,克服了病態(tài)計算問題克服了病態(tài)計算問題; ;i=i-r*hi(x)約束問題間接求解方法三。三。序列二次規(guī)劃方法（序列二次規(guī)劃方法（Sequential Quadratic Programming,

20、 SQP）算法思想算法思想用牛頓法解用牛頓法解L L平穩(wěn)點方程，每一步迭代又轉(zhuǎn)化為求二次規(guī)劃平穩(wěn)點方程，每一步迭代又轉(zhuǎn)化為求二次規(guī)劃問題。問題。min f(x)s.t. hi(x)=0, i=1,2,m )(),.,(),()(),(),.,(),()( , 0)(),( , 0)()()()(),(21211xhxhxhxAxhxhxhxhxhxLxAxgxhxfxLmTmTTmiiixmiiixhxfxL1)()(),(L L平穩(wěn)點方程平穩(wěn)點方程約束問題間接求解方法 )(),(0)()(),(),(),( ,2211kkkxkTkkkxxkkkkkkkkxhxLddxxAxAxLxLddx

21、xLddxxx ,)()(),(1dxAxgxLkkkTkkkkx12,)()(0)()(),(kkkkTkkkxxxhxgdxxAxAxL三。三。序列二次規(guī)劃方法序列二次規(guī)劃方法L L平穩(wěn)點方程的牛頓法平穩(wěn)點方程的牛頓法即即根據(jù)根據(jù)得：得：即為下列二次規(guī)劃問題即為下列二次規(guī)劃問題一階必要條件：一階必要條件：)(0)()( . .),(21)()( min2dxdxhdxAtsdxLdxgddqkkkkxxTkT約束問題間接求解方法三。三。序列二次規(guī)劃方法序列二次規(guī)劃方法這樣，解此這樣，解此二次規(guī)劃問題可得二次規(guī)劃問題可得d=dx, 進而計算進而計算xk+1=xk+d.并由并由A(xk+1)T

22、=g(xk+1)得得k+1,從而完成一次牛頓迭代。從而完成一次牛頓迭代?？紤]到考慮到xk+1可能出可行域可能出可行域 (雖然前面考慮了約束雖然前面考慮了約束, ,但近似過程使但近似過程使約束可能沒有精確滿足約束可能沒有精確滿足) ，可改換用罰函數(shù)法一維搜索確，可改換用罰函數(shù)法一維搜索確x xk+1k+1=xk+ad。算法：算法：1 1。初始化，。初始化，k=0, xk=0, x0 0, , 0.2。解（解（x xk k, , k）處得二次規(guī)劃子問題）處得二次規(guī)劃子問題, ,得得d dk k。3 3。一維搜索。一維搜索 min min P(P(xk+adk), P(x)=f(x)+Mh(x),

23、P(x)=f(x)+Mh(x)2 2, , 得得x xk+1k+1= =xk+adk.4。解解A(xA(xk+1k+1) )T T=g(x=g(xk+1k+1) )得得k+1k+1。5 5。如果收斂，停止；否則，。如果收斂，停止；否則，k=k+1,k=k+1,轉(zhuǎn)步轉(zhuǎn)步2 2。約束問題間接求解方法約束問題間接求解方法約束問題間接求解方法mipmiiiiikkkkkkxxTkTxgxhxfxLgBhAxgdxBxhdxAtsdxLdxfddq11112)()()(),(,.)(,.),(0)()( 0)()( . .),(21)()( min三。三。序列二次規(guī)劃方法序列二次規(guī)劃方法-不等式約束問題

24、不等式約束問題min f(x)s.t. hi(x)=0, i=1,2,m gi(x)0, i=m+1,2,pmipmiiixgMxhMxfxP1122)(, 0max()()()(一維搜索一維搜索 min min P(xP(xk k+a+ad d ):):k+1計算計算: A(xk+1)T=g(xk+1)， A包含包含h h和和g g（有效約束）的梯度。（有效約束）的梯度。約束問題間接求解方法三。三。序列二次規(guī)劃方法序列二次規(guī)劃方法算法分析算法分析1 1。SQPSQP是解非線性約束優(yōu)化問題得最有效方法之一是解非線性約束優(yōu)化問題得最有效方法之一。2。L L的的HesseHesse矩陣可用擬牛頓法

25、中矩陣可用擬牛頓法中BFGSBFGS公式迭代計算。公式迭代計算。3。方法需要一、二階導(dǎo)數(shù)信息。方法需要一、二階導(dǎo)數(shù)信息。4。在每一步中，。在每一步中，L L的的HesseHesse矩陣正定是保證迭代順利進行的矩陣正定是保證迭代順利進行的 重要條件。重要條件。約束問題間接求解方法三。三。序列二次規(guī)劃方法序列二次規(guī)劃方法miiimiixhxhrxfrxM112)()(2)(),(minmiixhrxfrxP12)(2)(),(mini=i-r*hi(x)0)()( .),(21)()( min2kkkkxxTkTxhdxAtsdxLdxgddq無約束子問題無約束子問題,r,r為控制參數(shù)為控制參數(shù);

26、 ;病態(tài)計算問題病態(tài)計算問題; ;整體漸近整體漸近無約束子問題無約束子問題,r,r為控制參數(shù)為控制參數(shù); ;無無病態(tài)計算問題病態(tài)計算問題; ;整體漸近整體漸近約束子問題約束子問題, ,無控制參數(shù)無控制參數(shù); ;需要二階導(dǎo)數(shù)需要二階導(dǎo)數(shù); ;局部逼近局部逼近約束問題間接求解方法五。五。序列線性規(guī)劃法序列線性規(guī)劃法算法思想算法思想 針對非線性約束優(yōu)化問題，對目標(biāo)函數(shù)和約束函數(shù)針對非線性約束優(yōu)化問題，對目標(biāo)函數(shù)和約束函數(shù)進行線性化，求解線性規(guī)劃問題確定每步移動。進行線性化，求解線性規(guī)劃問題確定每步移動。min f(x)s.t. hi(x)=0, i=1,2,m gi(x)0, i=m+1,2,pdx

27、xdddxgdxgxhdxhtsxfdxfkkuklkkiTkikiTkikTk1 0)()( 0)()( . .)()( mink:=k+1約束問題間接求解方法算法算法1.1. 初始化初始化 x=xx=x0 0,k=0,k=0，d dk kl l,d dk ku u, r1;, r1;2.2. 計算計算 f(xf(xk k) )、 h hi i(x(xk k) )和和 g gi i(x(xk k) ); ;3.3. 如果如果 f(xf(xk k) )、 h hi i(x(xk k) )和和 g gi i(x(xk k) )滿足滿足K-TK-T條件條件, , 結(jié)束結(jié)束. .4.4. 否則否則, ,用單純形法解上述線性規(guī)劃問題用單純形法解上述線性規(guī)劃問題, ,求求d;d;5.5. x xk+1k+1= =x xk k+d+d, ,更新更新move-limit move-limit d dk kl l=r=r* *d dk kl l,d dk ku u=r=r* *d dk ku u; ;6.6. k=k+1,k=k+1,轉(zhuǎn)步轉(zhuǎn)步2.2.約束問題間接求解方法五。五。序列線性規(guī)劃法序列線性規(guī)劃法Move Limit Move Limit 根據(jù)線性化有效范圍限制根據(jù)線性化有效范圍限制最