最优化方法(试题+答案)

一、 填空题

1.若f(x) x1

x1 21 x1

x2 13则 f(x) ， 12 x x ，

2 2

2f(x) 2.设f连续可微且 f(x) 0，若向量d满足 ，则它是f在x处的一个下降方向。

3.向量(1,2,3)T关于3阶单位方阵的所有线性无关的共轭向量有4. 设f:Rn R二次可微，则f在x处的牛顿方向为5.举出一个具有二次终止性的无约束二次规划算法： .

6.以下约束优化问题：

minf(x) x1

s.t.h(x) x2 x12 1 0

g(x) x1 x2 0

的K-K-T条件为：

. 7.以下约束优化问题：

2

minf(x) x12 x2

s.t.x1 x2 1

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

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

1.设gi:Rn R,i 1,2, m1和hi:Rn R,i m1 1, m都是线性函数，证明下面的约束问题：

2

minf(x) xk

k 1n

s.t.gi(x) 0,

hj(x) 0,

是凸规划问题。

i I {1, m1}j E {m1 1, ,m}

2.设f:R R连续可微，ai R，hi R，i 1,2, m，考察如下的约束条件问题：

2n

minf(x)

s.t.aix bi 0,i I {1,2 m1}

aix bi 0,i E {m1 1, m}

设d是问题

TT

min f(x)Tds.t.aid 0,i I

aid 0,i E||d|| 1

的解，求证：d是f在x处的一个可行方向。

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

1.取初始点x(0) (1,1)T.采用精确线性搜索的最速下降法求解下面的无约束优化问题（迭代2步）：

2

minf(x) x12 2x2

TT

2.采用精确搜索的BFGS算法求解下面的无约束问题：

minf(x)

122

x1 x2 x1x2 2

3.用有效集法求解下面的二次规划问题：

2

minf(x) x12 x2 2x1 4x2

s.t. x1 x2 1 0x1 0,x2 0.

4.用可行方向算法（Zoutendijk算法或Frank Wolfe算法）求解下面的问题（初值设为x

(0)

(0,0),计算到x(2)即可)：

minf(x)

122x1 x1x2 x2 2x12

s.t.3x1 x2 3x1 0,x2 0.

参考答案

一、填空题 1.

4x1 2x2 1

2x1 4x2 3 42 24

2. f(x)Td 0

3. (2, 1,0)T，(3,0, 1)T（答案不唯一）。 4. 2f(x) 1 f(x)

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

6.

1 2 x1 0

xL(x, , ) 0

x2 x12 1 0

0,x1 x2 0, (x1 x2) 0

7. F (x) x1 x2

2

2

1

(x1 x2 1)2 2

二、证明题

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

2

一方面，由于f二次连续可微， f(x) 2I正定，根据凸函数等价条件可知目标函

数是凸函数。

另一方面，约束条件均为线性函数，若任意x,y D可行域，则

gi( x (1 )y) gi(x) (1 )gi(y) 0hj( x (1 )y) hj(x) (1 )hj(y) 0

故 x (1 )y D，从而可行域是凸集。

i Ii E

n

2.证明：要证d是f在x处的一个可行方向，即证当x D，d R时， 0，使得

x d D， (0, ]

当i I时，aix bi 0，aid 0，故ai(x d) bi aix bi aid 0； 当i E时，aix bi 0，aid 0，故ai(x d) bi aix bi aid 0. 因此，d是f在x处的一个可行方向。

T

T

T

T

T

T

T

T

T

T

三、计算题

1.解： ( ) f(x d) (x1 d1)2 2(x2 d2)2 令 '( ) 0 得

(0)(0)

第一次迭代： f(x(0)) ，d f(x)

d1x1 2d2x2d1 2d2

2 4

2

2

； f(x)

2x1

4x2

2 (0)(0)

， ( ) f(x d)， 4

令 '( ) 0，求得 0 5/18；

第二次迭代：x

(1)

x(0) 0d(0)

4 8 8 999 (1)(1)(1) ， ， f(x) d f(x) ，

2 1 2 9 9 9

( ) f(x(1) d(1))，令 '( ) 0，求得 1 1/2，故x(2) x(1) 1d(1) 0 ，由

于 f(x(2)) ，故x

0

0

0

(2)

为最优解。

2.解：取x

(0)

(1,1)T B0 I

x1 x2

f(x) 2x x

1 2

第一步迭代：

0

f(x(0)) 1

0 1

d(0) B0 f(x(0)) 1

，

( ) f(x(0) d(0))

第二步迭代：

1

(1 )2 ，令 '( ) 0，求得 0 1/2； 2

x(1) x(0) 0d(0)

1 1 0

1 ， f(x(1)) 2 ，s(0) x(1) x(0) 1 0

2 2

y(0)

1

f(x(1)) f(x(0)) 2

1

10 00 1/2 1 3/2 1 B1 01 12 12

01

1

12 B1 f(x(1)) ， ( ) f(x(1) d(1))，令 '( ) 0，求得 1 2。故

1 4

d(1)

x

(2)

x

(1)

1d

(1)

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

3. 解：取初始可行点x(0) (0,0),A0 A(x(0)) {2,3}.求解等式约束子问题

2

mind12 d2 2d1 4d2

s..td1 0,d2 0

得解和相应的Lagrange乘子

d(0) (0,0)T, ( 2, 4)T

故得

x(1) x(0) (0,0)T,A1 A0\{3} {2}

转入第二次迭代。求解等式约束子问题

得解

2

mind12 d2 2d1 4d2

s..td1 0

d(1) (0,2)T 0

计算

bi aiTx(1)b1 a1Tx(1)1T(1)

1 min{1,T(1)i 1,3,aid 0}

aidaiTd(1)2

令

x(2) x(1) 1d(1) (0,1)T,A2 A1} {1,2} 1 {转入第三次迭代。求解等式约束子问题

2

mind12 d2 2d1 2d2

s..td1 d2 0,d1 0

得解和相应的Lagrange乘子

d(2) (0,0)T, (2,0)T

由于

(2)

0，故得所求二次规划问题的最优解为

(2)

x x相应的Lagrange乘子为

4.解：计算梯度得

(0,1)T，

(2,0,0)T

f(x) (2x1 x2 2,2x2 x1)T

(0)T(0)

当k 0时，x (0,0)， f(x) ( 2,0).y是下面线性规划问题的解：

min f(x(0))y 2y1s.t.3y1 y2 3y1 0,y2 0.

解此线性规划（作图法）得y索

(0)

(2/3,0)T，于是d(0) y(0) x(0) (2/3,0)T.由线性搜

minf(x(0) td(0))

0 t 1

224t t 93

得t0 1.因此，x(1) x(0) t0d(0) (2/3,0)T.重复以上计算过程得下表：