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

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

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

4、mber(k)g1u( X ) 和r (k ) H h2( X ) 稱為懲罰項 Penalty term，其值為非負。從懲罰函數的表達式可以看到，懲罰函數值在一般情況下總是大于原目標函數的值，即 f 。為了使懲罰函數 X* f X * ，一方k面要構造合適的復合函數Gg X)Hh X，使其在懲罰函數的極小化過程中，當迭代uvX (k ) k 的增加，不斷地調整懲罰因子r (k) , r (k) 12如下性質lim r (k ) Gg1(X)0(k )lim r (k ) Hh2v(X)0(k )罰函數法。Exterior Point Penalty Method1）. 特點束的序列最優點X *

5、, X *,X*是從可行域的外部逼近原約束優化問題最優解X * 的在可行12k域內部，原目標函數與懲罰函數的等值線重合（ f，而在外部，由于 f懲罰起作解等式約束優化問題。僅有不等式約束的外點懲罰函數（1）問題懲罰函數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 ) 為單調增的正數數列uur(k )無論取何值都有r(k) mu 1max0, gu(X 0 ，此時有 f ，懲罰項不起

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

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

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

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

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

11、解不等式約束優化問題。內點懲罰函數問題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) 為單調減的正數。編程時一般取r(k1) er(k) ,0 e 1例7-3用內點法求下列優化問題的最優解min f (x) axg (x) b x 0解：構造內點懲罰函數(X , r(k ) ) ax r(k )不難求出其極值點的表達式為1b x*( )(x* , r ( k ) ) ab 2r(k ) aar ( k )x (r(k ) aa

12、r ( k )它的變化趨勢圖略見教材。例7-4用內點法求下列優化問題的最優解min f ( X ) x2 x2解：構造懲罰函數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)聯立求解得112r(k)122112r(k)當x* 時不滿足g(112r(k)0舍去121112r(k)則有無約束極值點為112r(k)122當 r(1) 4X* 2, T 當 r(2) 1.2X* 1.422, Tf 4 3.057 f 2.022當 r(3) 0.36X* 1.156, f 1.33

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