《最优化方法》复习题

1、最优化方法复习题一、简述题1、怎样判断一个函数是否为凸函数.(例如：判断函数f(x)=x2+2xx+2x2-10 x+5x是否为凸函数)122122、写出几种迭代的收敛条件.3、熟练掌握利用单纯形表求解线性规划问题的方法(包括大M法及二阶段法).见书本61页(利用单纯形表求解);69页例题(利用大M法求解、二阶段法求解)；4、简述牛顿法和拟牛顿法的优缺点.简述共轭梯度法的基本思想.写出Goldstein、Wolfe非精确一维线性搜索的公式。5、叙述常用优化算法的迭代公式(1)0.618法的迭代公式：人=ak+(1-叫一叮|p=a+t(ba).kkkk(k_1,2,n1)九=a+nk1(ba),

2、kkFkk2)Fibonacci法的迭代公式：nk+1|lx_a+nk(ba)kkFkknk+13)Newton一维搜索法的迭代公式：x_xG1gk+1kkk(4)推导最速下降法用于问题minf(x)_-xtGx+bTx+c的迭代公式:2x_x-gkTgkVf(x)k+1kgTGgxkkkkNewton法的迭代公式：x_xV2f(x)-iVf(x)k+1kkk共轭方向法用于问题minf(x)_-xtQx+bTx+c的迭代公式:2x_xk+1kdTQdkk二、计算题双折线法练习题课本135页例3.9.1FR共轭梯度法例题：课本150页例4.3.5二次规划有效集：课本213页例6.3.2,所有留过

3、的课后习题.三、练习题：1、设AeRnxn是对称矩阵，beRn,ceR,求f(x)=xtAx+bTx+c在任意点x处2的梯度和Hesse矩阵解Vf(x)=Ax+b,Vf(x)=A2、设申(t)=f(x+td),其中f:RntR二阶可导，xeRn,deRn,teR,试求(t)解0(t)=Vf(x+td)Td,0(t)=dTVf(x+td)d3、证明：凸规划minf(x)的任意局部最优解必是全局最优解.xeS证明用反证法设xeS为凸规划问题minf(x)的局部最优解，即存在x的某xeS个5邻域N(x)，使f(x)f(x),VxeN(无)S.若x不是全局最优解，则存在o5xeS，使f(x)f(x)由

4、于f(x)为S上的凸函数，因此VXe(0,1)，有f(九x+(1一九)x)九f(x)+(1一九)f(x)f(x)-当X充分接近1时，可使Xx+(1-X)xeN(x)nS，于是f(x)f(Xx+(1-X)x),5矛盾从而x是全局最优解.minf(x)=2x-x+x;13s.t3x+x+x60,4、已知线性规划：q13x-2x+2x10,13x+x-x0.1231)用单纯形法求解该线性规划问题；2)写出线性规划的对偶问题；解(1)引进变量x,x,x，将给定的线性规划问题化为标准形式：456minf(x)=2x-x+x;TOC o 1-5 h z123s.3x+x+x+x=60,12340.V126

5、所给问题的最优解为X二(0,20,0)T，最优值为f=-20(2)所给问题的对偶问题为：maxg(y)=-60y-10y-20y；TOC o 1-5 h z123s.t3yyy2,123y+2yy1,123y2y+y.1235、用0.618法求解minQ(t)=(t3)2，要求缩短后的区间长度不超过0.2，初始区间取0,10解第一次迭代：取a,b=0,10,s=0.2.11确定最初试探点九，卩分别为11X=a+0.382(b一a)=3.82,p=a+0.618(b一a)=6.18.1111111求目标函数值：Q(X)=(3.823)2=0.67,Q(p)=(6.183)2=10.11.11比较

6、目标函数值：Q(X)0.2=s11第二次迭代：a=a=0,b=p=6.18,p=X=3.82,Q(p)=Q(X)=0.671212121X=a+0.382(ba)=0.382(6.180)=2.36,Q(X)=(2.363)2=0.42222Q(X)s222第三次迭代：a=a=0,b=p=3.82,p=X=2.36,Q(p)=Q(X)=0.4TOC o 1-5 h z2323232X=a+0.382(ba)=0.382(3.820)=1.46,Q(X)=(1.463)2=2.373333Q(X)Q(p),bX=3.821.46s333第四次迭代：a=九=1.46,b=b=3.82,九=2.36

7、,甲(九)=q(p)=0.4.TOC o 1-5 h z3434343p二a+0.618(b-a)二1.46+0.0.618(3.82-1.46)二2.91&甲(卩)二0.0067.4444甲(九)申(p),b九二3.82-2.368.444第五次迭代：a=X=2.36,b=b=3.82,九=p=2.91&甲(九)=甲(p)=0.0067.4545454p=a+0.618(b一a)=3.262,甲(p)=0.0686.5555甲(九)(p),p-a=3.262一2.368.555第六次迭代：a=a=2.36,b=p=3.262,p=X=2.91&Q(p)=甲(九)=0.0067.5656565

8、X=a+0.382(b-a)=2.7045,Q(X)=0.087.6666Q(X)Q(p),b-X=3.262-2.70458666第七次迭代：a=X=2.7045,b=b=3.262,X=p=2.918,Q(X)=Q(p)=0.0067TOC o 1-5 h z6767676p=a+0.618(ba)=3.049,Q(p)=0.0027777Q(X)Q(p),b-X8777第八次迭代：a=X=2.918,b=b=3.262,X=p=3.049,Q(X)=Q(p)=0.0027878787p=a+0.618(ba)=3.131,Q(p)=0.0178888Q(X)8888第九次迭代：a=a=2

9、.918,b=p=3.131,p=X=3.049,Q(p)=Q(X)=0.0028989998X=a+0.382(ba)=2.999,Q(X)=0.0000019999Q(X)Q(p),p-a=3.049-2.91889996、用最速下降法求解minf(x)=x2+2xx+2x24x1123x,取x(0)12=(1,1)T,迭代两次解Vf(x)=(2x+2x一4,2x+4x一3)t，1212将f(x)写成f(x)=-xtGx+bTx的形式,2(22(413丿第一次迭代：x(1)二x(0)Vf(x(0)TVf(x(0)Vf(x(0)TGVf(x(0)Vf(x)(0,3)(01=(11(0,3)U

10、/4丿第二次迭代：x二x(1)Vf(x(1)TVf(x(1)Vf(x(1)Vf(x)tGV(x(1)(3/2,0)11/4l丿(3/2,0)(3/210I-2-26-2-2-26丿(14-九318914.人123丿的最优解,(1/2(-4/3、3九=,x(2)=x(1)+九d=1/33+-8/918118J/2丿4/3=(0,0,0)T.此时Vf(x)=(0,0,0)t,|Vf(x)|=00.01=s.得问题的最优解为x=(0,0,0)t，无需再进行迭代计算.8、求解问题(方法不限定)minf(x)=x-10 x2122st2x-3x3012x+4x012取初始点(0,59、采用精确搜索的BF

11、GS算法求解下面的无约束问题:minf(x)=解：取x(0)二(1,1)TB二I0第一步迭代：(0)Vf(x(0)二1V1丿/x-x12V2x-x21d(o)二-B-1Vf(x(o)二0、v-1丿(a)=f(x(0)+ad(0)=-+(1-a)2+a，令(a)=0，求得a二1/2；20第二步迭代：(11(11(0、x(1)=x(0)+ad(0)=01，Vf(x(1)=2，s(0)=x(1)-x(0)=1V2丿V0丿2丿(-1y(0)=Vf(x(1)-Vf(x(0)=2V-1?d(1)=-B-1Vf(x(1)=(a)=f(x(1)+ad(1),令(a)=0，求得a12。故001/2-+01-12

12、10B=1|_013/2-1-12(1(01x=x+ad=1V0丿(01由于Vf(x)=0，故x为最优解。010、用有效集法求解下面的二次规划问题：minf(x)=x2+x2-2x-4x1212s.t.xx+1n012xn0,xn0.12解：取初始可行点x(0)=(0,0)，A0=A(x(0)=2,3.求解等式约束子问题mind2+d2-2d-4d1212s.t.d=0,d=012得解和相应的Lagrange乘子d(0)=(0,0)t,九=(2,4)t故得x(1)=x(0)=(0,0)T,A=A3=210转入第二次迭代。求解等式约束子问题mind2+d22d4d1212s.t.d=01得解d(

13、1)=(0,2)t主0计算TOC o 1-5 h z.门baTx(i).1cbaTx(i)1ex=ninl,_iii=1,3,aTd0，故得所求二次规划问题的最优解为x*=X(2)=(0,1)T，相应的Lagrange乘子为X*=(2,0,0)t最速下降法的优缺点：优点：方法简单，计算量较小；最速下降法为全局收敛，对初始点的要求很少。缺点：最速下降法的收敛速度与变量的尺度关系很大，对有些例子，在极小点附近产生显著的锯齿现象，收敛十分缓慢；最速下降法的最速下降仅是一种局部性质，即从局部来看目标函数的值下降得最快，但从总体来看它可能走了许多弯路。牛顿法的优缺点：优点：牛顿法的收敛速度快，为二阶收敛；公式简单，计算方便。缺点：牛顿法要求f（x）二阶可微，迭代中需多次计算；牛顿法具有局部收敛性，对初始点的要求比较苛刻。共轭梯度法的优缺点：优点：计算公式简单，存储量较小，对初始点要求很少，对二次函数具有二次终止性；收敛速度介于最速下降法和牛顿法之间，对高维（n较大）的非线性函数具有较高的效率。对于二次函数具有二次终止性，一般情况下优于共轭梯度法。缺点：共轭