運籌學和最優(yōu)化

運籌學和最優(yōu)化2.0、預(yù)備知識1、向量和子空間投影定理(1)n維歐氏空間：Rn

點（向量）：x

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

分量xi

R(實數(shù)集)

方向（自由向量）：d

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

表示從0指向d的方向?qū)嵱弥校Ｓ脁+d表示從x點出發(fā)沿d方向移動

d長度得到的點d0xx+(1/2)d第2頁,共30頁，2024年2月25日，星期天2.0、預(yù)備知識（續(xù)）1、向量和子空間投影定理(2)向量運算：x,y

Rn

n

x,y的內(nèi)積：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‖

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

Rn

,x

Rn

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

lim‖x(k)-x‖=0

limxi(k)=xi,ik

k

k

x+yyx第3頁,共30頁，2024年2月25日，星期天2.0、預(yù)備知識（續(xù)）1、向量和子空間投影定理(3)子空間：設(shè)

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

Rn,d(k)

0

m

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

jd(j)

j

R

}

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

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

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

L

＝{x

Rn

xTy=0,

y

L

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

x

Rn，唯一x

L,y

L

,使z=x+y,且x

為問題

min‖z-u‖

s.t.u

L

的唯一解，最優(yōu)值為‖y‖。特別，

L

＝Rn時，正交子空間L

＝{0}（零空間）第4頁,共30頁，2024年2月25日，星期天2.0、預(yù)備知識（續(xù)）規(guī)定：x,y

Rn，x≤y

xi≤

yi，

i

類似規(guī)定x≥y，x=y，x<y,x>y.一個有用的定理設(shè)x

Rn，

R，L為Rn

的線性子空間，

(1)若xTy≤

,

y

Rn

且y≥

0，

則x≤0，

≥

0.(2)若xTy≤

,

y

L

Rn

，

則x

L

，

≥

0.(特別,

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

,

y

Rn

且y≤

0，則x≥0，

≥

0.”“若xTy≥

,

y

Rn

且y≥

0，則x≥0，

≤

0.”“若xTy≥

,

y

Rn

且y≤

0，則x≤0，

≤

0.”“若xTy≥

,

y

L

Rn

，則x

L

，

≤

0.”第5頁,共30頁，2024年2月25日，星期天2.0、預(yù)備知識（續(xù)）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)

i

jaijxixj

+cixi

+b

向量值線性函數(shù)：F(x)=Ax+d

Rm其中A為m

n矩陣，d為m維向量

F(x)=(f1(x),f2(x),…,fm(x))T記aiT為A的第i行向量，fi(x)=aiTx第6頁,共30頁，2024年2月25日，星期天2.0、預(yù)備知識（續(xù)）2、多元函數(shù)及其導數(shù)(2)梯度（一階偏導數(shù)向量）：

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

Rn

.

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

f(x)=c

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

f(x)=Qx+c

向量值線性函數(shù)：F(x)=Ax+d

RmF/x=AT第7頁,共30頁，2024年2月25日，星期天2.0、預(yù)備知識（續(xù)）2、多元函數(shù)及其導數(shù)(3)Hesse陣（二階偏導數(shù)矩陣）：

2f/x12

2f/x2x1

…2f/xnx1

2f(x)=

2f/

x1

x2

2f/x22

…2f/xnx2

…

…

……

2f/

x1

xn

2f/x2xn

…2f/xn2

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

2f(x)=0

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

2f(x)=Q第8頁,共30頁，2024年2月25日，星期天2.0、預(yù)備知識（續(xù)）2、多元函數(shù)及其導數(shù)(4)n元函數(shù)的Taylor展開式及中值公式：

設(shè)f(x):Rn

R

，二階可導。在x*的鄰域內(nèi)一階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,

,記x

x*+(x-x*)

f(x)=f(x*)+

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

2f(x

)(x-x*)第9頁,共30頁，2024年2月25日，星期天2.1數(shù)學規(guī)劃模型的一般形式

minf(x)

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

s.t.x

S

--------約束集合，可行集其中，S

Rn，f:S

R，x

S稱（fS)的可行解最優(yōu)解:x*

S，滿足f(x*)≤f(x),x

S。則稱

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)第10頁,共30頁，2024年2月25日，星期天2.1數(shù)學規(guī)劃模型的一般形式（續(xù)）局部最優(yōu)解:x*

S，

x*的鄰域N(x*)，使?jié)M足

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

S

N(x*)

。則稱x*為(fS)的局部最優(yōu)解,記l.opt.(localoptimum)在上述定義中，當x

x*時有嚴格不等式成立，則分別稱x*

為(fS)的嚴格全局最優(yōu)解和嚴格局部最優(yōu)解。嚴格l.opt.嚴格g.opt.l.opt.第11頁,共30頁，2024年2月25日，星期天2.1數(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)

:Rn

R(fgh)s.t.g(x)

≤0,g(x):Rn

Rm

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

Rl

當f(x),gi(x),hj(x)均為線性函數(shù)時，稱線性規(guī)劃；若其中有非線性函數(shù)時，稱非線性規(guī)劃。第12頁,共30頁，2024年2月25日，星期天2.2凸集、凸函數(shù)和凸規(guī)劃一、凸集1、凸集的概念：定義：設(shè)集合S

Rn，若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)的線段。凸集非凸集非凸集第13頁,共30頁，2024年2月25日，星期天2.2凸集、凸函數(shù)和凸規(guī)劃(續(xù))一、凸集1、凸集的概念：例:證明集合S={x∣Ax=b}是凸集。其中，A為m

n矩陣，b為m維向量。凸組合：設(shè)

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=1

j

R

—

構(gòu)成線性組合——

線性子空間

j≥0,

j>0—

構(gòu)成半正組合——

凸錐

j≥0,

j=0—

構(gòu)成凸組合——

凸集第14頁,共30頁，2024年2月25日，星期天2.2凸集、凸函數(shù)和凸規(guī)劃(續(xù))一、凸集1、凸集的概念：定理：S是凸集

S中任意有限點的凸組合屬于S多胞形H(x(1),x(2),…,x(m))：由x(1),x(2),…,x(m)的所有凸組合構(gòu)成。單純形：若多胞形H(x(1),x(2),…,x(m))滿足，

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

x(1)

線性無關(guān)。多胞形單純形單純形第15頁,共30頁，2024年2月25日，星期天2.2凸集、凸函數(shù)和凸規(guī)劃(續(xù))一、凸集

2、凸集的性質(zhì)：凸集的交集是凸集；（并？）凸集的內(nèi)點集是凸集；（逆命題是否成立？）凸集的閉包是凸集。（逆命題是否成立？）分離與支撐：凸集邊界上任意點存在支撐超平面兩個互相不交的凸集之間存在分離超平面支撐強分離分離非正常分離第16頁,共30頁，2024年2月25日，星期天2.2凸集、凸函數(shù)和凸規(guī)劃(續(xù))一、凸集3、凸錐：定義：C

Rn,若x

C,

>0

有

x

C,則稱C是以0為頂點的錐。如果C還是凸集，則稱為凸錐。集合{0}、Rn是凸錐。命題：C是凸錐

C中任意有限點的半正組合屬于S0第17頁,共30頁，2024年2月25日，星期天2.2凸集、凸函數(shù)和凸規(guī)劃(續(xù))二、凸函數(shù)

1、凸函數(shù)及水平集定義:設(shè)集合S

Rn為凸集，函數(shù)f:S

R

若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ù)第18頁,共30頁，2024年2月25日，星期天2.2凸集、凸函數(shù)和凸規(guī)劃(續(xù))二、凸函數(shù)1、凸函數(shù)及水平集：定理：f(x)為凸集S上的凸函數(shù)

S上任意有限點的凸組合的函數(shù)值不大于各點函數(shù)值的凸組合。思考：設(shè)f1,f2是凸函數(shù)，設(shè)

1,

2>0,

1f1+

2f2,

1f1-

2f2是否凸函數(shù)？f(x)=max{f1(x),f2(x)},g(x)=min{f1(x),f2(x)}是否凸函數(shù)？

第19頁,共30頁，2024年2月25日，星期天2.2凸集、凸函數(shù)和凸規(guī)劃(續(xù))二、凸函數(shù)1、凸函數(shù)及水平集：定義：設(shè)集合S

Rn，函數(shù)f:S

R，

R

，稱S

={x

S∣f(x)≤

}為f(x)在S上的

水平集。定理：設(shè)集合S

Rn是凸集，函數(shù)f:S

R是凸函數(shù)，則對

R

，S

是凸集。注：水平集的概念相當于在地形圖中，海拔高度不高于某一數(shù)值的區(qū)域。上述定理的逆不真?？紤]分段函數(shù)f(x)=1(x≥0)或0(x<0)，函數(shù)非凸，但任意水平集是凸集。第20頁,共30頁，2024年2月25日，星期天2.2凸集、凸函數(shù)和凸規(guī)劃(續(xù))二、凸函數(shù)2、凸函數(shù)的性質(zhì)：方向?qū)?shù)：設(shè)S

Rn為非空凸集，函數(shù)f:S

R，再設(shè)x*

S,d為方向，使當

>0

充分小時有x*+

d

S,

如果

lim

[f(x*+

d)-f(x*)]/

存在（包括

）

則稱f(x)為在點沿方向的方向?qū)?shù)存在，記

f`(x*;d)=lim

[f(x*+

d)-f(x*)]/

若f(x)在x*可導，則f`(x*;d)=[

f(x*)]Td.第21頁,共30頁，2024年2月25日，星期天2.2凸集、凸函數(shù)和凸規(guī)劃(續(xù))二、凸函數(shù)2、凸函數(shù)的性質(zhì)：以下設(shè)S

Rn為非空凸集，函數(shù)f:S

R2）若f凸，則f在S的內(nèi)點集上連續(xù)；注：f在S上不一定連續(xù)。

例:f(x)＝2(當

x

=1)；f(x)＝x2(當

x<1).

3）設(shè)f凸，則對任意方向方向?qū)?shù)存在。4）設(shè)S是開集，f在S上可微，則

f凸

x*

S，有f(x)≥f(x*)+

fT(x*)(x-x*),

x

S.5)設(shè)S是開集，f在S上二次可微，則

a)

f凸

x

S，2f(x)半正定；

b)若

x

S，2f(x)正定，則f嚴格凸。第22頁,共30頁，2024年2月25日，星期天2.2凸集、凸函數(shù)和凸規(guī)劃(續(xù))二、凸函數(shù)2、凸函數(shù)的性質(zhì)：例：

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)；第23頁,共30頁，2024年2月25日，星期天2.2凸集、凸函數(shù)和凸規(guī)劃(續(xù))三、凸規(guī)劃：當（fS）中，S為凸集，f是S上的凸函數(shù)（求min），稱（fS）為凸規(guī)劃；對于（fgh）,f,gi為凸函數(shù)，hj為線性函數(shù)時，（fgh）為凸規(guī)劃。定理：設(shè)集合S

Rn為凸集，函數(shù)f:S

Rf(x)為凸集S上的凸函數(shù)。X*為問題（fs）的l.opt，則X*為g.opt；又如果f是嚴格凸函數(shù)，那么X*是（fs）的唯一g.opt。第24頁,共30頁，2024年2月25日，星期天2.3多面體、極點、極方向1）多面體：有限個半閉空間的交例：S={x

Rn

Ax=b,x≥0}第25頁,共30頁，2024年2月25日，星期天2.3多面體、極點、極方向2)多面體的極點（頂點）：

x

S，不存在S

中的另外兩個點x(1)和x(2)，及λ(0,1)，使x=λx(1)+(1-λ)x(2).3)方向：x

S,d

Rn,d

0及λ>0,總有x+λd

S.

d(1)=λd(2)(λ>0)時，稱d(1)和d(2)同方向。4)極方向：方向d

不能表示為兩個不同方向的組合(d=d(1)+d(2)).第26頁,共30頁，2024年2月25日，星期天2.3多面體、極點、極方向多面體S={x

Rn

Ax=b,x≥0}的極點和極方向定理1（極點特征）設(shè)A

滿秩，x

是S極點的充分必要條件是:

存在分解A=[B,N]，其中B為m階非奇異矩陣，使xT=[xBT,xNT],

這里xB=B-1b≥0,xN=0.S中必存在有限多個極點。(≤Cnm)第27頁,共30頁，2024年2月25日，星期天2.3多面體、極點、極方向多面體

S={x

Rn

Ax=b,x≥0}的極點和極方向定理2（極方向特征）設(shè)A=[p1,p2,…,pn]滿秩，d

是S

極方向的充分必要條件是:存在分解A=[B,N]，其中B為m階非奇異矩陣，對