多變量約束優(yōu)化方法

第7章 多維約束優(yōu)化方法Chapter 7 Constrained Several Variables Technique7-1 概述 Summarize工程中的優(yōu)化設(shè)計問題絕大多數(shù)是約束優(yōu)化問題，即 約束最優(yōu)點不僅與目標(biāo)函數(shù)的性質(zhì)有關(guān)，也與約束函數(shù)的性質(zhì)有關(guān)。因此，約束優(yōu)化問題比無約束優(yōu)化問題情況更復(fù)雜，求解困難也更大。根據(jù)對約束條件處理方法的不同，解決約束優(yōu)化問題的方法分成二類:1) 直接法 Direct Method尋優(yōu)過程直接在設(shè)計空間的可行域D內(nèi)進(jìn)行，但對每一個迭代點必須進(jìn)行可行性和下降性檢查。直接算法簡單，直觀性強(qiáng)，對目標(biāo)函數(shù)和約束函數(shù)的函數(shù)性態(tài)沒有特殊的要求。但是它的計算量大、收斂速度慢，因此效率低，比較適用于解決低維數(shù)的、具有不等式約束的優(yōu)化問題。這類算法包括隨機(jī)方向法、復(fù)合形法等。2) 間接法 Indirect Method間接法的主要思路是，首先將約束優(yōu)化問題轉(zhuǎn)化為無約束優(yōu)化問題，然后再用無約束優(yōu)化方法來進(jìn)行求解。間接解法分很多類，其中比較有代表性的、用的比較廣泛的是懲罰函數(shù)法。7-2 懲罰函數(shù)法 Penalty Method在將約束優(yōu)化問題轉(zhuǎn)換成無約束優(yōu)化問題時,懲罰函數(shù)法的處理思路與拉格朗日法很相似, 都是把目標(biāo)函數(shù)與約束條件合并形成新的函數(shù),而后求其最優(yōu)解。但懲罰函數(shù)法得到的新函數(shù)不是一個而是一個系列。因此，用無約束優(yōu)化算法求解得的最優(yōu)解也是一個系列，即，當(dāng)時，。因此，懲罰函數(shù)法又稱序列無約束最小化技術(shù)Sequential Unconstrained Minimization Technique ， 即SUMT法。7-2-1懲罰函數(shù)法的基本原理 Principle 根據(jù)約束優(yōu)化問題構(gòu)造新的函數(shù) - 懲罰函數(shù) 其中，是和的復(fù)合函數(shù)；是在迭代過程中隨迭代次數(shù)的增大而不斷調(diào)整的參數(shù)，稱為懲罰因子Penalty Factor，它們是單調(diào)增monotone increasing (decreasing) 或者單調(diào)減的正實數(shù)數(shù)列positive real number；和稱為懲罰項 Penalty term，其值為非負(fù)。從懲罰函數(shù)的表達(dá)式可以看到，懲罰函數(shù)值在一般情況下總是大于原目標(biāo)函數(shù)的值，即。為了使懲罰函數(shù)的最優(yōu)解最后能夠收斂到原目標(biāo)函數(shù)的最優(yōu)解，一方面要構(gòu)造合適的復(fù)合函數(shù)和，使其在懲罰函數(shù)的極小化過程中，當(dāng)?shù)c不滿足原約束條件時受到懲罰；另一方面，隨著迭代次數(shù)的增加，不斷地調(diào)整懲罰因子的值，使懲罰項的懲罰作用越來越小并趨于消失。因此，構(gòu)造的懲罰項應(yīng)具有如下性質(zhì) 根據(jù)懲罰項的函數(shù)形式，懲罰函數(shù)法又分為內(nèi)點懲罰函數(shù)法、外點懲罰函數(shù)法和混合懲罰函數(shù)法。7-2-2 外點懲罰函數(shù)法 Exterior Point Penalty Method1）. 特點用外點懲罰函數(shù)法求解約束優(yōu)化問題時，懲罰函數(shù)定義在可行域外，在尋優(yōu)過程中無約束的序列最優(yōu)點 是從可行域的外部逼近原約束優(yōu)化問題最優(yōu)解的。在可行域內(nèi)部，原目標(biāo)函數(shù)與懲罰函數(shù)的等值線重合（即），而在外部，由于懲罰起作用，懲罰函數(shù)的等值線有畸形的趨勢。用外點法即可以求解不等式約束優(yōu)化問題，又可以求解等式約束優(yōu)化問題。2） 僅有不等式約束的外點懲罰函數(shù)（1）問題 （2）懲罰函數(shù) （3）說明式中， , 懲罰因子為單調(diào)增的正數(shù)數(shù)列（I）當(dāng)?shù)c滿足約束條件時，無論取何值都有，此時有，懲罰項不起作用；(II) 當(dāng)?shù)c不滿足約束條件時，如，就有，表明懲罰項起作用了，迭代點離邊界越遠(yuǎn)，項就越大，其懲罰作用也就越大，就迫使迭代點向可行域靠攏，最終；(III) 懲罰因子是一個遞增的正值數(shù)列，即，在計算過程中一般按迭代式取，其中 （一般取510）。（4）迭代過程及算法框圖(見教材P109)a) 選擇初始點(可任選,但的無約束極值點均在可行域外)，收斂精度(黃金,無約束,約束3個)，確定及 如；b) 置計數(shù)器 ;c) 選用一種無約束算法，求的無約束極值點 ；d) 檢驗收斂精度， ，；e) ， 3 )。(5) 例題例7-1 用外點法求下列優(yōu)化問題的最優(yōu)解 解: 外點懲罰函數(shù) 所以在可行域外, 懲罰函數(shù) , 令, 其無約束的極值點為 當(dāng) （圖略見教材）例7-2 用外點法求下列優(yōu)化問題的最優(yōu)解解：構(gòu)造懲罰函數(shù) 在可行域外有懲罰函數(shù) 由 聯(lián)立求解得 當(dāng) 當(dāng) 當(dāng) 當(dāng) 從例7-1和例7-2可以看到，外點法的尋優(yōu)路線是從可行域外部逼近最優(yōu)點的，但卻永遠(yuǎn)不會到達(dá)約束線或進(jìn)入可行域。因此，用外罰函數(shù)法得到的最終結(jié)果實際上仍然是不可行的點。3）同時具有等式和不等式約束的外點懲罰函數(shù)懲罰函數(shù)為 和同為單調(diào)增正數(shù)列，和可以取同樣的值。4）應(yīng)用中的問題 （1） 初始點的選擇可以任意在可行域內(nèi)外選擇初始點, 但的無約束極值點均在可行域外；（2） 懲罰因子初始值和衰減系數(shù)的選擇 和的選擇很有講究。理論和實踐都證明，值取的越小，迭代次數(shù)就越多，尋優(yōu)效率就會越低；但取的過大，懲罰函數(shù)會出現(xiàn)嚴(yán)重扭曲，用無約束算法尋優(yōu)會碰到困難，甚至導(dǎo)致失敗。常取，；（3） 約束裕量 圖7-1約束裕量法 從外點法的特點可知，由于不可能趨于，因此,外罰函數(shù)的序列只能是一個無限接近約束邊界的非可行點，也就是說該點不能嚴(yán)格地滿足所有的約束條件。這種情況有時在工程上的某些場合是不允許的。為了解決這類問題，對那些必須嚴(yán)格滿足約束條件引入一個約束裕量，其幾何意義就是將這些約束邊界向可行域內(nèi)移動一段距離，即約束條件成為 。這樣求出的雖不在新的可行域內(nèi)，但它已經(jīng)包括在原可行域內(nèi)。應(yīng)該注意，不能取得很大，否則造成新的可行域與原來相差太大而失去了意義。一般取。7-2-2 內(nèi)點懲罰函數(shù)法 1） 特點與外點懲罰函數(shù)相反, 內(nèi)點懲罰函數(shù)是定義在可行域內(nèi)的， 并在可行域內(nèi)求懲罰函數(shù)的序列最優(yōu)點，即求解無約束問題時的探索點（迭代點）總是保持在可行域內(nèi)。但內(nèi)懲罰函數(shù)法只能求解不等式約束優(yōu)化問題。 2）內(nèi)點懲罰函數(shù)（1）問題 （2）懲罰函數(shù) 懲罰因子為單調(diào)減的正數(shù)。編程時一般取 例7-3 用內(nèi)點法求下列優(yōu)化問題的最優(yōu)解解： 構(gòu)造內(nèi)點懲罰函數(shù) 不難求出其極值點的表達(dá)式為 它的變化趨勢圖略見教材。 例7-4 用內(nèi)點法求下列優(yōu)化問題的最優(yōu)解 解：構(gòu)造懲罰函數(shù) 由 聯(lián)立求解得 當(dāng) 時不滿足 舍去則有無約束極值點為 當(dāng) 當(dāng) 當(dāng) 當(dāng) 3）應(yīng)用中的問題 (1) 初始點的選擇 與外點法不同, 必須是一個可行點, 它可以人為指定,也可以用隨機(jī)等方法確定, 最簡單的是選擇原設(shè)計訪案。 （2）和的選擇 相比之下，的選擇對計算效率影響很大，確定它需要一定的經(jīng)驗，對于較復(fù)雜的優(yōu)化問題需通過多次試算決定。許多書上推薦其取，常用，也可以按書上的經(jīng)驗公式來確定。而的取值范圍常在之間。4）內(nèi)點法和外點法的比較 懲罰函數(shù)的定義范圍及其極值點的趨勢： 懲罰函數(shù)的表達(dá)式： 解決問題的范圍： 各自的優(yōu)點： 內(nèi)點法的迭代過程應(yīng)在可行域內(nèi)進(jìn)行，所以迭代初始點必須選在可行域內(nèi)，而外點法則無此要求，可以在全設(shè)計空間內(nèi)選擇初始點；內(nèi)點法不適用于等式約束的優(yōu)化問題，而外點法可以用，但最優(yōu)點必須在約束邊界上；外點法無法觀察在優(yōu)化過程中，可行域內(nèi)設(shè)計點的目標(biāo)函數(shù)值的變化情況，而往往這確是工程設(shè)計人員所關(guān)心的。而內(nèi)點法在給定一個可行的初始設(shè)計方案以后，它將產(chǎn)生一系列目標(biāo)函數(shù)得到改善的可以接受的設(shè)計方案。因為任何一個