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