運(yùn)籌學(xué)非線性規(guī)劃

1、第三章 非線性規(guī)劃,請回顧線性規(guī)劃: ,其目標(biāo)與約束函數(shù)均為線性的。線性規(guī)劃具有相對完美的理論與方法，應(yīng)用也很廣泛，但它終究不能窮盡各種優(yōu)化問題，因?yàn)槭澜缡欠蔷€性的。 非線性規(guī)劃（Nonlinear Programming）研究具有非線性構(gòu)成函數(shù)的優(yōu)化問題，是運(yùn)籌學(xué)中相對活躍的重要研究分支。,第一節(jié) 基本概念,一、非線性規(guī)劃問題與模型,⑵投資決策問題,2

2、.模型,二 、模型的解及相關(guān)概念,1.可行解與最優(yōu)解,★可行解：約束集D中的X。,★最優(yōu)解：如果有 ，對于任意的 ， 都有 ，則稱 為（NLP）的最優(yōu) 解，也稱為全局最小值點(diǎn)。,★局部最優(yōu)解：如果對于 ，使得在 的鄰 域

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

4、 在 點(diǎn)的二階泰勒展開式,解:,3.極值的條件,對于無約束極值問題，可以利用微積分的知識給出局部極值點(diǎn)的條件。將n(n>1)元函數(shù) 與一元函數(shù) 的極值條件加以對比并歸納如下：,例3：求 的極小值點(diǎn),解,4.凸規(guī)劃

5、,注：判斷一個(gè)可導(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ù)，

6、不等式約束函數(shù) 為凹函數(shù)，等式約束函數(shù) 為仿射函數(shù)，則稱（NLP）是一個(gè)凸規(guī)劃。,例4：判斷下面的非線性規(guī)劃是否為凸規(guī)劃,標(biāo)準(zhǔn)化,計(jì)算,第二節(jié) 無約束極值問題,★一般模型：,★求解（f(X)可微）：應(yīng)用極值條件求解，往往得到一個(gè)非線 性的方程組，求解十分困難。因此，求 解無約束問題一般 采用迭代法，稱

7、為下降類算法。,一、下降類算法的基本步驟與算法收斂性,1.基本思想,,,,,,,,2.基本步驟,(1),(2),(3),(4),注：不同的搜索方向，就形成了不同的算法，不 同的算法所產(chǎn)生的點(diǎn)列收斂于最優(yōu)解的速度 也不一樣。,3.收斂性,衡量標(biāo)準(zhǔn)：,①,②,③,二階收斂>超線性收斂>線性收斂,二、一維搜索,1.分?jǐn)?shù)法（斐波那契法）,,⑴基本思想,怎樣在區(qū)間中取點(diǎn)最好？,,⑵基本概念,⑶步驟,①,

8、②,③,④,例5：,2. 0.618法,★區(qū)別：每次取點(diǎn)得比例是定值0.168，即每次區(qū)間內(nèi)兩 點(diǎn)得位置均在區(qū)間相對長度得0.328和0.168處。,★特點(diǎn)：簡單，更易于應(yīng)用； 效果也比較好。,3.近似最佳步長公式,例6：,三、梯度法和共軛梯度法,1.梯度法,★一般步驟,(1),(2),(3),(4),例7:,上例中，目標(biāo)函數(shù)是同心圓族。無論初始點(diǎn)選在何處，在該點(diǎn)的負(fù)梯

9、度方向總是指向圓心，而圓心就是極小點(diǎn)，故沿負(fù)梯度方向搜索一步便可得極小點(diǎn)。,但對于一般的函數(shù)，若每次迭代均采用負(fù)梯度方向，則由于這些方向是彼此正交的，很可能形成開頭幾步下降較快，但后來便產(chǎn)生直角鋸齒狀的“拉鋸”現(xiàn)象，收斂速度很慢。可以證明，梯度法是線性收斂的。,注：,2.共軛梯度法,⑴基本概念,★,★,這一性質(zhì)說明采用共軛方向作為搜索方向，對二次函數(shù)求極小可以有限步終止。由此可構(gòu)造二次函數(shù)的共軛方向算法。共軛方向算法用于二次函數(shù)時(shí)均具有

10、二次終止性。由于一般函數(shù)在一點(diǎn)附近的性質(zhì)往往與二次函數(shù)很相似，因此共軛方向算法一般也可用于其他非線性函數(shù)，并且至少是線性收斂的。,⑵一般步驟,①,③,②,④,⑤,例8：,四、牛頓法與擬牛頓法,1.牛頓法,⑴牛頓方向,⑵一般步驟,①,③,④,②,當(dāng)一維搜索是精確的，牛頓法為二階收斂。,缺點(diǎn)：,2.擬牛頓法,DFP方法的一般步驟,①,③,②,④,例9:,第三節(jié) 約束極值問題,★一般模型,1.基本概念和性質(zhì),⑴起作用約束,⑵可行下降方向,

11、⑶可行下降方向的條件,2.最優(yōu)性條件（K-T條件）,定理 (K-T條件),例10：利用K－T條件求解下面的非線性規(guī)劃,為解此方程組，可分幾種情況考慮：,例11:考慮非線性規(guī)劃并驗(yàn)證它為凸規(guī)劃，用K－T條件求解,計(jì)算目標(biāo)和約束函數(shù)的海賽陣,3.二次規(guī)劃,★一般模型,思考:能否在此基礎(chǔ)上構(gòu)想基于線性規(guī)劃求解的方法?,例12: 求解二次規(guī)劃,解,求得的結(jié)果是：,4.罰函數(shù),外點(diǎn)法的關(guān)鍵是基于（NLP）構(gòu)造一個(gè)新的目標(biāo)函數(shù)P（X，M），稱