【正文】 ))(( 0gXg i ?G0－轉(zhuǎn)換點(diǎn)，一般取 約束裕量，將約束面放寬 采用一維搜索 H1－懲罰函數(shù) 在 Xk點(diǎn)的二階導(dǎo)數(shù)逆矩陣。因此該方法也是應(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)形式的混合法）。 外點(diǎn)形式的混合法 不等式約束部分按外點(diǎn)法處理的混合法，其懲罰函數(shù)的形式為 初始點(diǎn)可以在空間內(nèi)任選，初始罰因子 r(0)、遞增系數(shù) c可以參照外點(diǎn)法選取。由于該問(wèn)題的約束條件包含不等式約束與等式約束兩部分，因此，懲罰項(xiàng)也由對(duì)應(yīng)的兩部分組成。問(wèn)題這就是對(duì)于固定的所以)(m i n121)(*xrrrrxxkRxkn??????解。其確定是系列無(wú)約束最優(yōu)點(diǎn)是非可行點(diǎn)，對(duì)于工程設(shè)計(jì)一般是不可取的。隨著 r(K) 的增大，致使 。懲罰項(xiàng) ，在可行域上懲罰項(xiàng)為零；在非可行域上懲罰項(xiàng)恒為正。在可行域上，懲罰項(xiàng)的值為零，懲罰函數(shù)的值與原目標(biāo)函數(shù)的值相同；而在非可行域上懲罰項(xiàng)的值恒為正，懲罰函數(shù)大于原目標(biāo)函數(shù)，即在可行域外懲罰項(xiàng)起到了懲罰作用。 *x用外懲罰函數(shù)法解等式約束優(yōu)化問(wèn)題 設(shè)有二維等式約束優(yōu)化問(wèn)題 54)(m i n 2221 ??? xxXF010)(. 211 ???? xxXhts ： 函數(shù)圖形見(jiàn)圖。 算法步驟及流程圖 1)在 n維空間任取初始點(diǎn) x(0) ； 2)選取初始懲罰因子 r(0)，遞增系數(shù) c，并置 K?0； 3)求 ，取得最優(yōu)點(diǎn) ； 4)當(dāng) K=0轉(zhuǎn)步驟（ 5），否則轉(zhuǎn)步驟（ 6）； 5)K?K+1， ， ；并轉(zhuǎn)步驟（ 3）； 6)按終止準(zhǔn)則判別，若滿足則轉(zhuǎn)步驟（ 7），否則轉(zhuǎn)步驟（ 5）； 7)輸出最優(yōu)解 ，停止計(jì)算。這對(duì)某些工程問(wèn)題是不允許的。通常 c=5~10。 對(duì)幾個(gè)問(wèn)題的討論 初始點(diǎn) 的選取 由上述外點(diǎn)法的特點(diǎn)不難看出，外點(diǎn)法的初始點(diǎn) x(0)可 以任意選取，即在可行域或非可行域上選取皆可。 56 外懲罰函數(shù)法 外點(diǎn)法是從可行域的外部構(gòu)造一個(gè)點(diǎn)序列去逼近原約束問(wèn)題的最優(yōu)解。在機(jī)械優(yōu)化設(shè)計(jì)問(wèn)題中，這種近似解雖非最優(yōu)點(diǎn)，但比初始方案已經(jīng)有很大的改進(jìn)，如果已能較好地符合工程設(shè)計(jì)的要求，則可以被接受作為一種最優(yōu)設(shè)計(jì)。 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ì)算 。 一般而言 ， 太大 ， 將增加迭代次數(shù)；太小 ， 會(huì)使懲罰函數(shù)的性態(tài)變壞 ， 甚至難以收斂到極值點(diǎn) 。 例 51 用內(nèi)點(diǎn)法求 2212m i n ( )f x x??x1s . t . ( ) 1 0gx? ? ?x的約束最優(yōu)解。 m in ( )s . t . ( ) 0 ( 1 , 2 , , )jfg j m?? ???xx對(duì)于只具有不等式約束的優(yōu)化問(wèn)題： 轉(zhuǎn)化后的懲罰函數(shù)形式為： ()11( , ) ( )()mki ir f r g???? ?xx x()1( , ) ( ) l n [ ( ) ]mkiir f r g??? ? ??x x x或： 說(shuō)明： ”公式中“ 0)(??xg j? rk是懲罰因子 ， 它是一個(gè)由大到小且趨近于 0的正數(shù)列 ， 即 : 0 1 2 1 0kkr r r r r ?? ? ? ? ? ? 由于內(nèi)點(diǎn)法的迭代過(guò)程在可行域內(nèi)進(jìn)行 ， “ 懲罰項(xiàng) ” 的作用是阻止迭代點(diǎn)越出可行域 。 根據(jù)約束形式和定義及懲罰因子的遞推方法等不同 ， 罰函數(shù)法可分為 內(nèi)懲罰函數(shù)法 、 外懲罰函數(shù)法和混合懲罰函數(shù)法三種 。前提： 1 不能破壞約束問(wèn)題的約束條件 ， 2 使它歸結(jié)到原約束問(wèn)題的同一最優(yōu)解上去 。 例 :已知約束優(yōu)化問(wèn)題 (課堂練習(xí) ) 試以 X10=[2 1]T， X20=[4 1]T 和 X30=[3 3]T為復(fù)合形的初點(diǎn)，用復(fù)合形法進(jìn)行兩次迭代計(jì)算。 0x1x2xkskxk + 1g2( x ) = 0g1( x ) = 0a * skaMskx 改變步長(zhǎng)，使新點(diǎn) x返回到約束面上來(lái)。 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)。以后各次搜索方向均為適用可行方向，以最大步長(zhǎng)從一個(gè)邊界反彈到另一個(gè)邊界，直至滿足 KT 條件。 最優(yōu)步長(zhǎng)法： 第一次搜索為負(fù)梯度方向，終止于邊界。圖 58（ b）是 J=2 又與 成銳角構(gòu)成的扇形空間， x2 是既與 又與 成銳角而構(gòu)成的扇形空間。若 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)的起作用約束）。 。 二、適用可行方向的數(shù)學(xué)條件 適用性條件 前面已經(jīng)指出，搜索方向 S(K) 滿足適用性條件是 指目標(biāo) 函數(shù) F(X) 沿該方向是下降的 。 ? 如果 X(1) 點(diǎn)是在可行域邊界上或是由邊界以外調(diào)回到邊界上，則下一次不再采用負(fù)梯度為搜索方向，而采用一個(gè)適用可行方向 S (K)。 如果發(fā)生情況③，則通過(guò)一定的計(jì)算取得新的步長(zhǎng)，使其迭代點(diǎn)返回至可行域的邊界上，見(jiàn)圖 55。 圖 54適用 可行區(qū)域 一、基本搜索過(guò)程 ? 首先在可行域內(nèi)取一初始點(diǎn) X(0)。 步長(zhǎng) α(k) 的選擇原則： 使新點(diǎn) x(k+1) 在可行域內(nèi)。滿足上述兩個(gè)條件的方向稱(chēng)為 適用可行方向 。 （ 3） 因?yàn)榈^(guò)程始終在可行域內(nèi)進(jìn)行 ， 運(yùn)行結(jié)果可靠 。在新的復(fù)合形中重復(fù) 上述過(guò)程 …… 復(fù)合形 方法評(píng)價(jià)： （ 1） 復(fù)合形法 ， 僅通過(guò)選取各頂點(diǎn)并比較各點(diǎn)處函數(shù)值的大小 ， 就可尋找下一步的探索方向 。 求 XH的映射點(diǎn) XR，取映射系數(shù)為 ： 經(jīng)檢驗(yàn)，映射點(diǎn) XR在可行域內(nèi)。 4個(gè)復(fù)合形頂點(diǎn)。 若經(jīng)過(guò)多次的映射系數(shù)減半，仍不能使映射點(diǎn)優(yōu)于壞點(diǎn)，則說(shuō)明該映射方向不利，此時(shí)，應(yīng)改變映射方向，取對(duì)次壞點(diǎn)的映射。 （ 4）計(jì)算映射點(diǎn) X(R): 檢查 X(R)是否在可行域內(nèi)。 按照這個(gè)方法 ， 同樣使 X (q+2)、 X (q+3)、 …… X (K)都變?yōu)榭尚悬c(diǎn) ， 這 K個(gè)點(diǎn)就構(gòu)成了初始復(fù)合形 。但是，只要它們中間有一個(gè)點(diǎn)在可行域內(nèi)，就可以用一定的方法將非可行點(diǎn)逐一調(diào)入可行域。 同樣，產(chǎn)生其它的隨機(jī)點(diǎn) X (2)、 X (3)、 ……X (K)。對(duì)于維數(shù)較高的問(wèn)題，采用隨機(jī)方法，先產(chǎn)生 K個(gè)隨機(jī)點(diǎn)，然后再把非可行點(diǎn)逐一調(diào)入可行域內(nèi)。 最小值 ， 記為最好點(diǎn) X(L)。若滿足可行域，則用 X(R)代替X(H)構(gòu)成新的復(fù)合形。 例如： 設(shè)有一約束優(yōu)化問(wèn)題的數(shù)學(xué)模型是 該目標(biāo)函數(shù)的等值線和可行域的幾何圖形如圖 53所示。 167。 缺點(diǎn)： 1 對(duì)于嚴(yán)重非線性函數(shù) ， 只能得近似解； 2 當(dāng) m不夠大時(shí) ， 解的近似程度大； 3 對(duì)于非凸函數(shù) ， 有可能收斂于局部解 。 將 X1的表達(dá)式代入目標(biāo)函數(shù)中 ， 進(jìn)行一維搜索 ，令目標(biāo)函數(shù)對(duì)步長(zhǎng) a的一階導(dǎo)數(shù)為 0， 即可求出沿 e1方向的最優(yōu)步長(zhǎng) 。 入口 X← X(0)， a← a0 F0← F(X) K?1 j← 0 在 （ ?1， 1） 區(qū)間產(chǎn)生隨機(jī)數(shù) yi X← X (0)+aS Y gu(X)≤ 0 F← F(X) FF0 ? 更換初始點(diǎn) X (0)← X， F0← F j← 1 (x) X← X (0)+aS 給定： X(0)， a0， m， e j=0 ? Km ? a≤ e ? K← K+1 X*← X F*← F 出口 a← Y Y Y Y N N N N N ? ?T2112 1 nni iyyyy ????S圖 52隨機(jī)方向法程序框圖 三 舉例 例：用約束隨機(jī)方向法求解 解：人工選取一初始點(diǎn) X0=[5， 5]T，初始點(diǎn)在可行域內(nèi)。此時(shí)可將初始步長(zhǎng) h0縮半后繼續(xù)試探 ,直到 f(k+1)≤ f(k)，且沿 m個(gè)隨機(jī)方向都試探失敗時(shí)，則最后一個(gè)成功點(diǎn)（如圖中的 X (3)點(diǎn)）就是到達(dá)預(yù)定精