管理運(yùn)籌學(xué)06非線性規(guī)劃課件

1、第六章 非線性規(guī)劃非線性規(guī)劃問題及其數(shù)學(xué)模型極值問題凸規(guī)劃一維搜索無約束極值問題約束極值問題7/26/202211. 非線性規(guī)劃問題及其數(shù)學(xué)模型非線性規(guī)劃問題舉例： Example1：第82頁例6-1 Example2：第82頁例6-2非線性規(guī)劃問題的數(shù)學(xué)模型非線性規(guī)劃問題的圖示7/26/202221.1 非線性規(guī)劃問題舉例 Example1: 某商店經(jīng)銷A、B兩種產(chǎn)品，售價(jià)分別為20和380元。據(jù)統(tǒng)計(jì)，售出一件A 產(chǎn)品的平均時(shí)間為0.5小時(shí)，而售出一件B 產(chǎn)品的平均時(shí)間與其銷售的數(shù)量成正比，表達(dá)式為1 + 0.2n。若該商店總的營業(yè)時(shí)間為1000小時(shí)，試確定使其營業(yè)額最大的營業(yè)計(jì)劃。 7/2

2、6/202231.1 非線性規(guī)劃問題舉例解 設(shè)x1和x2分別為商店經(jīng)銷A、B兩種產(chǎn)品的件數(shù)，于是有如下數(shù)學(xué)模型： 7/26/202241.1 非線性規(guī)劃問題舉例Example 2: 在層次分析（Analytic Hierarchy Process, 簡記為 AHP）中，為進(jìn)行多屬性的綜合評(píng)價(jià)，需要確定每個(gè)屬性的相對(duì)重要性，即它們的權(quán)重。為此，將各屬性進(jìn)行兩兩比較，從而得出如下判斷矩陣： 7/26/202251.1 非線性規(guī)劃問題舉例 a11 a1nJ= , an1 ann其中： aij是第i個(gè)屬性與第j個(gè)屬性的重要性之比。7/26/202261.1 非線性規(guī)劃問題舉例 現(xiàn)需要從判斷矩陣求出各屬

3、性的權(quán)重，為使求出的權(quán)重向量W在最小二乘意義上能最好地反映判斷矩陣的估計(jì)，由aij=wi/wj可得：7/26/202271.2 非線性規(guī)劃問題的數(shù)學(xué)模型 s.t. 其中 是n維歐氏空間En中的向量點(diǎn)。7/26/202281.2 非線性規(guī)劃問題的數(shù)學(xué)模型 由于， ,“”不等式僅乘“-1”即可轉(zhuǎn)換為“”不等式；因此上述數(shù)學(xué)模型具有一般意義。又因?yàn)榈葍r(jià)于兩個(gè)不等式： ; ,因此非線性規(guī)劃的數(shù)學(xué)模型也可以表示為：7/26/202291.3 非線性規(guī)劃問題的圖示 若令其目標(biāo)函數(shù)f (X)=c,目標(biāo)函數(shù)成為一條曲線或一張曲面；通常稱為等值線或等值面。此例，若設(shè)f (X)=2和f (X)=4可得兩個(gè)圓形等值

4、線，見下圖：7/26/2022101.3 非線性規(guī)劃問題的圖示 由左圖可見,等值線f (X)=2和約束條件直線6-6相切，切點(diǎn)D即為此問題的最優(yōu)解，X*=(3, 3)，其目標(biāo)函數(shù)值 f (X*)=2。 3232066x1x2f(X)=4f(X)=27/26/2022111.3 非線性規(guī)劃問題的圖示 在此例中，約束 對(duì)最優(yōu)解發(fā)生了影響，若以 代替原約束，則非線性規(guī)劃的最優(yōu)解是 ，即圖中的C點(diǎn)，此時(shí) 。由于最優(yōu)點(diǎn)位于可行域的內(nèi)部，故事實(shí)上約束 并未發(fā)揮作用，問題相當(dāng)一個(gè)無約束極值問題。7/26/2022121.3 非線性規(guī)劃問題的圖示 注 線性規(guī)劃存在最優(yōu)解，最優(yōu)解只能在其可行域的邊緣上（特別能在

5、可行域的頂點(diǎn)上）得到；而非線性規(guī)劃的最優(yōu)解（如果存在）則可能在可行域的任意一點(diǎn)上得到。7/26/2022132. 極值問題局部極值與全局極值極值點(diǎn)存在的條件凸函數(shù)和凹函數(shù)凸函數(shù)的性質(zhì)函數(shù)凸性的判定7/26/2022142.1 局部極值與全局極值線性規(guī)劃 最優(yōu)解 全局最優(yōu)解非線性規(guī)劃 局部最優(yōu)解 未必全局最優(yōu)7/26/202215局部極值對(duì)于X-X* 均有不等式 f (X) f (X*) ，則稱 X*為 f (X)在 R上的局部極小點(diǎn)，f (X*)為局部極小值；對(duì)于X-X* f (X*) ，則稱 X*為 f (X)在 R上的嚴(yán)格局部極小點(diǎn)， f (X*)為嚴(yán)格局部極小值；7/26/202216全

6、局極值對(duì)于X,X* R均有不等式 f (X) f (X*) ，則稱 X*為 f (X)在 R上的全局極小點(diǎn)，f (X*)為全局極小值；對(duì)于X,X* R均有不等式f (X) f (X*) ，則稱X*為f (X)在R上的嚴(yán)格全局極小點(diǎn)， f (X*)為嚴(yán)格全局極小值。7/26/2022172.2 極值點(diǎn)存在的條件必要條件 設(shè)R是En上的一個(gè)開集，f (X)在R上有一階連續(xù)偏導(dǎo)數(shù)，且在點(diǎn) 取得局部極值，則必有 或7/26/202218必要條件 為函數(shù) f (X)在 X*點(diǎn)處的梯度。 由數(shù)學(xué)分析可知， 的方向?yàn)閄*點(diǎn)處等值面（等值線）的法線方向，沿這一方向函數(shù)值增加最快，如圖所示。7/26/20221

7、9必要條件 滿足 的點(diǎn)稱為平穩(wěn)點(diǎn)或駐點(diǎn)。極值點(diǎn)一定是駐點(diǎn)；但駐點(diǎn)不一定是極值點(diǎn)。 7/26/202220充分條件充分條件 設(shè)R是En上的一個(gè)開集，f (X)在R上具有二階連續(xù)偏導(dǎo)數(shù)，對(duì)于 ，若 且對(duì)任何非零向量有： 則X*為 f (X)的嚴(yán)格局部極小點(diǎn)。 稱為 f (X)在點(diǎn)X*處的海賽（Hesse）矩陣。 7/26/202221充分條件7/26/202222充分條件（充分條件）等價(jià)于： 如果函數(shù)f (X)在X*點(diǎn)的梯度為零且海賽矩陣正定，則X*為函數(shù)f (X)的嚴(yán)格局部極小點(diǎn)。7/26/2022232.3 凸函數(shù)和凹函數(shù) 設(shè) f (X)為定義在En中某一凸集R上的函數(shù)，若對(duì)于任何實(shí)數(shù)（01）

8、以及R中的任意兩點(diǎn)X(1)和X(2) ，恒有： 則稱 f (X)為定義在R上的凸函數(shù)；若上式為嚴(yán)格不等式，則稱 f (X)為定義在R上的嚴(yán)格凸函數(shù)。改變不等號(hào)的方向，即可得到凹函數(shù)和嚴(yán)格凹函數(shù)的定義。 7/26/202224凸函數(shù)和凹函數(shù)示意圖X(1)X(2)f (X)X凸函數(shù)X(1)X(2)f (X)X凹函數(shù)7/26/202225非凹非凸函數(shù)示意圖f (X(2)f (X(1)X(1) +(1-)X(2)X(1)X(2)f (X)X非凸非凹函數(shù)7/26/2022262.4 凸函數(shù)的性質(zhì)設(shè)f (X)為定義在凸集R上的凸函數(shù)，則對(duì)于任意實(shí)數(shù)0 ,函數(shù) f (X)也是定義在R上的凸函數(shù)。 設(shè)f1 (

9、X)和f 2(X)為定義在凸集R上的兩個(gè)凸函數(shù)，則其和f (X) = f1 (X) + f 2(X)仍然是定義在R上的凸函數(shù)。 設(shè)f (X)為定義在凸集R上的凸函數(shù)，則對(duì)于任意實(shí)數(shù),集合S =X|XR, f (X) 是凸集。7/26/2022272.4 凸函數(shù)的性質(zhì)設(shè)f (X)為定義在凸集R上的凸函數(shù)，則它的任一極小點(diǎn)就是它在R上的最小點(diǎn)（全局極小點(diǎn)）；而且它的極小點(diǎn)形成一個(gè)凸集。設(shè)f (X)為定義在凸集R上的可微凸函數(shù)，若它存在點(diǎn)X*R，使得對(duì)于所有的XR有 f (X *)T (X- X*) 0，則X*是f (X)在R上的最小點(diǎn)（全局極小點(diǎn)）。 7/26/2022282.5 函數(shù)凸性的判定根

10、據(jù)凸函數(shù)的定義進(jìn)行判定； 根據(jù)一階條件進(jìn)行判定；根據(jù)二階條件進(jìn)行判定；7/26/202229一階條件 設(shè)R為En上的開凸集， f (X)在R上具有一階連續(xù)偏導(dǎo)數(shù)，則f (X)為R上的凸函數(shù)的充分必要條件是，對(duì)于屬于R的任意兩個(gè)不同點(diǎn)X(1)和X(2)恒有： 7/26/202230二階條件 設(shè)R為En上的開凸集， f (X)在R上具有二階連續(xù)偏導(dǎo)數(shù)，則 f (X)為R上的凸函數(shù)的充分必要條件是： f (X)的海賽矩陣H(X)在R上處處半正定（ ZTH(X)Z0 ）。7/26/2022313. 凸規(guī)劃凸規(guī)劃的定義下降迭代算法7/26/2022323.1 凸規(guī)劃的定義 考慮非線性規(guī)劃： 假定其中 f

11、 (X)為凸函數(shù)， g j (X)為凹函數(shù)（- g j (X)為凸函數(shù)），這樣的非線性規(guī)劃稱為凸規(guī)劃。7/26/2022333.1 凸規(guī)劃的定義 凸規(guī)劃： 可行域是凸集、局部最優(yōu)即為全局最優(yōu)；若為嚴(yán)格凸函數(shù)，最優(yōu)解若存在必唯一。7/26/2022343.2 下降迭代算法基本思想： 給定一個(gè)初始估計(jì)解X(0)，然后按某種規(guī)則（即算法）找出一個(gè)比X(0)更好的解X(1) ，如此遞推即可得到一個(gè)解的序列X(k) ，若這一解的序列有極限X* ，即 則稱X*為最優(yōu)解。7/26/2022353.2 下降迭代算法基本問題： 遞推步驟的有限性，一般說很難得到精確解，當(dāng)滿足所要求的精度時(shí)即可停止迭代而得到一個(gè)近

12、似解。7/26/2022363.2 下降迭代算法下降算法： 若產(chǎn)生的解序列X(k) 能使目標(biāo)函數(shù)f (X(k)逐步減少，就稱此算法為下降算法。“下降”的要求很容易滿足，因此它包括了很多具體的算法。7/26/2022373.2 下降迭代算法若從 X (k)出發(fā)沿任何方向移動(dòng)都不能使目標(biāo)函數(shù)值下降，則 X (k)是一個(gè)局部極小點(diǎn)；若從 X (k)出發(fā)至少存在一個(gè)方向能使目標(biāo)函數(shù)下降，則可選定某一下降方向 P (k) ，沿這一方向前進(jìn)一步，得到下一個(gè)點(diǎn) X (k+1) 。沿P (k)方向前進(jìn)一步相當(dāng)于在射線 上選定新的點(diǎn) ,其中P (k)為搜索方向， 為步長。7/26/2022383.2 下降迭代算

13、法確定搜索方向P (k)是關(guān)鍵的一步，各種算法的區(qū)別主要在于確定搜索方向P (k)的方法不同。步長 的選定一般都是以使目標(biāo)函數(shù)在搜索方向上下降最多為依據(jù)的，稱為最佳步長，即沿射線 求目標(biāo)函數(shù)的極小值由于確定步長是通過求以 為變量的一元函數(shù) 的極小點(diǎn)來實(shí)現(xiàn)的，故稱這一過程為一維搜索。7/26/2022394. 一維搜索 一維搜索即沿某一已知方向求目標(biāo)函數(shù)的極小點(diǎn)，一維搜索的方法很多，在此只介紹斐波那契法和黃金分割法。7/26/2022404.1 斐波那契法 一維搜索過程是建立在一個(gè)被稱為斐波那契數(shù)序列基礎(chǔ)上的。斐波那契數(shù)序列是具有如下遞推關(guān)系的無窮序列：F0=F1=1Fn=Fn-1+Fn-2，n

14、 =2,3, n012345678Fn1123581321347/26/2022414.1 斐波那契法斐波那契法成功地實(shí)現(xiàn)了單峰函數(shù)極值范圍的縮減。設(shè)某一單峰函數(shù)在a, b上有一極小點(diǎn) x*，在此區(qū)間內(nèi)任意取兩點(diǎn)a1和b1 ，使a1b1 ，計(jì)算其函數(shù)值可能出現(xiàn)以下兩種情況： (1) f (a1) f (b1)，如圖(1)所示；此時(shí)極小點(diǎn)x*必在期間a, b1內(nèi)。 (2) f (a1) f (b1)，如圖(2)所示；此時(shí)極小點(diǎn)x*必在期間a1, b內(nèi)。 7/26/2022424.1 斐波那契法f (x)o a a1 x* b1 b x圖(1)7/26/2022434.1 斐波那契法f (x)o

15、a a1 x* b1 b x圖(2)7/26/2022444.1 斐波那契法只要在區(qū)間a, b內(nèi)任意取兩點(diǎn)a1和b1 ，使a1b1并計(jì)算其函數(shù)值加以比較，就可以把搜索區(qū)間a, b縮減成a, b1或a1, b。若要繼續(xù)縮小搜索期間a, b1或a1, b ，只需在期間內(nèi)再取一點(diǎn)算出其函數(shù)值并與f (a1)或 f (b1)加以比較即可。由此可見，計(jì)算函數(shù)的次數(shù)越多，搜索期間就縮得越小，即區(qū)間的縮短率（縮短后的區(qū)間長度與原區(qū)間長度之比）與函數(shù)的計(jì)算次數(shù)有關(guān)。7/26/202245斐波那契法的具體步驟1. 根據(jù)相對(duì)精度或絕對(duì)精度，確定試點(diǎn)個(gè)數(shù)；2. 確定兩個(gè)試點(diǎn)的位置a1、b1（對(duì)稱搜索）；Fn-2Fn

16、-1aba1b1Fn-2Fn-17/26/202246斐波那契法的具體步驟3. 計(jì)算函數(shù)值和并比較其大小，從而縮減搜索區(qū)間；4. 重復(fù)2、3兩步，直到得到近似最小點(diǎn)。7/26/202247斐波那契法例(第90頁例6-6)例6-6： 用斐波那契法求函數(shù) f (x)=3x2-12x+10的近似極小點(diǎn)和極小值，要求縮短后的區(qū)間不大于初始區(qū)間1,4的0.05倍。7/26/2022484.2 黃金分割法 用斐波那契法以n個(gè)點(diǎn)縮減某一區(qū)間時(shí)，區(qū)間長度的縮減率依次為：Fn-1/Fn, Fn-2/Fn-1 , F1/F2 。現(xiàn)將以上數(shù)列分為奇數(shù)項(xiàng)F2k-2/F2k和偶數(shù)項(xiàng)F2k/F2k+1 ，可以證明這兩個(gè)數(shù)

17、列收斂于同一個(gè)極限。7/26/2022494.2 黃金分割法以不變的區(qū)間縮減率，代替斐波那契法每次不同的縮減率，就得到了黃金分割法。黃金分割法是一種等速對(duì)稱的搜索方法，每次試點(diǎn)均取在區(qū)間長度的倍和倍處。7/26/202250黃金分割法例(第92頁例6-7)例6-7： 求二次函數(shù) f (x)=3x2-21x-1在區(qū)間0,20上的極小點(diǎn)，要求縮短后的區(qū)間長度不大于原區(qū)間長度的5%。7/26/2022515. 無約束極值問題迭代法解析法直接法用到函數(shù)的一、二階導(dǎo)數(shù)，即函數(shù)的解析性質(zhì)只用到函數(shù)值，而不要求函數(shù)的解析性質(zhì)7/26/202252三種方法梯度法（最速下降法）牛頓法變尺度法7/26/2022535.1 梯度法（最速下降法）基本原理7/26/2022545.1 梯度法（最速下降法）基本步驟7/26/2022555.1 梯度法（最速下降法）