第六章非線性規(guī)劃非線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型極值問(wèn)題凸規(guī)劃一維搜索無(wú)約束極值問(wèn)題約束極值問(wèn)題2/6/202311.非線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型非線性規(guī)劃問(wèn)題舉例：

Example1：第82頁(yè)例6-1

Example2：第82頁(yè)例6-2非線性規(guī)劃問(wèn)題的數(shù)學(xué)模型非線性規(guī)劃問(wèn)題的圖示2/6/202321.1非線性規(guī)劃問(wèn)題舉例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íng)業(yè)時(shí)間為1000小時(shí)，試確定使其營(yíng)業(yè)額最大的營(yíng)業(yè)計(jì)劃。

2/6/202331.1非線性規(guī)劃問(wèn)題舉例Example2:在層次分析（AnalyticHierarchyProcess,簡(jiǎn)記為AHP）中，為進(jìn)行多屬性的綜合評(píng)價(jià)，需要確定每個(gè)屬性的相對(duì)重要性，即它們的權(quán)重。為此，將各屬性進(jìn)行兩兩比較，從而得出如下判斷矩陣：

2/6/202351.1非線性規(guī)劃問(wèn)題舉例

a11…a1nJ=……,

an1…ann其中：aij是第i個(gè)屬性與第j個(gè)屬性的重要性之比。2/6/202361.1非線性規(guī)劃問(wèn)題舉例現(xiàn)需要從判斷矩陣求出各屬性的權(quán)重，為使求出的權(quán)重向量W在最小二乘意義上能最好地反映判斷矩陣的估計(jì)，由aij=wi/wj可得：2/6/202371.2非線性規(guī)劃問(wèn)題的數(shù)學(xué)模型由于，,“≤”不等式僅乘“-1”即可轉(zhuǎn)換為“≥”不等式；因此上述數(shù)學(xué)模型具有一般意義。又因?yàn)榈葍r(jià)于兩個(gè)不等式：;,因此非線性規(guī)劃的數(shù)學(xué)模型也可以表示為：2/6/202391.3非線性規(guī)劃問(wèn)題的圖示若令其目標(biāo)函數(shù)f(X)=c,目標(biāo)函數(shù)成為一條曲線或一張曲面；通常稱為等值線或等值面。此例，若設(shè)f(X)=2和f(X)=4可得兩個(gè)圓形等值線，見下圖：2/6/2023101.3非線性規(guī)劃問(wèn)題的圖示由左圖可見,等值線f(X)=2和約束條件直線6-6相切，切點(diǎn)D即為此問(wèn)題的最優(yōu)解，X*=(3,3)，其目標(biāo)函數(shù)值f(X*)=2。3232066x1x2f(X)=4f(X)=22/6/2023111.3非線性規(guī)劃問(wèn)題的圖示[注]線性規(guī)劃存在最優(yōu)解，最優(yōu)解只能在其可行域的邊緣上（特別能在可行域的頂點(diǎn)上）得到；而非線性規(guī)劃的最優(yōu)解（如果存在）則可能在可行域的任意一點(diǎn)上得到。2/6/2023132.極值問(wèn)題局部極值與全局極值極值點(diǎn)存在的條件凸函數(shù)和凹函數(shù)凸函數(shù)的性質(zhì)函數(shù)凸性的判定2/6/2023142.1局部極值與全局極值線性規(guī)劃最優(yōu)解全局最優(yōu)解非線性規(guī)劃局部最優(yōu)解未必全局最優(yōu)2/6/202315全局極值對(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)格全局極小值。2/6/2023172.2極值點(diǎn)存在的條件必要條件設(shè)R是En上的一個(gè)開集，f(X)在R上有一階連續(xù)偏導(dǎo)數(shù)，且在點(diǎn)取得局部極值，則必有

或2/6/202318必要條件為函數(shù)f(X)在X*點(diǎn)處的梯度。由數(shù)學(xué)分析可知，的方向?yàn)閄*點(diǎn)處等值面（等值線）的法線方向，沿這一方向函數(shù)值增加最快，如圖所示。2/6/202319充分條件充分條件設(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）矩陣。2/6/202321充分條件2/6/202322充分條件（充分條件）等價(jià)于：如果函數(shù)f(X)在X*點(diǎn)的梯度為零且海賽矩陣正定，則X*為函數(shù)f(X)的嚴(yán)格局部極小點(diǎn)。2/6/202323凸函數(shù)和凹函數(shù)示意圖X(1)X(2)f(X)X凸函數(shù)X(1)X(2)f(X)X凹函數(shù)2/6/202325非凹非凸函數(shù)示意圖f(X(2))f(X(1))X(1)+(1-)X(2)X(1)X(2)f(X)X非凸非凹函數(shù)2/6/2023262.5函數(shù)凸性的判定根據(jù)凸函數(shù)的定義進(jìn)行判定；根據(jù)一階條件進(jìn)行判定；根據(jù)二階條件進(jìn)行判定；2/6/202329一階條件設(shè)R為En上的開凸集，f(X)在R上具有一階連續(xù)偏導(dǎo)數(shù)，則f(X)為R上的凸函數(shù)的充分必要條件是，對(duì)于屬于R的任意兩個(gè)不同點(diǎn)X(1)和X(2)恒有：2/6/202330二階條件設(shè)R為En上的開凸集，f(X)在R上具有二階連續(xù)偏導(dǎo)數(shù)，則f(X)為R上的凸函數(shù)的充分必要條件是：f(X)的海賽矩陣H(X)在R上處處半正定（ZTH(X)Z≥0）。2/6/2023313.凸規(guī)劃凸規(guī)劃的定義下降迭代算法2/6/2023323.1凸規(guī)劃的定義考慮非線性規(guī)劃：假定其中f(X)為凸函數(shù)，gj(X)為凹函數(shù)（-gj(X)為凸函數(shù)），這樣的非線性規(guī)劃稱為凸規(guī)劃。2/6/2023333.1凸規(guī)劃的定義凸規(guī)劃：可行域是凸集、局部最優(yōu)即為全局最優(yōu)；若為嚴(yán)格凸函數(shù)，最優(yōu)解若存在必唯一。2/6/2023343.2下降迭代算法基本思想：給定一個(gè)初始估計(jì)解X(0)，然后按某種規(guī)則（即算法）找出一個(gè)比X(0)更好的解X(1)，如此遞推即可得到一個(gè)解的序列{X(k)}，若這一解的序列有極限X*，即則稱X*為最優(yōu)解。2/6/2023353.2下降迭代算法基本問(wèn)題：遞推步驟的有限性，一般說(shuō)很難得到精確解，當(dāng)滿足所要求的精度時(shí)即可停止迭代而得到一個(gè)近似解。2/6/2023363.2下降迭代算法下降算法：若產(chǎn)生的解序列{X(k)}能使目標(biāo)函數(shù)f(X(k))逐步減少，就稱此算法為下降算法?！跋陆怠钡囊蠛苋菀诐M足，因此它包括了很多具體的算法。2/6/2023373.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)為搜索方向，為步長(zhǎng)。2/6/2023383.2下降迭代算法確定搜索方向P(k)是關(guān)鍵的一步，各種算法的區(qū)別主要在于確定搜索方向P(k)的方法不同。步長(zhǎng)的選定一般都是以使目標(biāo)函數(shù)在搜索方向上下降最多為依據(jù)的，稱為最佳步長(zhǎng)，即沿射線求目標(biāo)函數(shù)的極小值由于確定步長(zhǎng)是通過(guò)求以為變量的一元函數(shù)的極小點(diǎn)來(lái)實(shí)現(xiàn)的，故稱這一過(guò)程為一維搜索。2/6/2023394.一維搜索一維搜索即沿某一已知方向求目標(biāo)函數(shù)的極小點(diǎn)，一維搜索的方法很多，在此只介紹斐波那契法和黃金分割法。2/6/2023404.1斐波那契法

一維搜索過(guò)程是建立在一個(gè)被稱為斐波那契數(shù)序列基礎(chǔ)上的。斐波那契數(shù)序列是具有如下遞推關(guān)系的無(wú)窮序列：F0=F1=1Fn=Fn-1+Fn-2，n=2,3,…n012345678Fn1123581321342/6/2023414.1斐波那契法斐波那契法成功地實(shí)現(xiàn)了單峰函數(shù)極值范圍的縮減。設(shè)某一單峰函數(shù)在[a,b]上有一極小點(diǎn)x*，在此區(qū)間內(nèi)任意取兩點(diǎn)a1和b1，使a1<b1，計(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)。2/6/2023424.1斐波那契法f(x)oaa1

x*b1bx圖(1)2/6/2023434.1斐波那契法f(x)oaa1

x*b1bx圖(2)2/6/2023444.1斐波那契法只要在區(qū)間[a,b]內(nèi)任意取兩點(diǎn)a1和b1，使a1<b1并計(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ū)間長(zhǎng)度與原區(qū)間長(zhǎng)度之比）與函數(shù)的計(jì)算次數(shù)有關(guān)。2/6/202345斐波那契法的具體步驟1.根據(jù)相對(duì)精度或絕對(duì)精度，確定試點(diǎn)個(gè)數(shù)；2.確定兩個(gè)試點(diǎn)的位置a1、b1（對(duì)稱搜索）；Fn-2Fn-1aba1b1Fn-2Fn-12/6/202346斐波那契法的具體步驟3.計(jì)算函數(shù)值和并比較其大小，從而縮減搜索區(qū)間；4.重復(fù)2、3兩步，直到得到近似最小點(diǎn)。2/6/202347斐波那契法例(第90頁(yè)例6-6)例6-6：用斐波那契法求函數(shù)f(x)=3x2-12x+10的近似極小點(diǎn)和極小值，要求縮短后的區(qū)間不大于初始區(qū)間[1,4]的0.05倍。2/6/2023484.2黃金分割法用斐波那契法以n個(gè)點(diǎn)縮減某一區(qū)間時(shí)，區(qū)間長(zhǎng)度的縮減率依次為：Fn-1/Fn,Fn-2/Fn-1,…,F1/F2?，F(xiàn)將以上數(shù)列分為奇數(shù)項(xiàng)F2k-2/F2k和偶數(shù)項(xiàng)F2k/F2k+1

，可以證明這兩個(gè)數(shù)列收斂于同一個(gè)極限。2/6/2023494.2黃金分割法以不變的區(qū)間縮減率，代替斐波那契法每次不同的縮減率，就得到了黃金分割法。黃金分割法是一種等速對(duì)稱的搜索方法，每次試點(diǎn)均取在區(qū)間長(zhǎng)度的倍和倍處。2/6/202350黃金分割法例(第92頁(yè)例6-7)例6-7：求二次函數(shù)f(x)=3x2-21x-1在區(qū)間[0,20]上的極小點(diǎn)，要求縮短后的區(qū)間長(zhǎng)度不大于原區(qū)間長(zhǎng)