多變量約束優(yōu)化方法

1、 PAGE PAGE 3第7章多維約束優(yōu)化方法Chapter 7 Constrained Several Variables TechniqueSummarize工程中的優(yōu)化設(shè)計(jì)問題絕大多數(shù)是約束優(yōu)化問題，即min f ( X )X Rngh(X)u(X)0u 1,2, mv 1,2, p nv約束最優(yōu)點(diǎn)不僅與目標(biāo)函數(shù)的性質(zhì)有關(guān)，也與約束函數(shù)的性質(zhì)有關(guān)。因此，約束優(yōu)化問題比無約束優(yōu)化問題情況更復(fù)雜，求解困難也更大。根據(jù)對(duì)約束條件處理方法的不同，解決約束優(yōu)化問題的方法分成二類:Direct Method尋優(yōu)過程直接在設(shè)計(jì)空間的可行域D X (k) 必須進(jìn)行可行性( g ( X ( k ) 0u

2、1,2,m) 和下降性( f X (k) ) f X (k) ) 檢查。直接算法簡(jiǎn)單，直觀性u(píng)Indirect Method間接法的主要思路是，首先將約束優(yōu)化問題轉(zhuǎn)化為無約束優(yōu)化問題，然后再用無約束 數(shù)法。Penalty Method在將約束優(yōu)化問題轉(zhuǎn)換成無約束優(yōu)化問題時(shí),懲罰函數(shù)法的處理思路與拉格朗日法很相似, 函數(shù)不是一個(gè)而是一個(gè)系列。因此，用無約束優(yōu)化算法求解得的最優(yōu)解也是一個(gè)系列，即X * X * ,X * k X * X * 。因此，懲罰函數(shù)法又稱序列無約束最小化技術(shù)12kkSequential Unconstrained Minimization Technique ， 即SUMT

3、 法。Principle根據(jù)約束優(yōu)化問題min f ( X )X Rns.t.g ( X ) uh ( X ) 0rvru 1,2,mv 1,2, p n構(gòu)造新的函數(shù) 懲罰函數(shù) ( X ,r(k)r(k)f (X)r(k) Ggk(X)k( ) Hh(X )12uu 12vv1其中，GgX )，Hh X g X h X 的復(fù)合函數(shù)；r (k ) r (k ) 是在迭代過程中隨迭代uvuv12次數(shù)k 的增大而不斷調(diào)整的參數(shù)，稱為懲罰因子 Penalty Factor，它們是單調(diào)增 monotoneincreasing (decreasing)或者單調(diào)減的正實(shí)數(shù)數(shù)列positive real nu

4、mber(k)g1u( X ) 和r (k ) H h2( X ) 稱為懲罰項(xiàng) Penalty term，其值為非負(fù)。從懲罰函數(shù)的表達(dá)式可以看到，懲罰函數(shù)值在一般情況下總是大于原目標(biāo)函數(shù)的值，即 f 。為了使懲罰函數(shù) X* f X * ，一方k面要構(gòu)造合適的復(fù)合函數(shù)Gg X)Hh X，使其在懲罰函數(shù)的極小化過程中，當(dāng)?shù)鷘vX (k ) k 的增加，不斷地調(diào)整懲罰因子r (k) , r (k) 12如下性質(zhì)lim r (k ) Gg1(X)0(k )lim r (k ) Hh2v(X)0(k )罰函數(shù)法。Exterior Point Penalty Method1）. 特點(diǎn)束的序列最優(yōu)點(diǎn)X *

5、, X *,X*是從可行域的外部逼近原約束優(yōu)化問題最優(yōu)解X * 的在可行12k域內(nèi)部，原目標(biāo)函數(shù)與懲罰函數(shù)的等值線重合（ f，而在外部，由于 f懲罰起作解等式約束優(yōu)化問題。僅有不等式約束的外點(diǎn)懲罰函數(shù)（1）問題懲罰函數(shù)s.t.min f ( X ), mX R, mg ( X )0u u(X,r(k) f(X)r(k)1Gg(X)f(X)r(k)m max0,gu(X)2說明u1u10 r(1) r(2) max0, gu(X) gu(X)g(X)(X)0, 懲罰因子r(k ) 為單調(diào)增的正數(shù)數(shù)列uur(k )無論取何值都有r(k) mu 1max0, gu(X 0 ，此時(shí)有 f ，懲罰項(xiàng)不起

6、作用；當(dāng)?shù)c(diǎn)不滿足約束條件時(shí)，如g1( X ) 0 ，就有r(k)m min0,guu1(X2 r(k)g2(X)0，表明懲罰項(xiàng)起作用了，迭代點(diǎn)X (k)離邊界越遠(yuǎn)，1g 2 ( X ) 項(xiàng)就越大，其懲罰作用也就越大，就迫使迭代點(diǎn) X (k ) 向可行域靠攏，最1終 X * ；懲罰因子r(k) 是一個(gè)遞增的正值數(shù)列，即0 r) r(2) ，在計(jì)算程中一般按迭代式r(k) Cr(k) 取，其中C 1 （一般取51。(P109)選擇初始點(diǎn)X (0) (可任選,但(X,r(k) ) 的無約束極值點(diǎn)均在可行域外)，收斂精度 黃金無約約束3 個(gè)，確定r() 0 及C如(r(11, C 10)；置計(jì)數(shù)器

7、 k 1;選用一種無約束算法，求Xr(k) ) X k(k 1 , X * ) ；1檢驗(yàn)收斂精度 X* X* ， Yes X * X stop ，No 6) ；kkkr(k) Cr(k) k k 1goto3 )。(5) 例題例 7-1 用外點(diǎn)法求下列優(yōu)化問題的最優(yōu)解min f (x) axg(x) b x 0解: 外點(diǎn)懲罰函數(shù) (x, rk) axrk) max0,bx2所以在可行域外, 懲罰函數(shù) (x, r( k ) ) ax r( k ) (b x)2 , 令 (x, r(k ) ) 0 , 其無約束的極值點(diǎn)為x*(r(k) baa2r(k )(x* , r(k ) ) ab a24r(

8、k )當(dāng)r(1) r(2) a2bax* b* 0abx* 0* ab2br(3) bx* * 24r( k ) x* b* ab（圖略見教材）例 7-2 用外點(diǎn)法求下列優(yōu)化問題的最優(yōu)解min f ( X ) x2 x2解：構(gòu)造懲罰函數(shù)12g( X ) 1 x 01( X , r ( k ) ) x2 x2 r ( k ) max0,(1 x )2 121在可行域外有懲罰函數(shù) ( X , r( k ) ) x2 x2 r ( k ) (1 x )2121 2x由1由1 2r(k ) (1 x ) 01 2x 022r(k)聯(lián)立求解得x* ,x 011r(k)2當(dāng) r(1) 0.3X* 0.23

9、1, T 0.23f 0.053當(dāng) r(2) 1.5X* 0.6, 0.6f 0.36當(dāng) r(3) 7.5X* 0.882, 0.882f 0.78當(dāng) r(k) X* 1, f 17-1 7-2 懲罰函數(shù)為2( )(X,r(k) f (X)r(k)m min0,g (X)r k2( )11u2vu1r (k ) r (k ) r (k ) r (k ) 可以取同樣的值。1212應(yīng)用中的問題X (0) 的選擇可以任意在可行域內(nèi)外選擇初始點(diǎn) , 但( X , r(k ) ) 的無約束極值點(diǎn)均在可行域外；懲罰因子初始值r(1) 和衰減系數(shù)C 的選擇r(1) 和C C 值取的越小，迭代次數(shù)就越尋優(yōu)會(huì)碰

10、到困難，甚至導(dǎo)致失敗。常取r(1) 1 C 5 10 ；約束裕量圖 7-1約束裕量法從外點(diǎn)法的特點(diǎn)可知，由于k 不可能趨于 X * 只能是k一個(gè)無限接近約束邊界的非可行點(diǎn)，也就是說該點(diǎn)不能嚴(yán)格地滿足所有的約束條4 PAGE PAGE 7 域內(nèi)移動(dòng)一段距離 ，即約束條件成為 gu(X ) guX 0 X * 雖k則造成新的可行域與原來相差太大而失去了意義。一般取 103 104 。內(nèi)點(diǎn)懲罰函數(shù)法1） 特點(diǎn)與外點(diǎn)懲罰函數(shù)相反, 內(nèi)點(diǎn)懲罰函數(shù)是定義在可行域內(nèi)的， 并在可行域內(nèi)求懲罰函數(shù)的序列最優(yōu)點(diǎn)X *, X *,X * 即求解無約束問題時(shí)的探索（迭代點(diǎn)總12k是保持在可行域內(nèi)。但內(nèi)懲罰函數(shù)法只能求

11、解不等式約束優(yōu)化問題。內(nèi)點(diǎn)懲罰函數(shù)問題min f ( X ), mX R, ms.t.g ( X )0u u(X,r(k) f (X)r(k)m1u 11g ( X 0 f ( X ) r(k muln g ( X ur(1) r(2) 懲罰因子r(k) 為單調(diào)減的正數(shù)。編程時(shí)一般取r(k1) er(k) ,0 e 1例7-3用內(nèi)點(diǎn)法求下列優(yōu)化問題的最優(yōu)解min f (x) axg (x) b x 0解：構(gòu)造內(nèi)點(diǎn)懲罰函數(shù)(X , r(k ) ) ax r(k )不難求出其極值點(diǎn)的表達(dá)式為1b x*( )(x* , r ( k ) ) ab 2r(k ) aar ( k )x (r(k ) aa

12、r ( k )它的變化趨勢(shì)圖略見教材。例7-4用內(nèi)點(diǎn)法求下列優(yōu)化問題的最優(yōu)解min f ( X ) x2 x2解：構(gòu)造懲罰函數(shù)12g( X ) 1 x 01(X , r(k ) ) x2 x2 r( k ) ln(1 x )1 2x 由x1由121r(k) 1x1 2x 0 x22112r(k)聯(lián)立求解得112r(k)122112r(k)當(dāng)x* 時(shí)不滿足g(112r(k)0舍去121112r(k)則有無約束極值點(diǎn)為112r(k)122當(dāng) r(1) 4X* 2, T 當(dāng) r(2) 1.2X* 1.422, Tf 4 3.057 f 2.022當(dāng) r(3) 0.36X* 1.156, f 1.33

13、6當(dāng) r(k) 0X* 1, f 1應(yīng)用中的問題(1) 初始點(diǎn)X(0) 的選擇與外點(diǎn)法不同,X(0) 必須是一個(gè)可行點(diǎn), 它可以人為1指定,也可以用隨機(jī)等方法確定, 最簡(jiǎn)單的是選擇原設(shè)計(jì)訪案。（2）r(1)e的選擇 r(1) 一定的經(jīng)驗(yàn)，對(duì)于較復(fù)雜的優(yōu)化問題需通過多次試算決定。許多書上推薦其取 1 50，r(1) 1e的取值范圍常在0.1 0.7之間。內(nèi)點(diǎn)法和外點(diǎn)法的比較懲罰函數(shù)的定義范圍及其極值點(diǎn)的趨勢(shì)：懲罰函數(shù)的表達(dá)式：解決問題的范圍：各自的優(yōu)點(diǎn)：內(nèi)，只要設(shè)計(jì)要求允許，都可以選用。Review 7Penalty MethodExterior pointEquality & inequalityX * X * ou