ch3凹函數(shù)與非線性規(guī)劃

第3章凹函數(shù)與非線性規(guī)劃3.1向量和子空間投影定理3.2多元函數(shù)及其導數(shù)3.3數(shù)學規(guī)劃模型的一般形式3.4凸集、凸函數(shù)和凸規(guī)劃3.5非線性規(guī)劃3.6海賽（Hessian）矩陣與二次型3.7更一般的提法及其在經濟中的應用3.1向量和子空間投影定理(1)n維歐氏空間：Rn

點（向量）：x

Rn,x=(x1,x2,…,xn)T

分量xi

R(實數(shù)集)

方向（自由向量）：d

Rn,d0d=(d1,d2,…,dn)T

表示從0指向d的方向實用中，常用x+d表示從x點出發(fā)沿d方向移動d長度得到的點d0xx+(1/2)d3.1向量和子空間投影定理(2)向量運算：x,y

Rn

n

x,y的內積：xTy=xiyi=x1y1+x2y2+…+xnyn

i=1

x,y的距離：

‖x-y‖=[(x-y)T(x-y)](1/2)

x的長度：

‖x‖=[xTx](1/2)

三角不等式：

‖x+y‖≤‖x‖＋‖y‖

點列的收斂：設點列｛x(k)｝Rn

,xRn

點列｛x(k)｝收斂到x，記limx(k)=x

lim‖x(k)-x‖=0limxi(k)=xi,ikkkx+yyx3.1向量和子空間投影定理(3)子空間：設

d(1),d(2),…,d(m)

Rn,d(k)

0

m

記L(d(1),d(2),…,d(m))={x=

jd(j)

jR

}

j=1為由向量d(1),d(2),…,d(m)

生成的子空間，簡記為L。正交子空間：設L

為Rn的子空間，其正交子空間為

L＝{xRn

xTy=0,

yL

}子空間投影定理：設L為Rn的子空間。那么

xRn，唯一xL,yL,使z=x+y,且x為問題

min‖z-u‖s.t.uL的唯一解，最優(yōu)值為‖y‖。特別，L

＝Rn時，正交子空間L＝{0}（零空間）3.1向量和子空間投影定理規(guī)定：x,y

Rn，x≤yxi≤

yi，i

類似規(guī)定x≥y，x=y，x<y,x>y.一個有用的定理設xRn，R，L為Rn

的線性子空間，

(1)若xTy≤,

yRn

且y≥

0，

則x≤0，≥

0.(2)若xTy≤,

yLRn

，

則xL，≥

0.(特別,

L＝Rn時,x=0)定理的其他形式：“若xTy≤,

yRn

且y≤

0，則x≥0，≥

0.”“若xTy≥,

yRn

且y≥

0，則x≥0，≤

0.”“若xTy≥,

yRn

且y≤

0，則x≤0，≤

0.”“若xTy≥,

yLRn

，則xL，≤

0.”3.2多元函數(shù)及其導數(shù)(1)n元函數(shù)：f(x):Rn

R

線性函數(shù)：f(x)=cTx+b=cixi

+b

二次函數(shù)：f(x)=(1/2)xTQx+cTx+b=(1/2)ijaijxixj

+cixi

+b

向量值線性函數(shù)：F(x)=Ax+dRm其中A為mn矩陣，d為m維向量

F(x)=(f1(x),f2(x),…,fm(x))T記aiT為A的第i行向量，fi(x)=aiTx3.2多元函數(shù)及其導數(shù)(2)梯度（一階偏導數(shù)向量）：

f(x)＝(f/x1,f/x2,…,f/xn)TRn

.

線性函數(shù)：f(x)=cTx+b,

f(x)=c

二次函數(shù)：f(x)=(1/2)xTQx+cTx+b

f(x)=Qx+c

向量值線性函數(shù)：F(x)=Ax+dRmF/x=AT3.2多元函數(shù)及其導數(shù)(3)Hesse陣（二階偏導數(shù)矩陣）：

2f/x12

2f/x2x1

…2f/xnx1

2f(x)=

2f/x1x2

2f/x22

…2f/xnx2

…

…

……

2f/x1xn

2f/x2xn

…2f/xn2

線性函數(shù)：f(x)=cTx+b,

2f(x)=0

二次函數(shù)：f(x)=(1/2)xTQx+cTx+b,

2f(x)=Q3.2多元函數(shù)及其導數(shù)(4)n元函數(shù)的Taylor展開式及中值公式：

設f(x):Rn

R

，二階可導。在x*的鄰域內一階Taylor展開式：

f(x)=f(x*)+fT(x*)(x-x*)+o‖x-x*‖二階Taylor展開式：

f(x)=f(x*)+fT(x)(x-x*)+(1/2)(x-x*)T

2f(x*)(x-x*)+o‖x-x*‖2一階中值公式：對x,,使

f(x)=f(x*)+［f(x*+(x-x*))]T(x-x*)Lagrange余項：對x,,記xx*+(x-x*)

f(x)=f(x*)+fT(x)(x-x*)+(1/2)(x-x*)T

2f(x)(x-x*)3.3數(shù)學規(guī)劃模型的一般形式

maxf(x)

--------目標函數(shù)

s.t.xS

--------約束集合，可行集其中，SRn，f:SR，xS稱（fS)的可行解最優(yōu)解:x*S，滿足f(x*)≤f(x),xS。則稱

x*為(fS)的全局最優(yōu)解(最優(yōu)解),

記g.opt.(globaloptimum),簡記opt.最優(yōu)值:x*為(fS)的最優(yōu)解,則稱f*=f(x*)

為

(fS)的最優(yōu)值(最優(yōu)目標函數(shù)值)(fS)3.3數(shù)學規(guī)劃模型的一般形式（續(xù)）局部最優(yōu)解:x*S，x*的鄰域N(x*)，使?jié)M足

f(x*)≤f(x),xSN(x*)

。則稱x*為(fS)的局部最優(yōu)解,記l.opt.(localoptimum)在上述定義中，當xx*時有嚴格不等式成立，則分別稱x*

為(fS)的嚴格全局最優(yōu)解和嚴格局部最優(yōu)解。嚴格l.opt.嚴格g.opt.l.opt.3.3數(shù)學規(guī)劃模型的一般形式（續(xù)）函數(shù)形式:

f(x),gi(x),hj(x):RnRminf(x)(fgh)s.t.gi(x)

≤0,i=1,2,…,m

hj(x)=0,j=1,2,…,l矩陣形式:minf(x)，f(x)

:RnR(fgh)s.t.g(x)

≤0,g(x):RnRm

h(x)=0,h(x):RnRl

當f(x),gi(x),hj(x)均為線性函數(shù)時，稱線性規(guī)劃；若其中有非線性函數(shù)時，稱非線性規(guī)劃。3.4凸集、凸函數(shù)和凸規(guī)劃一、凸集1、凸集的概念：定義：設集合SRn，若x(1),x(2)S,[0,1]，必有

x(1)＋(1-)x(2)S，則稱S為凸集。規(guī)定：單點集{x}為凸集，空集為凸集。注:x(1)＋(1-)x(2)=x(2)＋(x(1)-x(2))

是連接x(1)與x(2)的線段。凸集非凸集非凸集3.4凸集、凸函數(shù)和凸規(guī)劃(續(xù))一、凸集1、凸集的概念：例:證明集合S={x∣Ax=b}是凸集。其中，A為mn矩陣，b為m維向量。凸組合：設

x(1),x(2),…,x(m)

Rn,j≥

0

mm

j=1,那么稱

jx(j)為x(1),x(2),…,x(m)的

j=1j=1凸組合。

m比較:z=

jx(j)

j=1jR

—

構成線性組合——

線性子空間j≥0,

j>0—

構成半正組合——

凸錐j≥0,

j=0—

構成凸組合——

凸集3.4凸集、凸函數(shù)和凸規(guī)劃(續(xù))一、凸集1、凸集的概念：定理：S是凸集S中任意有限點的凸組合屬于S多胞形H(x(1),x(2),…,x(m))：由x(1),x(2),…,x(m)的所有凸組合構成。單純形：若多胞形H(x(1),x(2),…,x(m))滿足，

x(2)-x(1),x(3)-x(1),…,x(m)-

x(1)

線性無關。多胞形單純形單純形3.4凸集、凸函數(shù)和凸規(guī)劃(續(xù))一、凸集

2、凸集的性質：凸集的交集是凸集；（并？）凸集的內點集是凸集；（逆命題是否成立？）凸集的閉包是凸集。（逆命題是否成立？）分離與支撐：凸集邊界上任意點存在支撐超平面兩個互相不交的凸集之間存在分離超平面支撐強分離分離非正常分離3.4凸集、凸函數(shù)和凸規(guī)劃(續(xù))一、凸集3、凸錐：定義：C

Rn,若xC,>0

有xC,則稱C是以0為頂點的錐。如果C還是凸集，則稱為凸錐。集合{0}、Rn是凸錐。命題：C是凸錐C中任意有限點的半正組合屬于S03.4凸集、凸函數(shù)和凸規(guī)劃(續(xù))二、凸函數(shù)

1、凸函數(shù)及水平集定義:設集合SRn為凸集，函數(shù)f:SR

若x(1),x(2)S,(0,1)，均有

f(x(1)＋(1-)x(2))≤f(x(1))+(1-)f(x(2))，則稱f(x)為凸集S上的凸函數(shù)。若進一步有上面不等式以嚴格不等式成立，則稱f(x)為凸集S上的嚴格凸函數(shù)。當-f(x)為凸函數(shù)（嚴格凸函數(shù)）時，則稱f(x)為凹函數(shù)（嚴格凹函數(shù)）。嚴格凸函數(shù)凸函數(shù)嚴格凹函數(shù)3.4凸集、凸函數(shù)和凸規(guī)劃(續(xù))二、凸函數(shù)1、凸函數(shù)及水平集：定理：f(x)為凸集S上的凸函數(shù)S上任意有限點的凸組合的函數(shù)值不大于各點函數(shù)值的凸組合。思考：設f1,f2是凸函數(shù)，設1,2>0,1f1+2f2,1f1-2f2是否凸函數(shù)？f(x)=max{f1(x),f2(x)},g(x)=min{f1(x),f2(x)}是否凸函數(shù)？

3.4凸集、凸函數(shù)和凸規(guī)劃(續(xù))二、凸函數(shù)1、凸函數(shù)及水平集：定義：設集合SRn

，函數(shù)f:SR，R

，稱S={xS∣f(x)≤

}

為f(x)

在S上的水平集。定理：設集合SRn

是凸集，函數(shù)f:SR是凸函數(shù)，則對R

，S

是凸集。注：水平集的概念相當于在地形圖中，海拔高度不高于某一數(shù)值的區(qū)域。上述定理的逆不真?？紤]分段函數(shù)f(x)=1(x≥0)或0(x<0)，函數(shù)非凸，但任意水平集是凸集。3.4凸集、凸函數(shù)和凸規(guī)劃(續(xù))二、凸函數(shù)2、凸函數(shù)的性質：方向導數(shù)：設S

Rn為非空凸集，函數(shù)f:SR，再設x*

S,d為方向，使當

>0

充分小時有x*+d

S,

如果

lim

[f(x*+d)-f(x*)]/

存在（包括）

則稱f(x)為在點沿方向的方向導數(shù)存在，記

f`(x*;d)=lim

[f(x*+d)-f(x*)]/

若f(x)在x*可導，則f`(x*;d)=[f(x*)]Td.3.4凸集、凸函數(shù)和凸規(guī)劃(續(xù))二、凸函數(shù)2、凸函數(shù)的性質：以下設S

Rn為非空凸集，函數(shù)f:SR2）若f凸，則f在S的內點集上連續(xù)；注：f在S上不一定連續(xù)。

例:f(x)＝2(當x=1)；f(x)＝x2(當x<1).

3）設f凸，則對任意方向方向導數(shù)存在。4）設S是開集，f在S上可微，則

f凸x*S，有f(x)≥f(x*)+fT(x*)(x-x*),xS.5)設S是開集，f在S上二次可微，則

a)

f凸xS，2f(x)半正定；

b)若xS，2f(x)正定，則f嚴格凸。3.4凸集、凸函數(shù)和凸規(guī)劃(續(xù))二、凸函數(shù)2、凸函數(shù)的性質：例：

f(x)＝x12+2x1x2+2x22+10x1-4；

f(x)＝-3x12+x1x2-x22-2x32-2x2x3+26;

f(x)＝3x12+ax1x2+2x22-4x1+6(a=5,4.5)；3.4凸集、凸函數(shù)和凸規(guī)劃(續(xù))三、凸規(guī)劃：當（fS）中，S為凸集，f是S上的凸函數(shù)（求min），稱（fS）為凸規(guī)劃；對于（fgh）,f,gi為凸函數(shù)，hj為線性函數(shù)時，（fgh）為凸規(guī)劃。定理：設集合S

Rn為凸集，函數(shù)f:SRf(x)為凸集S上的凸函數(shù)。X*為問題（fs）的l.opt，則X*為g.opt；又如果f是嚴格凸函數(shù)，那么X*是（fs）的唯一g.opt。3.5非線性規(guī)劃若目標函數(shù)或約束條件中至少有一個是變量的非線性函數(shù)，稱這類規(guī)劃問題為非線性規(guī)劃問題（NonlinearProgramming;NP）。非線性規(guī)劃的系統(tǒng)研究始于上個世紀四十年代末，1951年Kuhn和Tucker提出了著名的Kuhn-Tucker條件，加上電子計算機的迅速發(fā)展，使得非線性規(guī)劃無論在基本理論還是實用算法都有了長足的發(fā)展，使之逐漸成為運籌學的一個非常重要的分支。特別是非線性規(guī)劃問題對于目標函數(shù)和約束條件幾乎沒有任何限制，使得非線性規(guī)劃越來越廣泛地應用于經濟管理、最優(yōu)設計等各個領域。一般地，非線性規(guī)劃（NP）問題的數(shù)學模型可表述其中，

是歐氏空間

中的向量。

以上（NP）模型稱為非線性規(guī)劃的一般形式。乘上“-1”即可將這種不等式的約束變成“”的形式。若模型的目標函數(shù)為極大化時，則可將其負值極小化;若若某個約束條件是“”形式，則只需要將不等式兩端為3.5非線性規(guī)劃又因為等式約束等價于以下兩個不等式約束所以，非線性規(guī)劃問題的數(shù)學模型又可寫成3.5非線性規(guī)劃例1考慮非線性規(guī)劃問題圖13.5非線性規(guī)劃目標函數(shù)f(X)是旋轉拋物面，約束條件是一個平面和一個拋物柱面所圍部分。雖然它們的圖形都可以畫出來，但使用起來并不方便，所以常將它們表示在某一個平面上。若令f(X)=C（常數(shù)）表示相等的目標函數(shù)值的集合。一般地它表示一條曲線或一張曲面，通常稱為等值線或等值面。如令

f(X)為4或20，便得到兩條圓形等值線，如圖1。半徑越大的等值線，其上的點對應的目標函數(shù)值越大。由圖1可知，該問題的可行域是拋物線段ABCD。3.5非線性規(guī)劃注1：我們令動點從A點出發(fā)沿拋物線ABCD移動，動點從A點移動到B時，目標函數(shù)值減小。當動點從B點移動到C點時，目標函數(shù)值最大。由此可知，在可行域ABC這一范圍內，B點的目標函數(shù)值最小，即B點是一個極小值點。而當動點從C點移動到D點時，目目標函數(shù)值又逐漸減小，且在D點的目標函數(shù)值值最小。這里，點B只是一部分可行域上的極小值點，稱為局部極小點（或相對極小點），對應的目標函數(shù)值稱為局部極小值（相對極小值）。而D點則是整個可行域上的極小值點，稱為全局極小值點（最小值點）或絕對極小點，對應的目標函數(shù)值稱為全局極小值（最小值）或絕對極小值。注2：約束條件自然對最優(yōu)解是有影響的。若不考慮約束條件，便是無約束問題。它的最優(yōu)解為x1*=2,x2*=1,f(X*)=0.3.5非線性規(guī)劃定義1設f(X)為定義在n維歐氏空間En上的某一區(qū)域上R的n元實函數(shù)，X=(x1,x2,xn)T

。若f(X)在R上可微，令（1）則f(X)

稱為f(X)的梯度向量，亦記作gradf。3.6海賽（Hessian）矩陣與二次型性質1函數(shù)f(X)在某點X*

處的梯度f(X)

（f(X)0）必與函數(shù)過該點的等值面（f(X)

=f(X*)的切平面垂直。性質2沿梯度的方向，函數(shù)值增加得最快，即該方向上函數(shù)變化率最大，而負梯度方向則是函數(shù)值減小最快的方向。3.6海賽（Hessian）矩陣與二次型為函數(shù)f(X)在X*點處的梯度。若在考察的區(qū)域內梯度是連續(xù)的，則有以下兩個性質。特別地，稱定義2設R是n維歐氏空間En上的某一開集，函數(shù)f(X)在R上具有連續(xù)的二階偏導數(shù)，令（2）則稱H(X)為函數(shù)f(X)的海賽矩陣（HessianMatrix）,亦記為2f(X)。3.6海賽（Hessian）矩陣與二次型注1：當f(X)的二階混合偏導數(shù)連續(xù)時，二階混合偏導數(shù)與取導數(shù)的順序無關，即因而H(X)為對稱矩陣。3.6海賽（Hessian）矩陣與二次型例如：設則梯度向量和海賽矩陣分別為：和定義3稱n元二次齊次函數(shù)（3）為n元二次型。其中矩陣A=(aij)nn為對稱矩陣。若A中所有元素均為實數(shù)，則該二次型為實二次型。

3.6海賽（Hessian）矩陣與二次型定義4設有實二次型f(X)=XTAX，(1)

若對任意X0，恒有f(X)<0，則稱f(A)為負定二次型（或稱f(X)為負定的），對應的矩陣A為負定矩陣；

(2)若對任意X0，恒有f(X)0，則稱f(A)為半正定的（或稱f(X)為非負定的），對應的矩陣A為半正定矩陣；(3)若對任意X0，恒有f(X)0，則稱f(A)為半負定的（或稱f(X)為非正定的），對應的矩陣A為半負定矩陣；(4)若存在某些X0

，有f(X)>0

，又存在某些X0

，有f(X)<0

，則稱f(X)為不定的，對應的矩陣A為不定矩陣。3.6海賽（Hessian）矩陣與二次型注1：實二次型f(X)=XTAX為正定的充要條件是矩陣A的各階順序主子式均大于零，即注2：實二次型f(X)=XTAX

為負定的充要條件是陣A的各階順序主子式正負交替出現(xiàn)，即3.6海賽（Hessian）矩陣與二次型為正定矩陣。是正定二次型，對應的矩陣例如是負定二次型，對應的矩陣是負定矩陣。例如例

判定非線性函數(shù)的海賽矩陣H(X)的正定性。解：因為所以海賽矩陣H(X)正定。3.6海賽（Hessian）矩陣與二次型例

判定二次型的正定性。解：因為二次型的矩陣為所以A為負定的，故二次型為負定二次型。二次型的有定性在極值判定中的應用：顯然，（1）若f(x1,x2,,xn)為正定（半正定）二次型，所以是的極小值；3.6海賽（Hessian）矩陣與二次型是的極大值；（2）若f(x1,x2,,xn)為負定（半負定）二次型，顯然，所以二次型的有定性在極值判定中的應用：3.6海賽（Hessian）矩陣與二次型（3）若f(x1,x2,,xn)為不定二次型，顯然不是的極值。3.6海賽（Hessian）矩陣與二次型二次型的有定性在極值判定中的應用：3.7更一般的提法及其在經濟中的應用前面的各種說法在一般的高等數(shù)學中基本都能見到，為了使這些理論適合更一般地情況，在很多書上會用更抽象的表述方式。因此，本課程在將通俗的提法介紹完之后，本節(jié)給各位講解一個在讀或寫論文中較為常見但卻不易看懂的表述模式。實質上二者是一致的，希望各位能將它們聯(lián)系起來，這樣有利于對內容的深入理解，以便于將來的應用。3.7.1非線性規(guī)劃“數(shù)學規(guī)劃”或者“非線性規(guī)劃”（NLP)是指求解約束優(yōu)化問題的一些方法。一般地，最基本的規(guī)劃問題可以表示為：

max{f(x;

)；x

C()｝(P)

x也就是說，給定某個參數(shù)，我們求解x使得f(·;

)在集合C()中取到極大值。在這個表達式中：．x=（x1，…，xn）

X

Rn稱為決策變量(DecisionVariables)或者選擇變量(ChoiceVariables)；3.7.1非線性規(guī)劃一些解釋（1）令表示所有可能的“環(huán)境”的集合，消費者在這些環(huán)境中都可以發(fā)現(xiàn)自己，參數(shù)的一個取值表示一個環(huán)境，令X表示消費者可以采取的行為的集合。給定的取值，消費者會發(fā)現(xiàn)他的選擇被限制到X的某個子集C中（例如，消費者理論中的預算集）。=(1,…,p)Rp是給定數(shù)值的參數(shù)(Parameter)向量；C()X稱為約束集(ConstraintSet)或可行集(FeasibleSet)它是對于給定的參數(shù)所有可行的x的集合；f是實值函數(shù)f

:Rn+p

XR，通常稱為目標函數(shù)(ObjectiveFunction).（2）隨著參數(shù)的改變，可行集也會改變，這可以表示為約束對應(ConstraintCorrespondence）C：

X。（3）函數(shù)f,X

R是消費者的目標函數(shù)f(x;)表示當消費者面對環(huán)境且采取行動x時消費者的支付。理性的消費者會選擇一個最優(yōu)的計劃，所謂最優(yōu)計劃是指對于給定的參數(shù)值在約束集中使得目標函數(shù)取到極大值的點。最優(yōu)行動的集合稱為決策規(guī)則（DecisionRule)或者最佳反應對應S()：3.7.1非線性規(guī)劃3.7.1非線性規(guī)劃S：

X，其中S()=argmax{f(x;

);xC()｝

x即S()是由(P)的最優(yōu)解x*組成的集合。若對的每個取值，(P)的解是惟一的，則這個對應變成一個函數(shù)，記為x*=x()。最優(yōu)化的消費者的支付通過一個（極大）值函數(shù)V給出，V：

R定義為：V()=max{f(x;

);xC()｝=f(x*;

),其中x*S()x

給定參數(shù)向量的取值，V()給出了可得到的最高支付。顯然,V()等于對于給定的目標函數(shù)f()在最優(yōu)解x*處的函數(shù)值。在許多經濟應用中，我們感興趣的是比較靜態(tài)和決策規(guī)則的性質。

：3.7.1非線性規(guī)劃也就是說，我們希望知道，當環(huán)境（他面對的價格、他的收等）變化時消費者的行為將如何改變。arg是元素（變元）的英文縮寫。

argmin就是使后面這個式子達到最小值時的x，t的取值

argmax就是使后面這個式子達到最大值時的x，t的取值S()=argmax{f(x;

);xC()｝x根據(jù)可行集的不同，我們考慮三種不同的規(guī)劃問題：凸約束集（ConvexConstraintSet）

C是Rn中的凸集；特別的情形，沒有約束的極大化，這里我們將C看成是整個Rn，以及另一種情形，極大值需滿足非負的約束，即可行集就是Rn中的非負集合。拉格朗日問題(LagrangeProblem)

約束集是由等式約束組成的集合：3.7.1非線性規(guī)劃庫恩-塔克問題(Kuhn-TuckerProblem)

約束集是由一些不等式約束組成的集合：C()={xX;g(x;

)=0｝

C()={xX;g(x;

)0｝

3.7.2凸約束優(yōu)化問題考慮問題：其中，C是Rn中的凸集，f：RnXR是C2函數(shù)。因為我們所關心的是對于給定的問題(P.C)的解，所以在討論中可以省去參數(shù)。max{f(x);xC｝

x我們對這個問題的特別情形很熟悉。若C=Rn,則x*是f的極大點的必要條件是Df(x*)=0

。但在一般情形中，關于極大點這個條件既不是必要的也不是充分的。在圖3.1給出了這樣的例子。圖3.1導數(shù)為0既不是最大點的必要條件也不是充分條件3.7.2凸約束優(yōu)化問題3.7.2凸約束優(yōu)化問題嚴格局部極大值。定理3.5

整體唯一性令x*是問題(P.C)的最優(yōu)解，C是凸集。若f是嚴格擬凹函數(shù)，則x*是唯一的最優(yōu)解。3.7.2凸約束優(yōu)化問題問題7.1.12