《最优化方法》复习题

《最优化方法》复习题

一、 简述题

1、怎样判断一个函数是否为凸函数.

2

（例如: 判断函数f(x) x12 2x1x2 2x2 10x1 5x2是否为凸函数）

2、写出几种迭代的收敛条件.

3、熟练掌握利用单纯形表求解线性规划问题的方法（包括大M法及二阶段法）.

见书本61页(利用单纯形表求解);

69页例题 (利用大M法求解、二阶段法求解); 4、简述牛顿法和拟牛顿法的优缺点. 简述共轭梯度法的基本思想.

写出Goldstein、Wolfe非精确一维线性搜索的公式。 5、叙述常用优化算法的迭代公式．

k ak (1 )(bk ak),

（1）0.618法的迭代公式：

a (b a).kkk k

Fn k 1

a (bk ak),k k

Fn k 1

(k 1,2, ,n 1)． （2）Fibonacci法的迭代公式：

F a n k(b a)

kkkk Fn k 1

1

gk． （3）Newton一维搜索法的迭代公式： xk 1 xk Gk

（4）推导最速下降法用于问题minf(x)

1T

xGx bTx c的迭代公式： 2

gkTgk

xk 1 xk T f(xk)

gkGkgxk

（5）Newton法的迭代公式：xk 1 xk [ 2f(xk)] 1 f(xk)． （6）共轭方向法用于问题minf(x)

1T

xQx bTx c的迭代公式： 2

f(xk)Tdk

xk 1 xk dk．

dkTQdk

二、计算题

双折线法练习题 课本135页 例3.9.1 FR共轭梯度法例题：课本150页 例4.3.5 二次规划有效集：课本213页例6.3.2,

所有留过的课后习题.

三、练习题：

1、设A Rn n是对称矩阵，b Rn,c R，求f(x) 的梯度和Hesse矩阵．

解 f(x) Ax b, 2f(x) A． 2、设 ()t f(xdt )

，其中f:Rn R二阶可导，x Rn,d Rn,t R，试求 (t)．

1T

xAx bTx c在任意点x处2

解 (t) f(x td)Td, (t) dT 2f(x td)d．

3、证明：凸规划minf(x)的任意局部最优解必是全局最优解．

x S

证明 用反证法．设 S为凸规划问题minf(x)的局部最优解，即存在的某

x S

个 邻域N ()，使f() f(x), x N () S．若不是全局最优解，则存在

) f()．由于f(x)为S上的凸函数，因此 S，使f(xx

(0,1)，有

) f() (1 )f(x ) f()． f( (1 )x

N () S，于是f() f( (1 )x )，当 充分接近1时，可使 (1 )x

矛盾．从而是全局最优解．

minf(x) 2x1 x2 x3;

s..t3x1 x2 x3 60,

4、已知线性规划： x1 2x2 2x3 10,

x1 x2 x3 20, x1,x2,x3 0.

（1）用单纯形法求解该线性规划问题； （2）写出线性规划的对偶问题；

解 （1）引进变量x4,x5,x6，将给定的线性规划问题化为标准形式：

minf(x) 2x1 x2 x3;

s..t3x1 x2 x3 x4 60,

x1 2x2 2x3 x5 10, x1 x2 x3 x6 20, x1,x2, ,x6 0.

所给问题的最优解为 (0,20,0)T，最优值为 20． （2）所给问题的对偶问题为：

maxg(y) 60y1 10y2 20y3; s..t 3y1 y2 y3 2,

y1 2y2 y3 1,

y1 2y2 y3 1, y1,y2,y3 0.

5、用0.618法求解 min (t) (t 3)2，要求缩短后的区间长度不超过0.2，初始区间取[0,10]． 解 第一次迭代： 取[a1,b1] [0,10], 0.2． 确定最初试探点 1, 1分别为

1 a1 0.382(b1 a1) 3.82， 1 a1 0.618(b1 a1) 6.18．

求目标函数值： ( 1) (3.82 3)2 0.67， ( 1) (6.18 3)2 10.11． 比较目标函数值： ( 1) ( 1)． 比较 1 a1 6.18 0 0.2 ． 第二次迭代：

a2 a1 0,b2 1 6.18, 2 1 3.82, ( 2) ( 1) 0.67．

2 a2 0.382(b2 a2) 0.382(6.18 0) 2.36, ( 2) (2.36 3)2 0.4．

( 2) ( 2), 2 a2 3.82 ． 第三次迭代：

a3 a2 0,b3 2 3.82, 3 2 2.36, ( 3) ( 2) 0.4．

3 a3 0.382(b3 a3) 0.382(3.82 0) 1.46, ( 3) (1.46 3)2 2.37．

( 3) ( 3),b3 3 3.82 1.46 ．

第四次迭代：

a4 3 1.46,b4 b3 3.82, 4 3 2.36, ( 4) ( 3) 0.4．

4 a4 0.618(b4 a4) 1.46 0.0.618(3.82 1.46) 2.918, ( 4) 0.0067． ( 4) ( 4),b4 4 3.82 2.36 ． 第五次迭代：

a5 4 2.36,b5 b4 3.82, 5 4 2.918, ( 5) ( 4) 0.0067．

5 a5 0.618(b5 a5) 3.262, ( 5) 0.0686．

( 5) ( 5), 5 a5 3.262 2.36 ． 第六次迭代：

a6 a5 2.36,b6 5 3.262, 6 5 2.918, ( 6) ( 5) 0.0067．

6 a6 0.382(b6 a6) 2.7045, ( 6) 0.087．

( 6) ( 6),b6 6 3.262 2.7045 ． 第七次迭代：

a7 6 2.7045,b7 b6 3.262, 7 6 2.918, ( 7) ( 6) 0.0067．

7 a7 0.618(b7 a7) 3.049, ( 7) 0.002． ( 7) ( 7),b7 7 ． 第八次迭代：

a8 7 2.918,b8 b7 3.262, 8 7 3.049, ( 8) ( 7) 0.002．

8 a8 0.618(b8 a8) 3.131, ( 8) 0.017． ( 8) ( 8), 8 a8 ． 第九次迭代：

a9 a8 2.918,b9 8 3.131, 9 9 3.049, ( 9) ( 8) 0.002．

9 a9 0.382(b9 a9) 2.999, ( 9) 0.000001． ( 9) ( 9), 9 a9 3.049 2.918 ．

故

9 9

2

3.024．

2

4x1 3x2,取x(0) (1,1)T,迭代6、用最速下降法求解 minf(x) x12 2x1x2 2x2

两次．

解 f(x) (2x1 2x2 4,2x1 4x2 3)T， 将f(x)写成f(x) 第一次迭代：

x

(1)

22 4 1T

,b xGx bTx的形式，则Q ．

2 24 3

x

(0)

f(x(0))T f(x(0)) f(x(0)) (0)T(0) f(x)G f(x)

0 (0,3)

1 0 1 3 ． 220131/4 (0,3)

24 3

第二次迭代：

x

(2)

f(x(1))T f(x(1))(1)

x f(x) (1)T(1)

f(x)G f(x)

(1)

3/2

( 3/2,0)

0 1 3/2 7/4 ． 22 3/21/401/4 ( 3/2,0) 24 0

7、用FR共轭梯度法求解

11

minf(x) (x1 x2 x3)2 ( x1 x2 x3)2 (x1 x2 x3)2，取x(0) (,1,)T，迭代

22

两次．若给定 0.01,判定是否还需进行迭代计算． 解 f(x) 3(x12 x22 x32) 2(x1x2 x1x3 x2x3)，

6 2 2

1

再写成f(x) xTGx，G 26 2 ， f(x) Gx．

2 2 26

第一次迭代：

f(x(0)) (0,4,0)T，令d0 f(x(0)) (0, 4,0)T，

从x(0)出发，沿d0进行一维搜索，即求minf(x(0) d0) 2 16 48 2的最优解，

0

得

0 1/6,x(1) x(0) 0d0 (1/2,1/3,1/2)T．

第一次迭代：

f(x(1)) (4/3,0,4/3)T． 0

f(x) f(x(0))

(1)

22

2

， 9

d1 f(x(1)) 0d0 ( 4/3, 8/9, 4/3)T．

从x(1)出发，沿d1进行一维搜索，即求

14 2 3

6 2 2

14181418

minf(x(1) d1) ( , , ) 26 2

39 0233923

2 26 14

23

的最优解，得

1 ,x(2)

此时

38

1/2 4/3 3

x(1) 1d1 1/3 8/9 (0,0,0)T．

1/2 8 4/3

f(x(2)) (0,0,0)T, f(x(2)) 0 0.01 ．

得问题的最优解为 (0,0,0)T，无需再进行迭代计算． 8、求解问题 （方法不限定）

minf x

1212

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