【正文】 是求解不等式約束最優(yōu)化問題的一種十分有效的方法 。 如太靠近某一約束邊界 ， 構(gòu)造的懲罰函數(shù)可能由于障礙項的值很大而變得畸形 ， 使求解無約束優(yōu)化問題發(fā)生困難 . 懲罰因子初值 r0的選取 懲罰因子的初值應(yīng)適當 ， 否則會影響迭代計算的正常進行 。 ? 內(nèi)點法的突出優(yōu)點在于每個迭代點都是可行點，當?shù)揭欢ǖ碾A段時，盡管迭代點還沒有達到最優(yōu)點，但也可以被接受為一個較好的近似解。在可行域的內(nèi)部及邊界上有 ；在非可行域則有 ，將原目標函數(shù)加大，使等值面抬高，懲罰因子 r(K) 愈大，增加愈烈，抬高的愈顯著。嚴格地說，它是一個非可行點。 x2 x1 例 54： 用外點法求解 st. 的最優(yōu)解 解 構(gòu)成懲罰函數(shù) 得到約束極值點， 即： 得： 無約束極值點沿直線 從約束區(qū)域外向最優(yōu)點 收斂。 此例可以推廣到一般具有等式約束優(yōu)化的問題 )(m in XFqvXhts v ,2 ,1 0)(. ???：構(gòu)成外懲罰函數(shù)如下 ?????qvvKK XhrXFrX12)()( )]([)() ,( 式中，懲罰因子 r(K)，規(guī)定為正，且是遞增數(shù)列，即 r(0)r(1)r(2)…… 。 外點法特點 : 外懲罰函數(shù)法既可解不等式約束優(yōu)化問題，也可解等式約束優(yōu)化問題，這是其重要優(yōu)點；另外一個優(yōu)點是其初始點 X(0) 可以任選，即在可行域中或非可行域均可。 一、混合懲罰函數(shù)法的形式及其特點 一般約束優(yōu)化問題的數(shù)學模型 由前述可知，懲罰函數(shù)是由原目標函數(shù)和懲罰項組成的。 首先寫出罰函數(shù) 。 二次擴展內(nèi)懲罰函數(shù) ?????miiKK XZrXfrX1)()(),(?)( XZ i)(1Xgi ))(( 0gXg i ? ]3))((3))([(10200?? gXggXgg ii －可行域內(nèi)，內(nèi)點法。 167。 對于設(shè)計點 x, 不滿足的等式約束和不等式約束部分按照外點法處理，而對于 x滿足不等式約束用內(nèi)點法形式處理，其懲罰函數(shù)的形式為 初始點必須是滿足諸不等式約束條件的可行點 x(o) ,初始罰因子 r(0)、降低系數(shù) c的選取均應(yīng)參照內(nèi)點法。就是所求原問題的最優(yōu)，*** 2121l i m)(l i mxxrrrxrr?????????內(nèi)點法和外點法的簡單比較 內(nèi)點法的特點： （ 1）始點必須為嚴格內(nèi)點 （ 2）不適于具有等式約束的數(shù)學模型 （ 3）迭代過程中各個點均為可行設(shè)計方案 （ 4）一般收斂較慢 （ 5）初始罰因子要選擇得當 （ 6）罰因子為遞減，遞減率 c有 0c1 外點法的特點： （ 1）初始點可以任選 （ 2）對等式約束和不等式約束均可適用 （ 3）僅最優(yōu)解為可行設(shè)計方案 （ 4）一般收斂較快 （ 5）初始罰因子要選擇得當 （ 6）罰因子為遞增，遞增率 c有 c1 167。為使罰因子 r(K) 是遞增數(shù)列，令 ， c是懲罰因子的遞增系數(shù)， c1。懲罰因子 r(K) 越大，則懲罰的作用越大。 入口 給定： X( 0), r( 0 ), c , e1? e2 K ? 0 min ? ( X , r( K )) 得最優(yōu)點*KX ， )(*KXFF ? K = 0 ？ 200e??FFF ？ r( K + 1)? cr( K ) F ? F0 *)0(1 KKXX ?? K ? K +1 **KXX ? )(**KFF x? 出口 Y Y N N 外點法流程圖 例 53用外點法求解 st. 的最優(yōu)解。 在實際計算中， r(0)、 c的選取經(jīng)常是通過若干次試算而選取的。外點法可以用來求解含不等式和等式約束的優(yōu)化問題。 內(nèi)點法特點 ? 內(nèi)點法只適用不等式約束優(yōu)化問題。 解 : 用內(nèi)點法求解該問題時，首先構(gòu)造內(nèi)點懲罰函數(shù) : 221 2 1( , ) l n ( 1 )kr x x r x? ? ? ? ?x用解析法求函數(shù)的極小值 ， 運用極值條件： 1112220120krxxxxx????? ? ??????????? ??聯(lián)立求解得： 121 1 2()2( ) 0kkkrxrxr? ??? ??? ??11 1 2()2rxr ??? 時不滿足約束條件 1( ) 1 0g x x? ? ?應(yīng)舍去 。 這種方法是 1968年由美國學者 A． V． Fiacco和 G． P． Mcormick提出的 ， 把不等式約束引入數(shù)學模型中 ， 為求多維有約束非線性規(guī)劃問題開創(chuàng)了一個新局面 。 一、懲罰函數(shù)法基本思想： 通過構(gòu)造懲罰函數(shù)把約束問題轉(zhuǎn)化為一系列無約束最優(yōu)化問題，進而用無約束最優(yōu)化方法去求解，這類方法稱為 序列無約束最小化方法(SUMT,sequential unconstrained minimization technique)。 四 .步長因子的確定 1 ( 0 , 1 , 2 , )k k kk ska? ? ? ?xx 確定的 步長 應(yīng)使新的迭代點為可行點，且目標函數(shù)具有最大的下降量 —— 約束一維搜索。第二次搜索沿適用可行方向作一維搜索以最優(yōu)步長因子求得最優(yōu)點。 起作用約束函數(shù)的負梯度為 ，則條件可用矩陣表示為 這說明，為滿足可行性要求，搜索矢量 與起作用約束 的夾角應(yīng)為銳角，如圖 57所示。若用方向?qū)?shù)的概念來描述， 即目標函數(shù) F(X) 在 X (K) 點沿 S(K) 的方向?qū)?shù)應(yīng)小于零。 X( 0 ) X( 1 ) X( 2 ) X( 3 ) X( 4 ) X* X( 0 ) X( 1 ) g 1 ( X ) g 2 ( X ) X* )1(0X a （ a ） （ b ） 圖 55沿負梯度迭代的步長 于是上述三種情況就歸結(jié)為兩種情況：一種是 X(1) 點在可行域的內(nèi)部（而非邊界上）；另一種是 X(1) 點落在可行域的邊界上。 S (k) 的選擇原 則： ① 必須保證搜索方向是在可行域內(nèi)進行， 即必須與所有適時約束的梯度方向成鈍角。 可行方向法是解決具有不等式約束優(yōu)化問題的直接 搜索法之一。 因 F(XR)= F(XH)，故用映射點替換 X3，構(gòu)成新的復合形： 4個點的目標函數(shù)值為： 最壞點為 X4，最好點為 X3。 ( ) ( ) ( ): ( ) m a x{ ( ) , 1 , 2 , , , }S H S H jX F X F X j K j H? ? ?再轉(zhuǎn)回本步驟的開始處，直到構(gòu)成新的復合形。 三、復合形法的迭代步驟 （ 1）構(gòu)造初始復合形； （ 2）計算各頂點的函數(shù)值 F(X(j))， j=1,2,….,K 。 K個隨機點 根據(jù)隨機數(shù)產(chǎn)生的標準函數(shù)，可以在（ 0， 1）開區(qū)間內(nèi)產(chǎn) 生均勻分布的隨機數(shù) ξi 。 在次好點和好點連線與壞點反向一側(cè)的各點應(yīng)具有較小的目標值 。用復合形法求該問題的約束最優(yōu)解的過程如下 : 1 1 0 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 1 2 3 4 5 6 7 8 9 10 x* x1 x2 圖 5 3 復合形法引例 令： X(R)= X(S)+α(X(S)X(H)) 稱 X(R)為映射點， α為映射系數(shù)，通常取 α=，可根據(jù)實際情況進行縮減。 復合形法是求解約束非線性最優(yōu)化問題的一種重要的直接方法 。 相應(yīng)的目標函數(shù)值為 F(X0)=50。 (1) 若在某個換向轉(zhuǎn)折點處（如圖中的 X (1)點），沿某搜索方向的試探點目標函數(shù)值增大或越出可行域，則棄去該方向，再產(chǎn)生另一隨機方向作試探。 若利用在 （ 0， 1） 之間產(chǎn)生的隨機數(shù) ， i=1， 2， …… ，n， 構(gòu)成單位矢量 S， 方法如下 。 凸集 非凸集 (2） 間接法 目的： 將有約束優(yōu)化問題轉(zhuǎn)化為無約束優(yōu)化問題 方法： 以原目標函數(shù)和加權(quán)的約束函數(shù)共同構(gòu)成一個 新的目標函數(shù) Φ( x, r1 ,r2 )， 成為無約束優(yōu)化問題 。 (為了能得到全局最優(yōu)解，在探索過程中最好能改變初始點，有時甚至要改換幾次。 56 外懲罰函數(shù)法 167。 51