最优化方法习题1答案

最优化方法习题1答案

《最优化方法》（研究生）期末考试练习题答案

二.简答题

min -5y1 9y2, s.t. 4y1 3y2 3, -2y1 y2 2, 1．

3y1 4y2 8, y1,y2 0;

x3 x4 0, （以x1为源行生成的割平面方程） 2．

注意：在x1为整数的情况下，因为x3,x4 0，该方程自然满足，这是割平面的退化情形

1

656

111

x3 x4 , （以x2为源行生成的割平面方程）

442

3．

a1 0,b1 3

1 a1 0.382(b1 a1) 0 0.382*3 1.146

1 a1 0.618(b1 a1) 0 0.618*3 1.854 ( 1) (1.146)3 2*1.146 1 0.2131 ( 1) (1.854)3 2*1.854 1 3.6648

事实上,不经计算也可以看出

( 1) ( 1)，所以a2 0,b2 1.854。

即：初始的保留区间为[0，1.854]。近似的最优解：x*

0 1.854

0.927.2

f1(x) x1e x2*( 1) 2.7 x1ex2 2.7

4．令

f2(x) x1e x2*(0) 1 x1 1f1(x) x1e

x2*(1)

0.4 x1e

x2

0.4

f1(x) x1e x2*(2) 0.1 x1e 2x2 0.1

拟合问题等价于求解下列最小二乘问题：min

(f(x))

i

i 1

4

2

三.计算题

1．分别用最速下降方法和修正的牛顿法求解无约束问题 minf(x) x1 4x2。 取初始点x

2

2

1

T

2,2 ， 0.1.

最优化方法习题1答案

解： f 2x 1

在初始点 x 1

2,2 T

8x 2 ，

，

f 4

16

从而最速下降法的搜索方向为：d1 4

16

.

最优步长 *满足f(x(1) *d1) min

f(x(1) d1)

其中

f(x(1) d1) f(2 4 ,2 16 ) (2 4 )2 4(2 16 )2.

求解得到： 17/130, 从而

x 2 2,2 T

17/130*(-4,-16)T (96/65, 6/65)T

在x 2

96/65, 6/65 T

， f 192/65 -48/65 ，

从而最速下降法的搜索方向为：d1 192/65

48/65

.

继续迭代,直至满足精度。

在初始点x 1 2,2 T

，

G 20 1

1/20 08 ,G 01/8

从而修正的牛顿法的搜索方向为：

d1 G 1 f 1/20 4 -2

01/8 16 -2

最优步长 *满足

f(x(1) *d1) minf(x(1) d1

)

f(x(1) d1) f(2 2 ,2 2 ) 5(2 2 )2. 1, 从而x 2 2 2 ,2 2 T

(0,0)T

在x 2 0,0 T

， f 0 0 ，显然满足精度。

2

f 20 x

(2) 正定， 08

x(2)即为所求的极小点。(1分)

易见：

最优化方法习题1答案

min

2．讨论约束极值问题

2

f(x) x12 x2 6x1 6x2 8

s.t.

x1 x2 4 x x 0

2 1

x1 0 x 0 2

的Kuhn-Tucker点。

f(x) [2x1 6,2x2 6]T

g1(x) x1 x2 4, g1(x) [1,1]T g2(x) x1 x2, g2(x) [1, 1]T

g3(x) x1, g3(x) [ 1,0]T。 g4(x) x2, g4(x) [0, 1]T

所以该约束问题的Kuhn-Tucker条件为

2x1 6 1 1 1 0 1 2 1 3 0 4 1 0 2x 6 1

2

(x x 4) 0

2

11

2(x1 x2) 0

3x1 0

4x2 0

x1 x2 4 0 x x 0

2

1

x1 0 x 0 2 1, 2, 3, 4 0

若x1 0,x2 0,则x1 x2 4 4 0, 从而 1 0。

代入第一个式子得到 6 2 3 0 6 2 4 0

从而 2 4 6 0,矛盾。

最优化方法习题1答案

若x1 0,x2 0,则x1 x2 0从而 2 0。又由于x2 0,从而 4 0

代入第一个式子得到 6 1 3 02x2 6 1 0

从而 1 3 6,2x2 6 3 6 2x2 3 0,与x2 0, 3 0矛盾。

若x1 0,x2 0,则x1 x2 0则 2 0, 3 0

代入第一个式子得到2x1 6 1 0 6 1 4 0

从而 1 4 6,2x1 6 4 6 2x1 4 0,与x1 0, 4 0矛盾。

若x1 0,x2 0,且x1 x2 0则 2 0。又由于x1 0,x2 0从而 3 0, 4 0,

代入第一个式子得到2x1 6 1 02x2 6 1 0

从而x1 x2,与x1 x2 0矛盾。

若x1 0,x2 0,x1 x2,但x1 x2 4则 1 0。又由于x1 0,x2 0从而 3 0, 4 0,

代入第一个式子得到2x1 6 2 02x2 6 2 0从而 1 2,

x1 x2 3,这与x1 x2 4矛盾。

x1 0,

x2 0,x1 x2 4,

讨论了所有的情况后,我们可以得出结论,从而(2,2)为该问题的一个Kuhn Tucker点.

3．构造増广函数

最优化方法习题1答案

x) (x 1)2 (x)2 2

12 3k(x1 x2 2)若x1 x2 2 0

k( (x2 (x2

1 1)2 3)

若x1 x2 2 0若x1 x2 2 0,则

由 2(x1 1) 0

k(x) 2(x 3)

2 0 ，可得

x1 1,x2 3,与x1 x2 2 0矛盾.若x1 x2 2 0,则

由 2(x1 1) 2 k(x1 x2 2) 0

k(x) 2(x 3) 2 k(x1 x2 2)

2 0 ，可得

x11

2 x1 2,x1 1 2 .从而x2 2

k1 2k这是对于固定的 k，minx R

2

k(x)的解. lim x1 k

lim

1

1 2 0

k k

x2 x1 2 2从而

x* (0,2)为原问题的最优解。

minf(x) x2

1 6x1 9 2x2

4．用内点法求解非线性规划

s.t. g1(x) x1 3 0 g2(x) x2 3 0

构造増广函数

2k(x) x1 6x1 9 2x2 k(

1x 1

3

)1 3x2

2x k 1 6 由 (x2 1 3) k(x) 0 k ，可得 2 0 (x

2 3)2 x k

1 3 k

2x2 3

2

这是对于固定的 k，min

x R

2

k(x)的解. lim k 3

k 0

x1 lim 0

3 k2

k

lim1 k 0

x lim3

k 0

2

3从而

x* (3,3)为原问题的最优解。

(4分)

(2分)

(4分)

(4分)

(2分)

(4分)

最优化方法习题1答案

5. 构造増广函数

1212

x1 x2 vk(x1 x2 1) k(x1 x2 1)226

x1 vk 2 k(x1 x2 1) 0

由 k(x) 1 0 ，可得 x v 2 (x x 1) 2 kk12

3

2 vk3(2 k vk)

x2 3x1,x1 k.从而x2

1 8 k1 8 k

k(x)

(4分)

(2分)

这是对于固定的 k，min k(x)的解.2

x R

k

lim x1 lim

2 k vk1

k 1 8 4k

(注意vk是一个数)

(4分)

3

x2 3x1

4从而

6．解：首先化成标准形式

13

x* (,)为原问题的最优解。

44

minZ 3x1 2x2 x3 Mx7 Mx8

x1 x2 x3 x4 6

x3 x5 x7 4 x1

x2 x3 x6 x8 3 x,x,x,x,x,x,x,x 0

以x1为换入变量，根据最小比值原则确定x7为换出变量。

最优化方法习 …… 此处隐藏：1996字，全部文档内容请下载后查看。喜欢就下载吧 ……