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

　　

【正文】 yyy ????S圖 52隨機方向法程序框圖 三 舉例 例：用約束隨機方向法求解 解：人工選取一初始點 X0=[5， 5]T，初始點在可行域內。 例如： 設有一約束優化問題的數學模型是 該目標函數的等值線和可行域的幾何圖形如圖 53所示。 同樣，產生其它的隨機點 X (2)、 X (3)、 ……X (K)。 若經過多次的映射系數減半，仍不能使映射點優于壞點，則說明該映射方向不利，此時，應改變映射方向，取對次壞點的映射。 （ 3） 因為迭代過程始終在可行域內進行 ， 運行結果可靠 。 如果發生情況③，則通過一定的計算取得新的步長，使其迭代點返回至可行域的邊界上，見圖 55。若 X (K)點的所有約束函數值都小于零， 則它是可行域內部的可行點；若 X (K) 點的某個約束函數值或 某幾個約束函數值等于零或接近于零，則該點是在邊界上的 可行點（這一個或幾個約束是 X (K) 點的起作用約束）。 0x1x2x0xkxk + 1g2( x ) =0g1( x ) =0g3( x ) =00()f?? x沿線性約束面的搜索 圖 510貼邊搜索法 若可行域是凸集，約束面是非線性時，從 xk點沿切線（面）方向 搜索，會進入非可行域 建立約束面的容差帶 +δ， 從 x(k) 出發，沿 s(k)方向搜索到 s(k) 方向與 g(x) +δ=0 的交點 x ′后，再沿適時約束的負梯度方向返回約束面的 x(k+1)點。 根據約束形式和定義及懲罰因子的遞推方法等不同 ， 罰函數法可分為 內懲罰函數法 、 外懲罰函數法和混合懲罰函數法三種 。 2） 選取初始罰因子 r(0)與罰因子降低系數 c， 并置 K← 0； 3） 求 minφ(x(K),r(K))解出最優點 xK*； 4） 當 K=0轉步驟 5） ， 否則轉步驟 6） ； 5） K←K+ 1， r(K+1)←r (K)， xK+10←x K* ， 并轉步驟 3） ； 6） 按終止準則判別 ， 若滿足轉步驟 7） ， 否則轉步驟 5） ； 7） 輸出最優解 （ X*， F*） ， 停止計算 。通常 c=5~10。在可行域上，懲罰項的值為零，懲罰函數的值與原目標函數的值相同；而在非可行域上懲罰項的值恒為正，懲罰函數大于原目標函數，即在可行域外懲罰項起到了懲罰作用。問題這就是對于固定的所以)(m i n121)(*xrrrrxxkRxkn??????解。因此該方法也是應用較多的有約束優化方法。 用內點形式的混合法的罰函數為 用外點形式的混合法的罰函數為 將已知條件代入上式中，選取初始點 X(0)，初始罰因子r(0)，遞減系數 c（對于內點形式的混合法）或遞增系數 c（對于外點形式的混合法）。其確定是系列無約束最優點是非可行點，對于工程設計一般是不可取的。 *x用外懲罰函數法解等式約束優化問題 設有二維等式約束優化問題 54)(m i n 2221 ??? xxXF010)(. 211 ???? xxXhts ： 函數圖形見圖。 對幾個問題的討論 初始點 的選取 由上述外點法的特點不難看出，外點法的初始點 x(0)可 以任意選取，即在可行域或非可行域上選取皆可。 一般而言 ， 太大 ， 將增加迭代次數；太小 ， 會使懲罰函數的性態變壞 ， 甚至難以收斂到極值點 。前提： 1 不能破壞約束問題的約束條件 ， 2 使它歸結到原約束問題的同一最優解上去 。以后各次搜索方向均為適用可行方向，以最大步長從一個邊界反彈到另一個邊界，直至滿足 KT 條件。 。 圖 54適用 可行區域 一、基本搜索過程 ? 首先在可行域內取一初始點 X(0)。在新的復合形中重復 上述過程 …… 復合形 方法評價： （ 1） 復合形法 ， 僅通過選取各頂點并比較各點處函數值的大小 ， 就可尋找下一步的探索方向 。 （ 4）計算映射點 X(R): 檢查 X(R)是否在可行域內。對于維數較高的問題，采用隨機方法，先產生 K個隨機點，然后再把非可行點逐一調入可行域內。 167。此時可將初始步長 h0縮半后繼續試探 ,直到 f(k+1)≤ f(k)，且沿 m個隨機方向都試探失敗時，則最后一個成功點（如圖中的 X (3)點）就是到達預定精度要求的約束最優點，迭代即可結束。 新目標函數： 其中： 懲罰項： ??? )(),( )(2)(1 xfrrx kk )]([)]([1)(21)(1 xhHrxgGrpv vkmu uk ?????加權因子 (懲罰因子 )： r1(k) , r2(k) 無約束優化問題： Φ函數的極小點序列 x (k)* ( r1 (k) , r2 (k) ) k= 0,1,2… 其收斂必須滿足： 167。 51約束最優解及其一階必要條件 機械優化設計中的問題，大多數屬于約束優化設計問題，其數學模型為 實際工程中大部分問題的變量取值都有一定的限制，也就是屬于有約束條件的尋優問題。 56 外懲罰函數法 167。 凸集 非凸集 (2） 間接法 目的： 將有約束優化問題轉化為無約束優化問題 方法： 以原目標函數和加權的約束函數共同構成一個 新的目標函數 Φ( x, r1 ,r2 )， 成為無約束優化問題 。 (1) 若在某個換向轉折點處（如圖中的 X (1)點），沿某搜索方向的試探點目標函數值增大或越出可行域，則棄去該方向，再產生另一隨機方向作試探。 復合形法是求解約束非線性最優化問題的一種重要的直接方法 。 在次好點和好點連線與壞點反向一側的各點應具有較小的目標值 。 三、復合形法的迭代步驟 （ 1）構造初始復合形； （ 2）計算各頂點的函數值 F(X(j))， j=1,2,….,K 。 因 F(XR)= F(XH)，故用映射點替換 X3，構成新的復合形： 4個點的目標函數值為： 最壞點為 X4，最好點為 X3。 S (k) 的選擇原 則： ① 必須保證搜索方向是在可行域內進行， 即必須與所有適時約束的梯度方向成鈍角。若用方向導數的概念來描述， 即目標函數 F(X) 在 X (K) 點沿 S(K) 的方向導數應小于零。第二次搜索沿適用可行方向作一維搜索以最優步長因子求得最優點。 一、懲罰函數法基本思想： 通過構造懲罰函數把約束問題轉化為一系列無約束最優化問題，進而用無約束最優化方法去求解，這類方法稱為 序列無約束最小化方法(SUMT,sequential unconstrained minimization technique)。 解 : 用內點法求解該問題時，首先構造內點懲罰函數 : 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? ? ?應舍去 。外點法可以用來求解含不等式和等式約束的優化問題。 入口 給定： 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(K) 是遞增數列，令 ， c是懲罰因子的遞增系數， c1。 對于設計點 x, 不滿足的等式約束和不等式約束部分按照外點法處理，而對于 x滿足不等式約束用內點法形式處理，其懲罰函數的形式為 初始點必須是滿足諸不等式約束條件的可行點 x(o) ,初始罰因子 r(0)、降低系數 c的選取均應參照內點法。 二次擴展內懲罰函數 ?????miiKK XZrXfrX1)()(),(?)( XZ i)(1Xgi ))(( 0gXg i ? ]3))((3))([(10200?? gXggXgg ii －可行域內，內點法。 一、混合懲罰函數法的形式及其特點 一般約束優化問題的數學模型 由前述可知，懲罰函數是由原目標函數和懲罰項組成的。 此例可以推廣到一般具有等式約束優化的問題 )(m in XFqvXhts v ,2 ,1 0)(. ???：構成外懲罰函數如下 ?????qvvKK XhrXFrX12)()( )]([)() ,( 式中，懲罰因子 r