【正文】 第五章 有約束優(yōu)化方法 167。 51 引言 167。 52 隨機方向法 167。 53 復合形法 167。 54 可行方向法 167。 55 懲罰函數(shù)法 167。 56 序列二次規(guī)劃法 167。 51 引言 機械優(yōu)化設計中的問題，大多數(shù)屬于約束優(yōu)化設計問題，其數(shù)學模型為 m i n ( ) ,. . ( ) 0 1 , 2 , ,( ) 0 1 , 2 , ,njkfRs t g j mh k l??????????xxxx 上一章討論的都是無約束條件下非線性函數(shù)的尋優(yōu)方法，但在實際工程中大部分問題的變量取值都有一定的限制，也就是屬于有約束條件的尋優(yōu)問題。 與無約束問題不同，約束問題目標函數(shù)的最小值是滿足約束條件下的最小值，即是由約束條件所限定的可行域內(nèi)的最小值。只要由約束條件所決定的可行域是一個凸集，目標函數(shù)是凸函數(shù)，其約束最優(yōu)解就必是全域最優(yōu)解。否則，將由于所選擇的初始點的不同，而探索到不同的局部最優(yōu)解上。在這種情況下，探索結果經(jīng)常與初始點的選擇有關。為了能得到全局最優(yōu)解，在探索過程中最好能改變初始點，有時甚至要改換幾次。 （ 1）直接法 直接法包括：網(wǎng)格法、復合形法、隨機試驗法、隨機方向法、可變?nèi)莶罘ê涂尚蟹较蚍ā? （ 2）間接法 間接法包括：罰函數(shù)法（內(nèi)點罰函數(shù)法、外點罰函數(shù)法、混合罰函數(shù)法）、廣義乘子法、廣義簡約梯度法和約束變尺度法等。 根據(jù)求解方式的不同，約束優(yōu)化設計問題可分為 :直接解法、間接解法。 直接解法通常適用于僅含不等式約束的問題，思路是在 m個不等式約束條件所確定的可行域內(nèi)，選擇一個初始點，然后決定可行搜索方向 d 且以適當?shù)牟介L ，進行搜索，得到一個使目標函數(shù)值下降的可行的新點，即完成一次迭代。再以新點為起點，重復上述搜索過程，直至滿足收斂條件。 ?1 ( 0 , 1 , 2 , )k k kk dk?? ? ? ?xxk?kd步長 可行搜索方向 可行搜索方向 :當設計點沿該方向作微量移動時，目標函數(shù)值將下降，且不會越出可行域 。 間接解法的基本思路是按照一定的原則構造一個包含原目標函數(shù)和約束條件的新目標函數(shù)，即將原約束優(yōu)化問題轉(zhuǎn)化成為一個或一系列的無約束優(yōu)化問題。再對新的目標函數(shù)進行無約束優(yōu)化計算，從而間接地搜索到原約束問題的最優(yōu)解。 167。 52 隨機方向法 基本思想：利用計算機產(chǎn)生的隨機數(shù)所構成的隨機方向進行搜索 ， 產(chǎn)生的新點必須在可行域內(nèi) ， 即滿足直接法的特性 。 隨機方向法 ， 是約束最優(yōu)化問題的一種常用的直接求解方法 。 它和隨機梯度法 、 Gauss－ Seidel法等都屬于約束隨機法 。 其基本原理如圖所示 ， 在約束可行域 S內(nèi)選取一個初始點 X(0)， 在不破壞約束的條件下以合適的步長 a。 沿 X(0)點周圍幾個不同的方向 （ 以某種形式產(chǎn)生的隨機方向 ）進行若干次探索 ， 并計算各方向上等距離 （ 步長 a。 ）點的函數(shù)值 ， 找出其中的最小值 f（ X(l)） 及點 X(l)。 若 f（ X(l)） ＜ f（ X(0)） ， 則繼續(xù)沿方向 （ X(l)X(0)） 以適當?shù)牟介L a向前跨步 ， 得到新點 X(1)， 若 f（ X(1)） 老 f（ X(l)） ， 則將新的起點移至 X(1) ， 重復前面過程 。 否則應縮短步長 a， 直至取得約束好點 。 如此循環(huán)下去 。當?shù)牟介L已經(jīng)很小時 ， 則表明已經(jīng)逼近約束最優(yōu)點。 達到計算精度要求時 ， 即可結束迭代計算 。 圖 約束隨機方向探索法的基本原理 ? ? 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 N 個均勻分布的偽隨機數(shù) 計算 ， nii ,2,1 ???1 , 2 , ,i i ia x b i n? ? ?? ? ? ?0 1 , 2 , ,i i i i ix a b a i n?? ? ? ? ? 產(chǎn)生隨機初始點 利用 n 個在 [ 0 ， 1] 內(nèi)均勻分布的偽隨機數(shù)和邊界約束 產(chǎn)生隨機點 X(0) 復合形法是求解約束非線性最優(yōu)化問題的一種重要的直接方法 。 它來源于用于求解無約束非線性最優(yōu)化問題的單純形法 ， 實際上是單純形法在約束問題中的發(fā)展 。 如前所述 ， 在求解無約束問題的單純形法中 ， 不需計算目標函數(shù)的梯度 ， 而是靠選取單純形的頂點并比較各頂點處目標函數(shù)值的大小 ， 來尋找下一步的探索方向的 。 在用于求解約束問題的復合形法中 ， 復合形各頂點的選擇和替換 ， 不僅要滿足目標函數(shù)值的下降 ， 還應當滿足所有的約束條件 。 167。 53 復合形法 基本思想：在可行域中選取 K 個設計點 （n+1≤K≤2n） 作為初始復合形的頂點 。 比較各頂點目標函數(shù)值的大小 ， 去掉目標函數(shù)值最大的頂點 (稱最壞點 )， 以壞點以外其余各點的中心為映射中心 ， 用壞點的映射點替換該點 ， 構成新的復合形頂點 。 反復迭代計算 ， 使復合形不斷向最優(yōu)點移動和收縮 ， 直至收縮到復合形的頂點與形心非常接近 ， 且滿足迭代精度要求為止 。 令： X(4)= X(0)+α(X(0)X(H)) 稱 X(4)為映射點，記為 X(R)， α為映射系數(shù)，通常取α=，可根據(jù)實際情況進行縮減。 取次好點和好點連線的中點為 X(0)。 一般情況下，映射點的函數(shù)值比壞點的函數(shù)值要小，即 F(X(R)) F(X(H))。若滿足可行域，則用 X(R)代替X(H)構成新的復合形。如此反復迭代直到找到最優(yōu)解。 在可行域內(nèi)任選三個初始點 X(1)、 X(2)、 X(3)， 連接這三點形成一個三角形 ， 此三角形稱為初始復合形 。 計算各個頂點函數(shù)值 F(X(1))、 F(X(2))、 F(X(3))， 找出最大值 ， 記為壞點 X(H)。 最小值 ， 記為最好點 X(L)。 在次好點和好點連線與壞點反向一側(cè)的各點應具有較小的目標值 。 在迭代過程中 ， 按映射系數(shù) α= ， 不一定滿足適用性和可行性 ， 如出現(xiàn)此情況 ， 將映射系數(shù)減半 ， 重新取得 X(R)， 使它滿足適用性和可行性 。 一、初始復合形的構成 復合形的頂點 K通常取 n+1≤K≤2n個。對于維數(shù)較低的優(yōu)化問題，由于頂點數(shù)目較少，可試湊幾個可行點作為復合形的頂點。對于維數(shù)較高的問題，采用隨機方法，先產(chǎn)生 K個隨機點，然后再把非可行點逐一調(diào)入可行域內(nèi)。 產(chǎn)生 K個隨機點 xi= ai +ξi (bi ai) i=1,2,….,n ξi為（ 0， 1）區(qū)間內(nèi)產(chǎn)生的均勻分布的隨機數(shù)，需要 n個隨機數(shù)產(chǎn)生一個點 X (1)。同樣，產(chǎn)生其它的隨機點 X (2)、X (3)、 ……X (K)。 將非可行點調(diào)入可行域 將產(chǎn)生的 K個隨機點進行判斷是否在可行域內(nèi)，重新排列，將可行點依次排在前面，如有 q個頂點 X (1)、 X (2)、 ……X (q)是可行點，其它 Kq個為非可行點。對X (q+1)，將其調(diào)入可行域的步驟是： （ 1）計算 q個點集的中心 X (s)； （ 2）將第 q+1點朝著點 X (s)的方向移動，按下式產(chǎn)生新的 X (q+1)，即 X(q+1)= X(s)+ (X(q+1)— X(s)) 這個新點 X(q+1)實際就是 X(s)與原 X(q+1)兩點連線的中點 ， 如圖 。 若新的 X(q+1)點仍為非可行點 ， 按上式再產(chǎn)生X(q+1)， 使它更向 X(s)靠攏 ， 最終使其成為可行點 。 按照這個方法 ， 同樣使 X (q+2)、 X (q+3)、 …… X (K)都變?yōu)榭尚悬c ， 這 K個點就構成了初始復合形 。 二、復合形法的迭代步驟 （ 1）構造初始復合形； （ 2）計算各頂點的函數(shù)值 F(X(j))， j=1,2,….,K 。選出好點X(L)和壞點 X(H)。 ( ) ( ) ( )( ) ( ) ( ): ( ) m in { ( ) , 1 , 2 , , }: ( ) m a x { ( ) , 1 , 2 , , }L L jH H jX F X F X j KX F X F X j K????（ 3）計算壞點外的其余各頂點的中心點 X(0)。 ()011,1KjjX X j HK ???? ?（ 4）計算映射點 X(R) 檢查 X(R)是否在可行域內(nèi)。若 X(R)為非可行點，將映射系數(shù)減半后再按上式改變映射點，直到 X(R)進入可行域內(nèi)為止。 ( ) ( 0 ) ( 0 ) ( )()RHX X X X?? ? ?（ 5）構造新的復合形 計算映射點的函數(shù)值 F(X(R))，并與壞點的函數(shù)值F(X(H))比較，可能存在兩種情況： 1）映射點優(yōu)于壞點 F(X(R)) F(X(H)) 在此情況，用 X(R)代替 X(H)，構成新的復合形。 若經(jīng)過多次的映射系數(shù)減半，仍不能使映射點優(yōu)于壞點，則說明該映射方向不利，此時，應改變映射方向，取對次壞點 ( ) ( ) ( ): ( ) m a x{ ( ) , 1 , 2 , , , }SH SH jX F X F X j K j H? ? ?的映射。 ()01( ) ( 0 ) ( 0 ) ( )1,1()KjjR SHX X j SHkX X X X?????? ? ??再轉(zhuǎn)回本步驟的開始處，直到構成新的復合形。 2） 映射點次于壞點 F(X(R)) 〉 F(X(H)) 這種情況由于映射點過遠引起的 ， 減半映射系數(shù) ，若有 F(X(R)) F(X(H))， 這又轉(zhuǎn)化為第一種情況 。 (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)解輸出。 ( ) ( )1( ) ( )KjLjF X F X ?????( ) ( ) 21[ ( ) ( ) ]KjLjF X F X ?????方法特點 （ 1） 復合形法是求解約束非線性最優(yōu)化問題的一種直接方法 ， 僅通過選取各頂點并比較各點處函數(shù)值的大小 ， 就可尋找下一步的探索方向 。 但復合形各頂點的選擇和替換 ， 不僅要滿足目標函數(shù)值下降