非線性規(guī)劃2-SUMT方法罰函數(shù)法

1、第二節(jié) SUMT方法（罰函數(shù)法）一、SUMT方法的原理SUMT（sequential unconstrained minimization technique）法，序列無(wú)約束極小化方法,亦稱為罰函數(shù)法。它是一種不等式約束最優(yōu)化問(wèn)題的間接解法它的基本思想是將原來(lái)的目標(biāo)函數(shù)和約束函數(shù)按一定的方式構(gòu)成一個(gè)新的函數(shù)，在這個(gè)新函數(shù)中，既包括目標(biāo)函數(shù)，又包括全部約束函數(shù)和一個(gè)可以變化的乘子。當(dāng)這個(gè)乘子按一定的方式改變時(shí)，就得到一個(gè)新函數(shù)序列，求每一個(gè)新函數(shù)的最優(yōu)解都是一個(gè)無(wú)約束最優(yōu)化問(wèn)題，這樣就把一個(gè)約束最優(yōu)化問(wèn)題轉(zhuǎn)化為一系列無(wú)約束最優(yōu)化問(wèn)題進(jìn)行求解。所得到的最優(yōu)解序列將逐步逼近原問(wèn)題的最優(yōu)解。引例一：s

2、.t 顯然f（X）的最優(yōu)點(diǎn)為x*=b，對(duì)應(yīng)的最小值為f（X*）=ab用SUMT求解函數(shù)的最優(yōu)解構(gòu)造函數(shù)可變化乘子，它是一個(gè)很小的正數(shù)。其最優(yōu)解為：此時(shí)對(duì)應(yīng)的的最小值為最優(yōu)點(diǎn)和最小值均是的函數(shù)。當(dāng)取不同值時(shí)，它們有不同的值，而當(dāng)時(shí)，即最后收斂于約束最優(yōu)點(diǎn)。以上分析從理論上說(shuō)明了無(wú)約束最優(yōu)化問(wèn)題與約束優(yōu)化問(wèn)題之間的聯(lián)系：約束非線性規(guī)劃問(wèn)題可以通過(guò)構(gòu)造新目標(biāo)函數(shù)序列，用無(wú)約束優(yōu)化方法求其極小點(diǎn)，并逐次逼近原問(wèn)題的最優(yōu)點(diǎn)。問(wèn)題：如何構(gòu)造新函數(shù)？或者說(shuō)新函數(shù)具有什么特點(diǎn)？特點(diǎn)：對(duì)于某一個(gè)（即當(dāng)它為某一定值時(shí)），當(dāng)設(shè)計(jì)點(diǎn)在可行區(qū)中且距離邊界較遠(yuǎn)時(shí)，其對(duì)應(yīng)的新函數(shù)的函數(shù)值不是很大，而當(dāng)設(shè)計(jì)點(diǎn)離約束邊界越近，

3、函數(shù)值越大，特別是當(dāng)設(shè)計(jì)點(diǎn)靠近約束邊界時(shí)，一個(gè)小小的接近會(huì)引起函數(shù)值的劇烈增加。因此在對(duì)新函數(shù)進(jìn)行最優(yōu)搜索過(guò)程中，搜索方向不會(huì)向邊界方向靠近，如果向邊界靠近，會(huì)通過(guò)函數(shù)值的陡增進(jìn)行懲罰。這是罰函數(shù)法的由來(lái)。當(dāng)然必須保證設(shè)計(jì)點(diǎn)在可行區(qū)內(nèi)。（思考：如果不在可行區(qū)內(nèi)會(huì)出現(xiàn)什么情況？）就是罰函數(shù)，為“懲罰因子”。由于的上述特征，對(duì)于處在可行區(qū)中的設(shè)計(jì)點(diǎn)就像有一堵“圍墻”一樣，阻止最優(yōu)搜索進(jìn)入非可行區(qū)，故又稱作“圍墻函數(shù)”，引入的乘子又稱為 “障礙因子”。以上是內(nèi)點(diǎn)法的理論分析引例二：目標(biāo)函數(shù)與約束函數(shù)同上s.t 構(gòu)造新函數(shù)：式中：懲罰因子，任意一個(gè)很大的正數(shù)對(duì)于這一新函數(shù)，當(dāng)設(shè)計(jì)點(diǎn)在可行區(qū)時(shí)，即不滿足

4、約束條件時(shí)，越大，也越大，它可看作是對(duì)不滿足約束條件的一種懲罰。這時(shí)，當(dāng)=，同樣可以得到一系列曲線，可用無(wú)約束優(yōu)化方法求其極小點(diǎn)，當(dāng)時(shí)，驗(yàn)證：以上對(duì)于不滿足約束條件設(shè)計(jì)點(diǎn)的分析分析是外點(diǎn)法的理論依據(jù)。兩個(gè)例子對(duì)罰函數(shù)法原理進(jìn)行了理論分析，罰函數(shù)法通常分為內(nèi)點(diǎn)法、外點(diǎn)法以及混合法，本節(jié)主要介紹內(nèi)點(diǎn)法、外點(diǎn)法的具體做法。二、SUMT內(nèi)點(diǎn)法一）內(nèi)點(diǎn)法原理內(nèi)點(diǎn)法將新目標(biāo)函數(shù)定義于可行區(qū)域內(nèi)，這樣它的初始點(diǎn)以及后面產(chǎn)生的迭代點(diǎn)序列，亦必定在可行區(qū)域內(nèi)。它是求解不等式約束優(yōu)化設(shè)計(jì)問(wèn)題中一種十分有效的方法。內(nèi)點(diǎn)懲罰函數(shù)法就是以不同的加權(quán)參數(shù)來(lái)構(gòu)造一序列無(wú)約束的新目標(biāo)函數(shù)，求這一序列懲罰因數(shù)的無(wú)約束極值點(diǎn)：，

5、使它逐漸逼近原約束問(wèn)題的最擾解，而且不論原約束問(wèn)題的最優(yōu)點(diǎn)在可行域內(nèi)還是在可行域邊界上，其整個(gè)搜索過(guò)程都在約束區(qū)域內(nèi)進(jìn)行。當(dāng)設(shè)計(jì)點(diǎn)趨向于邊界時(shí)，由于不等式約束函數(shù)趨近于零，其懲罰項(xiàng)的函數(shù)值就陡然增加并趨近于無(wú)窮大，這好像在可行域邊界上筑起了一道“圍墻”，使迭代點(diǎn)始終保持在可行區(qū)域內(nèi)。因此，也只有當(dāng)懲罰因子趨近于零時(shí)，才能求得約束邊界上的約束最優(yōu)點(diǎn)。二）內(nèi)點(diǎn)法算法從可行區(qū)域內(nèi)的某一個(gè)初始點(diǎn)開(kāi)始，再選取適當(dāng)?shù)某跏贾?，求出懲罰函數(shù)的最優(yōu)點(diǎn)。然后將它作為下一次求無(wú)約束極值的初始點(diǎn)，并把減至，再求的最優(yōu)點(diǎn)，如此繼續(xù)下去，直至收斂于原約束問(wèn)題的最優(yōu)點(diǎn)。其具體算法如下：三）內(nèi)點(diǎn)法算例四）內(nèi)點(diǎn)懲罰函數(shù)法使用中

6、的幾個(gè)問(wèn)題(1)初始點(diǎn)必須是嚴(yán)格可行的，一般可以來(lái)用隨機(jī)法來(lái)產(chǎn)生。而且要求它不應(yīng)靠近約束邊界，遠(yuǎn)離最優(yōu)點(diǎn)，這樣容易保證計(jì)算過(guò)程穩(wěn)定可靠。(2)選取適當(dāng)?shù)膽土P因子的初始值，對(duì)于SUMT方法的正常計(jì)算及其汁算效率都有一定的影響。在SUMT方法方法中，只有r0時(shí)，懲罰函數(shù)的極值點(diǎn)才是原問(wèn)題的約束最優(yōu)解。因此，要想在一開(kāi)始就通過(guò)取較小的值來(lái)加快收斂速度，這往往是不會(huì)成功的。即使采用最穩(wěn)定的最優(yōu)化方法，函數(shù)也難于收斂到極值點(diǎn)。相反，若選取較大的值就會(huì)增加求無(wú)約束極值的次數(shù)。因此，為了減少迭代次數(shù)，應(yīng)取較小的值，但為了使求極值的過(guò)程穩(wěn)定些，又應(yīng)將值取大些。通常，如果初始點(diǎn)是一個(gè)較保守的設(shè)計(jì)(即離約束邊界較

7、遠(yuǎn))，那么就應(yīng)該這樣來(lái)選擇值，即可使初始點(diǎn)的障礙項(xiàng)或懲罰項(xiàng)不要在懲罰函數(shù)中起支配作用。由此得到的一種選擇的方法是用這個(gè)辦法通常能得到相當(dāng)合理的初始值。一般推薦P=10，對(duì)于非凸規(guī)劃問(wèn)題，P=150；但當(dāng)初始點(diǎn)接近某個(gè)或幾個(gè)約束邊界時(shí)，上式的值就太小了，建議取P=100。當(dāng)目標(biāo)函數(shù)和約束函數(shù)的非線性程度不高時(shí)，直接取也可取得較好效果?？偟膩?lái)說(shuō)，的取值沒(méi)有固定的方法，它與目標(biāo)函數(shù)和約束函數(shù)的性態(tài)和設(shè)計(jì)點(diǎn)的位置有關(guān)，實(shí)際計(jì)算時(shí)往往需要多次試算才能取得較好的初值。(3)在序列無(wú)約束極小化的過(guò)程中，懲罰因子將是一個(gè)按簡(jiǎn)單關(guān)系遞減的數(shù)，即式中，c為下降系數(shù)，c1。如果c過(guò)小，會(huì)造成懲罰函數(shù)的等值線變化過(guò)快

8、，導(dǎo)致無(wú)約束極小化的困難。遇到這種情況，建議把c值取大一點(diǎn)，如Cmax=0.5-0.7。內(nèi)點(diǎn)法是機(jī)械設(shè)計(jì)中一般愿意采用的方法。因?yàn)檫@種方法有一個(gè)誘人的特點(diǎn)就是在給定一個(gè)可行的初始方案之后，它能給出一系列逐步得到改進(jìn)的可行的設(shè)計(jì)方案，因此，只要設(shè)計(jì)要求允許，我們可以選用其中任一個(gè)無(wú)約束員優(yōu)解，而不一定取問(wèn)題的最后的約束最優(yōu)解，使設(shè)計(jì)方案儲(chǔ)備一定的能力。三、SUMT外點(diǎn)法一）外點(diǎn)法原理與內(nèi)點(diǎn)法將懲罰函數(shù)定義于可行域內(nèi)且求解無(wú)約束問(wèn)題的探索點(diǎn)總是保持在可行域內(nèi)的特點(diǎn)不同，外點(diǎn)法的特點(diǎn)是將懲罰函數(shù)定義于約束可行域之外，且求解無(wú)約束問(wèn)題的探索點(diǎn)是從可行域外部逼近原目標(biāo)函數(shù)的約束最優(yōu)解的。對(duì)于目標(biāo)函數(shù)f（

9、X）受約束于gi（X）0的最優(yōu)化設(shè)計(jì)問(wèn)題，利用外點(diǎn)法求解時(shí)，作為無(wú)約束新目標(biāo)函數(shù)的懲罰函數(shù)，其一般表達(dá)式為其中：懲罰項(xiàng)構(gòu)造懲罰項(xiàng)的指數(shù)，其取值會(huì)影響懲罰函數(shù)的性質(zhì)，一般取=2懲罰因子，是大于零的一個(gè)序列，應(yīng)滿足二）外點(diǎn)法算法三）外點(diǎn)法算例四）外點(diǎn)懲罰函數(shù)法使用中的幾個(gè)問(wèn)題1.懲罰因子的大小對(duì)罰函數(shù)的性態(tài)的影響，太小太大均不好。2.初始點(diǎn)的選擇：可以在可行區(qū)內(nèi)，也可在外，只要原目標(biāo)函數(shù)的極值點(diǎn)不在可行區(qū)內(nèi)，搜索到的極值點(diǎn)一般在可行區(qū)外。3.最優(yōu)解和約束裕量：最優(yōu)解只有在（）時(shí)，才會(huì)得到可行解，通常取，就認(rèn)為已經(jīng)達(dá)到了約束邊界。這樣，只能取得一個(gè)接近于可行域的非可行設(shè)計(jì)方案。當(dāng)要求嚴(yán)格滿足不等式約束條件(如強(qiáng)度、剛度等性能約束)時(shí)，為了最終取得一個(gè)可行的最優(yōu)設(shè)計(jì)方案必須對(duì)那些要求嚴(yán)格滿足的約束條件，增加約束裕量，這就是說(shuō)，定義新的約束條件這樣可以用新定義的約束函數(shù)構(gòu)成的懲罰函數(shù)來(lái)求它的極小化，取得最優(yōu)設(shè)