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

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

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

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

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

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

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