《最优化方法》复习题

一、 简述题

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

210x15x2是否为凸函数） （例如: 判断函数f(x)x122x1x22x22、写出几种迭代的收敛条件.

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

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

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

;

写出Goldstein、Wolfe非精确一维线性搜索的公式。

5、叙述常用优化算法的迭代公式．

kak(1)(bkak),（1）法的迭代公式：

kak(bkak).Fnk1a(bkak),kkFnk1(k1,2,（2）Fibonacci法的迭代公式：Fank(ba)kkkkFnk11gk． （3）Newton一维搜索法的迭代公式： xk1xkGk,n1)．

（4）推导最速下降法用于问题minf(x)1TxGxbTxc的迭代公式： 2gkTgkxk1xkTf(xk)

gkGkgxk（5）Newton法的迭代公式：xk1xk[2f(xk)]1f(xk)． （6）共轭方向法用于问题minf(x)1TxQxbTxc的迭代公式： 2f(xk)Tdkxk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(xtd)，其中f:RnR二阶可导，xRn,dRn,tR，试求(t)． 解 (t)f(xtd)Td,(t)dT2f(xtd)d．

（

1TxAxbTxc在任意点x处2

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

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

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

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

(0,1)，有

f(x(1)x)f(x)(1)f(x)f(x)．

当充分接近1时，可使x(1)xN(x)S，于是f(x)f(x(1)x)，矛盾．从而x是全局最优解．

minf(x)2x1x2x3;s..t3x1x2x360,x12x22x310, 4、已知线性规划：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.—

所给问题的最优解为x(0,20,0)T，最优值为f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、用法求解 min(t)(t3)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． 故x992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)

2241TxGxbTx的形式，则Q,b． 2243(1)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． 1/4(3/2,0)223/201/42407、用FR共轭梯度法求解

11minf(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(1))f(x(0))222， 9d1f(x(1))0d0(4/3,8/9,4/3)T．

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

142362214181418minf(x(1)d1)(,,)262

3902339232261423的最优解，得

1/24/33(2)3T1,xx(1)1d11/38/9(0,0,0)． 81/284/3此时

f(x(2))(0,0,0)T,f(x(2))00.01．

》

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

minfx1212x1x25x110x222Ts..t2x13x230取初始点0,5.

x14x220x1,x209、采用精确搜索的BFGS算法求解下面的无约束问题：

minf(x)解：取x(0)T122x1x2x1x2 2x1x2(1,1) B0I f(x)2xx

12第一步迭代：

0f(x(0))11201d(0)B0f(x(0))1，

()f(x(0)d(0))(1)2，令'()0，求得01/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011212112(1)(1)(1)B1f(x)，()f(xd)，令'()0，求得12。故

14d(1)00(2)(2)，由于，故为最优解。 xx(2)x(1)1d(1)f(x)0010、用有效集法求解下面的二次规划问题：

2minf(x)x12x22x14x2s.t.x1x210x10,x20.

解：取初始可行点x(0)

(0,0),A0A(x(0)){2,3}.求解等式约束子问题

2mind12d22d14d2s..td10,d20得解和相应的Lagrange乘子

d(0)(0,0)T,(2,4)T 故得

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

2mind12d22d14d2转入第二次迭代。求解等式约束子问题 得解

s..td10d(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}{1,2}

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

2mind12d22d12d2s..td1d20,d10

得解和相应的Lagrange乘子

!

d(2)(0,0)T,(2,0)T

由于(2)0，故得所求二次规划问题的最优解为

xx相应的Lagrange乘子为

(2)(0,1)T，

(2,0,0)T

最速下降法的优缺点：

优点：方法简单，计算量较小；最速下降法为全局收敛，对初 始点的要求很少。

缺点：最速下降法的收敛速度与变量的尺度关系很大，对有些 例子，在极小点附近产生显著的锯齿现象，收敛十分缓慢；最

，

速下降法的最速下降仅是一种局部性质，即从局部来看目标函数 的值下降得最快，但从总体来看它可能走了许多弯路。 牛顿法的优缺点：

优点：牛顿法的收敛速度快，为二阶收敛；公式简单， 计算方便。

缺点：牛顿法要求f(x)二阶可微，迭代中需多次计算 ；牛顿法具有局部收敛性，对初始点的要求比较苛刻。 共轭梯度法的优缺点：

优点：计算公式简单，存储量较小，对初始点要求很少，对二 次函数具有二次终止性；收敛速度介于最速下降法和牛顿法之 间，对高维（n 较大）的非线性函数具有较高的效率。对于二 次函数具有二次终止性，一般情况下优于共轭梯度法。 缺点：共轭梯度法的收敛性依赖于精确的一维搜索，计算量较 大；共轭梯度法的一些理论背景至今尚不清楚，如周期性的重新 开始，初始搜索放心的选取，一维搜索的精确性等，对共轭梯度 法执行的影响仍有待进一步研究。 拟牛顿法的优缺点：

优点：拟牛顿法具有较快的收敛速度（是超线性的）； 对于二次函数具有二次终止性，一般情况下优于共轭梯度法。

缺点：拟牛顿法需要的存储量较大，对大型计算不便；DFP法 远不如BFGS法数值稳定性好，BFGS法具有较强的数值计算 稳定性。