1、2 懲罰函數法基本思想： 通過引入懲罰函數，將求解約束非線性規劃問題轉化為求解一系列無約束非線性規劃問題具體說：根據約束的特點，構造某種懲罰函數，然后把它加到目標函數中去，將約束問題的求解化為一系列無約束問題的求解（準確地說，是將這些無約束問題的極小點依次作為迭代點）第1頁，共52頁。 根據懲罰函數表達式（構造方法的不同），形輔助函數: 外點罰函數法、內點罰函數法、乘子法(外點罰函數法的一種推廣和發展)成不同的罰函數法。我們重點介紹三種：第2頁，共52頁。作輔助函數:考慮如下問題：做法：其中不斷循環求解.接下來求解并不斷改變一、外點懲罰函數法外點法第3頁，共52頁。1. 解析法：(1)構造:其

2、中一般取是很大的正數得最優解(2)求解:(3) 令有即得原問題的最優解.第4頁，共52頁。2.罰函數的特點分析：當不是可行點時，又因是大正數故此很難成為的極小點. 因此，按上策略得到的的極小點應充分靠近可行域，逐漸接近原問題的最優解其中一般取是很大的正數輔助函數:當是可行點時，第5頁，共52頁。例1：求解等式約束問題:分析:圖解法求出最優解下面看用外點法如何求解. 即如何構造懲罰函數？第6頁，共52頁。解：構造罰函數和輔助函數：其中是很大的正數令：得：并且可見正定.又因該點處第7頁，共52頁。令時，有：即：無約束問題的最優解的極限為原問題的最優解處取得極小值.因此在點第8頁，共52頁。例2：用

3、外點罰函數法求解：解：即：因此：作輔助函數第9頁，共52頁。令：得：又因該點處并且可見正定.同理：第10頁，共52頁。處取得極小值.因此在點令得：所以原問題的最優解及最優值分別為：易驗證即滿足約束條件,第11頁，共52頁。3 算法實現對于上述解法中,的選取對問題的求解十分重要,一般策略是取一個趨于無窮大的嚴格遞增正數列得極小點序列然后求解隨著迭代次數(k)的增加，該點列漸漸收斂于原問題的極小點.下面看一下外點法的求解問題的數值算法.第12頁，共52頁。算法實現（數值解法）1) 給定初始點初始懲罰因子允許誤差放大因子否則，令返回 2)3) 若停止運算，取作為近似解令2) 以為初始點，求解得極小點

4、，記作根據經驗, 常常取第13頁，共52頁。收斂性定理定理設的極小點為則會出現以下兩種情況：（1）如果存在某個滿足則結束運算;無窮點列（2）如果上述情況不發生, 若則這時就得到一個第14頁，共52頁。4 注意事項：(1) 用上述方法得到得往往不滿足約束條件,即從可行域外部趨向于的因此叫外罰函數法因此，上述算法（數值解法）又稱SUMT外點法(2)該方法是通過求解一系列無約束最優化問題來求解約束最優化問題的方法，這又被稱為序列無約束極小化技術SUMT.(Sequential Unconstrained Minimization Technique)第15頁，共52頁。5 算法評價（優缺點）(1)若

5、有了求解無約束問題的好算法，則利用外罰函數法求解約束問題很方便(2)每個近似解可能不是可行解，這是某些實際問題所無法接受的內點罰函數法可以解決而(3)理論上已證明取越大越好，越大將造成增廣目標函數的Hesse陣條件數越大，趨于病態，給無約束問題求解增加很大困難，甚至無法求解乘子法可解決這個問題第16頁，共52頁。二、內點罰函數法(碰壁函數法)內點法基本思想:極小點得新的可行點,注意：該方法只適合于不等式約束問題，并且要求可行域的內點集非空，不能包含孤立點或孤立線段.直觀看來,而且中的點可以任意接近于的任一點.從一個可行點出發,通過求輔助函數即在可行點之間進行迭代,使迭代點逐漸靠近或收斂于最優點

6、.最終第17頁，共52頁。懲罰策略：在可行域的邊界上筑起一道很高的“圍墻”,當迭代點靠近可行域的邊界時，目標函數值陡然增大,這相當于對它進行懲罰，從而阻止迭代點穿越邊界，這樣就可以把最優解“擋”在可行域內了其中：定義懲罰項(碰壁項)函數滿足:作輔助函數不斷循環求解.接下來求解并不斷改變第18頁，共52頁。1. 解法：(1)構造:得最優解(2)求解:(3) 令有即得原問題的（近似）最優解.或其中：第19頁，共52頁。2 罰函數的特點構造：其中：或分析：為可行域的內點時，為有限正數，幾乎不受懲罰；接近邊界時，趨于無窮大，施以很重的懲罰；這樣迫使極小點落在可行域內，逐漸逼近極小點第20頁，共52頁。

7、例3：用內點罰函數法求解：令：解：作輔助函數第21頁，共52頁。所以令有：再注意到可驗證該點處的海森矩陣正定,所以是的極小點.第22頁，共52頁。3. 算法實現Step2:以為初始點求無約束問題：得最優解,記作Step3:若則停；否則轉Step4Step4:令轉 Step2.Step1:給出(要求是可行點)，罰因子縮小系數令第23頁，共52頁。例4：用SUMT內點法求解：取迭代結果見下表：注: 在求解無約束問題時,要注意限制一維搜索的初始區間, 即保證迭代點始終在可行域之內.在本問題中, 如果對一維搜索的初始區間不加限制, 函數值會趨于負無窮.第24頁，共52頁。10(2.0402,3.162

8、3)12.529012.77551(1.1473,0.3162)3.61650.99510.1(1.0488,0.1000)2.96670.30490.01(1.0157,0.0316)2.76160.09530.001(1.0016,0.0316)2.70460.0941第25頁，共52頁。收斂性定理定理任給初始可行點，記由上述若則SUMT內點罰函數法產生的點列為第26頁，共52頁。4. 注意事項1）初始點x0的選取 使用內點法時，初始點應選擇一個離約束邊界較遠的可行點。如太靠近某一約束邊界，構造的懲罰函數可能由于障礙項的值很大而變得畸形，使求解無約束優化問題發生困難.2）懲罰因子初值r0的

9、選取 懲罰因子的初值應適當，否則會影響迭代計算的正常進行。一般而言，太大，將增加迭代次數；太小，會使懲罰函數的性態變壞，甚至難以收斂到極值點。無一般性的有效方法。對于不同的問題，都要經過多次試算，才能決定一個適當 r0第27頁，共52頁。 3) 懲罰因子的縮減系數c的選取 在構造序列懲罰函數時，懲罰因子r是一個逐次遞減到0的數列，相鄰兩次迭代的懲罰因子的關系為 : 式中的c稱為懲罰因子的縮減系數，c為小于1的正數。一般的看法是，c值的大小在迭代過程中不起決定性作用，通常的取值范圍在0.10.7之間。4). 由于無約束優化問題的解法目前已經有許多很有效的算法，如DFP算法，BFGS法等，所以在求

10、解一些復雜的約束優化問題時，工程技術人員一般樂于采用內點罰函數法。此方法簡單、易懂。第28頁，共52頁。5). 盡管外點法和內點法目前都已被廣泛應用，但算法中懲罰因子的選取對收斂速度的影響比較大。懲罰因子的增大（外點法）與縮小（內點）使得問題的求解變得很困難，有時甚至會使增廣目標函數趨于病態。一些學者對之分別提出了混合罰函數法、乘子法。進行改進， 針對罰函數法這些固有的弱點，第29頁，共52頁。 把外點罰函數與內點罰函數結合起來，構造新的罰函數. 三、 混合懲罰函數法1. 基本思想：約束,設當前迭代點為用內點法來構造碰壁項對于滿足的那些不等式對于不滿足的那些不等式約束和等式約束,按外點法構造懲

11、罰項即定義混合罰函數為：第30頁，共52頁。構造新的輔助函數其中：第31頁，共52頁。2. 算法實現Step2:以為初始點求無約束問題：得最優解Step3:若則停；否則轉Step4Step4:令轉 Step2.Step1:給出誤差精度參數縮小系數令第32頁，共52頁。 乘子法是由Powell和Hestenes于1969年彼此獨立對等式約束的優化問題首次提出來的。四、 乘子法廣義乘子法 1973年，Rockafellar將其推廣到不等式約束的優化問題，成為求解約束優化問題的一類重要而有效的方法。 后來，D. A. Bertsekas 對乘子法做了系統的論述與理論分析。與此同時，一些學者給出了乘子

12、法的Fortran程序，使乘子法得到廣泛的應用。第33頁，共52頁。 把外點罰函數與Lagrange函數結合起來，構造出更合適的新目標函數，使得在罰因子適當大的情況下，借助于Lagrange乘子就能逐步達到原約束問題的最優解。基本思想： 由于這種方法要借助于Lagrange乘子的迭代進行求解而又區別于經典的Lagrange乘子法，故稱為廣義乘子法。 第34頁，共52頁。1. 等式約束問題的乘子法(Hestenes乘子法)其中和二階連續可微設為Lagrange乘子向量，則對應Lagrange 函數為：設是的極小點， 是最優的乘子向量 則(1)可等價為：第35頁，共52頁。啟發：采用外點罰函數法構

13、造：可以證明：適當大時，極小點是但事先是未知的，怎么辦？用迭代法求出以上就是乘子法的基本思想迭代公式為:并求解下面考慮在求的同時,第36頁，共52頁。依據：給定設對應的無約束問題即的最優解為迭代公式為:則根據最優解的必要條件知又因適當大時，所以適當大時，第37頁，共52頁。對照以上兩式，而在處，由K-T條件得有于是迭代公式取為:所以適當大時，第38頁，共52頁。定理4：設迭代什么時間終止呢？第39頁，共52頁。第40頁，共52頁。等式約束的乘子法Step2:以為初始點求無約束問題：得Step3:若則停；否則轉Step4.Step4:若說明收斂速度還不錯，轉Step5;否則，令轉Step5;St

14、ep5:令轉Step2;Step1:給出初始值及放大系數衡量標準第41頁，共52頁。例5：用乘子法求解：解：定義增廣Lagrange函數如下取用解析法解可見因此還需迭代下去.第42頁，共52頁。按公式修正乘子可見, 即分別是所求非線性規劃的最優乘子和最優解.接下來再解得得：如此繼續. 一般地, 在第k次迭代時,求解第43頁，共52頁。2*.等式約束問題的乘子法(Powell乘子法)Powell在1969年與Hestenes幾乎同時，又提出了一種類似的乘子方法：他考慮含有兩組參數的罰函數：第44頁，共52頁。可見，Powell法是一種比Hestenes的方法更廣泛一些的乘子法，但兩者的出發點不同。Powell法基于下面的事實。定理4：第45頁，共52頁。由定理4可知,第46頁，共52頁。3. 不等式約束的乘子法(Rockafellar的乘子法)對不等式約束問題,引進輔助變量上面的問題轉化為下面等式約束問題,接下來定義其增廣Lagrange函數：并求其極小.第47頁，共52頁。代入增廣的目標函數，有：由于的取值必滿足：是引入的變量，可以證明，為使取得極小，接下來就可用求解等式約束情況的方法進行求解了.相應地, 乘子的迭代公式為：第48頁，共52頁。4. 一般約束情形的乘子法 對于一般約束問題,只要綜合等式約束和