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

非線性規(guī)劃的基本概念和基本原理1第一頁，共五十一頁，編輯于2023年，星期二7.1數(shù)學模型和基本概念非線性規(guī)劃是運籌學中包含內容最多，應用最廣泛的一個分支，計算遠比線性規(guī)劃復雜。2第二頁，共五十一頁，編輯于2023年，星期二一、數(shù)學模型例某單位擬建一排廠房，廠房建筑平面如圖所示。由于資金及材料的限制，圍墻及隔墻的總長度不能超過80米。為使建筑面積最大，應如何選擇長寬尺寸？分析：設長為米，寬為米，則有

f(x)為非線性函數(shù)3第三頁，共五十一頁，編輯于2023年，星期二例設某物理過程具有如下規(guī)律用試驗法。現(xiàn)要確定參數(shù)使所得試驗點構成的曲線與理論曲線誤差平方和為最小，且滿足

非負。4第四頁，共五十一頁，編輯于2023年，星期二非線性規(guī)劃：目標函數(shù)或（和）約束條件為非線性函數(shù)的規(guī)劃。分析：

f(x)為非線性函數(shù)，求最小。5第五頁，共五十一頁，編輯于2023年，星期二一般模型Minf(X)s.t.hi(X)=0(i=1,2,….m)（P）

gj(X)0(j=1,2….l)XEnf(X)hi(X)gj(X)為En上的實函數(shù)?；?第六頁，共五十一頁，編輯于2023年，星期二二、基本概念1、全局極值和局部極值

為目標函數(shù)，為可行域。若存在，，都有，則稱為該問題的全局極小點，

為全局極小值。

為目標函數(shù)，為可行域。若有，，都有，則稱為該問題的嚴格全局極小點，

為嚴格全局極小值。

7第七頁，共五十一頁，編輯于2023年，星期二若存在，令，都有，

則稱為該問題的局部極小點，為局部極小值。

若存在，令，都有，

則稱為該問題的嚴格局部極小點，為嚴格局部極小值。

相應不等式反號，得到相應極大點，極大值定義。8第八頁，共五十一頁，編輯于2023年，星期二定義如果X滿足（P）的約束條件

hi(X)=0(i=1,2,….m)gj(X)0(j=1,2….l)

則稱XEn

為（P）的一個可行解。記（P）的所有可行解的集合為D，D稱為（P）可行域。9第九頁，共五十一頁，編輯于2023年，星期二定義

X*稱為（P）的一個（整體）最優(yōu)解，如果X*D，滿足

f(X)f(X*)，X

D。

定義

X*稱為（P）的一個（局部）最優(yōu)解，如果X*D，且存在一個X*的鄰域N(X*,)=XEnX-X*<

,>0滿足

f(X)f(X*)，X

DN(X*,)

10第十頁，共五十一頁，編輯于2023年，星期二f(X)局部最優(yōu)解整體最優(yōu)解11第十一頁，共五十一頁，編輯于2023年，星期二2.梯度向量f(X)=gradf(X)=(f/x1,f/x2,…..,f/xn)T區(qū)間內連續(xù)的梯度的性質：①在某點的f(X（0）)必與函數(shù)過該點的等值面的切平面相垂直。②梯度方向是函數(shù)值增加最快的方向（函數(shù)變化率最大的方向）負梯度方向是函數(shù)值減小最快的方向。12第十二頁，共五十一頁，編輯于2023年，星期二13第十三頁，共五十一頁，編輯于2023年，星期二3、海賽(Hesse)矩陣

2f(X)=H(X)2f/x12

2f/x1x2…..2f/x1xn2f/x2x12f/x22

…..2f/x2xn……..2f/xnx1

2f/xnx2…..2f/xn2=14第十四頁，共五十一頁，編輯于2023年，星期二2f(X)是對稱矩陣。（f(X)二階偏導數(shù)連續(xù)時，混合偏導數(shù)和取導數(shù)的順序無關）f(X)是二次函數(shù)，則可寫成

f(X)＝1/2XTAX+BTX+C則2f(X)＝A（與X的位置無關）15第十五頁，共五十一頁，編輯于2023年，星期二4、正定矩陣、負定、半定、不定正定：特征值>0；各階主子式>0(Ai>0)半正定：特征值≥0；detA=0,Ai≥0負定：特征值<0；Ai<0(i為奇）,Ai>0(i為偶）半負定：特征值≤0；detA=0，Ai≤0(i為奇）,Ai≥0(i為偶）不定：特征值有>

0及<

0；除了上述情況外即為不定。16第十六頁，共五十一頁，編輯于2023年，星期二例：判定正定性解：17第十七頁，共五十一頁，編輯于2023年，星期二例：判定正定性解：18第十八頁，共五十一頁，編輯于2023年，星期二作業(yè)：P2004.4（1）19第十九頁，共五十一頁，編輯于2023年，星期二7.2無約束問題的極值條件例求解如下非線性規(guī)劃問題o262620第二十頁，共五十一頁，編輯于2023年，星期二分析：

非線性規(guī)劃的最優(yōu)解可能在可行域的任一點達到。o226621第二十一頁，共五十一頁，編輯于2023年，星期二若H(x)為正定，該駐點X*是嚴格局部極小值點；若H(x)為負定，該駐點X*是嚴格局部極大值點；若H(x)為半正定（半負定），則進一步觀察它在該點某鄰域內的情況，可能是可能不是；如果H(x)不定的，該駐點X*就不是f(X)極值點。一、用海賽矩陣判斷駐點的性質22第二十二頁，共五十一頁，編輯于2023年，星期二二、極值點的必要條件和充分條件最優(yōu)性條件的研究是非線性規(guī)劃理論研究的一個中心問題。為什么要研究最優(yōu)性條件？本質上把可行解集合的范圍縮小。它是許多算法設計的基礎。23第二十三頁，共五十一頁，編輯于2023年，星期二無約束問題的最優(yōu)性條件（P1）Minf(X)XEn

定理3（一階必要條件）

設f(X)在X*點可微，則X*為（P1）的一個局部極值點，一定有f(X*)=gradf(X*)=0（X*稱為駐點）24第二十四頁，共五十一頁，編輯于2023年，星期二無約束問題的最優(yōu)性條件（P1）Minf(X)XEn

定理4（二階必要條件）

設f(X)在X*點二階可微，如果X*為（P1）的一個局部極小點，則有f(X*)=0和H（X*

）為半正定。25第二十五頁，共五十一頁，編輯于2023年，星期二無約束問題的最優(yōu)性條件（P1）Minf(X)XEn

定理5（二階充分條件）

設f(X)在X*點二階可微，如果f(X*)=0和H(X*)為正定，則X*為(P1)的一個嚴格局部極小點。26第二十六頁，共五十一頁，編輯于2023年，星期二例

Minf(X)=2x12+5x22+x32+

2x2x3

+

2x1x3-

6x2+3XE3

解：f(X)=（4x1+

2x3,10x2+

2x3–

6,2x1+

2x2+

2x3

）=0駐點x*=(1,1,-2)H(X)=2f(X)=02010222227第二十七頁，共五十一頁，編輯于2023年，星期二H(X)=2f(X)=020102222各階主子式：4>0,=40>04

0010020102222

=24>0H(X)正定，X*=(1,1,-2)，f(X*)=028第二十八頁，共五十一頁，編輯于2023年，星期二例利用極值條件解無約束非線性規(guī)劃問題解因為

，

令即求得到4個駐點：

，和不是極小點；

是極小點。29第二十九頁，共五十一頁，編輯于2023年，星期二凸集概念：

設D是n維線性空間En的一個點集，若D中的任意兩點x(1),x(2)的連線上的一切點x仍在D中，則稱D為凸集。即：若D中的任意兩點x(1),x(2)

∈D，任意0<<1使得x=x(1)+(1-)x(2)∈D,則稱D為凸集7.3凸函數(shù)與凸規(guī)劃30第三十頁，共五十一頁，編輯于2023年，星期二一、凸函數(shù)的定義幾何解釋31第三十一頁，共五十一頁，編輯于2023年，星期二f(X)X32第三十二頁，共五十一頁，編輯于2023年，星期二f(X)Xf(X1)f(X2)X1X233第三十三頁，共五十一頁，編輯于2023年，星期二f(X)Xf(x1)

+(1-)f(x2)f(X1)f(X2)X1X2x1+(1-)x2f(x1+(1-)x2)34第三十四頁，共五十一頁，編輯于2023年，星期二f(X)Xf(x1)

+(1-)f(x2)f(X1)f(X2)X1X2x1+(1-)x2f(x1+(1-)x2)任意兩點的函數(shù)值的連線上的點都在曲線的上方35第三十五頁，共五十一頁，編輯于2023年，星期二線性函數(shù)既是凸函數(shù),又是凹函數(shù)。如果-f(X)為R上的(嚴格)凸函數(shù),則f(X)為R上的(嚴格)凹函數(shù).36第三十六頁，共五十一頁，編輯于2023年，星期二二．凸函數(shù)的性質

性質1設都是定義在凸集R上的凸函數(shù)，那么仍是在凸集R上的凸函數(shù)。性質2設是定義在凸集S上的凸函數(shù)，那么對任意實數(shù)，集合是S的凸子集。性質3f(x)是凸集R上凸函數(shù)，則f(x)在R上局部極小點就是全局極小點，且極小點的集合是凸集。

37第三十七頁，共五十一頁，編輯于2023年，星期二三、凸函數(shù)的判別38第三十八頁，共五十一頁，編輯于2023年，星期二例39第三十九頁，共五十一頁，編輯于2023年，星期二作業(yè)：P2004.6（1）（2）40第四十頁，共五十一頁，編輯于2023年，星期二定理6（充要條件）：若是二階連續(xù)可微的凸函數(shù)，則是全局極小點。類似地，若二階連續(xù)可微的嚴格凸函數(shù)，則是惟一全局極小點。四、凸函數(shù)極值點的充要條件41第四十一頁，共五十一頁，編輯于2023年，星期二解無約束問題的算法：求f(X)的駐點X*，若是凸函數(shù)，得到最優(yōu)解。否則，轉下一步。在駐點X*處，計算H(x)。根據(jù)H(x)來判斷該駐點X*是否是極值點。42第四十二頁，共五十一頁，編輯于2023年，星期二例

求極值f(X)=x1+

2x3+x2x3-x12-x22-x32XE3

解：f(X)=(1-2x1,x3-2x2,2+x2-

2x3)=0駐點x*=(1/2,2/3,4/3)H(X)=xxf(X)=-2000-2101-243第四十三頁，共五十一頁，編輯于2023年，星期二H(X)=xxf(X)=各階主子式：-2<0,=4>0-2

00-2=-6<0-2000-2101-2-2000-2101-2

H(X)負定，f(X)

是凹函數(shù)X*=(1/2,2/3,4/3)為極大值點。f(X*)=f(1/2,2/3,4/3)=19/1244第四十四頁，共五十一頁，編輯于2023年，星期二

五、凸規(guī)劃下述問題為凸規(guī)劃.求凸函數(shù)