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

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

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

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

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

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

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