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