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

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

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

為駐點。

②極值點存在的充分條件：

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

1、定義：y=f(x)是En中某凸集R上的函數(shù)①對[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上的嚴格凸函數(shù)。②對[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上的嚴格凹函數(shù)。yxoX1X2X1+(1-)X2y=f(x)凸函數(shù)yxoX1X2X1+(1-)X2y=f(x)凹函數(shù)yxoX1X2y=f(x)非凸、非凹函數(shù)第五頁，共三十六頁。2、性質(zhì)：fi(X)為凸集R上的凸函數(shù)，則對ki≥0，i=1,2,…,m，有

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

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

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

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

第六頁，共三十六頁。五、凸規(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)為嚴格凸函數(shù)時，其最優(yōu)解必唯一。特例:線性函數(shù)既是凸函數(shù)又是凹函數(shù)，故L.P.為凸規(guī)劃。六、尋優(yōu)方法概述：

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

2、尋優(yōu)方法

①間接法(解析法)：適應(yīng)于目標函數(shù)有簡單明確的數(shù)學表達式。②直接法(搜索法)：目標函數(shù)復雜或無明確的數(shù)學表達式。

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

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

x1、x2[a0,b0]，且x2＜x1，計算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]，此時x*[a0,x1]②x1,x2均在x*的左側(cè)，f(x2)＞f(x1)，去掉[a0,x2]，此時x*[x2,b0]③x1,x2均在x*的兩側(cè)，f(x2)＝f(x1)：

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

第八頁，共三十六頁。二、黃金分割法(0.618法)：是一種常用的消去法與對分法、Fibonacci法比較，具有計算次數(shù)少，過程簡單的特點。1、原理：LxL-xLx1x22、取點法則：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計算n個點后，總縮短率為En=n-1＜，可得試點數(shù)n。第九頁，共三十六頁。3、計算步驟：求函數(shù)f(x)的極值點

第一步：取初始區(qū)間[a0,b0]x1x2a0b0⑴若求f(x)的極小值點，則①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)的極大值點，則①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的極大值點，≤0.1，起始搜索區(qū)間為[0,3]解：①用間接法：令f’(x)=-36x+72=0，得駐點x=2

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

約6步即可，計算結(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)一、爬山法原理：通過點的直接移動，逐步改善目標函數(shù)取值，直至達到極值點為止。由以下二部分組成：①選定搜索方向；②在選定的方向上爬山搜索。二、變量輪換法(或降維法):選擇與坐標軸平行的方向為搜索方向設(shè)S=f(X)=f(x1,x2,…,xn)，極值點存在的區(qū)間為

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

，xn*[an,bn]1、原理：①從起點X(0)出發(fā)，沿平行于x1

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

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

|f(X(k))

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

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

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

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

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

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

此時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)|＜ox1X(0)X(1)X(2)X(3)X(4)x2第十三頁，共三十六頁。例求S=f(x)=x12+x22-x1x2-10x1-4x2+60的極小值點，=0.01解：設(shè)起始點X(0)=(0,0)T，用變量輪換法計算：①先固定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

最后得極小點X*=(8,6)T，f(X*)=8ox1X(0)X(1)X(2)X(3)X(4)x2計算結(jié)果見下表：第十四頁，共三十六頁。k固定的xi單變量的目標函數(shù)f(xj)求得極點xj目標值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缺點：①很大程度上取決于目標函數(shù)性質(zhì)。目標函數(shù)等高線的性質(zhì)很重要。②道路迂回曲折，多次變換方向，在極點附近，目標值改進更小，收斂速度慢。故不是一個有利方向。第十五頁，共三十六頁。三、一階梯度法(最速下降或上升法):選擇負梯度方向為搜索方向設(shè)求S=f(X)=f(x1,x2,…,xn)的極值點。

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

|f(X(k))

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

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

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

出發(fā)

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

|f(X(k+1))

-f(X(k))|＜或

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

|f(X(k+1))

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

||G(k)||＜0.1

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

當遇到山脊時，會慢慢爬行。②在遠離極點時，收斂速度較快;

在極點附近，收斂速度不快。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第十八頁，共三十六頁。四、共軛梯度法:選擇共軛方向為搜索方向㈠問題的提出：在極值點附近，如何加快收斂速度，須對函數(shù)在極值點附近的性質(zhì)進行研究。

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

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

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

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

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

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

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

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

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

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

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

用共軛梯度法。

一般有：第二十六頁，共三十六頁。例求S=f(x)=x12+x22-x1x2-10x1-4x2+60的極小值點。解:①②第二十七頁，共三十六頁。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個s.t.中解出m個變量xi=h(xm+1,xm+2,…,xm),i=1,2,…,m,

代入目標函數(shù)中消去m個變量，則問題變?yōu)橐粋€求n-m個變量函數(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)的駐點。

令

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

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

影子價格---單位資源的目標增量

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

知k是約束式gk每變化一個單位,引起目標f值的變化率。

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