《運(yùn)籌學(xué)》 課件 第5章-非線性規(guī)劃

7/16/2024第5章非線性規(guī)劃1CONTENTS目錄7/16/20245.1

概述5.2

非線性規(guī)劃問(wèn)題的解5.3

凸函數(shù)和凸規(guī)劃5.4

下降迭代算法5.5

一維搜索5.6

無(wú)約束極值問(wèn)題的求解算法5.7

約束極值問(wèn)題的最優(yōu)性條件5.8約束極值問(wèn)題的求解算法25.1概述例5.1曲線擬合問(wèn)題

7/16/20245.1.1非線性規(guī)劃問(wèn)題舉例

(1)47/16/20245.1.1非線性規(guī)劃問(wèn)題舉例解:按題意，根據(jù)最小二乘原理，有

5例5.3構(gòu)件設(shè)計(jì)問(wèn)題

7/16/20245.1.1非線性規(guī)劃問(wèn)題舉例67/16/20245.1.1非線性規(guī)劃問(wèn)題舉例

77/16/20245.1.2非線性規(guī)劃數(shù)學(xué)模型非線性規(guī)劃數(shù)學(xué)模型的一般形式是：—可行域

—特別當(dāng)R=En,稱為無(wú)約束優(yōu)化問(wèn)題85.2非線性規(guī)劃問(wèn)題的解7/16/20245.2.1解（極值點(diǎn)）的定義

107/16/20245.2.1解（極值點(diǎn)）的定義

117/16/20245.2.2多元函數(shù)極值點(diǎn)的存在條件

利用可行方向的定義，下面給出局部極小點(diǎn)所滿足的條件。127/16/20245.2.2多元函數(shù)極值點(diǎn)的存在條件

137/16/20245.2.2多元函數(shù)極值點(diǎn)的存在條件

(b)局部極大點(diǎn)(b)局部極大點(diǎn)(c)鞍點(diǎn)

014147/16/20245.2.2多元函數(shù)極值點(diǎn)的存在條件

157/16/20245.2.2多元函數(shù)極值點(diǎn)的存在條件

165.3凸函數(shù)和凸規(guī)劃7/16/20245.3.1凸函數(shù)的定義

若將上述式中的不等號(hào)反向，那么就得到凹函數(shù)（ConcaveFunction）和嚴(yán)格凹函數(shù)（StrictConcaveFunction）的定義。187/16/20245.3.1凸函數(shù)的定義197/16/20245.3.2凸函數(shù)的性質(zhì)

207/16/20245.3.2凸函數(shù)的性質(zhì)

217/16/20245.3.3凸函數(shù)的判定條件

要判定一個(gè)函數(shù)是否是凸函數(shù)，可以直接根據(jù)5.3.1節(jié)的定義。而如果函數(shù)

是可微的，則還有下面兩個(gè)性質(zhì)。227/16/20245.3.4凸規(guī)劃

性質(zhì)5.7凸規(guī)劃的最優(yōu)解具有下述特殊性質(zhì)：（1）如果最優(yōu)解存在，那么最優(yōu)解集為凸集；（2）任何局部最優(yōu)解也就是全局最優(yōu)解；（3）如果目標(biāo)函數(shù)為嚴(yán)格凸函數(shù)且最優(yōu)解存在，

那么最優(yōu)解唯一。235.4下降迭代算法7/16/20245.4.1下降迭代算法

257/16/20245.4.2下降迭代算法的步驟

265.5一維搜索7/16/2024黃金分割法（0.618法）

TheGoldenSectionSearchMethod基本思想：對(duì)稱取點(diǎn)，等比例的縮小區(qū)間，除第一次外，每次只需計(jì)算一次函數(shù)值，可使區(qū)間縮小。b0a0t11t12b1a1f(t11)<f(t12)t22t215.5.1斐波那契法和黃金分割法287/16/20245.5.1斐波那契法和黃金分割法特點(diǎn)：具有相同的區(qū)間縮短率0.618；精度不如Fobonacci分?jǐn)?shù)法；適用于不可微、不連續(xù)函數(shù)，可以先用“成功-失敗”法搜索到一個(gè)包含極小點(diǎn)的區(qū)間。297/16/2024斐波那契法

TheFibonacciSearchMethod問(wèn)題：如何選擇實(shí)驗(yàn)點(diǎn)，計(jì)算n次函數(shù)值能得到多大的區(qū)間縮短率？換句話說(shuō)，計(jì)算n次函數(shù)值能將多大的區(qū)間縮短到1。答案：若對(duì)稱取點(diǎn)，利用上次已有的實(shí)驗(yàn)點(diǎn)的函數(shù)值，計(jì)算n次函數(shù)值可獲得1/Fn區(qū)間縮短率。5.5.1斐波那契法和黃金分割法307/16/20245.5.1斐波那契法和黃金分割法Fibonacci數(shù)列(FibonacciSequence)F0=1,F1=1,F2=2,F3=3,F4=5,……Fk=Fk-1+Fk-2特點(diǎn)：需要預(yù)先確定迭代次數(shù)n;在計(jì)算n次函數(shù)值情況下，該方法獲得最大的區(qū)間縮短率，精度最高；適用于不可微、不連續(xù)函數(shù)。317/16/20245.5.2牛頓法（切線法）基本思想：適合二階連續(xù)可微的函數(shù)，求導(dǎo)數(shù)為0的方程根。特點(diǎn)適用于二階可微函數(shù)；最快的收斂速度，二階收斂速度；初始點(diǎn)要求接近極小點(diǎn)；可與“成功-失敗”法聯(lián)合使用。327/16/2024

5.5.3函數(shù)逼近法基本思想：在極小點(diǎn)附近以插值多項(xiàng)式來(lái)逼近目標(biāo)函數(shù)的一種方法。事實(shí)上，上面的牛頓法就是在附近用一階Taylor展式來(lái)近似目標(biāo)函數(shù)的。函數(shù)逼近法（插值法）335.6無(wú)約束極值問(wèn)題的求解算法7/16/2024最速下降法（梯度法）

TheSteepestdescentmethod（TheGradientMethod））基本思想：以負(fù)梯度方向作為尋優(yōu)方向特點(diǎn)：迭代過(guò)程簡(jiǎn)單，存儲(chǔ)量少，計(jì)算量小；即使是正定二次函數(shù)也不能有限步收斂；相鄰兩次尋優(yōu)方向是垂直的;尋優(yōu)路線呈鋸齒狀（Zig-Zag)，在極小點(diǎn)附近收斂緩慢;5.6.1梯度法357/16/20245.6.1梯度法

36X0P0P1X1X2P2P3X3X*X47/16/20245.6.1梯度法377/16/20245.6.2牛頓法牛頓法（Newton’smethod)

在搜索方向上比梯度法有所改進(jìn)。利用了目標(biāo)函數(shù)在搜索點(diǎn)的梯度（一階導(dǎo)數(shù)）利用了目標(biāo)函數(shù)的二階導(dǎo)數(shù)不但考慮了函數(shù)的梯度，還考慮了梯度的變化趨勢(shì)，收斂速度快。缺點(diǎn)：計(jì)算復(fù)雜，每步迭代都需要計(jì)算目標(biāo)函數(shù)的二階偏導(dǎo)數(shù)（Hessian矩陣）和矩陣的逆。387/16/20245.6.2牛頓法

397/16/20245.6.3擬牛頓法擬牛頓法（Quasi-Newtonmethod）（變尺度法（VariableMetricMethod)）

405.7約束極值問(wèn)題的最優(yōu)性條件7/16/20245.7.1起作用約束

427/16/20245.7.2可行方向和可行下降方向

437/16/20245.7.2可行方向和可行下降方向

447/16/20245.7.3庫(kù)恩-塔克條件庫(kù)恩-塔克（Kuhn-Tucker）條件，簡(jiǎn)稱K-T條件，是非線性規(guī)劃領(lǐng)域中最重要的理論成果之一，是由H.W.Kuhn和A.W.Tucker在1951年發(fā)表的關(guān)于最優(yōu)性條件的論文中提出的。K-T條件是確定某點(diǎn)為局部最優(yōu)解的一階必要條件，只要是最優(yōu)點(diǎn)（同時(shí)是正則點(diǎn)）就必須滿足這個(gè)條件。但一般來(lái)說(shuō)，它不是充分條件，即滿足這個(gè)條件的點(diǎn)不一定是最優(yōu)點(diǎn)。不過(guò)對(duì)于凸規(guī)劃來(lái)說(shuō)，庫(kù)恩-塔克條件既是必要條件，也是充分條件。455.8約束極值問(wèn)題的求解7/16/20245.8.1外點(diǎn)法和內(nèi)點(diǎn)法

外點(diǎn)法（罰函數(shù)法）

外點(diǎn)法和內(nèi)點(diǎn)法都是通過(guò)構(gòu)造某種罰函數(shù)，將有約束的優(yōu)化問(wèn)題轉(zhuǎn)換為一系列無(wú)約束的優(yōu)化問(wèn)題來(lái)進(jìn)行求解，因此稱之為序列無(wú)約束極小化技術(shù)（SequentialUnconstrainedMinimizationTechnique,SUMT）。極限意義下，無(wú)約束優(yōu)化問(wèn)題的解將最終收斂到有約束優(yōu)化問(wèn)題的解。477/16/20245.8.1外點(diǎn)法和內(nèi)點(diǎn)法

內(nèi)點(diǎn)法（障礙函數(shù)法）

和外點(diǎn)法從可行域外部逐漸靠近最優(yōu)解不同，內(nèi)點(diǎn)法的主要思想是：在可行域的邊界上筑起一道很高的“圍墻”，當(dāng)?shù)c(diǎn)從可行域內(nèi)部靠近邊界時(shí)，目標(biāo)函數(shù)陡然增大，以示懲罰，阻止迭代點(diǎn)穿越邊界，因此搜索過(guò)程始終在可行域內(nèi)，每一個(gè)迭代點(diǎn)都是嚴(yán)格可行的。顯然，內(nèi)點(diǎn)法要求優(yōu)化問(wèn)題的可行域