非線性規(guī)劃演示文稿2

非線性規(guī)劃演示文稿1第一頁，共三十六頁。2（優(yōu)選）非線性規(guī)劃第二頁，共三十六頁。2、多元函數(shù)y=f(X)=f(x1,x2,…,xn)：在X0附近作泰勒展開，得

第三頁，共三十六頁。①極值點(diǎn)存在的必要條件：f(x)=0，此時(shí)求出的x0

為駐點(diǎn)。

②極值點(diǎn)存在的充分條件：

第四頁，共三十六頁。四、凸函數(shù)與凹函數(shù)：

1、定義：y=f(x)是En中某凸集R上的函數(shù)①對(duì)[0,1]及X1、X2R，且X1≠X2

若f[X1+(1-)X2]≤f(X1)+(1-)f(X2)，則f(x)為R上的凸函數(shù)。若f[X1+(1-)X2]＜f(X1)+(1-)f(X2)，則f(x)為R上的嚴(yán)格凸函數(shù)。②對(duì)[0,1]及X1、X2R，且X1≠X2

若f[X1+(1-)X2]≥f(X1)+(1-)f(X2)，則f(x)為R上的凹函數(shù)。若f[X1+(1-)X2]＞f(X1)+(1-)f(X2)，則f(x)為R上的嚴(yán)格凹函數(shù)。yxoX1X2X1+(1-)X2y=f(x)凸函數(shù)yxoX1X2X1+(1-)X2y=f(x)凹函數(shù)yxoX1X2y=f(x)非凸、非凹函數(shù)第五頁，共三十六頁。2、性質(zhì)：fi(X)為凸集R上的凸函數(shù)，則對(duì)ki≥0，i=1,2,…,m，有

k1f1(X)+k2f2(X)+…+kmfm(X)仍為凸函數(shù)。

3、凸函數(shù)的判定：f(X)定義在凸集R上，若f(X)有連續(xù)的二階導(dǎo)數(shù)，則f(X)為凸函數(shù)H為半正定。

f(X)為嚴(yán)格凸函數(shù)H為正定。

4、凸函數(shù)的局部極值與全局極值的關(guān)系若目標(biāo)函數(shù)在可行域中為凸函數(shù)，則其極值點(diǎn)為最優(yōu)值點(diǎn)；若目標(biāo)函數(shù)在可行域中為嚴(yán)格凸函數(shù)，則其極值點(diǎn)為唯一最優(yōu)值點(diǎn)。

第六頁，共三十六頁。五、凸規(guī)劃：

1、定義：非線性規(guī)劃(p)

Minf(X)

gi(X)≥0

，i=1,2,…,m

若f(X)，-gi(X)為凸函數(shù)，則(p)稱為凸規(guī)劃。2、性質(zhì)：①(p)的可行解集R是凸集；最優(yōu)解集R*也是凸集。②(p)的任何局部最優(yōu)解均是全局最優(yōu)解。③若f(X)為嚴(yán)格凸函數(shù)時(shí)，其最優(yōu)解必唯一。特例:線性函數(shù)既是凸函數(shù)又是凹函數(shù)，故L.P.為凸規(guī)劃。六、尋優(yōu)方法概述：

1、N.L.P.問題分類①無約束條件的NLP問題。②有約束條件的NLP問題。

2、尋優(yōu)方法

①間接法(解析法)：適應(yīng)于目標(biāo)函數(shù)有簡(jiǎn)單明確的數(shù)學(xué)表達(dá)式。②直接法(搜索法)：目標(biāo)函數(shù)復(fù)雜或無明確的數(shù)學(xué)表達(dá)式。

a.消去法(對(duì)單變量函數(shù)有效)：不斷消去部分搜索區(qū)間，逐步縮小極值點(diǎn)存在的范圍。

b.爬山法(對(duì)多變量函數(shù)有效)：根據(jù)已求得的目標(biāo)值，判斷前進(jìn)方向，逐步改善目標(biāo)值。第七頁，共三十六頁。9.2無約束條件下單變量函數(shù)尋優(yōu)一、消去法原理：逐步縮小搜索區(qū)間，直至極值點(diǎn)存在的區(qū)間達(dá)到允許的誤差范圍為止。設(shè)要尋求f(X)的極小值點(diǎn)為X*，起始搜索區(qū)間為[a0,b0]。

x1、x2[a0,b0]，且x2＜x1，計(jì)算f(x1)和f(x2)，并且比較結(jié)果：f(x)xoa0b0X*x1,x2在x*的右側(cè)x1x2f(x)xoa0b0X*x1,x2在x*的左側(cè)x1x2f(x)xoa0b0X*x1,x2在x*的兩側(cè)x1x2①x1,x2均在x*的右側(cè)，f(x2)＜f(x1)，去掉[x1,b0]，此時(shí)x*[a0,x1]②x1,x2均在x*的左側(cè)，f(x2)＞f(x1)，去掉[a0,x2]，此時(shí)x*[x2,b0]③x1,x2均在x*的兩側(cè)，f(x2)＝f(x1)：

a.去掉[x1,b0]，此時(shí)x*[a0,x1]b.去掉[a0,x2]，此時(shí)x*[x2,b0]

第八頁，共三十六頁。二、黃金分割法(0.618法)：是一種常用的消去法與對(duì)分法、Fibonacci法比較，具有計(jì)算次數(shù)少，過程簡(jiǎn)單的特點(diǎn)。1、原理：LxL-xLx1x22、取點(diǎn)法則：Lx1x2a0b0L①f(x2)≤f(x1)，取[a1=a0,b1=x1]x’1=x2

x’2=b1-(b1-a1)

a1b1x’1x’2②f(x2)＞f(x1)，取[a1=x2,b1=b0]x’1=a1+(b1-a1)

x’2=x1

a1b1x’1x’2計(jì)算n個(gè)點(diǎn)后，總縮短率為En=n-1＜，可得試點(diǎn)數(shù)n。第九頁，共三十六頁。3、計(jì)算步驟：求函數(shù)f(x)的極值點(diǎn)

第一步：取初始區(qū)間[a0,b0]x1x2a0b0⑴若求f(x)的極小值點(diǎn)，則①f(x2)≤f(x1)，取[a1=a0,b1=x1]x’1=x2

x’2=b1-(b1-a1)②f(x2)＞f(x1)，取[a1=x2,b1=b0]x’1=a1+(b1-a1)

x’2=x1

a1b1x’1x’2a1b1x’1x’2⑵若求f(x)的極大值點(diǎn)，則①f(x2)≥f(x1)，取[a1=a0,b1=x1]x’1=x2

x’2=b1-(b1-a1)②f(x2)＜f(x1)，取[a1=x2,b1=b0]x’1=a1+(b1-a1)

x’2=x1

第二步：求區(qū)間的縮短率第十頁，共三十六頁。例求解f(x)=-18x2+72x+28的極大值點(diǎn)，≤0.1，起始搜索區(qū)間為[0,3]解：①用間接法：令f’(x)=-36x+72=0，得駐點(diǎn)x=2

又因?yàn)閒’’(x)=-36＜0，故x=2為f(x)的極大值點(diǎn)，fmax=100②用直接法中的黃金分割法：令n-1=，得n=1+(lg)/(lg)≈5.78442

約6步即可，計(jì)算結(jié)果見下表：kakbkf(ak)f(bk)pk=

bk-akpk/p0x1k=ak+·pkx2k=bk-·pkf(x2k)△f(x1k)0032882311.8541.14686.9＜99.62f(x)xo3x1x211.146386.9821.8540.6182.2921.85499.62＞98.4621.1462.29286.998.461.1460.3821.8541.58496.89＜99.6231.5842.29296.8998.460.7080.2362.0221.85499.62＜99.9941.8542.29299.6298.460.4380.1462.1252.02299.99＞98.7251.8542.12599.6299.720.2710.0903第十一頁，共三十六頁。9.3無約束條件下多變量函數(shù)尋優(yōu)一、爬山法原理：通過點(diǎn)的直接移動(dòng)，逐步改善目標(biāo)函數(shù)取值，直至達(dá)到極值點(diǎn)為止。由以下二部分組成：①選定搜索方向；②在選定的方向上爬山搜索。二、變量輪換法(或降維法):選擇與坐標(biāo)軸平行的方向?yàn)樗阉鞣较蛟O(shè)S=f(X)=f(x1,x2,…,xn)，極值點(diǎn)存在的區(qū)間為

x1*[a1,b1]，x2*[a2,b2]，…

，xn*[an,bn]1、原理：①?gòu)钠瘘c(diǎn)X(0)出發(fā)，沿平行于x1

軸的方向P(1)進(jìn)行一維搜索，求得f(X)在該方向P(1)上近似極值點(diǎn)X(1)；②從點(diǎn)X(1)出發(fā)，沿平行于x2

軸的方向P(2)進(jìn)行一維搜索，求得f(X)在該方向P(2)上近似極值點(diǎn)X(2)；③從點(diǎn)X(2)出發(fā)，照此交替進(jìn)行下去，直至滿足給定的精度為止

|f(X(k))

-f(X(k-1))|＜或

|S(k)-S(k-1)|＜

第十二頁，共三十六頁。2、算法步驟：設(shè)S=f(X)=f(x1,x2)，極值點(diǎn)存在的區(qū)間為x1*[a1,b1]，x2*[a2,b2]

第一步：從X(0)=(x1(0),x2(0))T出發(fā)①先固定x1=x1(0):求以x2為單變量的目標(biāo)函數(shù)的極值點(diǎn)，得X(1)=(x1(0),x2(1))T

，S(1)=f(X(1))②再固定x2=x2(1):求以x1為單變量的目標(biāo)函數(shù)的極值點(diǎn)，得X(2)=(x1(2),x2(1))T

，S(2)=f(X(2))

此時(shí)S(2)優(yōu)于S(1)，且搜索區(qū)間縮短為x1*[x1(2),b1]，x2*[x2(1),b2]

第二步：如此交替搜索，直至滿足給定精度為止

|f(X(k))

-f(X(k-1))|＜或

|S(k)-S(k-1)|＜o(jì)x1X(0)X(1)X(2)X(3)X(4)x2第十三頁，共三十六頁。例求S=f(x)=x12+x22-x1x2-10x1-4x2+60的極小值點(diǎn)，=0.01解：設(shè)起始點(diǎn)X(0)=(0,0)T，用變量輪換法計(jì)算：①先固定x1=x1(0)=0:則f(0,x2)=x22-4x2+60，尋優(yōu)得x2(1)=2

于是X(1)=(x1(0),x2(1))T=(0,2)T

，S(1)=f(X(1))=56②再固定x2=x2(1)=2:則f(x1,2)=x12-12x1+56，尋優(yōu)得x1(2)=6

于是X(2)=(x1(2),x2(1))T=(6,2)T

，S(2)=f(X(2))=20

如此交替搜索，直至滿足給定精度=0.01為止

|f(X(k))

-f(X(k-1))|＜0.01或

|S(k)-S(k-1)|＜0.01

最后得極小點(diǎn)X*=(8,6)T，f(X*)=8ox1X(0)X(1)X(2)X(3)X(4)x2計(jì)算結(jié)果見下表：第十四頁，共三十六頁。k固定的xi單變量的目標(biāo)函數(shù)f(xj)求得極點(diǎn)xj目標(biāo)值S(k)|S(k)-S(k-1)|12345678x1=x1(0)=0x2=x2(1)=2x1=x1(2)=6x2=x2(3)=5x1=x1(4)=7.5x2=x2(5)=5.75x1=x1(6)=7.88x2=x2(7)=5.94f(0,x2)=x22-4x2+60f(x1,2)=x12-12x1+56f(6,x2)=x22-10x2+36f(x1,5)=x12-15x1+65f(7.5,x2)=x22–11.5x2+41.25f(x1,5.75)=x12–15.75x1+70.06f(7.88,x2)=x22–11.88x2+43.27f(x1,5.94)=x12–15.94x1+71.50x2=x2(1)=2x1=x1(2)=6x2=x2(3)=5x1=x1(4)=7.5x2=x2(5)=5.75x1=x1(6)=7.875x2=x2(7)=5.94x1=x1(8)=7.975620118.758.18758.04698.01178.00293692.250.56250.14060.03520.0088ox1X(0)X(1)X(2)X(3)X(4)x2缺點(diǎn)：①很大程度上取決于目標(biāo)函數(shù)性質(zhì)。目標(biāo)函數(shù)等高線的性質(zhì)很重要。②道路迂回曲折，多次變換方向，在極點(diǎn)附近，目標(biāo)值改進(jìn)更小，收斂速度慢。故不是一個(gè)有利方向。第十五頁，共三十六頁。三、一階梯度法(最速下降或上升法):選擇負(fù)梯度方向?yàn)樗阉鞣较蛟O(shè)求S=f(X)=f(x1,x2,…,xn)的極值點(diǎn)。

1、原理：①?gòu)钠瘘c(diǎn)X(0)出發(fā)，沿某個(gè)有利方向P(0)進(jìn)行一維搜索，求得f(X)在P(0)方向近似極小點(diǎn)X(1)；②從點(diǎn)X(1)出發(fā)，沿某個(gè)新有利方向P(1)進(jìn)行一維搜索，求得f(X)在P(1)方向近似極小點(diǎn)X(2)；③從點(diǎn)X(2)出發(fā)，照此進(jìn)行下去，直至滿足給定的精度為止

|f(X(k))

-f(X(k-1))|＜或

|S(k)-S(k-1)|＜

2、算法步驟：設(shè)求S=f(X)=f(x1,x2)的極值點(diǎn)。第一步：從給定起點(diǎn)X(0)

出發(fā)

第二步：從點(diǎn)X(1)出發(fā)，照此進(jìn)行下去，直至滿足給定的精度為止

|f(X(k+1))

-f(X(k))|＜或

||G(k)||＜第十六頁，共三十六頁。例求S=f(x)=x12+x22-x1x2-10x1-4x2+60的極小值點(diǎn)，=0.1解:①②從點(diǎn)X(1)出發(fā)，照此進(jìn)行下去，直至滿足給定的精度=0.1為止

|f(X(k+1))

-f(X(k))|＜0.1或

||G(k)||＜0.1

第十七頁，共三十六頁。計(jì)算結(jié)果見下表：缺點(diǎn)：①搜索效果比變量輪換法快，但愈接近極值點(diǎn)，步長(zhǎng)愈小，目標(biāo)值改進(jìn)愈小。當(dāng)遇到強(qiáng)交互作用時(shí)，不是有效的方法;

當(dāng)遇到山脊時(shí)，會(huì)慢慢爬行。②在遠(yuǎn)離極點(diǎn)時(shí)，收斂速度較快;

在極點(diǎn)附近，收斂速度不快。k01234507.636.817.957.827.9903.055.115.565.875.93-102.21-1.490.33-0.220.05-4-5.53-0.60-0.82-0.09-0.1210.775.591.600.890.240.13-0.930.37-0.930.37-0.930.37-0.37-0.93-0.37-0.93-0.37-0.9288.222.211.220.330.180.056015.749.158.178.038.003744.266.590.980.140.026ox1x(0)x(1)x(2)X(3)x2第十八頁，共三十六頁。四、共軛梯度法:選擇共軛方向?yàn)樗阉鞣较颌鍐栴}的提出：在極值點(diǎn)附近，如何加快收斂速度，須對(duì)函數(shù)在極值點(diǎn)附近的性質(zhì)進(jìn)行研究。

設(shè)有n維目標(biāo)函數(shù)S=f(X)=f(x1,x2,…,xn),在極值點(diǎn)X*附近展開成泰勒級(jí)數(shù)：

特別：對(duì)二元二次函數(shù)，可證明：在極值點(diǎn)附近，其等高線可近似視為同心橢園族，而同心橢園族的任意兩根平行切線的切點(diǎn)連線必通過橢園中心。

ox1X(0)P(0)X’(0)X(2)X(1)x2P(0)P(1)=X(2)-X(1)P(1)與P(0)共軛故：在極值點(diǎn)附近，沿搜索方向P(0)上巳得到一個(gè)切點(diǎn)X(1)，則只要得出通過極值點(diǎn)的連線方向

P(1),在此方向上尋優(yōu),可一步直達(dá)極值點(diǎn)。而這個(gè)連線方向P(1)是上一次搜索方向P(0)的共軛方向。第十九頁，共三十六頁。㈡共軛方向的定義：

1、定義：設(shè)X,Y是n維向量空間En中兩個(gè)向量，A為n×n對(duì)稱正定矩陣，若XTAY=0，則稱向量X與Y對(duì)于矩陣A共軛。特例：若A=I，得XTY=0，則稱向量X與Y正交。

2、幾何意義：共軛方向是通過極值點(diǎn)的方向。㈢尋優(yōu)原理：設(shè)n元函數(shù)S=f(X)=f(x1,x2,…,xn),在極值點(diǎn)X*附近可用一個(gè)二次函數(shù)逼近其中H為n×n對(duì)稱正定矩陣第二十頁，共三十六頁。特別：對(duì)二元二次函數(shù)S=f(X)=f(x1，x2)①?gòu)哪滁c(diǎn)X(0)出發(fā),以P(0)方向搜索,使f(X)達(dá)到極小值點(diǎn)X(1),

則:X(1)必為該點(diǎn)處等高線的切點(diǎn),P(0)為切線方向，且點(diǎn)X(1)的梯度方向f(X(1))為該等高線的法線方向，這兩個(gè)方向正交。②從另一點(diǎn)X’(0)出發(fā),仍以P(0)方向搜索,使f(X)達(dá)到另一個(gè)極小值點(diǎn)X(2),

則:X(2)也必為該點(diǎn)處等高線的切點(diǎn),P(0)為切線方向，且點(diǎn)X(2)的梯度方向f(X(2))為該等高線的法線方向，這兩個(gè)方向正交。ox1X(0)P(0)X’(0)X(2)X(1)x2P(0)P(1)=X(2)-X(1)P(1)與P(0)共軛故:對(duì)二元二次函數(shù),只須搜索兩個(gè)方向P(0)和P(1)就可達(dá)到極值點(diǎn)X*。一般:對(duì)n元二次函數(shù),可用不超過n次搜索就可達(dá)到極值點(diǎn)X*。而n元非二次函數(shù)在極值點(diǎn)附近可用二次函數(shù)逼近。第二十一頁，共三十六頁。㈣尋優(yōu)步驟：例求S=f(x)=x12+x22-x1x2-10x1-4x2+60的極小值點(diǎn)。解①ox1X(0)P(0)X(1)x2第二十二頁，共三十六頁。②即ox1X(0)P(0)X(1)x2P(1)與P(0)共軛X(2)對(duì)二元二次函數(shù),只須兩次搜索就可達(dá)到極值點(diǎn)X*,一般:對(duì)n元二次函數(shù),可用不超過n次搜索就可達(dá)到極值點(diǎn)X*。而n元非二次函數(shù)在極值點(diǎn)附近可用二次函數(shù)逼近。第二十三頁，共三十六頁。㈤適用于一般目標(biāo)函數(shù)的共軛梯度法：

1、共軛方向的計(jì)算問題：須用到目標(biāo)函數(shù)的海賽矩陣H(二階偏導(dǎo)數(shù)矩陣)，若目標(biāo)函數(shù)為二次函數(shù)時(shí)，H容易求出；若目標(biāo)函數(shù)為高次或高維函數(shù)時(shí)，H難以求出，此時(shí)共軛方向難以求出。

2、共軛方向的計(jì)算方法：F-R法，由Fletcher和Reeves提出，可避免海賽矩陣H的計(jì)算，方便地確定共軛方向，簡(jiǎn)單有效。第二十四頁，共三十六頁。

3、搜索過程：①?gòu)腦(0)出發(fā)：②從X(1)出發(fā)：第二十五頁，共三十六頁。③從X(2)出發(fā)：4、搜索方法:①若目標(biāo)函數(shù)為n元二次函數(shù)，則理論上最多經(jīng)n次迭代可達(dá)極小點(diǎn)，實(shí)際由于舍入誤差，須n次以上的迭代。②若目標(biāo)函數(shù)為n元非二次函數(shù)，但共軛方向只有n個(gè)，迭代n次以后應(yīng)重新開始迭代，減少誤差積累。一般，在開始階段(二次型較弱)用一階梯度法，接近極點(diǎn)(二次型較強(qiáng))

用共軛梯度法。

一般有：第二十六頁，共三十六頁。例求S=f(x)=x12+x22-x1x2-10x1-4x2+60的極小值點(diǎn)。解:①②第二十七頁，共三十六頁。9.4有約束條件下多變量函數(shù)尋優(yōu)一、具有等式約束的極值問題：

1、消元法：n元非線性規(guī)劃

S=f(X)=f(x1,x2,…,xn)s.t.gk(X)=0,k=1,2,…,m,m<n

若可從m個(gè)s.t.中解出m個(gè)變量xi=h(xm+1,xm+2,…,xm),i=1,2,…,m,

代入目標(biāo)函數(shù)中消去m個(gè)變量，則問題變?yōu)橐粋€(gè)求n-m個(gè)變量函數(shù)的無約束條件的極值問題。例：求解Mins.t.第二十八頁，共三十六頁。

2、拉格朗日(Lagrangian)乘子法：n元非線性規(guī)劃

S=f(X)=f(x1,x2,…,xn)s.t.gk(X)=0,k=1,2,…,m

例：求解Mins.t.則L(X,)有極值的必要條件為：

求出的解就是f(X)的駐點(diǎn)。

令

第二十九頁，共三十六頁。

其中，拉格朗日乘子k的經(jīng)濟(jì)意義：

影子價(jià)格---單位資源的目標(biāo)增量

S=f(X)=f(x1,x2,…,xn)s.t.gk(X)=bk,k=1,2,…,m

知k是約束式gk每變化一個(gè)單位,引起目標(biāo)f值的變化率。

⑴若目標(biāo)f為效用函數(shù)極大化，b為預(yù)算約束，