第三章非線性規(guī)劃2

第三章

非線性規(guī)劃請回顧線性規(guī)劃:,其目標(biāo)與約束函數(shù)均為線性的。線性規(guī)劃具有相對完美的理論與方法，應(yīng)用也很廣泛，但它終究不能窮盡各種優(yōu)化問題，因為世界是非線性的。

非線性規(guī)劃（NonlinearProgramming）研究具有非線性構(gòu)成函數(shù)的優(yōu)化問題，是運籌學(xué)中相對活躍的重要研究分支。第一節(jié)基本概念一、非線性規(guī)劃問題與模型1.問題⑴生產(chǎn)計劃問題x:產(chǎn)量;P(x):價格;C(x)成本⑵投資決策問題

2.模型

二、模型的解及相關(guān)概念1.可行解與最優(yōu)解★可行解：約束集D中的X。

★最優(yōu)解：如果有，對于任意的，都有，則稱為（NLP）的最優(yōu)解，也稱為全局最小值點。

★局部最優(yōu)解：如果對于，使得在的鄰域中的任意都有，則稱為（NLP）的局部最優(yōu)解，也稱為局部最小值點。例1：考慮非線性問題如果約束改為呢？2.梯度、海塞陣與泰勒公式

★梯度★海塞陣★泰勒公式例2：寫出在點的二階泰勒展開式3.極值的條件對于無約束極值問題，可以利用微積分的知識給出局部極值點的條件。將n(n>1)元函數(shù)與一元函數(shù)的極值條件加以對比并歸納如下：

充分條件

必要條件例3：求的極小值點4.凸規(guī)劃★凸函數(shù)：f(X)是定義在凸集D上且滿足對任意有下式成立的函數(shù)：若不等式中嚴(yán)格不等號成立，則稱f(X)為嚴(yán)格凸函數(shù)注：判斷一個可導(dǎo)函數(shù)f(X)是否是凸函數(shù)的方法一元函數(shù)f(x)：二階導(dǎo)大于等于零;多元函數(shù)f(X)：海塞陣半正定。★凸規(guī)劃性質(zhì)：★約束集是凸集；★最優(yōu)解集是凸集；★任何局部最優(yōu)解也是全局最優(yōu)解；★若目標(biāo)函數(shù)是嚴(yán)格凸函數(shù)，且最優(yōu)解存在，則其最優(yōu)解是唯一的。在非線性規(guī)劃模型（NLP）中，若目標(biāo)函數(shù)f（X）是凸函數(shù)，不等式約束函數(shù)為凹函數(shù)，等式約束函數(shù)為仿射函數(shù)，則稱（NLP）是一個凸規(guī)劃。例4：判斷下面的非線性規(guī)劃是否為凸規(guī)劃標(biāo)準(zhǔn)化計算第二節(jié)無約束極值問題★求解（f(X)可微）：應(yīng)用極值條件求解，往往得到一個非線性的方程組，求解十分困難。因此，求解無約束問題一般采用迭代法，稱為下降類算法。一、下降類算法的基本步驟與算法收斂性1.基本思想2.基本步驟(1)(2)(3)(4)注：不同的搜索方向，就形成了不同的算法，不同的算法所產(chǎn)生的點列收斂于最優(yōu)解的速度也不一樣。3.收斂性衡量標(biāo)準(zhǔn)：①二階收斂>超線性收斂>線性收斂二、一維搜索1.分?jǐn)?shù)法（斐波那契法）⑴基本思想怎樣在區(qū)間中取點最好？⑵基本概念★滿足絕對精度：★滿足相對精度：★斐波那契數(shù)：553421138532119876543210⑶步驟①②③④例5：2.0.618法★區(qū)別：每次取點得比例是定值0.168，即每次區(qū)間內(nèi)兩點得位置均在區(qū)間相對長度得0.328和0.168處?！锾攸c：簡單，更易于應(yīng)用；效果也比較好。3.近似最佳步長公式例6：三、梯度法和共軛梯度法1.梯度法

★一般步驟例7:上例中，目標(biāo)函數(shù)是同心圓族。無論初始點選在何處，在該點的負(fù)梯度方向總是指向圓心，而圓心就是極小點，故沿負(fù)梯度方向搜索一步便可得極小點。但對于一般的函數(shù)，若每次迭代均采用負(fù)梯度方向，則由于這些方向是彼此正交的，很可能形成開頭幾步下降較快，但后來便產(chǎn)生直角鋸齒狀的“拉鋸”現(xiàn)象，收斂速度很慢。可以證明，梯度法是線性收斂的。注：2.共軛梯度法⑴基本概念★★這一性質(zhì)說明采用共軛方向作為搜索方向，對二次函數(shù)求極小可以有限步終止。由此可構(gòu)造二次函數(shù)的共軛方向算法。共軛方向算法用于二次函數(shù)時均具有二次終止性。由于一般函數(shù)在一點附近的性質(zhì)往往與二次函數(shù)很相似，因此共軛方向算法一般也可用于其他非線性函數(shù)，并且至少是線性收斂的。⑵一般步驟①③②

④

⑤例8：四、牛頓法與擬牛頓法1.牛頓法⑴牛頓方向⑵一般步驟①

③

④②當(dāng)一維搜索是精確的，牛頓法為二階收斂。缺點：★計算海賽陣的逆的工作量很大?！镆骹(X)的二階導(dǎo)存在且海賽陣是正定的(以保證H的逆陣存在和算法是下降的;改進(jìn)：構(gòu)造一個矩陣代替牛頓方向中的，使?jié)M足：★正定★只用到f(X)的一階導(dǎo)信息★隨著k的增加，充分接近于稱為尺度陣。由于它每次都在變，故稱以代替牛頓法中的的算法為變尺度法。2.擬牛頓法★擬牛頓法是尺度陣滿足的一類變尺度法;★擬牛頓法一般是超線性收斂的;★DFP是一種著名的擬牛頓法;★當(dāng)f(X)為二次函數(shù)時，DFP法是共扼方向法，且具有二次終止性。DFP方法的一般步驟①③②④例9:第三節(jié)約束極值問題★一般模型1.基本概念和性質(zhì)⑴起作用約束⑵可行下降方向⑶可行下降方向的條件2.最優(yōu)性條件（K-T條件）定理(K-T條件)例10：利用K－T條件求解下面的非線性規(guī)劃為解此方程組，可分幾種情況考慮：例11:考慮非線性規(guī)劃并驗證它為凸規(guī)劃，用K－T條件求解計算目標(biāo)和約束函數(shù)的海賽陣3.二次規(guī)劃★一般模型思考:能否在此基礎(chǔ)上構(gòu)想基于線性規(guī)劃求解的方法?例12:求解二次規(guī)劃求得的結(jié)果是：4.罰函數(shù)基本思想：將約束與目標(biāo)組合在一起，化為無約束極值問題求解。★內(nèi)點法：從可行域的內(nèi)部逐步逼近最優(yōu)解。★外點法：從可行域的外部逐步逼近最優(yōu)解?！锿恻c法的關(guān)鍵是基于（NLP）構(gòu)造一個新的目