北航数学规划基础答案2016最新.pdf 44页

'数学规划基础部分习题参考解答刘红英编北京航空航天大学数学与系统科学学院2016年4月 内容简介本书是《数学规划基础》(刘红英，夏勇，周水生，北京航空航天大学出版社，2012.10)的配套教学辅导材料，较详细地给出了该教材各章后部分习题的参考解答. 前言本习题解答自2008年春季开始编写，当时由硕士研究生阎凤玉提供部分习题解答，经讨论和确认后，由作者首次录入排版.后来陆续参加习题解答修订的硕士研究生包括王浩、欧林鑫、朱丽媛、易彩霞、杨茜和杨欣，其中的数值结果由欧林鑫提供.作者在此向他们的辛勤劳动表示衷心的感谢.本解答得到了？项目的资助，在此表示感谢.由于这些参考解答尚未经过特别严格的校对，仅供参考.任何意见、建议或其它反馈都可以发送至liuhongying@buaa.edu.cn，在此深表感谢.刘红英2016.4于北京 目录第一章引言1第二章线性规划:基本理论与方法3第三章线性规划：应用及扩展23第四章无约束优化：基础27第六章无约束优化：线搜索法31第六章无约束优化：信赖域法375 第一章引言1.2(该练习的目的是提高你的建模技巧，同时熟悉利用计算机求解线性优化问题)一个原油精练场有8百万桶原油A和5百万桶原油B用以安排下个月的生产.可用这些资源来生产售价为38元/桶的汽油，或者生产售价为33元/桶的民用燃料油.有三种生产过程可供选择，各自的生产参数如下：过程1过程2过程3输入原油A315输入原油B513输出汽油413输出燃料油314成本(单位：元)511140除成本外，所有的量均以桶为单位.例如，对于第一个过程而言，利用3桶原油A和5桶原油B可以生产4桶汽油和3桶民用燃料油，成本为51元.表格中的成本指总的成本(即原油成本和生产过程的成本).将此问题建模成线性规划，其能使管理者极大化下个月的净利润.请利用Lingo,Cplex或Matlab在计算机上求解此问题.解:设下个月利用第一个过程生产x次,第二个过程生产y次,第三个过程生产z次.则利润为f(x,y,z)=(38×4+33×3−51)x+(38+33−11)y+(38×3+33×4−40)z=200x+60y+206z其数学模型为maximize200x+60y+206zsubjectto3x+y+5z≤80000005x+y+3z≤5000000x,y,z≥0,且x,y,z是整数.忽略掉整性要求后，调用Matlab中的linprog.m函数求解，得最优解x=0,y=500000,z=1500000，自动满足整性要求.1.3利用图解法和优化软件两种方法求解下列问题minimize(x1−2)2+(x2−1)2subjecttox21−x2≤0,x1+x2≤2.1.4确定下列n元函数的梯度向量和Hessian阵：(a)aTx:a是常向量；(b)xTAx:A是非对称的常矩阵；(c)1xTAx−bTx:A是对称的常矩阵，b是常向量；2TTTT(d)r(x)r(x):r(x)=(r1(x),···,rm(x))是依赖于x的m维向量，记∇r为A，它一般不是常量.1 2第一章引言解:(a)∇f(x)=a,∇2f(x)=0n×n;(b)∇f(x)=(A+AT)x,∇2f(x)=A+AT;(c)∇f(x)=Ax−b,∇2f(x)=A;∑m2∑mT(d)f(x)=i=1ri(x),∇f(x)=2i=1ri(x)∇ri(x)=2A(x)r(x),2∑m2∑nT∇f(x)=2i=1ri(x)∇ri(x)+2i=1∇ri(x)(∇ri(x))∑m2T=2i=1ri(x)∇ri(x)+2A(x)A(x).1.6考虑向量值函数f(x):Rn→Rm，设f的每个分量函数fi(x)在x′都可微.写出′TTf在x的Taylor展式，请用A(x)表示∇f(x)(=[∇f1(x),···,∇fm(x)]).解:为了具体，考虑m=2,n=3给出，再表示成一般形式.此时()()f1(x)f1(x1,x2,x3)f(x)==.f2(x)f2(x1,x2,x3)因为函数f1(x)和f2(x)可微，则由多元函数的Taylor展式，有′′T′′fi(x)=fi(x)+∇fi(x)(x−x)+o(∥x−x∥),i=1,2.写成向量形式，即f(x)=f(x′)+A(x′)(x−x′)+o(∥x−x′∥),(1.1)这里o(∥x−x′∥)表示f(x)−f(x′)−A(x′)(x−x′)lim=0.x→x′∥x−x′∥这里的式(1.1)即为f在x′的Taylor展式，其中的矩阵A(x)称为雅可比(Jacob)矩阵，它的第i行为fi(x)在x处的梯度向量的转置.1.7假设在点x′有g′̸=0，证明在所有单位向量pTp=1中，函数沿方向向量p=g′/∥g′∥2的斜率最大.称该方向是函数的最速上升(steepestascent)方向.证：记g′=∇f(x′).因为函数可微，由方向导数与梯度的关系知函数沿方向p的方向导数，即斜率为pTg′.设θ为方向向量p与梯度向量g′的夹角，则由向量夹角的定义和∥p∥2=1，有T′T′T′′pg=∥p∥2∥g∥2cosθ≤∥p∥2∥g∥2=∥g∥2,其中等式成立当且仅当θ=0，即p与梯度向量g′同方向.又因为p为单位向量，所以当p=g′/∥g′∥2时，函数沿该方向的斜率(也即方向导数)最大. 第二章线性规划:基本理论与方法习题设计说明：1.化标准形练习：习题2.1-习题2.3，其中习题2.2和习题2.3是最优化中常用的两种重新表述技巧，这两种技巧的应用和进一步说明分别见习题2.27和习题7.19.2.基本解、基本可行解、退化基本可行解的练习：习题2.4,习题2.5，习题2.6，习题2.7，教材第25页的例2.2.3.3.习题2.8,习题2.9、习题2.12(b)是为了理解使用单纯形法时，如何根据单纯形表的数据判断线性规划何时有惟一解，何时有多解.如果有多解时，如何得到多个解.结论是：最优解不惟一时，某基本可行解的非基变量的相对费用系数非负，并且至少有一个非基变量的相对费用系数是零.此外，习题2.30说明，当原始问题的最优解是对偶非退化的(即非基变量的既约费用系数严格大于零)，对偶问题有惟一解；否则，对偶问题有多个极点解，进而有无穷多个解(这些极点解的凸组合都是原始问题的解).4.单纯形法的练习：习题2.10，习题2.11，习题2.12，习题2.13，习题2.20(说明单纯形法的效率的一般性例子中，自变量为三个时所得问题)，习题2.21(说明单纯形法采用最小相对费用系数进基原则确定进基变量时，如果所求解问题是退化的，则单纯形法会出现循环！)，习题2.31.5.两阶段法的练习：习题2.14-习题2.16；大M法的练习：习题2.18.6.修正单纯形法的练习：习题2.17，习题；单纯形法的矩阵表示：2.19.7.习题2.11，习题2.12(c)，2.32是关于灵敏度分析的练习，这也可以看成是单纯形法的应用，是难点.8.关于对偶性的练习：习题2.22－习题2.36.2.1将下面的线性规划问题化成标准形，并求解第3个问题(c)：(c)minimizex1+4x2+x3subjecttox1−2x2+x3=4x1−x3=1x2≥0,x3≥0.解:(c)由于变量x1无限制，可利用约束x1=x3+1对其消去.因此，得其标准形minimize4x2+2x3subjectto−2x2+2x3=3x2≥0,x3≥0.再把约束2x3=3+2x2代入目标函数，得6x2+4,又因为x2≥0，所以其最小值为4，最优解为x1=2.5,x2=0,x3=1.5.3 4第二章线性规划:基本理论与方法2.2将下面的问题化成线性规划minimize|x|+|y|+|z|subjecttox+y≤12x+z=3.方法1:令x=u1−v1,|x|=u1+v1,u1≥0,v1≥0,类似地表示y和z，则可将原问题重新编述为minimizeu1+u2+u3+v1+v2+v3subjecttou1−v1+u2−v2+s=1,2u1−2v1+u3−v3=3,ui,vi,s≥0,i=1,2,3.方法2:引入非负变量t1,t2,t3，将原问题转化成等价问题minimizet1+t2+t3subjecttox+y≤1,2x+z=3,|x|=t1,|y|=t2,|z|=t3.该问题的最优值与minimizet1+t2+t3subjecttox+y≤1,2x+z=3,|x|≤t1,|y|≤t2,|z|≤t3.的最优值相同，将这个问题的最优解投影到(x,y,z)所在的空间可以得到原问题的解.这个问题可以写成线性规划问题：minimizet1+t2+t3subjecttox+y≤1,2x+z=3,−t1≤x≤t1,−t2≤y≤t2,−t3≤z≤t3.2.3一类逐段线性函数f(x)=max{cTx+d,cTx+d,···,cTx+d}，其中c∈Rn,d∈1122ppiiR,i=1,···,p.针对这样的函数，考虑问题minimizef(x)x∈RnsubjecttoAx=bx≥0.将此问题化成线性规划. 5解:引入变量t，所给问题等价于minimizetsubjecttof(x)=t,Ax=b,x≥0.考虑问题minimizetsubjecttof(x)≤t,Ax=b,x≥0,因为该问题关于t最小化，故将最优解代入第一个不等式，必有等号成立，即问题的最优解和最优值与上一个问题的相同.从而所给问题等价于线性规划问题minimizetsubjecttocTx+d≤t,i=1,···,p,iiAx=b,x≥0.2.5考虑问题minimizec1x1+c2x2+c3x3subjecttox1+x2+x3≤4x1≤2x3≤33x2+x3≤6x1,x2,x3≥0.注意系数c1,c2,c3尚未确定.表示成标准形Ax=b,x≥0后,其中x1x211110004x310001002A=,x=x4,b=;00100103x503100016x6x7记A的第i列为ai.(a)画出所给问题的可行域(三维空间中).(b)点(0,1,3,0,2,0,0)T是基本可行解吗？(c)点(0,1,3,0,2,0,0)T是退化基本可行解吗？如果是的话，找出可能的与其对应的基. 6第二章线性规划:基本理论与方法解:(a)略.(b)是基本可行解，因为满足约束条件，且非零元素对应列a2,a3,a5线性无关.(c)是退化的基本可行解，因为非零元素个数是3，小于系数矩阵A的秩4；共有四个基与该基本可行解对应，他们是B=[a2a3a5aj]，其中j=1,4,6,7.2.8如果与每个非基变量xj对应的既约费用系数rj>0，证明与其对应的基本可行解是唯一的最优解.证明:不妨设满足条件的基本可行解x∗对应的基B为系数矩阵A的前m列，即x∗=(x∗,...,x∗,0,0,...0)T，且r>0,j=m+1,···,n.则对所有可行的x，有1mj∑nTT∗cx−cx=rjxj≥0.j=m+1设x¯是另一个最优解，则必有cTx¯−cTx∗=0.由于诸r>0，而x¯≥0，由上jj式，对j=m+1,...,n有x¯j=0；∑n∑m此外，因为x¯满足j=1ajx¯j=b，将x¯j=0,j=m+1,...,n代入，得j=1ajx¯j=∗∑m∗b.再由x的可行性，也有j=1ajxj=b.而a1,···,am线性无关，从而有x¯j=x∗j,j=1,···,m.综上，问题的任一最优解均和所给解x∗相同，从而满足条件的基本可行解是问题的惟一最优解.2.9举例说明退化基本可行解不用满足所有rj≥0也可以是最优的.解:考虑问题minimize−x1−x2x∈R3subjecttox1+x2+x3=0x1≥0,x2≥0,x3≥0.显然可行解只有x=(0,0,0)T，这也是最优解。但若用单纯形法来求解，例如选取x3为基变量,则表格为a1a2a3b1110rT−1−100此时非基变量所对应的相对费用系数都是负的，但可见这已经达到最优.2.10将下面的问题转化成标准形，用单纯形法求解，然后画出问题在x1,x2空间的可行域，并标明单纯形法的迭代路径.(b)maximizex1+x2subjectto−2x1+x2≤1x1−x2≤1x1≥0,x2≥0. 7解:(b)引入松驰变量x3,x4，化为标准形minimize−x1−x2subjectto−2x1+x2+x3=1,x1−x2+x4=1,xi≥0,i=1,2,3,4.写出初始表，其已是第一张单纯形表x1x2x3x4xBx1x2x3x4xBx3−21101x30−1123→x41−1011x11−1011cT(rT)−1−1000rT0−2011因为x2对应列无正元素,所以原问题是无界的.2.11(a)利用单纯形法求解maximize2x1+4x2+x3+x4subjecttox1+3x2+x4≤42x1+x2≤3x2+4x3+x4≤3xi≥0,i=1,2,3,4.利用(a)中的求解结果回答以下问题：(b)为使最优基保持不变，给出b=(4,3,3)T中第一个元素的可变范围(其它的保持不变)；(c)为使最优基保持不变，给出c=(2,4,1,1)T中第一个元素的可变范围(其它的保持不变)；第四个的？(d)对于b微小的改变，最优解将发生怎样的改变？(e)对于c微小的改变，最优值将发生怎样的改变？解:将原问题化为标准形，得初始表，并依次演算，得x1x2x3x4x5x6x7xBx513011004x621000103x701410013cT(rT)−2−4−1−10000x1x2x3x4x5x6x7xBx405/2011−1/205/2→x111/20001/203/2x601410013rT0−3−1−10103 8第二章线性规划:基本理论与方法x1x2x3x4x5x6x7xBx20102/52/5−1/501→x1100−1/5−1/53/501x60043/5−2/51/512rT00−11/56/52/506x1x2x3x4x5x6x7xBx20102/52/5−1/501→x1100−1/5−1/53/501x30013/20−1/101/201/41/2rT0007/2011/109/201/413/2至此，所有rj≥0,得到最优解x∗=(1,1,1/2,0)T.最优基B=[a2a1a3].因为初始单纯形表的最后三列是单位矩阵，故2/5−1/50B−1=−1/53/50.−1/101/201/4(a)设b的改变量为∆b=(∆b,∆b,∆b)T.要使最优基不变,此时相对费用系数保持123不变，故仅需要B−1(b+∆b)=xB+B−1∆b≥0,即12/5−1/50∆b11+−1/53/50∆b2≥0.(2.1)1−1/101/201/4∆b23当b的第一个分量发生变化时，∆b2=∆b3=0.将此代入(2.1)，可得第一个分量的变化范围为∆b1∈[−5/2,5],相应的，分量b1的取值范围为b1∈[3/2,9].(b)设c的改变量为∆c=(∆c,∆c,∆c,∆c)T.要使最优基不变,基变量的取值不1234变，仅需要(−c−∆c)T−(−c−∆c)TB−1N≥0(请注意该问题是max).而NNBB(−c−∆c)T+(c+∆c)TB−1NNNBB=(−cT+cTB−1N)−∆cT+∆cTB−1NNBNB=rT−∆cT+∆cTB−1N.NNB将所需条件写成分量形式，再由yj=B−1aj，得Trj−∆cj+∆cByj≥0,j=4,5,6,7.(2.2)由(a)中的最优单纯形表读出rj,yj,j=4,5,6,7，代入不等式组(2.2).当c只有一个分量改变时,令其他分量的改变量为零，解不等式组(2.2)，可得各分量的变化范围.具体地，对第一和第四个分量分别有∆c1∈[−3/4,7/4],∆c4∈(−∞,7/20]c1∈[5/4,15/4],c4∈(−∞,27/20].. 9(c)当b改变时，新的基本解是B−1(b+∆b)=B−1b+B−1∆b，因为B−1b>0，故当b变化不大时，新的基本解仍然是可行的，从而也是最优的.这时，最优解的改变量()T−12113111B∆b=∆b1−∆b2,−∆b1+∆b2,−∆b1+∆b2+∆b3.555510204(d)当c改变时，新的相对费用系数见(2.2).因为rj>0,j=4,5,6,7，故当c的改变量不大时，相对费用系数仍然是非负的，从而原来的最优解也是最优的.此时，新的最优值是(−c−∆c)TB−1b，最优值的改变量BB1T−1T∗−∆cBBb=−∆cBxB=−∆c1−∆c2−∆c3.22.12考虑问题minimizex1−3x2−0.4x3subjectto3x1−x2+2x3≤7−2x1+4x2≤12−4x1+3x2+3x3≤14x1≥0,x2≥0,x3≥0.(a)找出一个最优解.(b)存在多少个最优基本可行解？(c)证明：如果c+1a+4a≥0，则以费用系数c和系数向量(a,a,a)T引45145244142434入另一个变量x4后，最优解仍保持不变.解:(a)引入松驰变量x4,x5,x6化为标准形后，得初始表，其也是第一张单纯形表，然后依次演算，x1x2x3x4x5x6xBx43−121007x5−24001012x6−43300114cT(rT)1−3−0.40000x1x2x3x4x5x6xBx45/20211/4010→x2−1/21001/403x6−5/4030−3/415rT−1/20−0.403/409x1x2x3x4x5x6xBx1104/52/51/1004→x2012/51/53/1005x60051−1/2115rT0001/54/5011 10第二章线性规划:基本理论与方法因为r≥0,得到一个最优解(4,5,0)T,且最优值f∗=−11.j(b)在(a)的最后一张单纯形表中，因为r3=0，令x3进基,由最小正比率法则，知x6出基,即以5为转轴元转轴后，得x1x2x3x4x5x6xBx11006/259/50−4/258/5x20103/258/25−2/2519/5x30011/5−1/101/53rT0001/54/5011因为r≥0,所以又得到一个最优基本可行解(8/5,19/5,3)T,且目标值仍为f∗=−11.j(c)将c4和(a14,a24,a34)代入单纯形表，得最后的单纯形表a1a2a3a4a5a6a7B−1b104/5(2/5)a14+(1/10)a242/51/1004012/5(1/5)a14+(3/10)a241/53/1005005a14+a34−(1/2)a241−1/2115rT000(1/5)a+(4/5)a+c1/54/501114244如c4+(1/5)a14+(4/5)a24≥0,则上表达到最优,且最优解保持不变.也可以由(a)中的最后一张表读出最优基B的逆，然后由y4=B−1a4和r4=c4−cTy4算出单纯形B表中与x4对应的数据，然后得出结论.2.16在两阶段法的第I阶段，假定给系统Ax=b,x≥0的辅助问题应用单纯形法后，所得表格(忽略费用行)形如x1xkxk+1···xny1···ykyk+1···ym10···0b′1...R......1S1...10···0b′k0···010...........R2S2.0···010即基变量中有m−k个人工变量，它们取零值.(a)证明R2中的任何非零元素都可作为转轴元以消去人工基变量，这样将产生一个类似的表格，但k会增加1.(b)重复(a)中的过程，直到R2=0.证明原始系统是冗余的，并说明可以删除底端的这些行，然后继续第II阶段. 11(c)利用上面的方法(即两阶段法)求解线性规划minimize2x1+6x2+x3+x4subjecttox1+2x2+x4=6x1+2x2+x3+x4=7x1+3x2−x3+2x4=7x1+x2+x3=5xi≥0,i=1,2,3,4.解：(c)第I阶段：引入人工变量y1,y2,y3,y4，构造辅助问题minimizey1+y2+y3+y4subjecttox1+2x2+x4+y1=6,x1+2x2+x3+x4+y2=7,x1+3x2−x3+2x4+y3=7,x1+x2+x3+y4=5,xi≥0,yi≥0,i=1,2,3,4.辅助问题的初始表为x1x2x3x4y1y2y3y4xBy1120110006y2121101007y313−1200107y4111000015cT000011110将最后一行与基变量对应的系数化为零，得第一张单纯形表后，因此进行转轴运算，得x1x2x3x4y1y2y3y4xBy1120110006y2121101007y313−1200107y4111000015rT−4−8−1−40000−25x1x2x3x4y1y2y3y4xBy11/302/3−1/310−2/304/3y21/305/3−1/301−2/307/3→x21/31−1/32/3001/307/3y42/304/3−2/300−1/318/3rT−4/30−11/34/3008/30−19/3 12第二章线性规划:基本理论与方法x1x2x3x4y1y2y3y4xBy11/500−1/51−2/5−2/502/5x31/501−1/503/5−2/507/5→x22/5103/501/51/5014/5y42/500−2/50−4/51/514/5rT−3/5003/5011/56/50−6/5x1x2x3x4y1y2y3y4xBx1100−15−2−202x30010−11001→x20101−21102y40000−20110rT000031000因为该单纯形表第4行与原问题数据对应的数全为零，从而不能再次转轴将人工变量y赶出基；此时，第4个约束为冗余的,将其删除后，得基本可行解(2,2,1,0)T.4第II阶段：以上述基本可行解作为初始基本可行解，利用单纯形法求解原问题.首先得到如下初始表x1x2x3x4xBx1100−12x300101x201012cT26110将最后一行与基变量对应的系数化为零后，得第一张单纯形表后，因此进行转轴运算，得x1x2x3x4xBx1100−12x300101x201012rT000−3−17x1x2x3x4xBx111004→x300101x401012rT0300−11因为rj≥0,所以得最优解x∗=(4,0,1,2)T,f∗=11. 132.19下面的表格是用单纯形法求解极小化问题的一个中间表格y1y2y3y4y5y6y012/3004/3040−7/331−2/3020−2/3−202/312rT08/3−1104/30−8(a)确定下一个转轴元.(b)给定当前基的逆11−1B−1=[a,a,a]−1=11−221463−121和对应的费用系数c=(c,c,c)T=(−1,−3,1)T.确定原问题的数据(c,A,b).B146解：(a)下一个转轴元为3(第2行第3列)210(b)B=(a1,a4,a6)=(B−1)−1=101.01110由y0=B−1b可得b=By0=6.4−132由yq=B−1aq可得[a2,a3,a5]=B[y2,y3,y5]=0−22.−310所以2−13120A=[a1a2a3a4a5a6]=10−20210−31101由r=c−cTy可得(c,c,c)T=(25/3,−22,8/3)T.所以原问题为qqBq235minimize−x1+(25/3)x2−22x3−3x4+(8/3)x5+x6subjectto2x1−1x2+3x3+x4+2x5=10,x1−2x3+2x5+x6=6,−3x2+x3+x4+x6=4,xi≥0,i=1,2,3,4,5,6.2.20利用单纯形法求解问题(2.2.14)，其中初始点x(0)=(0,0,0)T，要求每次迭代选既约费用系数最负的变量进基. 14第二章线性规划:基本理论与方法解：将原始问题化为标准形,利用单纯形法求解，因此得如下单纯形表格x1x2x3x4x5x6xBx41001001x5410010100x684100110000rT-4-2-10000x1x2x3x4x5x6xBx11001001−→x5010-41096x6041-8019992rT0-2-14004x1x2x3x4x5x6xBx11001001−→x2010-41096x60018-419608rT00-1-420196x1x2x3x4x5x6xBx41001001−→x2410010100x6-8010-419600rT40-1020200x1x2x3x4x5x6xBx41001001−→x5410010100x6-8010-419600rT-4000-219800x1x2x3x4x5x6xBx11001001−→x2010-41096x30018-419608rT0004-219804 15x1x2x3x4x5x6xBx11001001−→x5010-41096x3041-8019992rT020-4019996x1x2x3x4x5x6xBx41001001−→x5410010100x384100110000rT42000110000整个迭代遍历了原问题在三维空间中的超立方体可行域的全部8个顶点.得最优解x∗=(0,0,10000)T;对应的目标函数值是10000.2.24构造一个原始问题和对偶问题都没有可行解的例子.解：构造原问题如下minimize−x1−x2subjecttox1≥1,−x2≥1,x1≥0,x2≥0.其对偶问题为maximizeλ1+λ2subjecttoλ1≤−1,−λ2≤−1,λ1≥0,λ2≥0.易见二者均无可行解.2.25设A是m×n矩阵,b是n维向量.证明Ax≤0蕴含着cTx≥0当且仅当存在≥0使得c+AT=0.给出该结论的一个几何解释.证：充分性.假设存在≥0，使得cT+TA=0成立，则对任意的x∈Rn，有cTx=−T(Ax)成立.如果x使得Ax≤0，则由≥0必有cTx≥0成立.必要性.构造如下线性规划问题，即minimizecTxsubjecttoAx≤0.它的对偶问题为maximize0subjecttoTA=cT≤0. 16第二章线性规划:基本理论与方法易见x=0是原始问题的一个可行解，且由Ax≤0蕴含着cTx≥0可知，原始问题的目标函数有下界.根据弱对偶性，对偶问题也有可行解，即存在′≤0且满足(′)TA=cT.令=−′，易见即为满足条件的向量.注：这个结论即著名的Farkas引理，详见课本163页的引理7.3.4.关于该结论的证明常见的有两种，一种即该作业的基于线性规划对偶理论的证明，还有一种就是课本上给出的基于点与闭凸锥的分离定理(引理7.3.5)的证明.课本上给出的证明是构造性的，即给出了具体的满足要求的向量.将该结论用在非线性规划的最优性条件的推导中，这个结论中的向量就是著名的Lagrange乘子.此外，如果要用对偶性构造出所需的向量，需要用线性规划强对偶定理的证明，即37页的定理2.3.2，那里也用了凸集分离定理.几何解释：定义集合C={c∈Rn|c=AT,≥0}，此即A的行向量生成的锥集合(行向量的所有非负线性组合形成的集合)，以及C◦={x|Ax≤0}，此集合由与C中每个向量所夹角均不是锐角的向量组成，也称为C的极锥或者法锥(polarconeornormalcone)1.Farkas引理表明：如果向量c与C◦中的每个向量的夹角为锐角或者直角，即满足T◦cx≥0,∀x∈C,[]11那么−c必属于C，反之亦成立.令A=，Farkas引理的几何解释见图2.1.13a2Ca1aC图2.1:习题2.25Farkas引理的几何解释Farkas引理的另一种描述：系统I：Ax≤0,cTx<0与系统II：≥0,cT+TA=0有且只能有一个有解.系统I有解等价于存在向量x，它与A的每个行向量的夹角至少为90◦，且它与向量−c的夹角小于90◦；系统II有解等价于向量−c在由A的行向量生成的凸锥中.基于此描述，Farkas引理的几何解释如下：给定一个由A的行向量生成的凸锥C和向量−c，要么向量−c属于锥，要么存在一个超平面H:={y∈Rn:yTx∗=0},其中x∗为系统I的解1◦nTC=fy2R:yc0;8c2Cg 17分离该凸锥和这个向量(即C在这个超平面的非正半空间，向量−c在这个超平面确定的正半空间)，且二者不会同时成立.2.27博弈论(gametheory)部分地涉及线性规划理论.考虑如下博弈，其中参与人甲可以在m种策略(strategy)中任选一种，参与人乙可以在n种策略中任选一种；如果甲选择策略i，乙选择策略j，则甲从乙处赢得的数量为aij.博弈通常会重复多次.假设参与人甲设计了一种混合(mixed)策略，记为向量x=(x,···,x)T，其中分量1m∑mxi≥0表示参与人选择策略i的概率，要求i=1xi=1.同样的，乙的混合策略记为∑ny=(y,···,y)T，其中y≥0,y=1，这时甲的平均收益P(x,y)=xTAy.1nii=1i(a)考虑线性规划问题maximizeα∑msubjecttoi=1xi=1∑mi=1xiaij≥α,j=1,2,···,nxi≥0,i=1,2,···,m.设(α,x)是该问题的可行解.证明当参与人甲选择可行解中的x作为自己的策略时，不管乙选取何种策略y，甲的支付至少为α.(b)证明上面问题的对偶是minimizeβ∑nsubjecttoj=1yj=1∑nj=1aijyj≤β,i=1,2,···,myj≥0,j=1,2,···,n.(c)证明maxα=minβ.(称这个共同的值是博弈的值(value)，对应的解x∗和y∗是这个博弈的平衡点).(d)考虑“匹配博弈”.每个参与人选择正面或反面.如果选择是匹配的话，即一个选正面的同时另外一个选反面，则甲从乙那儿赢得1元；如果它们不匹配，乙从甲那儿赢得1元.求出该博弈的值和平衡点.(e)考虑博弈，其中每个参与人可以选择1，2，3中的某个，相应的支付规则是当参与人的数字相等时，不发生支付；否则，当参与人的数字恰好比另一个参与人的数字大1时，该参与人输3元；当参与人的数字恰好比另一个参与人的数字大2时，参与人赢1元.确定该博弈的值和平衡点.(a)证明：a11a12...a1ny1Ta21a22...a2ny2P(x,y)=xAy=(x1,x2,...,xm)...............am1am2...amnyn∑m∑m∑m=y1i=1xiai1+y2i=1xiai2+...+yni=1xiain∑m由已知，i=1xiaij≥α,j=1,2,...,n可得：P(x,y)≥y1α+y2α+...+ynα=(y1+y2+...+yn)α=α 18第二章线性规划:基本理论与方法所以得证X的支付至少是α.(b)问题(a)可以用向量形式表示为αx1maximize(1,0,0,...,0)...xm01...1()1−a11...−an1subjecttoαx1···xm(=≤···≤)(10···0)............1−am1...−amnxi≥0,i=1,2,...,m根据一般性对偶原则可写出上述问题的对偶问题是βy1minimize(10···0)...yn01...1β=11−a11...−an1y1≥0subjectto...............···...1−am1...−amnyn≥0yj≥0,j=1,2,...,n化简得minimizeβ∑nsubjecttoj=1yj=1∑nβ−j=1aijyj≥0,i=1,2,...,myj≥0,j=1,2,...,n,此即(b)中所给问题.(c)该问题为线性规划，并且再由已知条件可知(a)问题必有有限最优解.再由线性规划的强对偶定理可得maxα=minβ.(d)用1表示正面，用2表示反面.根据所给规则，a11=a22=−1,a12=a21=1.从而参与人甲对应的问题是maximizeαsubjecttox1+x2=1−x1+x2≥αx1−x2≥αx1≥0,x2≥0该问题的最优解x∗=(1,1)T，最优值为0；同理可得y∗=(1,1)T，最优值也为0.2222 19(e)根据问题的描述，该博弈的支付矩阵为03−1A=−3031−30对应的(a)中的线性规划问题是maximizeαsubjecttox1+x2+x3=1−3x2+x3≥α3x1−3x3≥α−x1+3x2≥αx1≥0,x2≥0,x3≥0该问题的最优解x∗=(3,1,3)T，最优值为0；同理可得y∗=(3,1,3)T，最优值也为7777770.2.32(a)利用单纯形法求解minimize2x1+3x2+2x3+2x4subjecttox1+2x2+x3+2x4=3x1+1x2+2x3+4x4=5xi≥0,i=1,2,3,4.(b)利用(a)中所作工作和对偶单纯形法求解相同的问题,除了方程组的右端向量变成(18)T.解:(a)因为该问题没有显然的基本可行解，利用两阶段法求解该问题.第I阶段：首先引入人工变量x5,x6，构造辅助问题minimizex5+x6subjecttox1+2x2+x3+2x4+x5=3,x1+x2+2x3+4x4+x6=5,xi≥0,i=1,2,3,4,5,6.利用单纯形法求解辅助问题.首先得初始表x1x2x3x4x5x6xBx51212103x61124015cT0000110将基变量x5,x6对应的最后一行的系数化为零，得第一张单纯形表x1x2x3x4x5x6xBx51212103x61124015rT−2−3−3−600−8 20第二章线性规划:基本理论与方法以4为转轴元，即x4进基，x6出基，得x1x2x3x4x5x6xBx51/23/2001−1/21/2x41/41/41/2101/45/4rT−1/2−3/20003/2−1/2再次转轴之后，得x1x2x3x4x5x6xBx21/31002/3−1/31/3x41/601/21−1/61/37/6rT0000110因为辅助问题的最优值为0，所以原始问题有可行解.因为基变量不含人工变量，故x=(0,1/3,0,7/6)T是一个基本可行解.第II阶段：在第I阶段的最后一个单纯形表中删去人工变量所对应列和最后一行，可得原始问题的一张初始表x1x2x3x4xBx21/31001/3x41/601/217/6cT23220将基变量x2和x4下面的系数化为零，得第一张单纯形表x1x2x3x4xBx21/31001/3x41/601/217/6rT2/3010−10/3因为相对费用系数向量非负，故得最优解x∗=(0,1/3,0,7/6)T，最优值z∗=10/3.[]2/3−1/3(b)由(a)可知B=(a2,a4)，所以B−1=.右端项改为(18)T后，只−1/61/3[][]1−2需将上表的最后一列改为B−1=.这时，得新问题的单纯形表8156x1x2x3x4xBx21/3100−2x1/601/211546rT2/30101此时，由对偶单纯形法，x2出基，但是第一行没有负元素.由单纯形表第一行的数据知，问题的第一个约束等价于1x+x=−2.而变量非负，故修改右端项后所得新312问题没有可行解. 212.34考虑minimize12x1+8x2+16x3+12x4subjectto−2x1−x2−4x3+x5=−2−2x1−2x2−4x4+x6=−3xi≥0,i=1,···,6.(a)利用对偶单纯形法求解问题；(b)写出对偶问题，并用图解法求解；(c)写出(a)中与每张单纯形表对应的单纯形乘子，并将这些点标在(b)中的图上.写出你发现的事实.2.34解：(a)利用对偶单纯形法求解原始问题的步骤如下，x1x2x3x4x5x6xBx5-2-1-4010-2x6-2-20-401-3rT1281612000x1x2x3x4x5x6xBx31/21/410-1/401/2−→x6-2-20-401-3rT4401240-8x1x2x3x4x5x6xBx30-1/41-1-1/41/4-1/4−→x111020-1/23/2rT000442-14x1x2x3x4x5x6xBx201-441-11−→x1104-2-11/21/2rT000442-14所以最优解x∗=(1/2,1,0,0,0,0)T，最优目标值z∗=14.(b)其对偶问题如下.根据图2.2，可知它的最优解∗=(−4,−2)T，最优目标值是14.maximize−2λ1−3λ2subjectto−2λ1−2λ2≤12−λ1−2λ2≤8−4λ1≤16−4λ2≤12λ1≤0λ2≤0. 22第二章线性规划:基本理论与方法2!2!2"121241!16!21!32(1)(0)1(2)(3)4!122!!2"812图2.2:习题2.34中所给问题的对偶问题的可行域(c)由rT=c−cTB−1A可得BT−1(r5,r6)=(0,0)−cBBIT−1=−cBB.而单纯形乘子T=cTB−1，所以与每张单纯形表对应的乘子分别是B(0)=(0,0)T,(1)=(−4,0)T,(2)=(−4,−2)T,(3)=(−4,−2)T.它们的位置如图2.2，可发现单纯形乘子沿着对偶问题可行域的边界移动，最后到达对偶问题的最优点. 第三章线性规划：应用及扩展习题设计说明：1.习题3.1用以熟悉网络单纯形法中各个量的计算方式；习题3.4用以熟悉网络单纯形法求解运输问题时，其中各个量的存储和计算方式.2.习题3.2和习题3.3是关于网络流问题的理论性质的练习.3.习题3.5，习题3.6和习题3.7介绍典型的可以建模为整数规划的运筹问题，其中背包问题和车辆路由问题都可建模为0-1线性规划、二次指派是0-1二次规划，利用线性化技术也可表示成0-1线性规划问题.并以背包问题为例，说明求解该问题的分枝定界法的计算复杂度是指数级的.4.习题3.8是用以体会对偶单纯形法在求解整数线性规划的分支限界法中的特殊应用，体会根据问题性质和应用场景选取算法的重要性！5.习题3.9用以熟悉分枝定界法，如剪枝、定界、分支等.3.1.考虑图3.1.1所示的网络流问题，令T={(b,c),(c,a),(d,c),(e,b)}，即如下生成树.abcde请以e为根节点,完成以下工作:(a)求每个树弧上的原始流量；(b)求与每个节点对应的单纯形乘子；(c)求与每个非树弧对应的既约费用系数.解:(a)原始流量为xca=2,xdc=5,xbc=1,xeb=1.(b)以e为根节点，则单纯形乘子依次为yb=−11,yc=−13,yd=12,ya=−27.(c)非树弧的既约费用系数依次为rab=28,rce=23,rda=−29,rde=−2.3.4考虑表3.2.1所给的运输问题.(a)表3.2.2给出的树解原始可行吗？对偶可行吗？(b)求解该运输问题.解:(a)树解非负，故为原始可行，相对费用系数含负数，故不是最优解.23 24第三章线性规划:应用及扩展(b)首先假设S={1,2,3,4},D={5,6,7}.表3.2.1费用信息SD102715756*1184318*9*16*36表3.2.2运输问题的树解yiyj-5-1-4075*338-48*18*2*115因为只有r27=−4为负，所以选x27为入弧，这样弧x26,x27,x46,x47形成一个圈.与x27异向的弧有x26,x47，选取流量最小的弧x26为出弧；更新圈上弧的流量为x26=0,x27=8,x46=9,x47=7.然后分别计算子树3,6的单纯形乘子和非树弧x16,x26的相对费用系数y3=12,y6=3,(入弧指向不含根节点的子树，单纯形乘子均减少-4)；r16=9,r26=4.(非树弧均与入弧同向，相对费用系数都减少-4)最后得到更新后的树解：yiyj-530079*334812*18*6*97因为相对费用系数都非负，所以当前树解是最优的；最小运输费f∗=314.3.7二次指派问题(quadraticassignmentproblem).令F是n个工厂的集合,C是n个城市的集合.要求在每一城市中设置且只设置一个工厂,并要使工厂两两之间总的通讯费用最小.每对工厂(i,k)之间一定时间内通讯的次数为tik,每对城市(j,l)之间的距离为djl.通讯费用cijkl=tikdjl.(a)试为该问题建立目标函数为二次函数的整数规划模型.(b)将上述模型中的非线性目标函数线性化.解:(a)建模：设xij=1表示在城市j建工厂i，xij=0表示不在城市j建工厂i，则i∈F,j∈C.这样，cijkl（即tikdjl）表示在城市j的工厂i到在城市l的工厂k之间的通讯费.这样得到二次的目标函数，即∑∑cijklxijxkl.i;k∈Fj;l∈C显然有0,1约束：xij∈{0,1}.由于每一个城市中有且只有一个工厂，故得∑到约束Fxij=1,∀j∈C.而每一个工厂也只能在一个城市中，故得到约束∑Cxij=1,∀i∈F. 习题325综上，二次指派问题的优化模型为∑∑minimizei;k∈Fj;l∈Ccijklxijxkl∑subjecttoi∈Fxij=1,∀j∈C,∑j∈Cxij=1,∀i∈F,xij∈{0,1},∀i∈F,j∈C.(b)线性化目标函数：由于诸cijkl≥0，故可以利用新变量yijkl来替换xijxkl，其中yijkl满足yijkl≥xij+xkl−1,yijkl≥0.这样，二次指派问题就转化为具有线性目标函数的0-1线性规划问题，即∑minimizei;k∈F;j;l∈Ccijklyijkl∑subjecttoi∈Fxij=1,∀j∈C,∑j∈Cxij=1,∀i∈F,yijkl≥xij+xkl−1,yijkl≥0,∀i,k∈F,j,l∈Cxij∈{0,1},∀i∈F,j∈C.3.8考虑例3.4.4的枚举树上节点2的线性规划松弛问题P2.请从P0的最优单纯形表开始,利用对偶单纯形法求解P2.解:首先写出P0的最优单纯形表x1x2x3B−1b10.5−0.251.25rT01.50.25−1.25给P0添加约束x1≥2就得到P2，再对该约束引进一个松弛变量x4，继而写出表格x1x2x3x4B−1b10.5−0.2501.25−1001−2rT01.50.250−1.25将第一行加到第二行后，得到单纯形表x1x2x3x4B−1b10.5−0.2501.2500.5-0.251−0.75rT01.50.250−1.25此时得到的P2的基本解是对偶可行的，所以利用对偶单纯形法求解.以-0.25为转轴元转轴后，得到x1x2x3x4B−1b100−120−21−43rT0201−2 26第三章线性规划:应用及扩展此为最优表，得最优解x∗=(2,0)T.3.9对线性规划minimize−x1−2x2subjectto−2x1+2x2≤32x1+2x2≤9,分(i)无整数限制,(ii)x1为整数,(iii)x1,x2均为整数三种情况，用图解法求解相应的问题.并给出用分枝定界法求解(iii)的过程,画出枚举树.解:根据题意，由图3.1(a)可知，三种情况的最优解分别是x∗=(1.5,3)T;(ii)x′=(2,2.5)T;(iii)x′′=(2,2)T.x0-¥22x12x2!9x1£1x1³2(0)x-7.5-7.512x(1)(2)xx(5)x2£2x2³3x2£2x2³3x(3)x(7)(8)x3-64-6-75-76xx1£2x1³31"2x12x2!3"x"2x-6.578-6.512(b)分枝定界法的枚举树(采用的是深度优先(a)整数规划的图解.的枚举策略).图3.1:习题3.9图解图3.1(b)表示用分枝定界法求解(iii)的枚举树，其中枚举策略是深度优先.方法依次求解问题的详细信息见下表，其中Pi表示子问题编号，L表示为子问题确定的下界，x∗和f∗分别表示松弛子问题后所得线性规划问题的最优解和最优值，xˆ和fˆ分别表示当前最好解和最好值.(Pi,L)x∗Tf∗采取措施xˆTfˆ(P0,−∞)(1.5,3)−7.5分枝，得(P1,−7.5)&(P2,−7.5)[]+∞(P1,−7.5)(1,2.5)−6分枝，得(P3,−6)&(P4,−6)(P3,−6)(1,2)−5得可行解，更新xˆ，剪枝(1,2)−5(P4,−6)[]+∞子问题不可行，剪枝(P2,−7.5)(2,2.5)−7分枝，得(P5,−7)&(P6,−7)(P5,−7)(2.5,2)−6.5分枝，得(P7,−6.5)&(P8,−6.5)(P7,−6.5)(2,2)−6得可行解，更新xˆ，剪枝(2,2)−6(P8,−6.5)(3,1.5)−6f∗≥L,剪枝(P6,−7)[]+∞子问题不可行，剪枝 第四章无约束优化：基础习题设计说明：1.最优性条件：习题4.1-习题4.5.2.凸函数：习题4.6.收敛速度：习题4.7.3.一维搜索：4.8-4.13.4.2考虑问题min∥Ax−b∥2,其中A是m×n矩阵,b是m维向量，m>n.x∈Rn(a)给出问题的几何解释.(b)写出最优性的必要条件.它也是一个充分条件吗？(c)最优解唯一吗？理由是什么？(d)你能给出最优解的一种闭合形式(解析式)吗？在满足题目所给信息下，允许规定任何你所需的假设.(e)求解该问题,其中1−1020211A=,b=.01011010解:(a)几何解释：问题在求向量b到A的值空间R(A)(即由A的列生成的子空间)的最小距离.设b在R(A)上的投影为c，则满足Ax=c的解x∗即为最优解.具体例子见(e)，这时有三个未知数，四个方程，所给方程没有普通意义的解，称这里求出的x∗是方程组的最小二乘解.(b)令f(x)=∥Ax−b∥2=xTATAx−2bTAx+bTb,∇f(x)=2ATAx−2ATb.一阶必要条件为：TTAAx=Ab.(4.1)又因为∇2f(x)=2ATA为半正定矩阵，所以f(x)为凸函数，从而方程(4.1)也是充分条件.(c)最优解不一定唯一.当b∈R(A)且rank(A)0αp(k))的所有极小点.[][]T[]2(x1+x22)T2−1解:g(x)=,g(k)p(k)==−2<0,故p(k)是一个下4x2(x1+x22)01降方向.[][][]1−11−αx(k)+αp(k)=+α=,01α所以f(x(k)+αp(k))=(1−α+α2)2,而1−α+α2=(α−1)2+3≥3,当且仅当244α=1时取等号，所以当α=1时，f(x(k)+αp(k))的值最小.224.11对于函数ϕ(α)=1−αe−2,对σ=ρ=1及σ=ρ=1两种情况分别确定满104足Goldstein条件,Wolfe条件以及强Wolfe条件的α值的可接受区间.对于后一种情况,以α=0和1为初值,应用算法4.4.1和算法4.4.2得到一个可接受点.解：首先对函数ϕ(α)=1−αe−2求导，得ϕ′(α)=(2α2−1)e−2，从而得到ϕ(0)=1,ϕ′(0)=−1，再由Armijo条件ϕ(α)≤ϕ(0)+αρϕ′(0)可得−2e≥ρ,α>0.(4.2)进一步，将所给数据代入Goldstein条件的第二个不等式ϕ(α)≥ϕ(0)+α(1−ρ)ϕ′(0)可得−2e≤1−ρ.(4.3)将所给数据代入Wolfe条件中的斜率条件ϕ′(α)≥σϕ′(0)，得到(2α2−1)e−2≥−σ.(4.4)将所给数据代入强Wolfe条件中的双边斜率条件|ϕ′(α)|≤−σϕ′(0)得−σ≤(2α2−1)e−2≤σ.(4.5)从而，当ρ=0.1时，解(4.2)得0<α≤1.5174；解(4.3)得α≥0.3246；解(4.4)得α≥0.6509；解(4.5)得0.6509≤α≤0.7682.这样，Goldstein条件的可接受区间为[0.3246,1.5174]；Wolfe条件的可接受区间为[0.6509,1.5174]；强Wolfe条件的可接受区间为[0.6509,0.7682].当ρ=0.25时，解(4.2)得0<α≤1.1774；解(4.3)得α>0.5364；解(4.4)得α≥0.5716；解(4.5)得0.5716≤α≤0.8775.这样，Goldstein条件的可接受区间为[0.5364,1.1774]；Wolfe条件的可接受区间为[0.5716,1.1774]；强Wolfe条件的可接受区间为[0.5716,0.8775].在划界与分割阶段，程序均用极小化二次插值多项式的方法选取α.对于初始条件ϕ¯=0,α0=0,α1=1,σ=ρ=0.25，划界与分割阶段各迭代1次，就可得到αk=0.75，由上可知它满足强Wolfe条件. 第六章无约束优化：线搜索法习题设计说明：1.最速下降法：习题5.1-习题5.6，重点理解最速下降法有限步收敛的条件和收敛因子的上界等结论.2.牛顿法：习题5.7-习题5.14，重点理解牛顿法是局部二阶收敛的，当初始点不合适时，牛顿法的不适定性，从而需要修正牛顿法.3.共轭梯度法：习题5.15-习题5.17(向量共轭的定义)，习题5.18(共轭梯度法的性质)，习题5.19(共轭梯度法的有限步收敛性).4.拟牛顿法：习题5.22(关于曲率条件的理解，进而理解拟牛顿法通常与Wolfe或者强Wolfe线索搭配使用的原因)，习题2.23(DFP法的练习，帮助理解使用精确线搜索时，DPF法产生的方向是共轭的性质)，习题5.24(证明DFP校正能保证正定性的充要条件是曲率条件).5.说明各种方法之间关系的综合性练习：习题5.20(最速下降法、共轭梯度法和BFGS法的关系)，习题2.23(DFP法使用精确线搜索时产生的方向是共轭的)，习题5.25(非常有名的逆的校正公式，在数值计算中有重要的应用，利用他可以由BFGS的关于Hessian阵的校正公式推出关于Hessian阵逆的校正公式).6.最小二乘：习题5.26-习题5.29，练习GN法，也可以编写LM方法求解.7.理解方法性质的数值训练：习题5.6(理解最速下降法的收敛速度与收敛因子上界等结果，体会方法的收敛速度对初值的依赖性)，习题5.8(这是求解线性规划的对数障碍法中得到的子问题，体会函数有定义域时如何使用线搜索法，并体会障碍因子对方法收敛速度的影响)，习题5.9(体会最速下降法与牛顿法的异同，并体会线搜索牛顿法中线搜索策略的意义！)，习题5.19(理解共轭梯度法的n步之内收敛性质，体会理论结果与实际计算的差异；这里的Hilbert矩阵是有名的病态矩阵，它的坏条件数很大).5.4考虑使用精确线搜索的最速下降法,证明对所有的k,搜索方向p(k+1)正交于p(k).将该方法应用于函数q(x)=10x21+x22,选取初始点x(0)=(1/10,1)T.从数值上验证本例可以达到最速下降法的最坏收敛速度,即方法产生的序列{q(k)−q∗}是线性收敛，且收敛因子是(λ1−λn)2/(λ1+λn)2,其中λ1,λn分别为G的最大和最小特征值.注意,如果G相当病态,则这里的收敛因子能任意接近于1.解：记当前点为x(k).则由精确线搜索可知∇q(x(k)+αp(k))Tp(k)=0k由于有∇q(x(k)+αp(k))=−p(k+1)，故p(k+1)Tp(k)=0.易见最优解x∗=0.又[]k200因为G=，所以λ1=20,λ2=2;从而得收敛因子的上界为02(λ1−λ2)2=0.6694.(λ1+λ2)2选取初始点x(0)=(1/10,1)T，数值结果(后4次迭代)见表6.1.5.5假设我们需要极小化q(x)=5x21+5x22−x1x2−11x1+11x2+11.31 32第五章无约束优化:线搜索法表6.1:说明最速下降法的收敛因子可以达到最坏情况的例子−5(k)q(k+1)−q∗k10·xq(k)−q∗49(0.656,6.558)0.669350(−0.537,5.365)0.669451(0.439,4.390)0.669552(−0.3592,3.5920)(a)找到一个满足一阶必要条件的解.(b)说明该点是全局极小点.(c)针对该问题,最速下降法的收敛因子最大不会超过多少?(d)从x(0)=(1,1)T出发,最多需要多少步可将目标函数值减少到10−11?[][]10x1−x2−110解：(a)令g(x)==,可得满足一阶必要条件的解为10x2−x1+110x∗=(1,−1)T.[]10−1(b)因为G=正定，所以q(x)是凸函数，从而x∗=(1,−1)T也−110是全局极小点。(c)因为G的特征值为9,11，所以得线性收敛的收敛因子的上界a=(11−9)2=0.01.11+9(d)因为q(x∗)=0,q(x(0))=20,q(x(k))−q(x∗)≤ak(q(x(0))−q(x∗))(6.1)令10−11=10−2k·20，解得k=⌈11+log20⌉=⌈6.150⌉=7.这样，k=7是使不等2式(6.1)成立的最小正整数.所以应取k=7，否则有可能达不到要求.这样，最多需要7步即可达到要求.请注意，这里的“最多需要”是因为利用条件数估计的是收敛因子的上界，也即最坏情况估计.5.12应用牛顿法于函数f(x)=11x6−38x4+1x2,5463642其中x(0)=1.01为初始点.验证G(k)总是正定的,且f(k)是单调递减的.说明方法产生的序列{xk}的聚点x∞=±1,且g∞̸=0.验证对任意固定的正数ρ,不管其多么小,Armijo条件(4.3.1)对充分大的k总不成立(舍入误差起支配作用的情况除外).证：对函数f(x)=11x6−38x4+1x2，易得：5463642′115383g(x)=f(x)=x−x+x9191′′5541142G(x)=f(x)=x−x+19191 习题533因而，基于步长为1的基本牛顿法，第k次迭代过程可以写为：(k)(k)5(k)3(k)(k)g11x−38x+91xs=−=−G(k)(k)4(k)255x−114x+91(k)5(k)3(k+1)(k)(k)44x−76xx=x+s=(k)4(k)255x−114x+91572由上面的计算结果，易见G(x)的最小值1−>0，所以G(x)恒大于零.将91×55给定的初始点x(0)=1.01代入上式进行迭代，前10个迭代点的信息见表6.2.从数值结果可以看出f(k)是单调递减的，并最终收敛到0.4158.此外，对于{x(k)}，指标为偶数的子列收敛到1，指标为奇数的子列收敛到−1.因而用牛顿法产生的迭代点列{x(k)}有两个聚点：1和−1,并且g∞=±64̸=0.91表6.2:基本牛顿法求解习题5.12的部分迭代数据(k)(k)(k)(k)(k)(k)kxfgkxfg01.01000.42280.70685-1.00020.4159-0.70341-1.00370.4183-0.704661.00010.41580.703321.00160.41690.70397-10.4158-0.70333-1.00080.4163-0.7036810.41580.703341.00040.41600.70349-10.4158-0.7033(k)(k)(k)2(k)对任意给定的正数ρ，将ρgs=−ρg/G<0代入Armijo条件，即f(k)+ρg(k)s(k)−f(k+1)≥0，得G(k)ρ≤(f(k)−f(k+1)).(6.2)g(k)2由前面的分析知：当k趋于无穷大时，不等式的右边大于零且趋于零(因为G(x∞)∞∞91(g(x∞))2(f(x)−f(x))=128×0=0).从而对于给定的正数ρ，无论其多小，由极限的定义，存在指标K，当k>K时，不等式(6.2)的右边严格小于ρ，此时Armijo条件不再成立(舍入误差除外).说明：该问题说明，当我们使用基本牛顿法时，即使初始点使得迭代过程中每个迭代点的Hessian阵正定，且基本牛顿法产生的序列有聚点，也不一定是稳定点.一种可能的原因是步长为1的基本牛顿法得到的迭代点不满足Armijo条件.如果每个迭代点满足Armijo条件，可以得到基本牛顿法是收敛的，即迭代序列的聚点是稳定点.5.21考虑四元二次函数1xTGx+bTx,其中G为习题5.17中的三对角矩阵,b=√2(−1,0,2,5)T.取初始点x(0)=0，应用共轭梯度法极小化该函数,并验证经两次迭代后终止,且向量组g(0),Gg(0),G2g(0),G3g(0)中只有两个独立向量.2−100−12−10√解：G=,b=(−1,0,2,5)T，由共轭梯度法求得x∗=0−12−100−12(0.4472,1.8944,3.3416,2.7889)T,f∗=18.7082.以下验证向量组g(0),Gg(0),G2g(0),G3g(0)中只有两个独立向量. 34第五章无约束优化:线搜索法√√√首先，g(0)=Gx(0)+b=(−1,0,2,5)T,Gg(0)=(−2,−1,4−5,−2+25)T线√√√性无关.此外，易验证G2g(0)=(−3,−4+5,11−45,−8+55)T和G2g(0)=√√λ0g(0)+λ1Gg(0),其中λ0=−5+25,λ1=4−5.进一步，可验证G3g(0)=G·G2g(0)=λGg(0)+λG2g(0)=λλg(0)+(λ+λ2)Gg(0).010101由上分析可见所要验证的结论成立.由上述验证过程知g(0),Gg(0),G2g(0),G3g(0)中只有两个独立向量，又因为span{p(0),p(1),p(2),p(3)}=span{g(0),Gg(0),G2g(0),G3g(0)},故{p(0),p(1),p(2),p(3)}中也只有两个独立变量，所以共轭梯度法经两次迭代后终止.5.22(a)如果f是连续可微的,则f严格凸当且仅当Tf(y)>f(x)+∇f(x)(y−x),∀x̸=y.利用该事实证明：对于连续可微的严格凸函数,曲率条件s(k)Ty(k)>0对任一向量x(k)̸=x(k+1)成立,其中s(k)=x(k+1)−x(k),y(k)=g(k+1)−g(k).(b)给出一个单变量函数f满足f(0)=−1和f(1)=−1/4,并说明在这种情况下曲率条件不成立.解:(a)对于严格凸函数，由所给性质有f(k)>f(k+1)+g(k+1)T(x(k)−x(k+1))f(k+1)>f(k)+g(k)T(x(k+1)−x(k))将这两个不等式相加，得(g(k)−g(k+1))T(x(k+1)−x(k))<0,给该不等式两边同时乘以−1得s(k)Ty(k)>0.(b)取f(x)=−x2+7x−1，则f′(x)=−2x+7.且f(0)=−1,f(1)=44−1,f′(0)=7,f′(1)=−1.如果取x(k)=0,x(k+1)=1，则有s(k)Ty(k)=444(1−0)(−1−7)=−2<0，所以曲率条件不成立.445.23把精确步长的DFP法应用于习题5.4，其中H(0)=I.(a)验证：经过n次一维搜索后的二次终止性,且H(n)=G−1.(b)验证该方法与共轭梯度法的等价性.解：(a)原问题为最小化二次函数q(x)=10x21+x22，且[]200G=,x(0)=(0.1,1)T.02 习题535应用DFP法，其中H(0)=I.第一步迭代的相关数据如下g(0)=Gx(0)=(2,2)T,p(0)=−H(0)g(0)=−(2,2)T,g(0)Tp(0)α(0)=−=1/11,p(0)TGp(0)x(1)=x(0)+α(0)p(0)=(−9/110,9/11)T,g(1)=Gx(1)=(−18/11,18/11)T,s(0)=x(1)−x(0)=−(2/11,2/11)T,y(0)=g(1)−g(0)=−(40/11,4/11)T,[](1)(0)H(0)y(0)y(0)TH(0)s(0)s(0)T1123−119H=H−+=.y(0)TH(0)y(0)y(0)Ts(0)2222−1192301第二步迭代的相关数据为(1)1Tp=(18,−180),101α(1)=101/220,x(2)=(0,0)T,g(2)=(0,0)T,s(1)=(9/110,−9/11)T,y(1)=(18/11,−18/11)T,[]1/200H(2)=.01/2由于g(2)=0,因此迭代停止，且H(2)=G−1，得证.(b)使用共轭梯度法求解该问题，第一步迭代的相关数据如下p(0)=−g(0)=−(2,2)T,g(0)Tg(0)α(0)=−=1/11,p(0)TGp(0)x(1)=x(0)+αp(0)=(−9/110,9/11)T,0g(1)=Gx(1)=(−18/11,18/11)T,g(1)Tg(1)β(0)==81/121,g(0)Tg(0)p(1)=−g(1)+β(0)p(0)=(36/121,−360/121)T.进行第二次迭代，得α(1)=11/40,x(2)=x(1)+α(1)p(1)=(0,0)T,g(2)=(0,0)T.因为g(2)=0，迭代终止，所以两种方法具有同样的二次终止性. 第六章无约束优化：信赖域法习题设计说明：1.习题6.1：熟悉信赖域子问题的定义，及两种情况(模型函数为开口向上的抛物面的和马鞍面型的)下信赖域子问题解的特点，理解柯西点的定义与确定方法.2.习题6.2：将信赖域半径当成参数，计算特殊的信赖域子问的解与柯西点，并判断二者的关系.帮助理解刻画信赖域子问题解的结论(定理6.2.1).3.数值计算：习题6.3和习题6.4均是编写信赖域算法，其中习题6.3利用dog-leg折线法求解信赖域子问题，习题6.4利用Steihaug共轭梯度法求解信赖域子问题.请根据数值结果体会信赖域策略的意义，并体会算法的主要计算量.4.信赖域子问题中的信赖域由无穷范数定义：习题6.6-习题6.8.5.理解信赖域子问题解的刻画和求解子问题的精确数值方法：习题6.9，习题6.14.6.理解LM轨道，即2范数信赖域子问题中半径变化时，子问题的解的轨迹：习题6.10-习题6.13.6.1设f(x)=10(x2−x21)2+(1−x1)2.并假定信赖子问题的二次模型函数中取B(k)=G(k).(a)完整写出信赖域法在点x(k)=(0,−1)T的二次子问题,并画出子问题目标函数的等值线.(b)针对该子问题,画出信赖域半径从∆=0变到∆=2时,信赖域子问题解族的示意图.(c)对∆=1,求出该信赖域子问题的柯西点.对于点x(k)=(0,1)T重复上面的工作.2[][]−2420解:(a)首先f(x(k))=11,g(k)=,G(k)=.所以原问题在−20020x(k)的信赖域子问题为minimizem(s):=1(42s2+20s2)−2s−20s+11k21212subjecttos21+s22≤∆2.因为G(k)正定，所以信赖域子问题的目标函数的等值线是一族同心椭圆，求m(s)的稳定点可得椭圆的中心s∗=(1,1)T.具体的等值线族如图6.1，这里以k21s1为横坐标，以s2为纵坐标，以(0,−1)为原点.(b)当信赖域半径从∆=0变到∆=2时，可用图解法求解信赖域子问题，有三种情况√.(i)当∆=0时，解s(k)=(0,0)T；(ii)当0<∆<∥s∗∥2=1+1时，以(0,0)T为中心以∆为半径的圆与m(s)等值线的切点是信赖212k域子问题的解s(k)；(iii)当∆≥∥s∗∥2时，信赖域子问题的解即为s∗.从而，当信赖域半径从∆=0变到∆=2时，信赖域子问题解族的示意图是一条连接(0,0)T与s∗的曲线，为了示意图更准确，取∆=1，用图解法得到37 38第6章无约束优化:信赖域法子问题的解，三点就可以较精确地确定出该曲线.当信赖域半径变化时，解族的轨迹如图6.1中绿线所示.21.51(1/21,1)0.50(0,0)−0.5−1−1.5−2−2−1.5−1−0.500.511.52图6.1:x(k)=(0,−1)T处信赖域子问题解的轨迹(c)信赖域子问题的柯西点是mk(s)沿最速下降方向，且限制在信赖域内的极小点，即需要求解问题minm(−αg(k)).(6.1)k∥−g(k)∥≤∆k将该点处的梯度g(k)=(−2,−20)T,∆k=1代入(6.1)，得min4084α2−404α+110≤≤√122+202√求得目标函数的无约束极小点α∗=404=0.0495，其在约束区间[0,1/22+202]=2×4084[0,0.0499]内.故该信赖域子问题的柯西点(k)∗(k)404T101Ts=−αg=(2,20)=(1,10).C2×40841021在点x(k)=(0,1)T重复上面的工作：2[][]−2−180(a)对于点x(k)=[0,1]，f(x(k))=3.5,g(k)=,G(k)=.210020所以原问题在x(k)的信赖域子问题为minimizem(s)=1(−18s2+20s2)−2s+10s+3.5k21212subjecttos21+s22≤∆2.因为G(k)是不定的，从而信赖域子问题的目标函数的等值线是一族双曲线，渐√近线为3(s+1)±10(s+1)=0.详见图6.2.1922(b)当∆=0时，解为s(k)=(0,0)T；当0<∆≤2时，以(0,0)T为中心以∆为半径的圆与mk(s)等值线(水平双曲线的右端分支)的切点是信赖域子问题的解. 习题6392.521.510.5[0,0]0−0.5[−1/9,−1/2]−1−1.5−2−2.5−2.5−2−1.5−1−0.500.511.522.5图6.2:x(k)=(0,1)T处信赖域子问题解的轨迹2(c)将g(k)=(−2,10)T代入(6.1)，得min964α2−104α+3.5√0≤≤1=22+102√求得目标函数的无约束极小点是α∗=52，其在区间[0,1/22+102]内.故该964信赖域子问题的柯西点(k)∗(k)52Ts=−αg=−(−2,10).C9646.2假设在信赖域子问题(6.2.1)中取B=νI，其中ν为参数.记子问题(6.2.1)的解为s∗.请完成以下问题(a)写出ν=0时s∗的表达式.(b)写出ν<0时信赖域子问题的柯西点sC的表达式.(c)画出ν>0时q(sC)随信赖域半径∆变化的图像.q(s∗)解：(a)将ν=0代入m(s)，得m(s)=gTs，所以对其最小化只需取负梯度方向，并在信赖域边界上取得最优值，即s∗=−∆g.||g||2(b)记柯西点sC=−αCg.为此，令T12T12Tϕ(α)=m(−αg)=−αgg+ναgg=(να−α)gg,(6.2)22为了得到αC，需要minϕ(α).(6.3)0<<∆∥g∥2 40第6章无约束优化:信赖域法当ν<0，由(6.2)知ϕ(α)在(0,+∞)上严格单调递减.所以柯西点在信赖域边界上，即s=−∆g.C||g||2(c)先求m(sC)：当ν>0，由(6.3)知ϕ(α)在(0,+∞)上存在唯一极小点α∗=1.另外，当信赖域内不包含极小点时，柯西点在其边界上，即α=∆；C||g||2否则αC=α∗，于是{√1ν∆2−gTg∆,∆<||g||2m(s)=ϕ(α)=2CC1T||g||2−gg,∆≥.2再求m(s∗)：根据题意，B=νI正定，所以子问题是一个凸规划，且目标函数的稳定点(即无约束极小点)sˆ=−1g.如果sˆ在信赖域内，则s∗=sˆ.否则，即∆2<1gTg时，极小点只能在信赖域边界上取得((s∗Ts∗=∆2))，且此2时需考虑T12m(s)=gs+ν∆2由(a)可知，它的极小点是s∗=−∆g,所以||g||2{√1ν∆2−gTg∆,∆<||g||2m(s∗)=2−1gTg,∆≥||g||2.2最后可得m(sc)=1.这样，当ν>0时q(sC)随信赖域半径∆变化如图6.3所示.m(s∗)q(s∗)1*))/m(scm(s00∆=||g||/δ2m(sc)图6.3:m(s∗)与∆的关系'