版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
關(guān)于非線性規(guī)劃的基本概念和基本原理27.1數(shù)學(xué)模型和基本概念非線性規(guī)劃是運(yùn)籌學(xué)中包含內(nèi)容最多,應(yīng)用最廣泛的一個(gè)分支,計(jì)算遠(yuǎn)比線性規(guī)劃復(fù)雜。第2頁(yè),共54頁(yè),2024年2月25日,星期天3一、數(shù)學(xué)模型例某單位擬建一排廠房,廠房建筑平面如圖所示。由于資金及材料的限制,圍墻及隔墻的總長(zhǎng)度不能超過80米。為使建筑面積最大,應(yīng)如何選擇長(zhǎng)寬尺寸?分析:設(shè)長(zhǎng)為米,寬為米,則有
f(x)為非線性函數(shù)第3頁(yè),共54頁(yè),2024年2月25日,星期天4例設(shè)某物理過程具有如下規(guī)律用試驗(yàn)法?,F(xiàn)要確定參數(shù)使所得試驗(yàn)點(diǎn)構(gòu)成的曲線與理論曲線誤差平方和為最小,且滿足
非負(fù)。第4頁(yè),共54頁(yè),2024年2月25日,星期天5非線性規(guī)劃:目標(biāo)函數(shù)或(和)約束條件為非線性函數(shù)的規(guī)劃。分析:
f(x)為非線性函數(shù),求最小。第5頁(yè),共54頁(yè),2024年2月25日,星期天6一般模型Minf(X)s.t.hi(X)=0(i=1,2,….m)(P)
gj(X)
0(j=1,2….l)X
Enf(X)hi(X)gj(X)為En上的實(shí)函數(shù)。或第6頁(yè),共54頁(yè),2024年2月25日,星期天7二、基本概念1、全局極值和局部極值
為目標(biāo)函數(shù),為可行域。若存在,,都有,則稱為該問題的全局極小點(diǎn),
為全局極小值。
為目標(biāo)函數(shù),為可行域。若有,,都有,則稱為該問題的嚴(yán)格全局極小點(diǎn),
為嚴(yán)格全局極小值。
第7頁(yè),共54頁(yè),2024年2月25日,星期天8若存在,令,都有,
則稱為該問題的局部極小點(diǎn),為局部極小值。
若存在,令,都有,
則稱為該問題的嚴(yán)格局部極小點(diǎn),為嚴(yán)格局部極小值。
相應(yīng)不等式反號(hào),得到相應(yīng)極大點(diǎn),極大值定義。第8頁(yè),共54頁(yè),2024年2月25日,星期天9定義如果X滿足(P)的約束條件
hi(X)=0(i=1,2,….m)gj(X)
0(j=1,2….l)
則稱X
En
為(P)的一個(gè)可行解。記(P)的所有可行解的集合為D,D稱為(P)可行域。第9頁(yè),共54頁(yè),2024年2月25日,星期天10定義
X*稱為(P)的一個(gè)(整體)最優(yōu)解,如果X*D,滿足
f(X)
f(X*),
X
D。
定義
X*稱為(P)的一個(gè)(局部)最優(yōu)解,如果X*D,且存在一個(gè)X*的鄰域N(X*,)=X
EnX-X*<
,>0滿足
f(X)
f(X*),
X
DN(X*,)
第10頁(yè),共54頁(yè),2024年2月25日,星期天11f(X)局部最優(yōu)解整體最優(yōu)解第11頁(yè),共54頁(yè),2024年2月25日,星期天122.梯度向量
f(X)=gradf(X)=(f/x1,f/x2,…..,f/xn)T區(qū)間內(nèi)連續(xù)的梯度的性質(zhì):①在某點(diǎn)的
f(X(0))必與函數(shù)過該點(diǎn)的等值面的切平面相垂直。②梯度方向是函數(shù)值增加最快的方向(函數(shù)變化率最大的方向)負(fù)梯度方向是函數(shù)值減小最快的方向。第12頁(yè),共54頁(yè),2024年2月25日,星期天13第13頁(yè),共54頁(yè),2024年2月25日,星期天143、海賽(Hesse)矩陣
2f(X)=H(X)
2f/x12
2f/x1x2…..2f/x1xn
2f/x2x1
2f/x22
…..2f/x2xn……..
2f/xnx1
2f/xnx2…..2f/xn2=第14頁(yè),共54頁(yè),2024年2月25日,星期天15
2f(X)是對(duì)稱矩陣。(f(X)二階偏導(dǎo)數(shù)連續(xù)時(shí),混合偏導(dǎo)數(shù)和取導(dǎo)數(shù)的順序無關(guān))f(X)是二次函數(shù),則可寫成
f(X)=1/2XTAX+BTX+C則2f(X)=A(與X的位置無關(guān))第15頁(yè),共54頁(yè),2024年2月25日,星期天164、正定矩陣、負(fù)定、半定、不定正定:特征值>0;各階主子式>0(Ai>0)半正定:特征值≥0;detA=0,Ai≥0負(fù)定:特征值<0;Ai<0(i為奇),Ai>0(i為偶)半負(fù)定:特征值≤0;detA=0,Ai≤0(i為奇),Ai≥0(i為偶)不定:特征值有>
0及<
0;除了上述情況外即為不定。第16頁(yè),共54頁(yè),2024年2月25日,星期天17例:判定正定性解:第17頁(yè),共54頁(yè),2024年2月25日,星期天18例:判定正定性解:第18頁(yè),共54頁(yè),2024年2月25日,星期天19作業(yè):P2004.4(1)第19頁(yè),共54頁(yè),2024年2月25日,星期天207.2無約束問題的極值條件例求解如下非線性規(guī)劃問題o2626第20頁(yè),共54頁(yè),2024年2月25日,星期天21分析:
非線性規(guī)劃的最優(yōu)解可能在可行域的任一點(diǎn)達(dá)到。o2266第21頁(yè),共54頁(yè),2024年2月25日,星期天22若H(x)為正定,該駐點(diǎn)X*是嚴(yán)格局部極小值點(diǎn);若H(x)為負(fù)定,該駐點(diǎn)X*是嚴(yán)格局部極大值點(diǎn);若H(x)為半正定(半負(fù)定),則進(jìn)一步觀察它在該點(diǎn)某鄰域內(nèi)的情況,可能是可能不是;如果H(x)不定的,該駐點(diǎn)X*就不是f(X)極值點(diǎn)。一、用海賽矩陣判斷駐點(diǎn)的性質(zhì)第22頁(yè),共54頁(yè),2024年2月25日,星期天23二、極值點(diǎn)的必要條件和充分條件最優(yōu)性條件的研究是非線性規(guī)劃理論研究的一個(gè)中心問題。為什么要研究最優(yōu)性條件?本質(zhì)上把可行解集合的范圍縮小。它是許多算法設(shè)計(jì)的基礎(chǔ)。第23頁(yè),共54頁(yè),2024年2月25日,星期天24無約束問題的最優(yōu)性條件(P1)Minf(X)X
En
定理3(一階必要條件)
設(shè)f(X)在X*點(diǎn)可微,則X*為(P1)的一個(gè)局部極值點(diǎn),一定有
f(X*)=gradf(X*)=0(X*稱為駐點(diǎn))第24頁(yè),共54頁(yè),2024年2月25日,星期天25無約束問題的最優(yōu)性條件(P1)Minf(X)X
En
定理4(二階必要條件)
設(shè)f(X)在X*點(diǎn)二階可微,如果X*為(P1)的一個(gè)局部極小點(diǎn),則有
f(X*)=0和H(X*
)為半正定。第25頁(yè),共54頁(yè),2024年2月25日,星期天26無約束問題的最優(yōu)性條件(P1)Minf(X)X
En
定理5(二階充分條件)
設(shè)f(X)在X*點(diǎn)二階可微,如果
f(X*)=0和H(X*)為正定,則X*為(P1)的一個(gè)嚴(yán)格局部極小點(diǎn)。第26頁(yè),共54頁(yè),2024年2月25日,星期天27例
Minf(X)=2x12+5x22+x32+
2x2x3
+
2x1x3-
6x2+3X
E3
解:
f(X)=(4x1+
2x3,10x2+
2x3–
6,2x1+
2x2+
2x3
)=0駐點(diǎn)x*=(1,1,-2)H(X)=2f(X)=020102222第27頁(yè),共54頁(yè),2024年2月25日,星期天28H(X)=2f(X)=020102222各階主子式:4>0,=40>04
0010020102222
=24>0H(X)正定,X*=(1,1,-2),f(X*)=0第28頁(yè),共54頁(yè),2024年2月25日,星期天29例利用極值條件解無約束非線性規(guī)劃問題解因?yàn)?/p>
,
令即求得到4個(gè)駐點(diǎn):
,和不是極小點(diǎn);
是極小點(diǎn)。第29頁(yè),共54頁(yè),2024年2月25日,星期天30凸集概念:
設(shè)D是n維線性空間En的一個(gè)點(diǎn)集,若D中的任意兩點(diǎn)x(1),x(2)的連線上的一切點(diǎn)x仍在D中,則稱D為凸集。即:若D中的任意兩點(diǎn)x(1),x(2)
∈D,任意0<
<1使得x=
x(1)+(1-
)x(2)∈D,則稱D為凸集7.3凸函數(shù)與凸規(guī)劃第30頁(yè),共54頁(yè),2024年2月25日,星期天31一、凸函數(shù)的定義幾何解釋第31頁(yè),共54頁(yè),2024年2月25日,星期天32f(X)X第32頁(yè),共54頁(yè),2024年2月25日,星期天33f(X)Xf(X1)f(X2)X1X2第33頁(yè),共54頁(yè),2024年2月25日,星期天34f(X)X
f(x1)
+(1-
)f(x2)f(X1)f(X2)X1X2
x1+(1-
)x2f(x1+(1-
)x2)第34頁(yè),共54頁(yè),2024年2月25日,星期天35f(X)X
f(x1)
+(1-
)f(x2)f(X1)f(X2)X1X2
x1+(1-
)x2f(x1+(1-
)x2)任意兩點(diǎn)的函數(shù)值的連線上的點(diǎn)都在曲線的上方第35頁(yè),共54頁(yè),2024年2月25日,星期天36線性函數(shù)既是凸函數(shù),又是凹函數(shù)。如果-f(X)為R上的(嚴(yán)格)凸函數(shù),則f(X)為R上的(嚴(yán)格)凹函數(shù).第36頁(yè),共54頁(yè),2024年2月25日,星期天37二.凸函數(shù)的性質(zhì)
性質(zhì)1設(shè)都是定義在凸集R上的凸函數(shù),那么仍是在凸集R上的凸函數(shù)。性質(zhì)2設(shè)是定義在凸集S上的凸函數(shù),那么對(duì)任意實(shí)數(shù),集合是S的凸子集。性質(zhì)3f(x)是凸集R上凸函數(shù),則f(x)在R上局部極小點(diǎn)就是全局極小點(diǎn),且極小點(diǎn)的集合是凸集。
第37頁(yè),共54頁(yè),2024年2月25日,星期天38三、凸函數(shù)的判別第38頁(yè),共54頁(yè),2024年2月25日,星期天39例第39頁(yè),共54頁(yè),2024年2月25日,星期天40作業(yè):P2004.6(1)(2)第40頁(yè),共54頁(yè),2024年2月25日,星期天41定理6(充要條件):若是二階連續(xù)可微的凸函數(shù),則是全局極小點(diǎn)。類似地,若二階連續(xù)可微的嚴(yán)格凸函數(shù),則是惟一全局極小點(diǎn)。四、凸函數(shù)極值點(diǎn)的充要條件第41頁(yè),共54頁(yè),2024年2月25日,星期天42解無約束問題的算法:求f(X)的駐點(diǎn)X*,若是凸函數(shù),得到最優(yōu)解。否則,轉(zhuǎn)下一步。在駐點(diǎn)X*處,計(jì)算H(x)。根據(jù)H(x)來判斷該駐點(diǎn)X*是否是極值點(diǎn)。第42頁(yè),共54頁(yè),2024年2月25日,星期天43例
求極值f(X)=x1+
2x3+x2x3-x12-x22-x32X
E3
解:
f(X)=(1-2x1,x3-2x2,2+x2-
2x3)=0駐點(diǎn)x*=(1/2,2/3,4/3)H(X)=xxf(X)=-2000-2101-2第43頁(yè),共54頁(yè),2024年2月25日,星期天44H(X)=xxf(X)=各階主子式:-2<0,=4>0-2
00-2=-6<0-2000-2101-2-2000-2101-2
H(X)負(fù)定,f(X)
是凹函數(shù)X*=(1/2,2/3,4/3)為極大值點(diǎn)。f(X*)=f(1/2,2/3,4/3)=19/12第44頁(yè),共54頁(yè),2024年2月25日,星期天45
五、凸規(guī)劃下述問題為凸規(guī)劃.求凸函數(shù)f(x)在凸集R上的極小點(diǎn)的問題,稱為凸規(guī)劃。第45頁(yè),共54頁(yè),2024年2月25日,星期天46性質(zhì):1、凸規(guī)劃的局部極小點(diǎn)就是全局極小點(diǎn)。2、極小點(diǎn)的集合是凸集。3、若目標(biāo)函數(shù)為嚴(yán)格凸函數(shù),若存在極小點(diǎn),則極小點(diǎn)必定唯一。凸規(guī)劃是一類比較簡(jiǎn)單而又具有重要理論
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 三八婦女節(jié)演講稿13篇
- 簡(jiǎn)單平面圖形旋轉(zhuǎn)信息技術(shù)與學(xué)科教學(xué)融合課教學(xué)設(shè)計(jì)表
- 人教版四年級(jí)下冊(cè)《三角形的分類》教學(xué)設(shè)計(jì)
- Unit 3 What would you likePart B Read and write小學(xué)英語(yǔ)教學(xué)設(shè)計(jì)
- 端午節(jié)周記6篇
- 幸福的演講稿5篇
- 二級(jí)建造師之二建建設(shè)工程法規(guī)及相關(guān)知識(shí)題庫(kù)(綜合卷)
- 碧桂園公園上城李文焱直播腳本 -房地產(chǎn)-2021
- 地產(chǎn)項(xiàng)目事件營(yíng)銷活動(dòng)方案
- 鞋面改款與風(fēng)格轉(zhuǎn)換技巧考核試卷
- 高速公路總體施工組織布置及規(guī)劃方案
- 《中國(guó)現(xiàn)代文學(xué)》PPT課件
- 急診科3月三基三嚴(yán)理論考試題
- 2021年人教版小學(xué)二年級(jí)數(shù)學(xué)下冊(cè)期末考試試卷及答案
- 幼兒園課件:大班美術(shù)《美麗的郵票》
- 大學(xué)物理:量子物理第五章固體的能帶結(jié)構(gòu)
- 工程項(xiàng)目成本優(yōu)化措施及成本總結(jié)
- 白內(nèi)障超聲乳化技術(shù)相關(guān)知識(shí)
- 六年級(jí)科學(xué)總復(fù)習(xí)空氣和水練習(xí)卷
- 小學(xué)六年級(jí)上冊(cè)音樂-第5課《今天是你的生日》--人音版(簡(jiǎn)譜)(11張)ppt課件
- T∕CAGHP 066-2019 危巖落石柔性防護(hù)網(wǎng)工程技術(shù)規(guī)范(試行)
評(píng)論
0/150
提交評(píng)論