第四章非線性規(guī)劃4復(fù)合形法

1、第四節(jié) 復(fù)合形法復(fù)合形法(Complex Method)是1965年由博克斯(Box)提出，后經(jīng)古恩(Gwin)修正的解非線性規(guī)劃的一種直接搜索法。如同隨機(jī)方向搜索法一樣在確定搜索方向時(shí)，它不需要函數(shù)的梯度信息，它是求解非線規(guī)劃中的一種簡單適用的方法。一、基本原理對(duì)于約束優(yōu)化問題使用迭代格式所謂復(fù)合形是指在n維設(shè)計(jì)空間的可行域內(nèi)由k(n+12n)個(gè)頂點(diǎn)所構(gòu)成的多面體。復(fù)合形法是一種在可行域內(nèi)直接的求優(yōu)方法。利用復(fù)合形各頂點(diǎn)處目標(biāo)函數(shù)值的大小關(guān)系，判斷目標(biāo)函數(shù)值的下降方向，不斷丟掉函數(shù)值最大的所謂最差點(diǎn)，代之以既使目標(biāo)函數(shù)值有所下降又能滿足所有約束條件的一個(gè)新點(diǎn)，從而不斷地構(gòu)成新的復(fù)合形。如此重

2、復(fù)計(jì)算，使新的復(fù)合形不斷地向可行域的最優(yōu)點(diǎn)移動(dòng)和收縮，直至得到滿足收斂準(zhǔn)則的近似解為止。由于對(duì)復(fù)合形不必保持規(guī)則圖形，頂點(diǎn)數(shù)較多，因此可以求解非線性的約束問題，面且計(jì)算穩(wěn)定可靠。但不能用于解含有等式約束的問題。二、復(fù)合形的迭代步驟一）確定復(fù)合形的頂點(diǎn)復(fù)合形法是一種在可行域內(nèi)直接的求優(yōu)方法，要求第一個(gè)復(fù)合形的k個(gè)頂點(diǎn)都是可行的。對(duì)復(fù)合形的頂點(diǎn)數(shù)一般推薦取k=2n，當(dāng)n計(jì)算問題的維數(shù)較多(如n>5)時(shí)，可取kn+1。如果復(fù)合形頂點(diǎn)數(shù)少了，一旦出現(xiàn)丟失頂點(diǎn)現(xiàn)象就可能會(huì)出現(xiàn)降維搜索而找不到真正的最優(yōu)點(diǎn)。初始復(fù)合形的確定方法有如下幾種： (1)給定k個(gè)初始頂點(diǎn)。由設(shè)計(jì)者預(yù)先選擇k個(gè)設(shè)計(jì)方案，即人工

3、構(gòu)造一個(gè)初始復(fù)合形。由于k個(gè)頂點(diǎn)都必須滿足所有的約束條件，因此當(dāng)設(shè)計(jì)變量數(shù)目較多或約束條件比較復(fù)雜時(shí)，這樣做可能是很不方便的或者是很困難的。(2)給定一個(gè)初始頂點(diǎn)，隨機(jī)產(chǎn)生其他頂點(diǎn)。如果用常規(guī)設(shè)計(jì)方法能取得一個(gè)設(shè)計(jì)方案，此方案雖然不是最優(yōu)的，但卻是一個(gè)可行的。則其他k-1個(gè)頂點(diǎn)可用隨機(jī)法產(chǎn)生式中 各設(shè)計(jì)變量的的上、下界限，一般取邊界約束值；0,1區(qū)間內(nèi)服從均勻分布的偽隨機(jī)數(shù)。這樣隨機(jī)產(chǎn)生的k-1個(gè)頂點(diǎn)，雖然可以滿足邊界約束條件，但不一定能滿足性能約束條件，還必須逐個(gè)進(jìn)行檢查，把不滿足約束條件的頂點(diǎn)移到可行域內(nèi)。設(shè)已有q個(gè)頂點(diǎn)滿足全部約束條件，先求出q個(gè)頂點(diǎn)的中心點(diǎn) 即然后將不滿足約束條件的點(diǎn)向

4、中心點(diǎn)靠攏，即 （復(fù)合形的收縮運(yùn)算）若還不滿足約束條件，則可以重復(fù)用上式計(jì)算。（即以新的進(jìn)行收縮）只要中心點(diǎn)是可行點(diǎn)，點(diǎn)經(jīng)逐步向靠攏，最終總能成為一個(gè)可行頂點(diǎn)。對(duì)隨機(jī)產(chǎn)生的各個(gè)頂點(diǎn)進(jìn)行這種處理后，最后可取得k個(gè)初始可行頂點(diǎn)，從而構(gòu)成初始復(fù)合形。事實(shí)上，只要可行域是凸集，其中心點(diǎn)必為可行點(diǎn)，因而用上述方法可以成功地在可行域內(nèi)構(gòu)成初始復(fù)合形。如果可行域?yàn)榉峭辜蔷陀惺〉目赡埽?dāng)中心點(diǎn)處于可行域之外時(shí)，就應(yīng)該縮小隨機(jī)選點(diǎn)的邊界域，重新產(chǎn)生各頂點(diǎn)。(3)隨機(jī)產(chǎn)牛全部頂點(diǎn)。二）計(jì)算各頂點(diǎn)函數(shù)值最差點(diǎn)（函數(shù)值最大的點(diǎn)）最好點(diǎn)（函數(shù)值最小的點(diǎn)）復(fù)合形的幾何中心 即三）復(fù)合形法運(yùn)算，構(gòu)造新的復(fù)合形復(fù)合形不斷

5、地向可行域的最優(yōu)點(diǎn)移動(dòng)和收縮，是通過反射、收縮、擴(kuò)展和重構(gòu)復(fù)臺(tái)形等四種運(yùn)算來實(shí)現(xiàn)的。1.反射運(yùn)算去掉最壞點(diǎn)后所有點(diǎn)的幾何中心點(diǎn)反射就是沿最壞點(diǎn)和的連線方向上取映射點(diǎn)，即式中稱為反射系數(shù)一般，例如可?。˙ox建議）。如果滿足所有約束條件，且，即可用代替組成新復(fù)合形，完成一次迭代。如果不滿足約束條件，或不滿足，則將反射系數(shù)減半重新計(jì)算，若仍不滿足要求，可繼續(xù)將減半，直到減到很小(例如小于10-5)還不滿足要求時(shí)，那就只能放棄這一方向，改用次壞點(diǎn)的映射方向，重新尋求滿足條件的映像點(diǎn)。2.擴(kuò)展運(yùn)算若初次確定的反射點(diǎn)，其目標(biāo)函數(shù)值比最好點(diǎn)的還小，即時(shí)，說明沿此方向映射的效果顯著，有進(jìn)一步擴(kuò)張的必要，以探

6、求更好的點(diǎn)。即按下式計(jì)算新點(diǎn) （擴(kuò)展運(yùn)算）式中，稱為擴(kuò)展系數(shù)，一般多。如果，則說明擴(kuò)展成功，用替換組成新復(fù)合形，完成本次迭代。如果，則擴(kuò)展失敗，仍取原反射點(diǎn)替換組成新復(fù)合形。3. 收縮運(yùn)算若已找不到好的反射點(diǎn)，還可以從到中心點(diǎn)連線以內(nèi)收縮尋找。按下式計(jì)算收縮點(diǎn)式中，稱為收縮系數(shù)，一般。與擴(kuò)展同樣，如果則收縮成功，用替換，否則失敗。4.重構(gòu)若采取上述措施均元效，還可以采取向最好點(diǎn)靠攏的措施，即：各頂點(diǎn)向最好點(diǎn)靠攏后再重新尋求新頂點(diǎn)。四）檢查停機(jī)準(zhǔn)則在迭代計(jì)算中，由于復(fù)合形不斷向最好點(diǎn)移動(dòng)和縮小，因此當(dāng)復(fù)合形的k個(gè)頂點(diǎn)的目標(biāo)函數(shù)值的與中心點(diǎn)均方差很小時(shí)，則停止迭代或五）獲取最優(yōu)解滿足停機(jī)準(zhǔn)則后取函數(shù)值最小的頂點(diǎn)作為最優(yōu)解。三、算法框圖四、討論由于復(fù)合形法在迭代過程中不必計(jì)算目標(biāo)函數(shù)的一、二階導(dǎo)數(shù)，也無需進(jìn)行一維最優(yōu)化探索，因此對(duì)目標(biāo)函數(shù)和