第四章約束最優(yōu)化方法

第四章

約束最優(yōu)化方法簡介上一章介紹了無約束問題的最優(yōu)化方法，但實際問題中，大多數(shù)都是有約束條件的問題.求解帶有約束條件的問題比起無約束問題要困難得多，也復雜得多.在每次迭代時，不僅要使目標函數(shù)值有所下降，而且要使迭代點都落在可行域內(nèi).求解帶有約束的極值問題常用方法有：將約束問題化為一個或一系列的無約束極值問題；將非線性規(guī)劃化為近似的線性規(guī)劃；將復雜問題變?yōu)檩^簡單問題，等等.2§4.1最優(yōu)性條件考慮只含不等式約束條件下求極小值問題的數(shù)學模型：34定義4.1.15定義4.1.2定理4.1.16庫恩-塔克（Kuhn-Tucker）條件庫恩-塔克條件是非線性規(guī)劃領(lǐng)域中的重要理論成果之一，是確定某點為局部最優(yōu)解的一階必要條件.只要是最優(yōu)點（同時是正則點）就必滿足這個條件.但一般來說它不是充分條件，即滿足這個條件的點不一定是最優(yōu)點.但對于凸規(guī)劃，庫恩-塔克條件既是必要條件，也是充分條件.71、只含有不等式約束891011122、同時含有等式與不等式約束1314例：求下列非線性規(guī)劃問題的K-T點.151617181920§4.2可行方向法可以看到，利用K-T條件求極小點是很困難的，因此帶有約束的極值問題仍以迭代算法為主要的求解方法.21221、約束為線性函數(shù)的情形可行下降方向的確定232425262、約束為非線性函數(shù)的情形27282930步長的確定311、當約束為線性函數(shù)時32333435363738例用可行方向法求解3940414243444546472、當約束為非線性函數(shù)時48495051§4.3近似規(guī)劃法近似規(guī)劃是一種線性化的方法，將非線性規(guī)劃線性化，然后解線性規(guī)劃來求原問題的近似最優(yōu)解.525354近似規(guī)劃法的算法步驟：5556例：用近似規(guī)劃法求解下列問題575859606162636465§4.4制約函數(shù)法基本思想：通過構(gòu)造制約函數(shù)，將約束問題轉(zhuǎn)化為一系列無約束問題，進而用無約束最優(yōu)化方法求解，因此該方法也稱為序列無約束最小化技術(shù)，簡記為SUMT（sequentialunconstrainedminimizationtechnique）.常用的制約函數(shù)基本上有兩類：一為懲罰函數(shù)（或稱罰函數(shù)），一為障礙函數(shù).對應(yīng)于這兩種函數(shù)，SUMT有外點法與內(nèi)點法之分.661、外點法基本原理：通過構(gòu)造一個由目標函數(shù)與約束函數(shù)組成的懲罰函數(shù)的辦法，對懲罰函數(shù)實行極小化來實現(xiàn)這一目的.

為了便于說明問題，先考慮只含有不等式約束的問題：676869707172外點法的計算步驟73例：用外點法求解非線性規(guī)劃747576772、內(nèi)點法基本原理：

78與外點法不同的是，內(nèi)點法要求整個迭代過程始終在可行域內(nèi)部進行.初始點也必須選一個嚴格內(nèi)點.然后再在可行域邊界上設(shè)置一道“障礙”，以阻止搜索點到可行域邊界上去，一旦接近可行域邊界時，就要受到很大的懲罰，迫使迭代點始終留在可行域內(nèi)部.與外點法相似，用目標函數(shù)疊加一個懲罰項來構(gòu)成制約函數(shù)，在內(nèi)點法中稱為障礙函數(shù).要求障礙函數(shù)具備這樣的功能：在可行域內(nèi)部離邊界面較遠之處，障礙函數(shù)與目標函數(shù)盡可能地接近，而在接近邊界面時，可以變成很大的值.因此滿足這種要求得障礙函數(shù)其極小值顯然不會在可行域的邊界上達到.也就是說，用障礙函數(shù)來代替原有目標函數(shù)，且在可行域內(nèi)使其極小化.因極小點不在可行域的邊界上，因而這種障礙函數(shù)具有無約束性質(zhì)的極值，可用無約束極值法求解.798081內(nèi)點法的計算步驟8283例：用內(nèi)點法求解非線性規(guī)劃848586初始內(nèi)點的求法878889