【正文】 然后轉(zhuǎn)到第一步，分布網(wǎng)格，重新計(jì)算。 優(yōu)化方法 類型 特點(diǎn) 適用范圍 （正交）網(wǎng)格法 直接方法 算法簡(jiǎn)單，對(duì)函數(shù)性態(tài)要求不高，可求得全局最優(yōu)解，特別適用于具有離散變量的問題，對(duì)于連續(xù)變量應(yīng)給出個(gè)變量的區(qū)間，計(jì)算量大 適用于維數(shù)不大于 8，約束個(gè)數(shù)不太多（一般小于 10~15）的問題 約束隨機(jī)方向法 直接方法 方法簡(jiǎn)單，使用方便，對(duì)目標(biāo)函數(shù)性態(tài)無特殊要求，一般收斂較快，但計(jì)算精度較低，對(duì)嚴(yán)重非線性問題一般只能提供較近似的最優(yōu)解 適用于中小型優(yōu)化問題，不僅可求解約束優(yōu)化問題，也能求解無約束優(yōu)化問題 復(fù)合形法 直接方法 方法簡(jiǎn)單，對(duì)目標(biāo)函數(shù)和約函數(shù)性態(tài)無特殊要求，應(yīng)用較廣，有一定收斂精度，但收斂速度一般較慢，若用隨機(jī) 適用于維數(shù)不高的約束優(yōu)化問題（一般 n≤15 ），不適用于有等式約束的問題 可行方向法 直接方法 要求可行域是連續(xù)閉集，目標(biāo)函數(shù)和約束函數(shù)一階可微，該方法收斂較快，是一種求解不等式約束優(yōu)化問題比較有效的方法 適用于高維（ n≥15 ）不等式約束優(yōu)化問題 懲 罰 函 數(shù) 法 內(nèi)點(diǎn)法 間接方法 初始點(diǎn)必須為嚴(yán)格內(nèi)點(diǎn)，初始罰因子對(duì)收斂速度和迭代成敗影響較大，應(yīng)用很廣泛 適用于中小型不等式約束優(yōu)化問題，不適于具有等式約束的數(shù)學(xué)模型 外點(diǎn)法 初始點(diǎn)可任選，其它同內(nèi)點(diǎn)法 適用于中小型一般非線性約束優(yōu)化問題，但多用于等式約束優(yōu)化問題 混合法 混合法是用內(nèi)點(diǎn)法處理不等式約束，用外點(diǎn)法處理等式約束。具有內(nèi)點(diǎn)法的特點(diǎn)，迭代過程在可行域之內(nèi)進(jìn)行，參數(shù)的選擇同內(nèi)點(diǎn)法 適用于中小型一般非線性約束優(yōu)化問題 序列二次規(guī)劃法 間接方法 將一般非線性約束優(yōu)化問題轉(zhuǎn)化為一系列二次規(guī)劃子問題求解，迭代中不僅用到函數(shù)值和函數(shù)一階偏導(dǎo)數(shù)信息，而且用到二階偏導(dǎo)數(shù)信息，因而收斂速度快、效率高，公認(rèn)為是目前最優(yōu)秀的約束優(yōu)化方法之一 對(duì)中小型、大型約束優(yōu)化問題均適用，對(duì) n100的大型約束優(yōu)化問題仍具有較好的數(shù)字穩(wěn)定性 常用約束優(yōu)化方法總結(jié) 有約束優(yōu)化上機(jī) 復(fù)合形法優(yōu)化設(shè)計(jì)程序 題目：編程求解函數(shù) 221 2 1 2 1 2112231425 1 2m in ( ) 10 4 60. . ( ) 0( ) 0( ) 6 0( ) 8 0( ) 11 0f x x x x x xs t g xgxg x xg x xg x x x? ? ? ? ? ?? ? ?? ? ?? ? ?? ? ?? ? ? ?xxx無約束優(yōu)化方法 1 ( 0 , 1 , 2 , )k k kk sk?? ? ? ?xx1 ( ) ( 0 , 1 , 2 , )k k kka f k? ? ? ? ?x x x1 2 1[ ( ) ] ( ) ( 0 , 1 , 2 , )k k k kf f k??? ? ? ? ?x x x x1 2 1[ ( ) ] ( ) ( 0 , 1 , 2 , )k k k kk f f k???? ? ? ? ?x x x x一般迭代式： 梯度法： 牛頓法： 阻尼牛頓法： 優(yōu)化方法的演化 —— 間接法 1 ()k k k kk f?? ? ? ?x x A x變尺度法： α0d0 x 0 x1 x* 1 α1d1 1()f?? x d1 ()k k kkf ? ?? ? ? ? 1d x d22()()kk kff????? 1xx1 ( 0 , 1 , 2 , )k k kk k?? ? ? ?x x d共軛梯度法： 1 ( ) ( 0 , 1 , 2 , )k k kka f k? ? ? ? ?x x x梯度法： 鮑威爾 (Powell)法 j j k k k d d dj g g k+1 x x k+1 共軛法 直接法 鮑威爾法原理， 如何構(gòu)成共軛方向？ ！ 坐標(biāo)輪換法 直接法 步長(zhǎng)加速法（ HookReeves算法） 單純形方法 —— 直接法 基本思想 在 n維空間中選取 n+1個(gè)點(diǎn)作為初始單純形的頂點(diǎn)。比較各頂點(diǎn)目標(biāo)函數(shù)值的大小，去掉目標(biāo)函數(shù)值最大的頂點(diǎn) (稱最壞點(diǎn) )，通過一些操作構(gòu)造新點(diǎn)代替最壞點(diǎn)構(gòu)成新的單純形。從一個(gè)單純形迭代到一個(gè)更優(yōu)的單純形，反復(fù)迭代計(jì)算，使單純形不斷向最優(yōu)點(diǎn)移動(dòng)和收縮，直至滿足迭代精度要求為止。在單純形替換算法中，從一個(gè)單純形到另一個(gè)單純形的迭代主要通過反射、擴(kuò)張、收縮和縮邊這 4個(gè)操作來實(shí)現(xiàn)。 反射、擴(kuò)張、收縮和縮邊 4個(gè)操作。 特點(diǎn)：?jiǎn)渭冃翁鎿Q法是一種不使用導(dǎo)數(shù)的求解無約束極小化問題的直接搜索方法 ， 與間接方法不同的是 ， 單純形替換法不是利用搜索方向從一個(gè)點(diǎn)迭代到另一個(gè)更優(yōu)的點(diǎn) ， 而是從一個(gè)單純形迭代到另一個(gè)更優(yōu)的單純形 ， 思路清楚 ， 但收斂慢 。 有約束優(yōu)化方法 基本思想：在可行域中選取 K 個(gè)設(shè)計(jì)點(diǎn) （n+1≤K≤2n） 作為初始復(fù)合形的頂點(diǎn) 。 比較各頂點(diǎn)目標(biāo)函數(shù)值的大小 ， 去掉目標(biāo)函數(shù)值最大的頂點(diǎn) (稱最壞點(diǎn) )， 以壞點(diǎn)以外其余各點(diǎn)的中心為映射中心 ， 用壞點(diǎn)的映射點(diǎn)替換該點(diǎn) ， 構(gòu)成新的復(fù)合形頂點(diǎn) 。 反復(fù)迭代計(jì)算 ， 使復(fù)合形不斷向最優(yōu)點(diǎn)移動(dòng)和收縮 ， 直至收縮到復(fù)合形的頂點(diǎn)與形心非常接近 ， 且滿足迭代精度要求為止 。 復(fù)合形法 初始復(fù)合形的構(gòu)成 —— 將非可行點(diǎn)調(diào)入可行域 方法特點(diǎn) （ 1） 復(fù)合形法是求解約束非線性最優(yōu)化問題的一種直接方法 ， 僅通過選取各頂點(diǎn)并比較各點(diǎn)處函數(shù)值的大小 ， 就可尋找下一步的探索方向 。 但復(fù)合形各頂點(diǎn)的選擇和替換 ， 不僅要滿足目標(biāo)函數(shù)值下降的要求 ， 還應(yīng)當(dāng)滿足所有的約束條件 。 （ 2） 復(fù)合形法適用于僅含不等式約束的問題 。 O x1 x2 O x1 x2 a) 極值點(diǎn)處于多角形的某一頂點(diǎn)上 b) 極值點(diǎn)處于等值線的中心 c) 極值點(diǎn)處于約束曲線與等值線的切點(diǎn)上 d) 極值點(diǎn)處于兩個(gè)約束曲線的交點(diǎn)上 x﹡ g1 (x)＝ 0 g2 (x)＝ 0 g3 (x)＝ 0 x﹡ g2(x)＝ 0 g3(x)＝ 0 g4(x)＝ 0 g1(x)＝ 0 g2(x)＝ 0 O x1 x2 O x1 x2 x﹡ g2(x)＝ 0 x﹡ g1(x)＝ 0 g1(x)＝ 0 圖 110 * 可行下降方向 1 可行方向 定義 設(shè)點(diǎn) ，若對(duì)于方向 d ，存在任意小正數(shù) δ 0 ，使得 則稱 d 為 X (k) 點(diǎn)的一個(gè)可行方向。 i. （ 1） X (k) 為可行域中的一個(gè)內(nèi)點(diǎn)， X (k) 的任何方向均為可行方向。 ii. （ 2） X (k) 為可行域中的一個(gè)邊界點(diǎn)，設(shè) X (k) 在約束面 gi (X ) = 0 上。 ? ? DX k ?? ? ? ? ? ?11 ,k k kX X d X D???? ? ? ?? ?? ? 0Tkig X d??????i. （ 3） X (k) 為可行域中的一個(gè)外點(diǎn) ， X (k) 的不存在可行方向 。 2 可行下降方向 定義 設(shè) d是 的一個(gè)可行方向，即 若對(duì)于上式中的 X (k) 、 X (k+1) 存在 則稱 d為 X (k) 點(diǎn)的一個(gè)可行下降方向。 i. （ 1） X (k) 為可行域中的一個(gè)內(nèi)點(diǎn) ? ? DX k ?? ? ? ? ? ?11 ,k k kX X d X D???? ? ? ?? ?? ? ? ?? ? 01 ?? ?kk XfXf[ ( ) ] 0k T kf??xd（ 2） X (k) 點(diǎn)是可行域中若干約束面的交點(diǎn) 設(shè) X (k) 點(diǎn)在約束面 gj (X ) = 0 ， j=1,2,…, J 若 dK 是 X (k) 點(diǎn)的一個(gè)可行下降方向，則應(yīng)有 可行： 下降： ? ?? ? 0 1 , 2 , ,kjg X j J??[ ( ) ] 0 ( 1 , 2 , , )k T kj jJ? ? ?g x d[ ( ) ] 0k T kf??xdi. （ 3） X (k) 為可行域中的一個(gè)外點(diǎn) ， X (k) 的不存在可行下降方向 。 根據(jù)約束函數(shù)和目標(biāo)函數(shù)的不同性狀，分別采用以下幾種策略繼續(xù)搜索。 0x1x2x0xkdkxk + 1g2( x ) =0g1( x ) =00()f?? x1 新點(diǎn)在可行域內(nèi)的情況 0x1x2x0xkdkxk + 1g2( x ) =0g1( x ) =0g3( x ) =00()f?? x2 新點(diǎn)在可行域外的情況 0x1x2x0xkxk + 1g2( x ) =0g1( x ) =0g3( x ) =00()f?? x 3 沿線性約束面的搜索 0x1x2x0xkxk + 1g2( x ) =0g1( x ) =0g3( x ) =00()f?? x1()f?? xx? 4 沿非線性約束面的搜索 ? 可行方向的產(chǎn)生方法 （ 1）優(yōu)選方向法 m in [ ( ) ]k T kf? xd[ ( ) ] 0 ( 1 , 2 , , )k T kj jJ? ? ?g x d[ ( ) ] 0k T kf??xd. 1k ?d各函數(shù)均為設(shè)計(jì)變量 dk的線性函數(shù)，因此該式為一個(gè)（線性）規(guī)劃問題。 x k d k g 1 ( x )=0 g 2 ( x )=0 g 3 ( x )=0 g 4 ( x )=0 ()kf?? x( ) / ( )k k kff? ? ? ?d P x P xP—— 投影算子，為 nXn階矩陣 1[]TT???P I G G G GG —— 起作用約束函數(shù)的梯度矩陣， nXJ階矩陣； 12[ ( ) , ( ) , , ( ) ]k k kJg g g? ? ? ?G x x x（ 2） 梯度投影法 基本思想：通過構(gòu)造罰函數(shù)把約束問題轉(zhuǎn)化為一系列無約束最優(yōu)化問題，進(jìn)而用無約束最優(yōu)化方法去求解，這類方法又稱為序列無約束最小化方法。簡(jiǎn)稱為 SUMT法。 懲罰函數(shù)法 內(nèi)點(diǎn)法 ()11( , ) ( )()mki ir f r g???? ?xx x()1( , ) ( ) l n[ ( ) ]mkiir f r g??? ? ??x x x或 外點(diǎn)法 2211( , ) ( ) m a x[ 0 , ( ) ] [ ( ) ]mlijijr f r g r h???? ? ???x x x x0 1 2r r r? ? ? ? ? 罰因子 混合法 ( ) ( ) 2()1111( , ) ( ) [ ( ) ]()mlkkjkijir f r hgr???? ? ???x x xx0 1 2 1 0kkr r r r r ?? ? ? ? ? ?罰因子 0 1 2 1 0kkr r r r r ?? ? ? ? ? ? 罰因子 懲罰函數(shù)的不同構(gòu)造形式