1、懲罰函數(shù)法,外點(diǎn)法,懲罰函數(shù)法是求解約束優(yōu)化問題的一種間接解法。它的基本思想是將一個(gè)約束的優(yōu)化問題轉(zhuǎn)化為一系列的無約束優(yōu)化問題來求解。為此，對(duì)于非線性約束優(yōu)化問題構(gòu)造如下無約束優(yōu)化問題 并且要求，當(dāng)點(diǎn)X不滿足約束條件時(shí)，等號(hào)后第二項(xiàng)和第三項(xiàng)的值很大，反之當(dāng)點(diǎn)X滿足約束條件時(shí)，這兩項(xiàng)的值很小或等于零。這相當(dāng)于，當(dāng)點(diǎn)X,在可行域之外時(shí)對(duì)目標(biāo)函數(shù)的值加以懲罰，因此，這兩項(xiàng) 和 稱為懲罰項(xiàng)，r1(k)和r2(k)稱為懲罰因子，（X， r1(k) ，r2(k) ）稱為懲罰函數(shù)。其中， 和 分別是由不等式約束函數(shù)和等式約束函數(shù)構(gòu)成的復(fù)合函數(shù)。 可以證明，當(dāng)懲罰項(xiàng)和懲罰函數(shù)滿足以下條件 lim =0 k l

2、im =0 k lim| （X， r1(k) ，r2(k) ）-f（X（k） |=0 k 時(shí)，無約束優(yōu)化問題在r1、 r2 的過程所產(chǎn)生的極小點(diǎn)X（k）序列將逐漸逼近于原約束優(yōu)化問題的最優(yōu)解，即有l(wèi)imX（k）=X* k ,這就是說，以這樣的復(fù)合函數(shù)和一組按一定規(guī)律變化的懲罰因子構(gòu)造一系列懲罰函數(shù)，并對(duì)每一個(gè)懲罰函數(shù)依次求極小，最終將得到約束優(yōu)化問題的最優(yōu)解。這種將約束優(yōu)化問題轉(zhuǎn)化為一系列無約束優(yōu)化問題求解的方法稱為懲罰函數(shù)法。 外點(diǎn)法既可以用來求解不等式約束問題又可以用來求解等式約束問題。 特點(diǎn)：將懲罰函數(shù)定義在可行域的外部，從而在求解系列無約束優(yōu)化問題的過程中，是從可行域的外部逐漸逼近原優(yōu)

3、化問題的最優(yōu)解。,對(duì)于不等式約束問題的求解,取外點(diǎn)懲罰函數(shù)的形式為： 式中的懲罰項(xiàng) 含義為：當(dāng)?shù)c(diǎn)X在 可行域內(nèi)，由于 無論,取何值，懲罰項(xiàng)的值區(qū)零，函數(shù)值不受到懲罰，這 時(shí)懲罰函數(shù)等于原目標(biāo)函數(shù) ；當(dāng)?shù)c(diǎn)X違反某一 約束，在可行域外，由于 無論 取何正值， 必定有 這表明在X的可行域外時(shí)，懲罰函數(shù)起著懲罰作用。X離 約束邊界越遠(yuǎn)， 起的作用越大。 懲罰項(xiàng)與懲罰函數(shù)也隨懲罰因子的變化而變化，當(dāng)外點(diǎn)的 懲罰因子 按一個(gè)遞增的正實(shí)數(shù)序列 即,變化時(shí)，依次求解各個(gè) 所對(duì)應(yīng)的極小化問題， 得到的極小點(diǎn)序列 將逐步逼近于原問題的最優(yōu)解，而且一般情況下該極小 點(diǎn)序列式由可行域外向可行域邊界逼近的。,對(duì)

4、于等式約束優(yōu)化問題,按同樣的形式構(gòu)造外點(diǎn)懲罰函數(shù) 可見，當(dāng)?shù)c(diǎn)在可行域上，懲罰項(xiàng)為零（因 ） 懲罰數(shù)值不受到懲罰；若迭代點(diǎn)在非可行域，懲罰項(xiàng)就顯 示其懲罰作用。由于懲罰數(shù)中的懲罰項(xiàng)所賦的懲罰因子 是一個(gè)遞增的正項(xiàng)數(shù)列，隨著迭代次數(shù)增加， 值也 越來越大，迫使所求迭代點(diǎn) 向原約束優(yōu)化問題的最 優(yōu)解逼近。,綜述,綜合上述兩種情況，可以得到一般的約束優(yōu)化問題的外點(diǎn)懲罰函數(shù)的形式為 外點(diǎn)法是通過對(duì)非可行點(diǎn)上的函數(shù)值加以懲罰，促使迭代點(diǎn)向可行域和最優(yōu)點(diǎn)逼近的算法。因此，初始點(diǎn)可以使可行域的內(nèi)點(diǎn)，也可以是可行域的外點(diǎn)，這種方法即可以處理不等式約束，又可以處理等式約束，可見外點(diǎn)法是一種適應(yīng)性很好的懲罰函數(shù)

5、法。,上述構(gòu)造出的外點(diǎn)懲罰函數(shù)，是經(jīng)過轉(zhuǎn)換的新目標(biāo)函數(shù)，對(duì)它不再存在約束條件，便成為無約束優(yōu)化問題的目標(biāo)函數(shù)，然后可用無約束優(yōu)化方法對(duì)其求解。,外點(diǎn)法的迭代步驟,（1）、給定初始點(diǎn) 、收斂精度 ， ，初始懲罰因 子 和懲罰因子遞增系數(shù) ，置 ； （2）、構(gòu)造懲罰函數(shù) （3）、求解無約束優(yōu)化問題 ，得 ； （4）、進(jìn)行收斂判斷：若滿足 和,則停止迭代，輸出最優(yōu)解 ， ；否則轉(zhuǎn)為下一 步； （5）、取 ， ， 置 轉(zhuǎn)步驟（2）繼續(xù)迭代。,給定 X(0) , r(0)， ，c,外點(diǎn)法的程序方框圖,開始,k 0,用無約束極小化方法求（X，r）的極小點(diǎn)X*（r（k）及極小值（X（k），r（k）,滿足收斂準(zhǔn)則嗎,是,輸出：X*，f（X*）,結(jié)束,r（k+1） c r (k) X