現(xiàn)代設(shè)計(jì)方法-優(yōu)化設(shè)計(jì)5-約束優(yōu)化推薦課件

1、現(xiàn)代設(shè)計(jì)方法優(yōu)化設(shè)計(jì)部分優(yōu)化設(shè)計(jì)部分黃正東，吳義忠二0一三年二月12021/8/22本章主要內(nèi)容本章主要內(nèi)容 優(yōu)化設(shè)計(jì)概述優(yōu)化設(shè)計(jì)概述 優(yōu)化設(shè)計(jì)的數(shù)學(xué)基礎(chǔ)優(yōu)化設(shè)計(jì)的數(shù)學(xué)基礎(chǔ) 一維探索優(yōu)化方法一維探索優(yōu)化方法 無(wú)約束優(yōu)化方法無(wú)約束優(yōu)化方法 約束問(wèn)題優(yōu)化方法約束問(wèn)題優(yōu)化方法 優(yōu)化設(shè)計(jì)若干問(wèn)題優(yōu)化設(shè)計(jì)若干問(wèn)題22021/8/22 優(yōu)化設(shè)計(jì)概述優(yōu)化設(shè)計(jì)概述 優(yōu)化設(shè)計(jì)的數(shù)學(xué)基礎(chǔ)優(yōu)化設(shè)計(jì)的數(shù)學(xué)基礎(chǔ) 一維探索優(yōu)化方法一維探索優(yōu)化方法 無(wú)約束優(yōu)化方法無(wú)約束優(yōu)化方法 約束問(wèn)題優(yōu)化方法約束問(wèn)題優(yōu)化方法 優(yōu)化設(shè)計(jì)若干問(wèn)題優(yōu)化設(shè)計(jì)若干問(wèn)題 單純形與復(fù)合形法單純形與復(fù)合形法 隨機(jī)隨機(jī)方向法方向法 可行方向法可行方向法

2、SQPSQP方法方法 懲懲罰函數(shù)法罰函數(shù)法 約束問(wèn)題優(yōu)化方法32021/8/22約束問(wèn)題優(yōu)化方法 直接法直接法復(fù)合形法隨機(jī)方向法可行方向法序列二次規(guī)劃 間接法間接法 懲罰函數(shù)法直接法：直接法：在可行域內(nèi)迭代找一序列點(diǎn)，每步降低目標(biāo)函數(shù)值，直至達(dá)到最優(yōu)解。間接法：間接法：將約束問(wèn)題 變換為一序列無(wú)約束問(wèn)題、或簡(jiǎn)單的約束問(wèn)題，這些子問(wèn)題的解收斂于原問(wèn)題的解。42021/8/221. 無(wú)約束單純形法(1) (1) 算法思想算法思想從初始單純形開(kāi)始，逐個(gè)去除最大值，翻滾（收縮或壓從初始單純形開(kāi)始，逐個(gè)去除最大值，翻滾（收縮或壓縮單純形）朝著最小值逼近，直到單純形邊長(zhǎng)小于精縮單純形）朝著最小值逼近，直到

3、單純形邊長(zhǎng)小于精度值。度值。單純形單純形（SimplexSimplex）概念概念: : n n維空間中的維空間中的n+1n+1面面體體52021/8/22無(wú)約束單純形法-（1）反射f(xf(xh h)=maxf(x)=maxf(x0 0), f(x), f(x1 1), ), ,f(x,f(xn n) ) - - 高點(diǎn)高點(diǎn)f(xf(xl)=minf(x)=minf(x0 0), f(x), f(x1 1), ), ,f(x,f(xn n) - ) - 低點(diǎn)低點(diǎn)x x= =nhiiinx, 01-除最高點(diǎn)外的所有點(diǎn)的形心除最高點(diǎn)外的所有點(diǎn)的形心xhx2x1xxrx xr r= =x x+a(+a

4、(x x-x-xh h) )-反射點(diǎn)，反射點(diǎn)，a a反射系數(shù)，一般取反射系數(shù)，一般取 a=1.a=1.62021/8/22無(wú)約束單純形法-（2）擴(kuò)張分三種分三種情況情況產(chǎn)生產(chǎn)生新新點(diǎn)點(diǎn): :x xe e= =x x+y(x+y(xr r- -x x) )若若f(xf(xr r) ) f(xf(xe e),),則則x xe e -x-xh h否則，否則， x xr r - x- xh h1 1。如果。如果f(xf(xl)f(x)f(xr), ), 進(jìn)一步擴(kuò)展進(jìn)一步擴(kuò)展 擴(kuò)展系數(shù)擴(kuò)展系數(shù)y1, y1, 一般一般y=2.y=2.xhx2xlxxrxef f(x xr r)比所有單純形點(diǎn)上值小比所有單

5、純形點(diǎn)上值小不進(jìn)一步擴(kuò)展不進(jìn)一步擴(kuò)展, ,避免狹窄單純形避免狹窄單純形72021/8/22無(wú)約束單純形法分三種分三種情況情況產(chǎn)生產(chǎn)生新新點(diǎn)點(diǎn): :2 2。如果如果maxf(xmaxf(xi i),i),i hh f(xf(xr) ) f(xf(xl),),則則 x xr r - x- xh hxhx2x1xxrf f(x xr r)在單純形點(diǎn)上值之間在單純形點(diǎn)上值之間, ,但最少比第二最大但最少比第二最大值小值小.82021/8/223 3。如果如果f(xf(xr r)maxf(x)maxf(xi i),i),i h,h,則則 f(x f(xh h)=minf(x)=minf(xh h),f(

6、x),f(xr r) 收縮收縮x xc c= =x x+b(x+b(xh h- -x x), 0b1), 0bx-xh h92021/8/22 4.4.如果如果f(xf(xc c) ) f(xf(xh h) ), ,x xc c -x xh h（上圖上圖） 否則否則（反射點(diǎn)和收縮點(diǎn)函數(shù)值都比較大（反射點(diǎn)和收縮點(diǎn)函數(shù)值都比較大），），以以x xl為中心壓縮整個(gè)為中心壓縮整個(gè)單純形（極小值點(diǎn)在壓縮的單純單純形（極小值點(diǎn)在壓縮的單純性內(nèi)）：性內(nèi)）： x xi i=x=xi i+0.5(x+0.5(xl-xi), i=0,1,2,), i=0,1,2,n,n無(wú)約束單純形法無(wú)約束單純形法-（4）壓縮）壓

7、縮xhx2xlx2xhf f(x xr r) 最少最少比第二最大比第二最大值大值大.102021/8/222. 復(fù)合形法(1) (1) 算法思想算法思想對(duì)于n維變量空間,單純形是n+1個(gè)頂點(diǎn).復(fù)合形法是多個(gè)單純形合并成的超多面體,頂點(diǎn)數(shù)n+1.復(fù)合形法與單純形極為相似,其不同之處:1.復(fù)合形法不限制頂點(diǎn)個(gè)數(shù)為n+1,復(fù)合形法頂點(diǎn)個(gè)數(shù)是k, 2nkn+1.2.2.復(fù)合形法需要檢查頂點(diǎn)的可行性復(fù)合形法需要檢查頂點(diǎn)的可行性, , 即是否滿足約束即是否滿足約束. .112021/8/22初始復(fù)合形法生成初始復(fù)合形法生成1.1.隨機(jī)測(cè)試找到一個(gè)可行點(diǎn)隨機(jī)測(cè)試找到一個(gè)可行點(diǎn)2.2.隨機(jī)生成其它點(diǎn)隨機(jī)生成其

8、它點(diǎn)3.3.計(jì)算可行點(diǎn)的中心點(diǎn)計(jì)算可行點(diǎn)的中心點(diǎn)4.4.中心點(diǎn)不可行時(shí)中心點(diǎn)不可行時(shí), ,不計(jì)最遠(yuǎn)點(diǎn)不計(jì)最遠(yuǎn)點(diǎn) 重新計(jì)算中心重新計(jì)算中心5.5.將不可行點(diǎn)向中心拉靠將不可行點(diǎn)向中心拉靠6.6.初始復(fù)合形初始復(fù)合形122021/8/22（1） 計(jì)算(2) (2) 算法算法 ( (反射、擴(kuò)張、收縮、壓縮）反射、擴(kuò)張、收縮、壓縮）XhXgXlXc,.,2 , 1),(min)(,.,2 , 1),(max)(,.,2 , 1),(max)(kjXfXfhjkjXfXfkjXfXfjljgjh)(11 ,.,2, 1hjkjjcXkX（2） 計(jì)算最高點(diǎn)次高點(diǎn)最低點(diǎn)最高點(diǎn)之外其它點(diǎn)的中心Step 1St

9、ep 1： 反射反射成功反射的條件是：g(Xr) f(Xh) 132021/8/22若f(Xr)相對(duì)于f(Xh)下降較多，如f(Xr) f(Xg)，則執(zhí)行擴(kuò)張步驟：0 . 1)(crreXXXXXhXgXlXcXrXe若f(Xe) f(Xc)， 則執(zhí)行收縮步驟：7 . 0, 1)(取hchkXXXX若f(Xk)5時(shí),可取k2n.172021/8/223. 隨機(jī)方向法（1）在可行域內(nèi)選一初始點(diǎn)x(0),以給定的步長(zhǎng)a=a(0),沿某隨機(jī)選取的方向S(1)取探索點(diǎn)x=x(0)+aS(1),若該點(diǎn)同時(shí)符合下降性（f(x)m(取50-100)次隨機(jī)采樣，均未找到成功的探索方向S(i)，則將步長(zhǎng)a減半。

10、（4）若步長(zhǎng)aeps均未找到成功的探索方向S(i)，結(jié)束。無(wú)一維搜索無(wú)一維搜索算法思想：算法思想：182021/8/22隨機(jī)方向法192021/8/22生成隨機(jī)方向：生成隨機(jī)方向：endyrandnifori);1 ,1(12 );1 ,0()1 ,0( ,.,2 ,1 202021/8/22212021/8/22222021/8/224. 可行方向法可行方向法是用梯度去求解約束非線性最優(yōu)化問(wèn)題的一種有代表性的直接解法，是求解大型約束優(yōu)化問(wèn)題的主要方法之一。其收斂速度快，效果好，但程序比較復(fù)雜，計(jì)算困難且工作量大。數(shù)學(xué)基礎(chǔ)：梯度法、方向?qū)?shù)、K-T條件 線性規(guī)劃，線性規(guī)劃，約束一維搜索約束一維

11、搜索適用條件：目標(biāo)函數(shù)和約束函數(shù)一階連續(xù)可微, 只有不等式約束。232021/8/22可行方向法 在可行域內(nèi)選擇一個(gè)初始點(diǎn)，當(dāng)確定了一個(gè)可行方向S(k)和適當(dāng)步長(zhǎng)后，按公式進(jìn)行迭代計(jì)算，通過(guò)調(diào)整可行方向，使其既不超出可行域，又使目標(biāo)函數(shù)值有所下降，經(jīng)過(guò)若干次迭代，使迭代點(diǎn)逐步逼近約束最優(yōu)點(diǎn)。 (1)算法思路)()()()1(kkkkSXX242021/8/22(2)產(chǎn)生可行方向的條件可行條件方向S(k)可行，是指沿該方向作微小移動(dòng)后，所得到的新點(diǎn)應(yīng)是可行點(diǎn)。 01g02g04g03g)(kX)(kS01g02g04g03g)(kX)(kS)()(2kXg01g02g04g03g)(kX)(kS

12、)()(2kXg)()(3kXg252021/8/22可行的含義： 若點(diǎn)X(k)在J個(gè)約束面的交集上（即點(diǎn)X(k)有J個(gè)起作用約束），要滿足可行條件，方向S(k)應(yīng)和這J個(gè)約束函數(shù)在點(diǎn)X(k)的梯度 的夾角均大于等于900，若用向量關(guān)系式表示為： )()(kkuIuXg)( 0)()()(kkTkiIiSXg可行條件可行條件262021/8/22下降條件 方向下降條件是指沿該方向作微小移動(dòng)后，所得新點(diǎn)的目標(biāo)函數(shù)值是下降的，而且下降的愈快愈好，顯然，如果負(fù)梯度方向是可行方向，那么沿負(fù)梯度方向進(jìn)行移動(dòng)最有利。 滿足下降條件的方向S(k)應(yīng)和目標(biāo)函數(shù)在點(diǎn)X(k)的梯度 交成鈍角。用向量關(guān)系式可表示為

13、：)(kXf0)()(kTkSXf下降條件下降條件272021/8/22 綜上所述，可行方向就是既滿足可行條件，又滿足下降條件的方向。用向量關(guān)系式表示為： )( 0)()()(kkTkuIuSXg0)()(kTkSXf可行條件可行條件下降條件下降條件同時(shí)滿足上面兩個(gè)條件的方向稱(chēng)為可行方向，又稱(chēng)為下降可行方向?？尚蟹较蚝芏?，哪一個(gè)最快最優(yōu)呢？可行方向很多，哪一個(gè)最快最優(yōu)呢？282021/8/22最佳下降可行方向最佳下降可行方向 在一個(gè)點(diǎn)的所有下降可行方向中，使目標(biāo)函數(shù)取得最大下降量的方向稱(chēng)為最佳下降可行方向，顯然，當(dāng)點(diǎn)X(k)處于可行域內(nèi)時(shí)，目標(biāo)函數(shù)的負(fù)梯度方向就是最佳下降可行方向，當(dāng)點(diǎn)X(k)

14、處于幾個(gè)起作用約束的交點(diǎn)或交線上，即 kkikkiIiXgIiXg00)()(合的起作用約束的下標(biāo)集為點(diǎn)）（kkXI292021/8/22式 和 只能提供下降可行方向的范圍，而不能直接給出最佳下降可行方向，但是可以在滿足上述可行條件的前提下，通過(guò)方向?qū)?shù)極小化（保證最佳）的求解得到最佳下降可行方向。)(0)()()(kkTkiIiSXg 目標(biāo)函數(shù)在S方向的方向?qū)?shù)反映了目標(biāo)函數(shù)值沿S方向的變化情況。方向?qū)?shù)越大，則目標(biāo)函數(shù)值增加越快，反之，方向?qū)?shù)越小，目標(biāo)函數(shù)值下降越快。 無(wú)約束情況下，負(fù)梯度方向是最好的方向。0)()(kTkSXf302021/8/22目標(biāo)函數(shù)f(X)在點(diǎn) X(k)的方向?qū)?/p>

15、數(shù)SXfSXfT(k)(k)由于梯度 是常數(shù)向量，則方向?qū)?shù)是S的線性函數(shù)，故最佳可行方向的尋求可歸結(jié)為以下線性線性規(guī)劃規(guī)劃問(wèn)題。 )(kXf ), 2 , 1( 11)(0. .min)()(nisIjSXgtsSXfSikTkjTk 為為常常數(shù)數(shù)向向量量式式中中，)(21,kuTnXgsssS 每次盡量沿著每次盡量沿著負(fù)梯度的方向！負(fù)梯度的方向！約束梯度法約束梯度法序列線性規(guī)劃法序列線性規(guī)劃法312021/8/22（4）可行方向法的迭代步驟1）給定初始內(nèi)點(diǎn)X(0)，收斂精度和約束允差，置k=0；2）確定點(diǎn)X(k)的起作用約束集合 當(dāng)Ik為空集（表示約束都不起作用），且點(diǎn)X(k)在可行域內(nèi)時(shí)

16、，如果 ，則令 ,終止計(jì)算;否則,令 ，轉(zhuǎn)（5）； 當(dāng)為非空時(shí)（表示有起作用約束），轉(zhuǎn)（3）；muXguXIkukk, 2 , 1,)()( )(kXf，)(*kXX )(*kXfXf kkXfS322021/8/223）收斂判斷：點(diǎn)X(k)是否滿足K-TK-T條件條件； 令 ，解出 若 ，輸出 ，終止迭代； 若 ，轉(zhuǎn)4）. 00ukuIuukXgXfk 0kuIuukXgXfku 0全全大大于于u，)(*kXX )(*kXfXf0不不全全大大于于u332021/8/224）求解線性規(guī)劃問(wèn)題 得到S*，令S(k)=S*（最佳下降可行方向）；5）在方向S(k)上進(jìn)行約束一維搜索約束一維搜索得點(diǎn)X

17、(k+1)，令k=k+1，轉(zhuǎn)（2）。 ), 2 , 1( 11)(0. .min)()(nisIuSXgtsSXfSikTkuTk 342021/8/22(3)約束一維搜索 所謂約束一維搜索是指求解一元函數(shù)約束極小點(diǎn)的算法，與前面講的一維搜索相比，其特點(diǎn)在于：確定初始區(qū)間時(shí)，對(duì)產(chǎn)生的每一個(gè)探測(cè)點(diǎn)都進(jìn)行可行性判斷，如果違反了某個(gè)或某些約束條件，就必須減小步長(zhǎng)因子，以使新的探測(cè)點(diǎn)落在最近的一個(gè)約束曲面上或約束曲面的一個(gè)允許的區(qū)間內(nèi)。 約束容限：約束容限：如果如果 ( (給定的約束容給定的約束容限限) )，則認(rèn)為點(diǎn)，則認(rèn)為點(diǎn)X(k)落在約束邊界上，亦即它是可行點(diǎn)。落在約束邊界上，亦即它是可行點(diǎn)。 (

18、 )( )(),kkuXgX滿足352021/8/22*4. SQP法（序列二次規(guī)劃）（約束擬牛頓法，約束變尺度法）每次盡量沿著擬每次盡量沿著擬牛頓的方向！牛頓的方向！可行條件可行條件362021/8/225. 懲罰函數(shù)法 內(nèi)點(diǎn)法 外點(diǎn)法 混合法 懲罰函數(shù)法是求解約束優(yōu)化問(wèn)題的間接法的一種。它是將目標(biāo)函數(shù)和約束條件構(gòu)造成一個(gè)新的目標(biāo)函數(shù)，將約束最優(yōu)化問(wèn)題轉(zhuǎn)化為無(wú)約束最優(yōu)化問(wèn)題，然后利用各種有效的無(wú)約束最優(yōu)化解法求解而得到約束最優(yōu)化的近似解。這是一種使用廣泛的有效的間接解法。372021/8/221.懲罰函數(shù)法的基本思路 將不等式約束 、等式約束 和待定系數(shù) （加權(quán)因子）經(jīng)加權(quán)轉(zhuǎn)化后，與原目標(biāo)函

19、數(shù)f(X)一起組成一個(gè)新的目標(biāo)函數(shù) （懲罰函數(shù)），然后對(duì)它求最優(yōu)解。 ), 2 , 1(0muXgu ), 2 , 1(0pvXhv kr krX,382021/8/22 ), 2 , 1(0), 2 , 1(0. .minpvXhmuXgtsRXXfvun 對(duì)于優(yōu)化問(wèn)題對(duì)于優(yōu)化問(wèn)題把其中不等式和等式約束函數(shù)值經(jīng)加權(quán)處理后，和原目標(biāo)函數(shù)結(jié)合新的目標(biāo)函數(shù): ( )( )( )( )121211min,pmkkkkuvuvX rrfXrG gXrH hX懲罰函數(shù)懲罰函數(shù)392021/8/22 懲罰函數(shù)中的后兩項(xiàng)稱(chēng)為懲罰項(xiàng)。懲罰項(xiàng)滿足下列要求： 當(dāng)滿足約束條件時(shí)，懲罰項(xiàng)的值很小或?yàn)?； 當(dāng)不滿足約束

20、條件時(shí)，懲罰項(xiàng)的值很大，即對(duì)不滿足約束條件的點(diǎn)的函數(shù)值進(jìn)行懲罰。 402021/8/22 新目標(biāo)函數(shù)中， 稱(chēng)為懲罰因子或加權(quán)因子，它們是一系列的按一定規(guī)則變化的值。當(dāng)按照一定的法則改變 的數(shù)值時(shí)，就構(gòu)成了一系列的無(wú)約束優(yōu)化問(wèn)題，求解這些優(yōu)化問(wèn)題可得到一系列的無(wú)約束的迭代點(diǎn)，使其一步步迭代，不斷地逼近原約束優(yōu)化問(wèn)題的最優(yōu)解。 )(2)(1kkrr、)(2)(1kkrr、412021/8/22數(shù)學(xué)上可以證明：當(dāng)懲罰函數(shù)滿足( )( )11( )( )21( )( )( )12lim()0lim()0lim(,)()0mkkukupkkvkvkkkkrG gXrH h XX rrf X時(shí)，上述懲罰函

21、數(shù)在 過(guò)程中產(chǎn)生的極小點(diǎn)序列將逐漸逼近于原約束優(yōu)化問(wèn)題的最優(yōu)解。即 k (0)(1)( )(1),kkXXXX( )*limkkXX422021/8/22 懲罰函數(shù)法又稱(chēng)序列無(wú)約束極小化方法，常稱(chēng)SUMT（ sequential unconstrained minimization technique）。根據(jù)懲罰項(xiàng)的構(gòu)成形式，懲罰函數(shù)法可分為：外點(diǎn)懲罰函數(shù)法內(nèi)點(diǎn)懲罰函數(shù)法混合懲罰函數(shù)法。 432021/8/222.外點(diǎn)懲罰函數(shù)法), 2 , 1(0)(), 2 , 1(0)(. .)(minpvXhmuXgtsRXXfvun pvvkmuukkXhrXgrXfrX12)(12)()(, 0ma

22、x,外點(diǎn)懲罰函數(shù)法構(gòu)造懲罰函數(shù)的形式為： 對(duì)于約束優(yōu)化問(wèn)題 442021/8/22分析： 對(duì)于不等式約束 ，當(dāng) 滿足約束條件時(shí)，懲罰項(xiàng)為0；當(dāng)不滿足約束條件時(shí)，懲罰項(xiàng)大于0，這相當(dāng)于給不滿足約束條件的迭代點(diǎn)在函數(shù)值上給予懲罰，以此來(lái)使迭代點(diǎn)逐步向可行域邊界靠近； 對(duì)于等式約束 ，也可以得出類(lèi)似的結(jié)論。()0ugX ( )kX()0vh X 外點(diǎn)法既可處理不等式約束，也可處理等式約束。外點(diǎn)法既可處理不等式約束，也可處理等式約束。452021/8/22 為了進(jìn)一步理解外點(diǎn)法，我們考慮一種只有不等式約束的情況，此時(shí)，懲罰函數(shù)1 1）特征）特征 2( )( )1,max 0,mkkuuX rfXrgX

23、根據(jù)對(duì)懲罰項(xiàng)性質(zhì)的分析，懲罰項(xiàng)可分以下兩種情況：( )2( )10,max,00ukmkuuufXgXX rfXrgXgX (當(dāng)時(shí)) (當(dāng)時(shí))462021/8/22 可以清楚地看出，外點(diǎn)法的懲罰項(xiàng)是定義于可行域之外的。事實(shí)上，外點(diǎn)法的迭代過(guò)程是從可行域外一步步向可行域邊界逼近的。這正是外點(diǎn)法名稱(chēng)的由來(lái)。472021/8/22 懲罰項(xiàng)的大小還與懲罰加權(quán)因子r(k)有關(guān)。當(dāng)懲罰因子按一個(gè)遞增的正數(shù)序列變化時(shí)，依次求解所對(duì)應(yīng)的無(wú)約束極小化問(wèn)題，將得到一個(gè)極小點(diǎn)序列 隨著r(k)逐步增大，這個(gè)極小點(diǎn)序列將逐步逼近原約束優(yōu)化問(wèn)題的最優(yōu)解。 012( )(1)kkrrrrr(0)(1)( )(1),kkX

24、XXX482021/8/222） 選擇 外點(diǎn)法懲罰因子按下式遞增： 式中：C懲罰因子遞增系數(shù)，通常C=510。 外點(diǎn)法懲罰因子 的合理取值很重要， 若 太大，懲罰項(xiàng)的作用就會(huì)很大，使懲罰函數(shù)的等值線變形或偏心，求極值將會(huì)很困難；若 太小，將增加迭代次數(shù)，計(jì)算效率降低。 多數(shù)情況下，取 ，C=10時(shí)效果較好。 ( )kr 1kkCrr)0(r)0(r)0(r1)0(r492021/8/223）迭代步驟步驟1 給定初始點(diǎn) 、收斂精度 、初始懲罰因子r(0)和懲罰因子遞增系數(shù) ，約束容限，并置 ；步驟2 構(gòu)造懲罰函數(shù)步驟3 求解無(wú)約束優(yōu)化問(wèn)題 ，得 ,令 )0(Xc0k pvvkmuukkXhrXg

25、rXfrX12)(12)()(, 0max,),(min)(krX*X*)1(XXk502021/8/22步驟4 判斷收斂精度：若滿足條件 則令 ，結(jié)束計(jì)算；否則，令 ，轉(zhuǎn)步驟2，繼續(xù)迭代。)()()()()()()()()1()()()1(kukkkkukkXgXfXfXfXgXX與與或或與與)()(,)1(*)1(*kkXfXfXX1,)()1(kkcrrkk512021/8/22例. 用外點(diǎn)法求解約束優(yōu)化問(wèn)題：收斂準(zhǔn)則： (1)( )0.10.01kkXX，約束容限 01.min1xXgtsxXf522021/8/223.內(nèi)點(diǎn)懲罰函數(shù)法1）特征 該法是求解不等式約束最優(yōu)化問(wèn)題的一種有效的

26、方法，但不能處理等式約束，其特點(diǎn)是將新的無(wú)約束目標(biāo)函數(shù)懲罰函數(shù)定義在可行域內(nèi)。在可行域內(nèi)，序列迭代點(diǎn)逐步逼近約束邊界上的最優(yōu)點(diǎn)。這樣，求解無(wú)約束問(wèn)題時(shí)的搜索點(diǎn)總是保持在可行域內(nèi)部。 532021/8/22 ), 2 , 1(0. .minmuXgtsRXXfun 對(duì)于約束優(yōu)化問(wèn)題對(duì)于約束優(yōu)化問(wèn)題內(nèi)點(diǎn)法求解時(shí)，懲罰函數(shù)的形式為 muuumuuumuukkmuukkXgXgGXgXgGXgrXfrXXgrXfrX1111ln 1 ln, 1, 或542021/8/22懲罰項(xiàng)的特點(diǎn)：懲罰項(xiàng)的特點(diǎn)：當(dāng)?shù)c(diǎn)在可行域內(nèi)且遠(yuǎn)離邊界時(shí)，兩種懲罰項(xiàng) 和 都是很小的正值，這時(shí)候懲罰作用很?。划?dāng)?shù)c(diǎn)靠近邊界時(shí)，

27、則懲罰項(xiàng)的值急劇增大并趨向無(wú)窮大，于是懲罰函數(shù)值也隨之急劇增大并趨向無(wú)窮大。這樣等于在約束邊界筑起一道“屏障”，使迭代點(diǎn)始終不能超出可行域。 muukXgr11 )(lnXgruk552021/8/22懲罰因子的特點(diǎn)：懲罰因子的特點(diǎn)：內(nèi)點(diǎn)懲罰函數(shù)法的懲罰因子r(k)是一個(gè)遞減的正數(shù)序列， ，c是懲罰因子的縮減系數(shù)，即當(dāng)懲罰因子 時(shí)，才能求得在約束邊界上的最優(yōu)解。 1kkcrr 0210 rrr0)(kr562021/8/222）初始懲罰因子r(0)的選擇 初始懲罰因子的選擇會(huì)影響到迭代計(jì)算能否正常進(jìn)行以及計(jì)算效率的高低，r(0)的值應(yīng)適當(dāng)。 若r(0)太大，則開(kāi)始幾次構(gòu)造的懲罰函數(shù)的無(wú)約束極值

28、點(diǎn)會(huì)離約束邊界很遠(yuǎn)，將增加迭代次數(shù)，使計(jì)算效率降低。 若r(0)太小，懲罰函數(shù)中的障礙項(xiàng)的作用就會(huì)很小，使懲懲罰函數(shù)性態(tài)變壞罰函數(shù)性態(tài)變壞，甚至難以收斂到原約束目標(biāo)函數(shù)的極值點(diǎn)。572021/8/22 目前，還沒(méi)有一定的有效方法，往往要經(jīng)過(guò)多次試算，才能確定一個(gè)適當(dāng)?shù)膔(0)。 多數(shù)情況下，一般取r(0)1 ，然后根據(jù)試算的結(jié)果，加以調(diào)整； 或按經(jīng)驗(yàn)公式取值 muuXgXfr100)0(1使懲罰項(xiàng)和原目標(biāo)使懲罰項(xiàng)和原目標(biāo)函數(shù)在懲罰函數(shù)中函數(shù)在懲罰函數(shù)中的作用相當(dāng)。的作用相當(dāng)。582021/8/223）罰因子縮減系數(shù)C的選擇 在構(gòu)造序列懲罰函數(shù)時(shí)，懲罰因子r(k)是一個(gè)逐次遞減到0的數(shù)列，相鄰兩次迭代的懲罰因子關(guān)系式為：其中，c是懲罰因子的縮減系數(shù)，通常取值為0.1-0.7。 1kkcrr一般來(lái)說(shuō)，一般來(lái)說(shuō)，c值的大小對(duì)收斂速度無(wú)明顯影響，在