管理运筹学麻省理工讲座译文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)

…… 此处隐藏：1825字，全部文档内容请下载后查看。喜欢就下载吧 ……