【正文】 行點 。 dkxk()k? gx?dkxk1()k? gx1?2?2()k? gxg1( x ) =0g2( x ) =0[ ( ) ] 0k T k??g x d[ ( ) ] 0 ( 1 , 2 , , )k T kj jJ? ? ?g x d? 2）下降條件 方向的下降條件是指沿該方向作微小移動后，所得新點的目標函數(shù)值是下降的。 適時約束 若有點 X k 使某個不等式約束 gu(X) ≤ 0 的等號 成立，即 則稱 g i(X) ≤ 0 為點 X k 的一個適時約束。 可行方向法的搜索策略？ 即： 11( ) 0( ) ( )kukkgFF???????xxxO x1 x2 O x1 x2 a) 極值點處于多角形的某一頂點上 b) 極值點處于等值線的中心 c) 極值點處于約束曲線與等值線的切點上 d) 極值點處于兩個約束曲線的交點上 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 關于設計約束的若干概念 可行域 所有滿足全部約束條件的點的集合。 (6)判斷終止條件 1)各頂點與好點函數(shù)值之差的均方根值小于誤差限，即 1( ) ( ) 2 211{ [ ( ) ( ) ] }K jLjF X F XK ?????2）各頂點與好點的函數(shù)值之差的平方和小于誤差限，即 3）各頂點與好點函數(shù)值差的絕對值之和小于誤差限，即 如果不滿足終止迭代條件，則返回步驟 2繼續(xù)進行下一次迭代；否則，可將最后復合形的好點 X(L)及其函數(shù)值F(X(L))作為最優(yōu)解輸出。選出好點X(L)和壞點 X(H)。對于維數(shù)較高的問題，采用隨機方法，先產(chǎn)生 K個隨機點，然后再把非可行點逐一調(diào)入可行域內(nèi)。如此反復迭代直到找到最優(yōu)解。 167。 如此循環(huán)下去 。 52 隨機方向法 基本思想：利用計算機產(chǎn)生的隨機數(shù)所構成的隨機方向進行搜索 ， 產(chǎn)生的新點必須在可行域內(nèi) ， 即滿足直接法的特性 。 （ 2）間接法 間接法包括：罰函數(shù)法（內(nèi)點罰函數(shù)法、外點罰函數(shù)法、混合罰函數(shù)法）、廣義乘子法、廣義簡約梯度法和約束變尺度法等。 56 序列二次規(guī)劃法 167。 51 引言 167。只要由約束條件所決定的可行域是一個凸集，目標函數(shù)是凸函數(shù)，其約束最優(yōu)解就必是全域最優(yōu)解。再以新點為起點，重復上述搜索過程，直至滿足收斂條件。 其基本原理如圖所示 ， 在約束可行域 S內(nèi)選取一個初始點 X(0)， 在不破壞約束的條件下以合適的步長 a。 圖 約束隨機方向探索法的基本原理 ? ? 1 , 2 , , , 1 , 2 , ,ji i n j N? ??，? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?1212 2 2 21211 , 2 ,jjjj j jnjnd j N??? ? ???????????????? ??? ? ????? ????1 產(chǎn)生隨機方向的方法 在 n 維設計空間中 在 [ 1 ， 1] 區(qū)間內(nèi) ， 產(chǎn)生 n 反復迭代計算 ， 使復合形不斷向最優(yōu)點移動和收縮 ， 直至收縮到復合形的頂點與形心非常接近 ， 且滿足迭代精度要求為止 。 最小值 ， 記為最好點 X(L)。 將非可行點調(diào)入可行域 將產(chǎn)生的 K個隨機點進行判斷是否在可行域內(nèi)，重新排列，將可行點依次排在前面，如有 q個頂點 X (1)、 X (2)、 ……X (q)是可行點，其它 Kq個為非可行點。若 X(R)為非可行點，將映射系數(shù)減半后再按上式改變映射點，直到 X(R)進入可行域內(nèi)為止。 （ 2） 復合形法適用于僅含不等式約束的問題 。 若有點 Xk 使得 則 Xk 為一個邊界點。 0x00()f? ??dx 根據(jù)約束函數(shù)和目標函數(shù)的不同性狀，分別采用以下幾種策略繼續(xù)搜索。 ? 滿足可行、下降條件的方向位于可行下降扇形區(qū)內(nèi)，在扇形區(qū)內(nèi)尋找一個最有利的方向作為本次迭代的搜索方向。 ? 約束一維搜索： 與以前所講過的一維搜索相比 ， 約束一維搜索的特點在于：確定初始區(qū)間時 ， 對產(chǎn)生的每一個探測點都進行可行性判斷 ， 如違反了某個或某些約束條件， 就必須減少步長因子 ， 以使新的探測點落在最近的一個約束曲面上或約束曲面的一個容許的區(qū)間 內(nèi) 。 i. （ 1） X (k) 為可行域中的一個內(nèi)點 ? ? DX k ?? ? ? ? ? ?11 ,k k kX X d X D???? ? ? ?? ?? ? ? ?? ? 01 ?? ?kk XfXf[ ( ) ] 0k T kf??xd（ 2） X (k) 點是可行域中若干約束面的交點 設 X (k) 點在約束面 gj (X ) = 0 ， j=1,2,…, J 若 dK 是 X (k) 點的一個可行下降方向，則應有 可行： 下降： ? ?? ? 0 1 , 2 , ,kjg X j J??[ ( ) ] 0 ( 1 , 2 , , )k T kj jJ? ? ?g x d[ ( ) ] 0k T kf??xdi. （ 3） X (k) 為可行域中的一個外點 ， X (k) 的不存在可行下降方向 。 按一定的法則改變罰因子 r1 和 r2的值 ，求得一序列的無約束最優(yōu)解 ， 不斷地逼近原約束優(yōu)化問題的最優(yōu)解 。 0kr ? 罰因子的作用 是：由于內(nèi)點法只能在可行域內(nèi)迭代 ， 而最優(yōu)解很可能在可行域內(nèi)靠近邊界處或就在邊界上 ， 此時盡管泛函的值很大 ， 但罰因子是不斷遞減的正值 ， 經(jīng)多次迭代 ， 接近最優(yōu)解時 ， 懲罰項已是很小的正值 。一般的看法是 ， c值的大小在迭代過程中不起決定性作用 ， 通常的取值范圍在 ~ 。 *1x *2x *()r? *()frr 1 10 1000 ∞ 1 0 8/3 8/3 用內(nèi)、外點法不同 2212m in ( )f x x??x1s . t . ( ) 1 0gx? ? ?x內(nèi)點法和外點法的簡單比較 內(nèi)點法的特點： （ 1）始點必須為嚴格內(nèi)點 （ 2）不適于具有等式約束的數(shù)學模型 （ 3）迭代過程中各個點均為可行設計方案 （ 4）一般收斂較慢 （ 5）初始罰因子要選擇得當 （ 6）罰因子為遞減，遞減率 c有 0c1 外點法的特點： （ 1）初始點可以任選 （ 2）對等式約束和不等式約束均可適用 （ 3）僅最優(yōu)解為可行設計方案 （ 4）一般收斂較快 （ 5）初始罰因子要選擇得當 （ 6）罰因子為遞增，遞增率 c’有 c’1 3. 混合法 ? 混合法是用內(nèi)點法處理不等式約束，用外點法處理等式約束。 m i n ( )s . t . ( ) 0fh?? ??xx對于 相對應的拉格朗日函數(shù)為： ( , ) ( ) ( )TL f h????x x x 在 xk點作泰勒展開 ， 取二次近似表達式 1 1 111( , ) ( , ) [ ( , ) ] ( )1( ) ( )2k k k k k k T k kk k k k kL L L? ? ?? ? ???? ? ? ?? ? ?x x x x xx x H x x令 , 1k k k???d x x拉格朗日函數(shù)的一階導數(shù)為 ( , ) ( ) ( ( ) )k k k k T kL f h??? ? ? ? ?x x x11( , ) ( ) ( ) ( ) ( ( ) ( ( ) ) )1()21( ) ( ) ( ( ) ( ( ) ) ( ( ) ( )2k k k k k k k T k T kk T k kk k T k k T k k T k k T k kL f h f hf h h f? ? ????? ? ? ? ? ??? ? ? ? ? ? ?x x x x x dd B dx x x d x d d B dHk用 變尺度矩陣 Bk來代替 將等式約束 函數(shù)在 xk作泰勒展開 ， 取線性近似式 : ( ) 0h ?x11( ) ( ) ( ) ( )( ) ( ) 0k k k T k kk k T kh h hhh??? ? ? ?? ? ? ?x x x x xx x d 構成二次規(guī)劃子問題 1m in ( ) [ ( ) ]2TTQ P f? ? ?d x d d Bds . t . ( ) ( ) 0Thh ? ? ?x x d 求解上述二次規(guī)劃子問題 ， 得到的 d就是搜索方向 。 窮舉法就是對所有研究對象進行普查，其優(yōu)點是結論完全可靠，但工作量大，適用于規(guī)模較小的問題。 蒙特卡洛優(yōu)化方法除了可以獨立尋求最優(yōu)解外 ，往往還與其它算法相配合 。然后轉(zhuǎn)到第一步，分布網(wǎng)格，重新計算。 有約束優(yōu)化方法 基本思想：在可行域中選取 K 個設計點 （n+1≤K≤2n） 作為初始復合形的頂點 。 ii. （ 2） X (k) 為可行域中的一個邊界點，設 X (k) 在約束面 gi (X ) = 0 上。 懲罰函數(shù)法 內(nèi)點法 ()11( , ) ( )()mki ir f r g???? ?xx x()1( , ) ( ) l n[ ( ) ]mkiir f r g??? ? ??x x x或 外點法 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ù)的不同構造形式