[所有分類]第五章約束優化方法(存儲版)

　　

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