第四章

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

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

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