管理运筹学麻省理工讲座译文lec1_unconstr_opt

管理运筹学麻省理工讲座译文

RobertM.Freund

2004

2

1

管理运筹学麻省理工讲座译文

1

1.1

(P)minxf(x)

s.t.

x=(x1,...,xn)∈ n,f(x): n→ ,

x∈X,

X

(

X= n).

x∈X,

x

(P)

(P)minx

s.t.

f(x)

gi(x)≤0i=1,...,mhi(x)=0x∈X,

i=1,...,l

g1(x),...,gm(x),h1(x),...,hl(x): n→ .

g(x)=(g1(x),...,gm(x)): n→ m,h(x)=(h1(x),...,hl(x)): n→ l.

(P)

(P)minx

s.t.

f(x)g(x)≤0h(x)=0x∈X.

g(x)≤0,h(x)=0,

x∈X,

x

(P)

1.2

x¯

B(¯x, ):={x| x x¯ ≤ }.

2

管理运筹学麻省理工讲座译文

F

P:minx

maxxf(x)

x∈F

/

s.t.

/P

/

1.1x∈F

>0,

y∈B(x, )∩F,

1.2x∈F1.3x∈F

f(x)≤f(y).

y∈F,

f(x)≤f(y).

PP

>0,

y∈B(x, )∩F,y=x,1.4x∈F

P

f(x)<f(y).

y∈F,y=x,

f(x)<f(y).1.5x∈F

P

>0,

y∈B(x, )∩F,

1.6x∈F1.7x∈F

f(x)≥f(y).

y∈F,

f(x)≥f(y).

PP

>0,

y∈B(x, )∩F,y=x,1.8x∈F

P

f(x)>f(y).

y∈F,y=x,

f(x)>f(y).

1.3

f(x):X→ ,

X

n

f(x)

x¯∈X

f(¯x)(f(x)

x¯

)

x∈X

f(x)=f(¯x)+ f(¯x)t(x x¯)+ x x¯ α(¯x,x x¯),

3

管理运筹学麻省理工讲座译文

limy→0α(¯x,y)=0.

f(x)

X

f(x)

x¯∈X

n

f(¯x)=(

1

f(¯x)

xn

)t.

f(x)=3(x1)2(x2)3+(x2)2(x3)3,

f(x)=(6(x1)(x2)3,9(x1)2(x2)2+2(x2)(x3)3,3(x2)2(x3)2)T.f(x)

x¯

d

λ→0

lim

f(¯x+λd) f(¯x)

2

(x x¯)tH(¯x)(x x¯)+ x x¯ 2α(¯x,x x¯),X

f(x)

limy→0α(¯x,y)=0.

f(x)

x¯∈X

H(¯x)ij=

x) 2f(¯

管理运筹学麻省理工讲座译文

x∈ n,

xtMx≥0.

x∈ n

x=0,

xtMx<0.

x∈ n,xtMx≤0.xtMx>0

x,y∈ n

ytMy<0

M

SPD,

M

(SymmetricandPositiveDefinite).

MSPSD,

M

(SymmetricandPositiveSemi-

Definite).

3

4

1.5

M=

2003

M=

8 1 2

1

x=0,

xTMx=8x2222

1 2x1x2+x2=7x1+(x1 x2)>0.

(P)minx

1+x

管理运筹学麻省理工讲座译文

(P)minx

1

管理运筹学麻省理工讲座译文

x′∈F,

{x∈F:f(x)≤f(x′)}

f(x)

c,

{x∈F:f(x)≤c}

7

管理运筹学麻省理工讲座译文

2

(P)minf(x)

s.t.

x∈X,

(

X= n).

x=(x1,...,xn)∈ n,f(x): n→ ,X2.1

¯d

f(x)

x=x¯

>0,

¯)<f(¯f(¯x+ dx).

“

x¯

(P)

x¯

...”

3

f(x)

x¯

dd

f(¯x)td<0,

λ>0,

f(¯x+λd)<f(¯x),

f(x)x¯

f(¯x+λd)=f(¯x)+λ f(¯x)td+λ d α(¯x,λd),

λ→0

α(¯x,λd)→0.

f(¯x+λd) f(¯x)

管理运筹学麻省理工讲座译文

f(¯x)=0,

d= f(¯x)

x¯

5

f(x)

x¯∈Xx¯

f(¯x)=0

H(¯x)

f(¯x)=0.

H(¯x)

dtH(¯x)d<0.

f(¯x+λd)=f(¯x)+λ f(¯x)td+

1

22

λdtH(¯x)d+λ2 d 2α(¯x,λd),

λ→0

,λd)→0.

α(¯xf(¯x+λd) f(¯x)

2

dtH(¯x)d+ d 2α(¯x,λd).dtH(¯x)d<0

λ→0

α(¯x,λd)→0,

λ>0,

f(¯x+λd) f(¯x)<0,

5

f(x)=

1

d

管理运筹学麻省理工讲座译文

“

x¯x¯

...,

x¯

(P)

”

6(

f(x))

x¯

f(¯x)=0

H(¯x)

x¯

f(x)=f(¯x)+

1

xk x¯ ,

f(xk)=f(¯x)+ xk x¯ 2

1

2

dtx)dk+α(¯x,xk x¯)=kH(¯

f(xk) f(¯x)

2

dtH(¯x)d,

H(¯x)

f(¯x)=0 f(¯x)=0

H(¯x)H(¯x)

x¯

x¯

6

5,

H(¯x)=

111410

管理运筹学麻省理工讲座译文

d=(d1,d2),

222

dTH(¯x)d=d21+2d1d2+4d2=(d1+d2)+3d2>0, d=0.

x¯

x¯

7

f(x)=x32

1+x2.

f(x)=

3x2

1,2x2

T

,

H(x)=

6x100

2

x¯=(0,0)

f(¯x)=0

H(¯x)=

0002

x¯

3<0=f(0,0)=f(¯x).

8

f(x)=x42

1+x2.

f(x)= 4x31

,2x2 T,H(x)=

12x21002

11

>0,

f( ,0)=

管理运筹学麻省理工讲座译文

x¯=(0,0)

f(¯x)=0

H(¯x)=

0002

x,

f(x)≥0=f(0,0)=f(¯x),x¯

2.1

x,y∈ n,λ∈[0,1],

λx+(1 λ)y

x

y

S n

x,y∈S

λ∈[0,1],

λx+(1 λ)y∈S.

f(x):S→ ,

S

f(x)

f(λx+(1 λ)y)≤λf(x)+(1 λ)f(y), x,y∈S, λ∈[0,1].

f(x)

x=y

λ∈(0,1),

f(x):S→ ,

S

f(x)

f(λx+(1 λ)y)≥λf(x)+(1 λ)f(y), x,y∈S, λ∈[0,1].

f(x)

x=y

λ∈(0,1),

(CP)minxf(x)

s.t.12

x∈S.

管理运筹学麻省理工讲座译文

7

S

f(x):S→

x¯

(CP)

x¯

f(x)

S

x¯

y∈Sy

f(y)<f(¯x).

y(λ):=λx¯+(1 λ)y,

λ∈[0,1]

y(λ)

x¯

(

λ∈[0,1]

y(λ)∈S).

λ→0

y(λ)→x¯.

f(x)

λ∈(0,1),

f(y(λ))=f(λx¯+(1 λ)y)≤λf(¯x)+(1 λ)f(y)<λf(¯x)+(1 λ)f(¯x)=f(¯x).

λ∈(0,1),

f(y(λ))<f(¯x),

x¯

f(x)

f(x)

f(x)

8

S

f(x):S→

f(x)

f(x)

f(y)≥f(x)+ f(x)t(y x)

f(x)

x,y∈S.

λ∈[0,1],

f(λy+(1 λ)x)≤λf(y)+(1 λ)f(x)

f(x+λ(y x)) f(x)

管理运筹学麻省理工讲座译文

x,y∈S

w

z

S

λ∈[0,1],x=λw+(1 λ)z.

f(w)≥f(x)+ f(x)t(w x)

f(z)≥f(x)+ f(x)t(z x).

λf(w)+(1 λ)f(z)≥f(x)+ f(x)t(λ(w x)+(1 λ)(z x))

=f(x)+ f(x)t0=f(λw+(1 λ)z),

f(x)

9

S

f(x):S→

H(x)

f(x)

f(x)

x∈S,H(x)

f(x)

x¯∈S,d

λ>0,

x¯+λd∈S.

f(¯x+λd)=f(¯x)+ f(¯x)t(λd)+

1

2

x)d+ d 2α(¯x,λd)≥0.dtH(¯λ→0,

λ2>0,

dtH(¯x)d≥0,

z∈S,

H(z)

x,y∈S.

f(y)=f(x)+ f(x)t(y x)+

1

管理运筹学麻省理工讲座译文

f(x)

(P),

f(x)

10

f(x):X→

X

x¯∈X

f(¯x)=0.

f(¯x)=0,

x¯∈X

X

4

f(x)

f(¯x)=0.

y∈X,

f(y)≥f(¯x)+

f(¯x)t(y x¯)=f(¯x),

x¯

9

5,

H(x)=

11

14 6x2

.f(·)

f(·)

X={(x1,x2)|x2<0},

10

f(x)= ln(1 x1 x2) lnx1 lnx2.

f(x)=

1

x1

1

x2

,

H(x)=

1

x1

2

15

1

1

1 x1 x2

2

x2

. 2

管理运筹学麻省理工讲座译文

f(x)

0,x2>0,x1+x2<1}

x¯=

f(x)

H(x)

1

3

X={(x1,x2)|x1>

f(¯x)=0,x¯

3

1.

f(x)=

x1+x2

管理运筹学麻省理工讲座译文

4.

S

n

S

k≥2

x1

,...,xk

∈S

kλjxj∈S

j=1

kλ1,...,λk

λ1,...,λk≥0

j=1λj

=1.5.Bertsekas,16

x

f(·)

1.1.1.(

f(x )=0.)6.Bertsekas,

16

1.1.2,(a),(b),(c),(d).(

x f(x )=0.)

17

f(·)

本文来源：https://www.bwwdw.com/article/1gre.html