非線性規(guī)劃的基本概念和基本原理

關(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ù)?；虻?頁(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)單而又具有重要理論