約束優(yōu)化方法2懲罰函數(shù)法.ppt

5.3.4 懲罰函數(shù)法,懲罰函數(shù)法簡介 內(nèi)點(diǎn)法 外點(diǎn)法 混合法 總結(jié),懲罰函數(shù)法簡介,懲罰函數(shù)法是一種使用很廣泛、很有效的間接法。,基本原理： 把約束優(yōu)化問題轉(zhuǎn)化成無約束優(yōu)化問題來求解。 兩個(gè)前提條件： 一是不破壞原約束的約束條件 二是最優(yōu)解必須歸結(jié)到原約束問題的最優(yōu)解上去,按照懲罰函數(shù)的構(gòu)成方式，懲罰函數(shù)法分為三種： 外點(diǎn)法、內(nèi)點(diǎn)法、混合法,懲罰項(xiàng),r(k) 、m(k)-罰因子,懲罰函數(shù),5.3.4.1 內(nèi)點(diǎn)法,引例 設(shè)有一維不等式約束優(yōu)化問題的數(shù)學(xué)模型,S.T. :,由圖可見，目標(biāo)函數(shù)的可行域?yàn)閤b，在可行域內(nèi)目標(biāo)函數(shù) 單調(diào)上升，它的最優(yōu)解顯然是,x*=b ，F(xiàn)*=ab,對引例的懲罰函數(shù)進(jìn)行分析，以對內(nèi)點(diǎn)法有初步認(rèn)識：,本問題是不等式約束優(yōu)化問題，故只有一項(xiàng)懲罰項(xiàng) ，一個(gè)罰因子,規(guī)定罰因子 為某一正數(shù)，當(dāng)?shù)c(diǎn)是在可行域內(nèi) 時(shí)，則懲罰項(xiàng)的值必為正值，因此必有,而且，當(dāng)x越趨近于約束邊界時(shí)，由于懲罰項(xiàng),增大，所以罰函數(shù) 的值越大。當(dāng)xb時(shí)，罰函 數(shù)的值將趨近于+。因此，當(dāng)初始點(diǎn)取在可行域內(nèi)，求 函數(shù) 的極小值時(shí)，只要適當(dāng)控制搜索步長， 防止迭代點(diǎn)跨入非可行域，則所搜索到的無約束極小點(diǎn) x*必可保持在可行域內(nèi)。,若對于罰因子的取值由初始的 逐漸變小 時(shí)，懲罰函數(shù) 愈逼近于原目標(biāo)函數(shù)F（x），罰 函數(shù)曲線越來越接近于原F（x）=ax直線，如圖所示，對 應(yīng)罰函數(shù) 的最優(yōu)點(diǎn)列 不斷趨近于原約 束優(yōu)化問題的最優(yōu)點(diǎn)x*=b,小結(jié),由以上可見，如果選擇一個(gè)可行點(diǎn)作初始點(diǎn) ，令其罰因子 由大變小，通過求罰函數(shù) 的一系列最優(yōu)點(diǎn)， 顯見，無約束最優(yōu)點(diǎn)序列將逐漸趨近于原約束優(yōu)化問題的最優(yōu)點(diǎn)x*。,內(nèi)點(diǎn)罰數(shù)法的形式及特點(diǎn),具有不等式約束的優(yōu)化問題的數(shù)學(xué)模型,u=1，2，p,構(gòu)造如下形式的內(nèi)點(diǎn)罰函數(shù),S.T. :,關(guān)于懲罰因子規(guī)定為正，即 。且在優(yōu)化過程中 是減小的，為確保為遞減數(shù)列，取常數(shù)C,0C1,稱系數(shù)C為罰因子降低系數(shù),=0,或,關(guān)于懲罰項(xiàng) ，由于在可行域內(nèi)有 ， 且 永遠(yuǎn)取正值，故在可行域內(nèi)懲罰項(xiàng)永為正。 的值越小則懲罰項(xiàng)的值越小。,由于在約束邊界上有 ，因此，當(dāng)設(shè)計(jì)點(diǎn)趨 于邊界時(shí)，懲罰項(xiàng)的值將趨于無窮大。由此可知，在可 行域內(nèi)，始終有 。,當(dāng) 時(shí) ，卻有 ，所以整個(gè)最 優(yōu)化的實(shí)質(zhì)就是用罰函數(shù) 去逼近原目標(biāo)函數(shù)F(x); 當(dāng)設(shè)計(jì)點(diǎn)逐漸由內(nèi)部趨近于邊界時(shí)，由于懲罰項(xiàng)無窮 增大，則罰函數(shù)也將無窮增大。,從函數(shù)圖形上來看，猶如在可行域的邊界上筑起一 道陡峭的高墻，使迭代點(diǎn)自動(dòng)保持在可行域內(nèi)，用此辦 法來保證搜索過程自始至終不離開可行域。所以，內(nèi)點(diǎn)法 也常稱為圍墻函數(shù)法。,內(nèi)點(diǎn)罰函數(shù)法的求解過程,為了用懲罰函數(shù) 去逼近原目標(biāo)函數(shù)F(x)， 則要用F(x)及 構(gòu)造一個(gè)無約束優(yōu)化問題的數(shù)學(xué)模型,選取初始點(diǎn)（原約束優(yōu)化問題的內(nèi)點(diǎn)） ，初始罰 因子 ，罰因子降低系數(shù)C。用無約束優(yōu)化方法求上式無 約束優(yōu)化問題的最優(yōu)解。,所得解為 ；當(dāng)k在增大的過程中，得到懲罰函數(shù)的無 約束最優(yōu)點(diǎn)列為,點(diǎn)列中各點(diǎn)均在可行域內(nèi)部，隨著k的過程， 點(diǎn)列將趨近于原約束問題的最優(yōu)解x*。即,=x*,由此可知，內(nèi)點(diǎn)法的序列無約束最優(yōu)點(diǎn) 是在可行域內(nèi) 部且趨近于約束最優(yōu)點(diǎn)x*的。,內(nèi)點(diǎn)罰函數(shù)還可以按如下形式構(gòu)成,初始點(diǎn)x(0)的選取,由于內(nèi)點(diǎn)法的搜索是在可行域內(nèi)進(jìn)行，顯然初始點(diǎn)必須 是域內(nèi)可行點(diǎn)。須滿足,確定初始點(diǎn)常用如下兩種方法,自定法 即根據(jù)設(shè)計(jì)者的經(jīng)驗(yàn)或已有的計(jì)算資料自行決 定某一可行點(diǎn)作為初始點(diǎn)。,搜索法 任選一個(gè)設(shè)計(jì)點(diǎn) 為初始點(diǎn)。通過對初始點(diǎn) 約束函數(shù)值的檢驗(yàn)，按其對每個(gè)約束的不滿足程度加以調(diào) 整，將 點(diǎn)逐步引入到可行域內(nèi)，成為可行初始點(diǎn)， 這就是搜索法。,關(guān)于幾個(gè)參數(shù)的選擇,初始罰因子r(0)的選取,如果 值選得太大，則在一開始罰函數(shù)的懲罰項(xiàng)的 值將遠(yuǎn)遠(yuǎn)超出原目標(biāo)函數(shù)的值，因此，它的第一次無約束極 小點(diǎn)將遠(yuǎn)離原問題的約束最優(yōu)點(diǎn)。在以后的迭代中，需要很 長時(shí)間的搜索才能使序列無約束極小點(diǎn)逐漸向約束最優(yōu)點(diǎn)逼近。,如果 值選得太小，則在一開始懲罰項(xiàng)的作用甚小， 而在可行域內(nèi)部懲罰函數(shù) 與原目標(biāo)函數(shù)F(x)很相近， 只在約束邊界附近罰函數(shù)值才突然增高。這樣，使其罰函數(shù) 在在約束邊界附近出現(xiàn)深溝谷地，罰函數(shù)的性態(tài)變得惡劣。,如下圖，對于有深溝谷地性態(tài)差的函數(shù)，不僅搜索所需的 時(shí)間長，而且很難使迭代點(diǎn)進(jìn)入最優(yōu)的鄰域，以致極易使 迭代點(diǎn)落入非可行域而導(dǎo)致計(jì)算的失敗。,r（0）=150,或,遞減系數(shù)C的選擇,罰因子遞減系數(shù)C的選擇，一般認(rèn)為對算法的成敗影響 不大。規(guī)定0C1。,若C值選得較小，罰因子下降快，可以減少無約束優(yōu)化 的次數(shù)，但因前后兩次無約束最優(yōu)點(diǎn)之間的距離較遠(yuǎn)，有 可能使后一次無約束優(yōu)化本身的迭代次數(shù)增多，而且使序 列最優(yōu)點(diǎn)的間隔加大，對約束最優(yōu)點(diǎn)的逼近不利。,相反，若C值取得較大，則無約束優(yōu)化次數(shù)就要增多。,通常建議取C=0.1-0.5,終止準(zhǔn)則,隨著罰因子 的值不斷減小，罰函數(shù)的序列無約 束最優(yōu)點(diǎn)將越來越趨近于原約束優(yōu)化問題的最優(yōu)點(diǎn)。,設(shè)懲罰函數(shù) 的無約束最優(yōu)點(diǎn)列為,對應(yīng)的罰函數(shù)值為,終止準(zhǔn)則可用下述兩者之一,相鄰兩次懲罰函數(shù)無約束最優(yōu)點(diǎn)之間的距離已足夠的小。,設(shè)1為收斂精度，一般取1=10-4-10-5，則需要滿足,相鄰兩次懲罰函數(shù)值的相對變化量已足夠小。,設(shè)2為收斂精度，一般取2=10-3-10-4，則需要滿足,算法步驟,構(gòu)造內(nèi)點(diǎn)懲罰函數(shù),選擇可行初始點(diǎn) ，初始罰因子 ，罰因子降低系 數(shù)C，收斂精度 與 ，置k0,求無約束優(yōu)化問題， 有最優(yōu)點(diǎn) 。,當(dāng)k=0時(shí)轉(zhuǎn)步驟，否則轉(zhuǎn)步驟,置kk+1， ，并轉(zhuǎn)步驟,由終止準(zhǔn)則，若滿足則轉(zhuǎn)步驟，否則轉(zhuǎn), , 輸出最優(yōu)解(x*,F*),內(nèi)點(diǎn)法流程圖,給定：x(0) D,r(0),C,1,2,k0,K=0?,入口,用無約束優(yōu)化方法求罰函數(shù) 的優(yōu)化點(diǎn),出口,+,+,-,-,內(nèi)點(diǎn)罰函數(shù)的特點(diǎn),內(nèi)點(diǎn)法只適用于解不等式約束優(yōu)化問題。由于內(nèi)點(diǎn)法 需要在可行域內(nèi)部進(jìn)行搜索，所以初始點(diǎn)必須在可行域 內(nèi)部選取可行設(shè)計(jì)點(diǎn)。,內(nèi)點(diǎn)法的突出優(yōu)點(diǎn)在于每個(gè)迭代點(diǎn)都是可行點(diǎn),因此，當(dāng)?shù)_(dá)到一定階段時(shí)，盡管尚沒有達(dá)到最優(yōu)點(diǎn)， 但也可以被接受為一個(gè)較好的近似解。,5.3.4.2 外點(diǎn)法,外點(diǎn)法可以解不等式約束優(yōu)化問題或等式約束優(yōu)化問題,引例 設(shè)有一維不等式優(yōu)化問題的數(shù)學(xué)模型,用外點(diǎn)法構(gòu)造懲罰函數(shù)，具體構(gòu)造形式如下,xb,xb,S.T. :,寫成另一種形式,如上圖，此處的懲罰函數(shù)也是由原目標(biāo)函數(shù)F(x)與懲罰 項(xiàng)而組成。懲罰項(xiàng)中包含有可調(diào)整的參數(shù)r(k)與約束函數(shù)。,由懲罰項(xiàng)的構(gòu)造可知，若迭代點(diǎn)在可行域的內(nèi)部，懲罰 項(xiàng)的值為0，懲罰函數(shù)值與原目標(biāo)函數(shù)值相等；而若在非可 行域（即可行域的外部），懲罰項(xiàng)是以約束函數(shù)的平方加 大的，即迭代點(diǎn)違反約束越嚴(yán)重，懲罰項(xiàng)的值增加的越大。 因此，在非可行域內(nèi)，必有 且罰因子r（k）越 大，懲罰作用越明顯。,由圖，對于某r(k)值，求出懲罰函數(shù) 的最優(yōu)點(diǎn) 當(dāng)取罰因子 為遞增數(shù)列，隨k的增加，罰函數(shù)的無約束最 優(yōu)點(diǎn)序列為,該序列將趨近與原約束問題的最優(yōu)點(diǎn)x*，x*=b。 值得注意的是，盡管 增加直至趨于無窮大，但最終 的近似最優(yōu)點(diǎn)x*仍在可行域的外部。 即外點(diǎn)法構(gòu)造的罰函數(shù)是使迭代點(diǎn)從可行域的外部逐 漸逼近約束最優(yōu)點(diǎn)，這正是外點(diǎn)法名稱的由來。,外點(diǎn)罰函數(shù)法的形式及特點(diǎn),先討論解不等式約束優(yōu)化問題,設(shè)有不等式約束優(yōu)化問題,u=1，2，p,構(gòu)造外點(diǎn)法懲罰函數(shù)的常見形式,取正遞增,S.T. :,引入罰因子遞增系數(shù)C1，并令,=,懲罰項(xiàng),的含義可用另一形式表示,當(dāng)gu(x) 0 （xD）,當(dāng)gu(x) 0 （xD）,在可行域內(nèi) （包括邊界）,在非可行域， 為遞增函數(shù),外點(diǎn)罰函數(shù)的求解過程,用外點(diǎn)罰函數(shù)去逼近原目標(biāo)函數(shù)F(x)，構(gòu)造一個(gè)無約束 優(yōu)化問題模型,xRn,任選初始點(diǎn)x(0)，初始法罰因子r(0)0,罰因子遞增系數(shù)C1,對于r(k)為某一值，同過對懲罰函數(shù)的無約束求優(yōu)，可 得最優(yōu)點(diǎn) 。隨著k的增大，得無約束最優(yōu)點(diǎn)列,在k的過程中，點(diǎn)列將趨近于原問題的最優(yōu)點(diǎn),實(shí)線為原目標(biāo) 函數(shù)等值線,虛線為罰函數(shù) 等值線,總結(jié),由上圖可見，兩種等值線在可行域內(nèi)部及邊界上是重合 的；而在非可行域中，罰函數(shù)的等值線升高了。即只有在 可行域外部懲罰項(xiàng)才起到懲罰的作用。r(k)值越大，懲罰作 用越大。,由上b圖可知，在起作用約束邊界處罰函數(shù)等值線變得越 密集和越陡峭。隨r(k)的增大，最優(yōu)點(diǎn)列將越接近于原約束 優(yōu)化問題的最優(yōu)點(diǎn)x*。但須注意，近似的最優(yōu)點(diǎn)是落在邊 界處非可行域一側(cè)。,對幾個(gè)問題的討論,（1）初始點(diǎn)x(0)的選取,在可行域及非可行域內(nèi)均可。,（2）初始罰因子r(0)和遞增系數(shù)C的選取,外點(diǎn)法中，這兩者的選擇對算法的成敗和計(jì)算速度有顯著 的影響。,選取過小，則序貫無約束求解的次數(shù)就增多，收斂速度慢；反之，則在非可行域中，發(fā)函數(shù)比原目標(biāo)函數(shù)要大得多，特別在起作用約束邊界處產(chǎn)生尖點(diǎn)，函數(shù)性態(tài)變壞，從而限制了某些無約束優(yōu)化方法的使用，致使計(jì)算失 敗。,C的選取影響不大，通 常C=5-10,（3）約束容差帶,最優(yōu)點(diǎn)在非可行域內(nèi)，是一個(gè)非可行點(diǎn)，這對某些工 程是不允許的。因此，可在約束邊界可行域一側(cè)加一條容 差帶。,相當(dāng)于將約束條件改為,是容差量，通常,終止準(zhǔn)則,隨著罰因子 的值不斷增大，罰函數(shù)的序列無約束最 優(yōu)點(diǎn)將越來越趨近于原約束優(yōu)化問題的最優(yōu)點(diǎn)。,設(shè)懲罰函數(shù) 的無約束最優(yōu)點(diǎn)列為,對應(yīng)的罰函數(shù)值為,終止準(zhǔn)則可用下述兩者之一,相鄰兩次懲罰函數(shù)無約束最優(yōu)點(diǎn)之間的距離已足夠的小。,設(shè)1為收斂精度，一般取1=10-4-10-5，則需要滿足,相鄰兩次懲罰函數(shù)值的相對變化量已足夠小。,設(shè)2為收斂精度，一般取2=10-3-10-4，則需要滿足,外點(diǎn)法流程圖,給定：x(0) R ,r(0),C,1,2,k0,k=0?,入口,用無約束優(yōu)化方法求罰函數(shù) 的優(yōu)化點(diǎn),出口,+,+,-,-,算法步驟與流程圖,求 ，得最優(yōu)點(diǎn),當(dāng)k=0時(shí)轉(zhuǎn)步驟，否則轉(zhuǎn)步驟,置kk+1， ，并轉(zhuǎn)步驟,由終止準(zhǔn)則，若滿足則轉(zhuǎn)步驟，否則轉(zhuǎn), , 輸出最優(yōu)解(x*,F*)，停止計(jì)算。,算法步驟,在n維空間任取初始點(diǎn)x（0）,選取初始罰因子r(0),遞增系數(shù)C，并置k0,用外點(diǎn)罰函數(shù)法解等式約束優(yōu)化問題,設(shè)有二維約束優(yōu)化問題,h1(x)=x1+x2-10=0,如右圖，h1(x)為該約束 問題的可行域，這條直線以 外的整個(gè)x1ox2平面為非可 行域。目標(biāo)函數(shù)等值線與該 直線的切點(diǎn)為最優(yōu)點(diǎn),最優(yōu)點(diǎn),S.T. :,按外點(diǎn)法的基本思想，構(gòu)造懲罰函數(shù),xD,xD,在可行域上，懲罰項(xiàng)的值為零，懲罰函數(shù)值與原目標(biāo)函數(shù) 值相同；在非可行域上，懲罰函數(shù)的值恒為正，罰函數(shù)大于 原目標(biāo)函數(shù)，即在可行域外懲罰項(xiàng)起到了懲罰作用。,在k的過程中，點(diǎn)列將趨近于原問題的最優(yōu)點(diǎn),對于m(k)，隨著k的增大，得無約束最優(yōu)點(diǎn)列,推廣到具有一般的等式約束優(yōu)化問題,首先構(gòu)造如下形式的外點(diǎn)懲罰函數(shù),懲罰因子m（k）規(guī)定取正，m(0)1,在可行域上值為零，非可行域上，值恒大于零,S.T. :,5.3.4.3 混合法,用罰函數(shù)法解決有等式約束和不等式約束的一般約束 （GP型）優(yōu)化問題的方法，把它稱為混合懲罰函數(shù)法， 簡稱混合法。,1 混合法懲罰函數(shù)的形式及特點(diǎn),一般約束問題的優(yōu)化模型,S.T. :,用懲罰函數(shù)法將其轉(zhuǎn)化為無約束優(yōu)化問題,懲罰函數(shù)是由原目標(biāo)函數(shù)及包含約束函數(shù)的懲罰項(xiàng)組 成。由于該問題的約束條件包含不等式約束與等式約束 兩部分。因此，懲罰項(xiàng)也應(yīng)由對應(yīng)的兩部分組成。對應(yīng) 等式約束部分的只有外點(diǎn)法一種形式，而對應(yīng)不等式 的約束部分有內(nèi)點(diǎn)法或外點(diǎn)法兩種形式。因此按照對不 等式約束處理的方法不同，混合法懲罰函數(shù)也具有兩種 形式。,內(nèi)點(diǎn)形式的混合法,不等式約束部分按內(nèi)點(diǎn)法形式處理的混合法，懲罰函數(shù) 形式為,是遞增序列,為了統(tǒng)一用一個(gè)罰因子r（k），且又按內(nèi)點(diǎn)法形式，即,0C1,上式可寫為,外點(diǎn)形式的混合法,不等式約束部分按外點(diǎn)法形式處理的混合法，懲罰函數(shù) 形式為,其中，罰因子r(k)恒為正，且為遞增序列，即,遞增系數(shù)C1,初始點(diǎn)可在Rn空間內(nèi)任選，初始罰因子及遞增系數(shù)參照 外點(diǎn)法選取。,2 算法步驟及流程圖,參照內(nèi)點(diǎn)法與外點(diǎn)法。（外點(diǎn)法，內(nèi)點(diǎn)法）,例題,設(shè)有二維一般約束優(yōu)化問題，數(shù)學(xué)模型為,S.T. :,目標(biāo)函數(shù)等值線及約束曲線見下圖。,最優(yōu)點(diǎn)x*既要在不等式 約束包括的范圍內(nèi)，同時(shí) 又必須在等式約束 h(x)=0 的直線上，試求該約束優(yōu)化