最优化方法试题答案

?

f

一、

填空题

f

(

x

)

?

?

x 1

x

2

?????

2

1

?? ???? ??

x 1

????

?

?1

3?????

x 1

????

，

则

1.若

1

2

x

2

x

2

(x

)

?

，

?

2

f

(

x

)

?

.

2.设

f

连续可微且

?

f

(

x

)

?

0

，若向量

d

f

在

x

处的一

满足，则它是

个下降方向。

3.向量有

( 1 ,

2 , 3 )

T

关于3 阶单位方阵的所有线性无关的共轭向量

.

4. 设

f

:

R

n ?

R

二次可微，则

f

在

x

处的牛顿方向为

.

5.举

出

一

个

具

有

二

次

终

止

性

的

无

约

束

二

次

规

划

算

.

法：

6.以下约束优化问题：

1 2

min

f

(

x

)

?

x 1 2

?

x

2

2

s . t

.

x 1

?

x

2

?

1

的外点罚函数为（取罚参数为

?）

.

二、证明题（7分+8分）

1.设

g

i

:

R

n

?

R

,

i

?

1 ,

2 ,

?

m 1

和

h i

:

R

n

?

R

,

i

?

m 1?

1 ,

?

m

都是线性函数，证明下

面的约束问题：

是凸规划问题。

min

f

(

x

)

n ?? k?1

x

2

n

i

?

I

?

{ 1 ,

?

m 1

}

?

,

m }

k

s . t

.

g

i

(

x

)

?

0 ,

h

j (

x

)

?

0 ,

j

?

E

?

{ m 1

?

1 ,

?

2.设

f

:

R

2

?

R

连续可微，

a ?i

R

，

hi ?

R

，

i

?

1 ,

2 ,

m，考察如下的约束条件

问题：

设

d

是问题

d

是

f

min

f

(

x

)

m 1

}

m }

s . t

.

a

T i

x

?

b i

?

0 ,

i

?

I

?

{ 1 ,

2

?

在

x

a

i

T

x

?

b i

?

0 ,

i

?

E

?

{ m 1

?

1 ,

?

min

?f

(

x

)

T

d

s . t

.

a

T i

d

?

0 ,

i

?

I

a

i

T

d

?

0 ,

i

?

E

||

d

||?

1

的解，求证：

处的一个可行方向。

三、计算题（每小题12分）

1.取初始点

x

(

0

)

?

( 1 , 1 )

T

.采用精确线性搜索的最速下降法求解下面的无约束优化问题

（迭代2步）：

min f ( x )?x 1 2?2 x 2 2 2.采用精确搜索的BFGS 算法求解下面的无约束问题： min 2 s . t . ?x 1?x 2?1?0
x 1	?	0	,	x	2	?	0 .

4.用可行方向算法（Zoutendijk算法或FrankWolfe算法）求解下面的问题（初

值设为	x	(	0	)	?	(	0 , 0 )	,计算到	x	(	2	)	即可)：											x	x		?	x	2	?	2	x
									min					f	(	x	)	?		1	x 1 2		?
																				2				1		2			2			1
									s . t		.		3		x 1		?	x		2	?	3
									x 1						?		0	,	x	2	?	0 .

参
一、填空题

? 1. ???

4

x 1

?

2

x

2

?

1

????

(

x

)

? ?? ?

4 2

(

2 4

? ?? ?

2. ?f

(

x

)

T

d

?

0

3. ( ?1 , 0 )

T

，

( 3 , 0 ,

?1 )

T

（答案不

2

?

4

x

?

3

x 1

2

唯一）。 4.

?

?

2

f

?1

?

f

x

)

5.牛顿法、修正牛顿法等（写出一个即可）
6.

?

x

L

(

x

,

?

?)

?

????

1

?

??

2?x 1

????

?

????

0

? ?? ?

??

0

?

x

2

?

x 1 2

?

1

?

0

?

0

??

0 ,

x 1

?

x

2

?

0 ,

?(

x 1

?

x

2

)

2

?

1 )

2

2

2

?

1

?(

x 1

?

F?(

x

)

?

x 1

2

?

7.

2

二、证明题
1.证明：要证凸规划，即要证明目标函数是凸函数且可行域是凸集。

一方面，由于

f

二次连续可微， 正定，根据凸函数等价条件可知目标函

数是凸函数。

故?x

?

( 1

?

?)

y

?

D

，从而可行域是凸集。

2.证明：要证

d

是

f

在

x

处的一个可行方向，即证当

x ?

D

，

d ?

R

n

时，

??

?

0

，

使得

x

??d

?

D

，??

(

0 ,?]

当

i ?

I

时，

a i

T

x

?

b i

?

0

，

a i

T

d

?

0

，故

a i

T

(

x

?

?d

)

?

b i

?

a i

T

x

?

b i

?

?a i

T

d

?

0

；

当

i ?

E

时，

a

i

T

x

?

b i

?

0

，

a

i

T

d

?

0

，故

a i

T

(

x

?

?d

)

?

b i

?

a i

T

x

?

b i

?

?a i

T

d

?

0

.

因此，

d

是

f

在

x

处的一个可行方向。

三、计算题

1.解：?(?)				?	f	(	x		?		?d			)	?			(	x 1			?		?d		1	)	2	?		2 (		x	2	?		?d		2	)	2
令?	(?)	?	0																								?		f	(	x	)			??	2	x 1
				得?				?		?		d	1	x		1	?2			d		2	x	2	；														??
																																	?
												d		1	2		?		2		d	2	2												??	4	x	2	??

第一次迭代：

?

f

(

x (

0

)

)

?

????

2

? ?? ?

，

d

(

0

)

?

??f

(

x

(

0

)

)

?

????

?

2

????

，

?(?)

?

f

(

x (

0

)

?

?d

(

0

) )

，令

4

?

4

?

(?)

?

0

，求得?0?

5

/

18

；

第

二

次

迭

代

：

x

( 1 )

?

)

?

?0

d

(

0

?

?? ? ? ??

4

1

?? ? ? ??

，

?

f

(

x

( 1 )

?

?? ? ? ??

8

2

?? ? ? ??

，

x

(

0

)

9

)

9

?

?

9

9

d

( 1 )

?

??

f

(

x

( 1 )

)

?

??? ?2? ?9

8

?? ? ? ??

，

9

?(?)

?

f

(

x

( 1 )

?

?d

( 1 )

)

，令

?(?)

?

0

，求得

?1?

1

/

2

，故

x (

2

)

?

x

( 1 )

?

?1 d

( 1 )

?

????

0

??

，由

0

??

于?f ( x ( 2 ) )? ? ?? ? 0 0????，故x ( 2 ) 为最优解。

2.解：取

x

(

0

)

?

( 1 , 1 )

T

B ?0

I

?

f

(

x

)

?

????

x 1

?

x

2

? ?? ?

2

x

2

?

x 1

第一步迭代：

?	f	(	x	(	0	)	)	?		????		0		????	d	(	0	)	(	?		?		B 0		?1?		f	(	x	(	0	)	)	?	????	0	?1???	，	?	0	，求得??	1	/	2	；
												1																									?
?(?)				?			f	(	x		(	0	)	?	?d					0	)	)	?		1		?	( 1	?		?)			2	?	?，令?(?)
																									2																	0

第二步迭代：

	( 1 )		?		x	(	0	)		?			?0	d		(	0	)		?			?? ???			1			?? ???	，				?			f		(	x		( 1 )			)		?		?? ???	1		?? ???		，			s		0		?		x	( 1 )									??	0	1	? ? ?? ?
x																										1																								2								(		)							?	x	(	0	)	?	?	?
																																																		0
																										2																																															?		2
y	(	0	)	?	?f				(	x			( 1 )	)	?		?				f		(		x		(	0	)	)		?		? ? ?? ?			1		? ?
																																					2		?
																																					?		1? ?
B 1			?	?1 ? ?0		0							?	???	0			0					???			?			?1 / ? ??				2						?1? 2? ?						?		?3 / ? ??				2		?1? 2? ?
						1									0			1															1																		1
d	( 1 )		?		?	B 1					?1?			f	(	x		( 1 )				)	?				?? ? ? ??		?		1			?? ? ? ??		，?(?)											?		f		(		x		( 1 )		?		?d			( 1 )		)			，令?(?)							?	0			。故
																															2																																													，求得?1?	2
																													?		1
																															4
x	(	2	)?		x	( 1 )				?		?1 d			( 1 )				?				????		0 0			????	，由于											?		f		(		x	(	2 )	)		?		????		0	????		，故				x		(	2	)	为最优解。
																																																							0
3.解：取初始可行点																									x		(0)				?			(0,0),									A 0				?		A x				(0)			)		?		{2,3}.							求解等式约束子问题
min																								d 1 2					?		d		2		?			2			d 1			?		4		d	2