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

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