約束優化方法約束優化方法直接法：間接法：算法簡單，對目標函數和約束函數無特殊要求；計算量大，不適用維數較高的問題；適用只含不等式約束的優化問題

這些算法一般比較復雜；但它們可以采用計算效率高、穩定性好的無約束優化方法；可用于求解高維的優化問題將約束非線性規劃轉換為一系列無約束優化問題用無約束優化方法來求解，逐漸逼近約束非線性規劃的最優解．坐標輪換法、復合形法1整體概述THEFIRSTPARTOFTHEOVERALLOVERVIEW,PLEASESUMMARIZETHECONTENT第一部分2懲罰函數法----一種使用廣泛、有效的間接法借助罰函數將約束非線性規劃轉化為一系列無約束問題，通過求解無約束問題來求解約束非線性規劃，所以也稱為序列無約束極小化技術(sequentailunconstrainedminimizationtechnique,簡稱SUMT)根據約束特點（等式或不等式）構造某種罰函數p(x)，把它加到目標函數中去，將約束非線性規劃轉化為一系列無約束問題：基本思想：罰因子懲罰函數懲罰項3懲罰函數法----一種使用廣泛、有效的間接法基本思想：這種懲罰策略，對于在無約束的求解過程中企圖違反約束的迭代點給予很大的目標函數值，迫使無約束問題的極小點或者無限地向可行域D靠近，或者一直保持在可行域D內移動，直到收斂到原來約束最優化問題的極小點。罰因子懲罰函數懲罰項4懲罰函數法外點法：

對違反約束的點在目標函數中加入相應的懲罰，可行點不予懲罰，這種方法的迭代點一般在可行域D的外部移動；罰因子按照懲罰函數的構成方式，懲罰函數法分為3種：懲罰函數5懲罰函數法內點法:對從內部企圖穿越可行域D邊界的點在目標函數中加入障礙，距邊界越近，障礙越大，在邊界上給予無窮大的障礙，從而保證迭代點一直在可行域內部移動；罰因子按照懲罰函數的構成方式，懲罰函數法分為3種：懲罰函數混合法：將外點法和內點法結合。6幾何解釋外點罰函數法求曲線y=f(x)在D內的最小點抬高到一定程度后，此曲線的無約束極小點就是原來函數在D內的最小點改造曲線，使其在D內保持不變，在D外將曲線逐步抬高，可行點不懲罰,違反約束的點在目標函數中加入懲罰，7外點罰函數法罰函數p(x)應滿足的性質(1)p(x)連續(2)(3)此時，當時，不受懲罰；當時，很大，受到懲罰。外點法的基本思想：對違反約束的點在目標函數中加入相應的懲罰，對可行點不予懲罰。性質：若是的最優解，且，則也是的最優解。證明：因為是的最優解，所以又故所以8外點罰函數法性質：若是的最優解，且，則也是的最優解。一般來說，僅在M充分大時才成立，但在實際計算中，過大的M會造成無約束問題的求解困難，因此取一個遞增且趨于的罰因子序列，即然后求解一系列無約束問題怎么構造？已知，約束優化可求解9外點罰函數法罰函數p(x)應滿足的性質(1)p(x)連續(2)(3)罰函數p(x)的構造給出了罰函數p(x)的一個形式gihj連續，p(x)也連續10外點罰函數法----算法步驟步驟1：給定初始點，初始罰因子(可取),精度

步驟2：以初始點，求解無約束優化問題

得到極小點，記為，其中步驟3：若，則停止計算，得到近似極小點；

用解析法求駐點或者

用無約束優化方法求解常取

否則，令，置k:=k+1，轉步驟2。11外點罰函數法最優解記為因為時，故12引理：對于由外點法產生的點列總有：外點罰函數法----算法收斂性分析證明：(1)對于由外點法產生的點列總有：13引理：對于由外點法產生的點列總有：外點罰函數法----算法收斂性分析證明：(2)14引理：對于由外點法產生的點列總有：外點罰函數法----算法收斂性分析證明：(3)又由(2)所以15定理：設約束問題(1)和無約束問題(2)的最優解為和取序列且則由外點法產生的點列的任何聚點必是(1)的最優解。證明：不妨設因為和分別為(1)和(2)的最優解，且所以有：外點罰函數法----算法收斂性分析16外點罰函數法----算法收斂性分析為單調有界序列，設其極限為為可行解。為最優解；即為(1)的最優解．又為單調有界序列，設其極限為故而所以故又17例1：用外點罰函數法求解如下優化問題：

外點罰函數法----算例解：問題只有不等式約束，對應的罰函數為:

下面用解析法求F(x,Mk)的駐點，令

18當時，

，舍去該點；

當時，由

，得到

所以

，令

，得到

19例2：用外點罰函數法求解如下優化問題：

外點罰函數法----算例解：問題只有等式約束，對應的罰函數為:

下面用解析法求F(x,Mk)的駐點，令

20外點罰函數法----算例從中解得

令

，得到

21外點罰函數法----算法步驟步驟1：給定初始點，初始罰因子(可取),精度

步驟2：以初始點，求解無約束優化問題

得到極小點，記為，其中步驟3：若，則停止計算，得到近似極小點；

否則，令，置k:=k+1，轉步驟2。

22外點罰函數法----特點(3)初始罰因子要選擇得當，否則會影響迭代計算的正常進行，

太小，將增加迭代的次數；太大，會使懲罰函數的性態變壞，甚至難以收斂到極值點許多計算表明，取

常常可以取得滿意的效果；按經驗公式計算

值(1)初始點可以任選(2)對等式約束和不等式約束均可適用23通常取c=[5,10]。外點罰函數法----特點(4)罰因子Mk遞增(→∞)，,遞增系數c,c>1(5)如果有了求解無約束問題的好算法，利用外罰函數法求解約束問題很方便。(6)每個近似解往往不是可行解，這是某些實際問題所無法接受的。內罰函數法可以解決(7)外點法中要求而太大將造成增廣目標函數的Hesse陣條件數越大，趨于病態，給無約束問題求解增加很大困難，甚至無法求解。乘子法可解決這個問題24外點罰函數法----缺點(1)如果在可行域外目標函數f(x)的性質復雜或者沒有定義時，外點法就不適用了；內點罰函數法可解決這兩個問題(2)每個近似解往往不是可行解，這是某些實際問題所能接受的。

如果要求在迭代中產生的點列，必須滿足某些約束條件時，方法也失效，為克服上述缺點，人們又提出了內點罰函數法。25基本思想迭代點在可行域的內部移動，內點法只適合于不等式約束問題內點法要求迭代點在可行域內部移動，初始點必須是內點，可行域的內部必須是非空的，內點法只能處理不等式約束，等式約束構成的集合內部為空.內點罰函數法內點罰函數法又稱為障礙函數法從而將最優解“擋”在可行域內。距邊界越近障礙越大，這相當于在可行域的邊界上筑起一道很高的“圍墻”，阻止迭代點穿越邊界，懲罰(加入障礙)，并對接近可行域邊界的點施加26內點罰函數法保持迭代點在可行域內部，B(x)滿足下面的條件：(1)B(x)在可行域D的內部連續；因子，稱為障礙函數。受到懲罰幾乎不受懲罰內點法的基本思想：對從內部企圖穿越可行域D邊界的點在目標函數中加入相應的障礙，從而保證迭代點一直在可行域內部移動；在可行域內部遠離可行域邊界時，很小，此時當x趨向可行域的邊界時，，且很大；的取值近似原目標函數f(x)；(2)其中是很小的正數，稱為障礙距邊界越近，障礙越大，在邊界上給予無窮大的障礙，不好求太小，27內點罰函數法B(x)滿足下面的條件：(1)B(x)在可行域D的內部連續；在可行域內部遠離可行域邊界時，很小，此時當x趨向可行域的邊界時，，且很大；的取值近似原目標函數f(x)；(2)28內點罰函數法障礙函數B(x)的構造的兩種常用形式如下：（1）（2）--------------倒數障礙函數

--------------對數障礙函數

可通過求解下面的約束優化得到約束優化(3)的最優解。rk越小，問題(4)的最優解越接近(3)的最優解。29內點罰函數法從形式上看，(4)仍是一個約束優化問題；從計算的觀點看，(4)是一個無約束優化問題。在可行域的邊界附近，(4)的目標函數值趨于，只要從可行域D的任何一個內點開始迭代，并注意控制一維搜索的步長，就可使得迭代點不越過可行域，因此不必直接地與約束問題打交道。30內點罰函數法----算法步驟步驟1：給定初始點，初始罰因子(可取),

精度

步驟2：以初始點，求解無約束優化問題

得到極小點，記為，其中步驟3：若，則停止計算，得到近似極小點；

否則，令，置k:=k+1，轉步驟2。

或者31引理：對于由內點罰函數法產生的點列總有：內點罰函數法----收斂性分析收斂性定理：設可行域的內點集非空，在上存在極小點對嚴格單減正數列且則由內點法產生的點列的任何聚點是約束問題(3)的最優解。32例1：用內點法求解下面的問題解：構造障礙函數：用解析法求函數F的極小點求解得內點罰函數法----算例不滿足約束條件，舍去。33無約束極值點為：即得到原問題的極小點為內點罰函數法----算例34例1：用內點法求解下面的問題解：構造障礙函數：用解析法求函數F的極小點內點罰函數法----算例35例2：用內點法求解：解：構造障礙函數內點罰函數法----算例用解析法求函數F的極小點36解得當時，注：一般的最優解很難用解析法求出，需采用無約束最優化方法．即得到原問題的極小點為內點罰函數法----算例37例2：用內點法求解：解：構造障礙函數內點罰函數法----算例用解析法求函數F的極小點381)

初始點x0的選取使用內點法時，初始點應選擇一個離約束邊界較遠的可行點。如果太靠近某一約束邊界，求解無約束優化問題時可能會發生困難。2)

初始罰因子r1的選取懲罰因子的初值應適當，否則會影響迭代計算的正常進行一般而言，太大，將增加迭代次數；太小，會使懲罰函數的性態變壞，甚至難以收斂到極值點。對于不同的問題，都要經過多次試算，才能決定一個適當r1內點罰函數法----幾點說明39

3)罰因子的縮減系數c的選取在構造序列懲罰函數時，罰因子r是一個逐次遞減到0的數列，相鄰兩次迭代的懲罰因子的關系為:一般的看法是，c值的大小在迭代過程中不起決定性作用，通常的取值范圍在0.1~0.7之間。由于無約束優化問題的解法目前已經有許多很有效的算法，如DFP算法，BFGS法等，所以在求解復雜的約束優化問題時，工程技術人員一般樂于采用罰函數法。此方法簡單、易懂。內點罰函數法----幾點說明405)為求解約束優化問題，需要求解一系列的無約束優化問題，計算量大，且罰因子的選取方法對收斂速度的影響比較大。并且罰因子的增大（外點法）與縮小（內點法）使得問題的求解變得很困難。常常會使增廣目標函數趨于病態。這是罰函數法固有的弱點，使其使用受到限制。這正是乘子法所要解決的問題。內點罰函數法----幾點說明內點法適于解僅含不等式約束問題，并且每次迭代的點都是可行點。這是設計員所希望的。但要求初始點為可行域的內點，需要浪費相當的工作量。結合外點法的優缺點，人們將內點法和外點法結合起來使用，得到所謂的混合罰函數法。41其中：對于一般約束問題(1)，引進增廣目標函數混合罰函數法任意給定初始點后，對等式約束和不被初始點滿足的不等式約束采用外點法，而對被初始點滿足的不等式約束采用內點法。42混合罰函數法----算法步驟步驟1：任意給定初始點，初始罰因子(可取),精度

步驟2：以初始點，求解無約束優化問題

得到極小點，記為步驟3：若且則停止計算，得到近似極小

點；否則，令，置k:=k+1，轉步驟2。

混合法具有內點法的特點，迭代過程在可行域之內進行，參數的選擇同內點法。43內點法和外點法的簡單比較初始點必須在可行域的內部初始點可以任選對等式約束和不等式約束均可適用適于僅具有不等式約束的數學模型僅最優解為可行設計方案迭代過程中各個點均為可行設計方案一般收斂較快一般收斂較慢迭代中xk不在可行域D中迭代中xk在可行域D中罰因子為遞增，遞增率c，有c>1罰因子為遞減，遞減率c，有0<c<1 內點法外點法非凸規劃適用非凸規劃適用44掌握內點法的構造形式、特點:罰函數法的小結掌握外點法的構造形式、特點:能用罰函數法求解簡單約束優化問題45作業P2468.1，8.28.4，8.9，8.1046線性規劃中的三個問題47使用表格形式的單純形方法記，則標準形式等價于1.構造單純形表標準形式的線性規劃標準形式繼續等價于符號寫錯啦！第一個問題48把約束方程的系數置于表中，就得到了所謂的單純形表1列cBTB-1

bB-1b右端m行B-1NIm0xNxBfn-m列m列1列1行-cBT

B-1N+cNT01目標函數值負的判別數基變量的值使用表格形式的單純形方法1.構造單純形表A中存在m階的單位矩陣xBf為了出現判別數，最后1行乘以-1負的目標值判別數第一個問題49使用表格形式的單純形方法記，則標準形式等價于1.構造單純形表標準形式的線性規劃標準形式繼續等價于第一個問題的改正!50把約束方程的系數置于表中，就得到了所謂的單純形表1列cBTB-1

bB-1b右端m行B-1NIm0xNxBfn-m列m列1列1行cBT

B-1N-cNT01目標函數值判別數基變量的值使用表格形式的單純形方法1.構造單純形表A中存在m階的單位矩陣xBf第一個問題的改正!51例3.利用單純形算法求解如下的線性規劃問題。解：

x6

，x7，x5對應的是單位矩陣，可選擇作為基變量，建立單純形表，利用主元消去法，進行迭代。minx6+x7

s.t.x1

+x2

-

x3

+x6

=

2x1-x2

-

x4

+x7

=1x1+x5=3xj≥0,j=1,2,……,7第二個問題：單純性方法的例352xBx1x2x3x4x5x6

x7

11-1