搜索
最优化方法-习题解答张彦斌计算机学院2014年10月20日Contents1第第第一一一章章章最最最优优优化化化理理理论论论基基基础础础-P13习习习题题题1(1)、、、2(3)(4)、、、3、、、412第第第二二二章章章线线线搜搜搜索索索算算算法法法-P27习习习题题题2、、、4、、、643第第第三三三章章章最最最速速速下下下降降降法法法和和和牛牛牛顿顿顿法法法P41习习习题题题1，，，2，，，374第第第四四四章章章共共共轭轭轭梯梯梯度度度法法法P51习习习题题题1，，，3，，，6(1)105第第第五五五章章章拟拟拟牛牛牛顿顿顿法法法P73-2126第第第六六六章章章信信信赖赖赖域域域方方方法法法P86-8147第第第七七七章章章非非非线线线性性性最最最小小小二二二乘乘乘问问问题题题P98-1，，，2，，，6188第第第八八八章章章最最最优优优性性性条条条件件件P112-1，，，2,5,6239第第第九九九章章章罚罚罚函函函数数数法法法P132，，，1-(1)、、、2-(1)、、、3-(3),62610第第第十十十一一一章章章二二二次次次规规规划划划习习习题题题11P178-1（（（1））），，，5291第第第一一一章章章最最最优优优化化化理理理论论论基基基础础础-P13习习习题题题1(1)、、、2(3)(4)、、、3、、、41.验证下列各集合是凸集:(1)S={(x1,x2)|2x1+x2≥1,x1−2x2≥1};需要验证：根据凸集的定义，对任意的x(x1,x2),y(y1,y2)∈S及任意的实数λ∈[0,1],都有λx+(1−λ)y∈S.即,(λx1+(1−λ)y1,λx2+(1−λ)y2)∈S证：由x(x1,x2),y(y1,y2)∈S得到，{2x1+x2≥1,x1−2x2≥12y1+y2≥1,y1−2y2≥1(1)1把(1)中的两个式子对应的左右两部分分别乘以λ和1−λ,然后再相加，即得λ(2x1+x2)+(1−λ)(2y1+y2)≥1,λ(x1−2x2)+(1−λ)(y1−2y2)≥1(2)合并同类项，2(λx1+(1−λ)y1)+(λx2+(1−λ)y2)≥1,(λx1+(1−λ)y1)−2(λx2+(1−λ)y2)≥1(3)证毕.2.判断下列函数为凸（凹）函数或严格凸（凹）函数：(3)f(x)=x21−2x1x2+x22+2x1+3x2首先二阶导数连续可微，根据定理1.5，f在凸集上是（I）凸函数的充分必要条件是∇2f(x)对一切x为半正定；（II）严格凸函数的充分条件是∇2f(x)对一切x为正定。∇2f(x)=(2−2−22)(4)半正定矩阵（4）∇2f(x)=41−3120−304(5)正定矩阵3.证明f(x)=12xTGx+bTx为严格凸函数当且仅当Hesse矩阵G正定。证明：根据严格凸函数定义证明。对任意x̸=y,及任意实数λ∈(0,1)都有f(λx+(1−λ)y)λf(x)+(1−λ)f(y).充分性：Hesse矩阵G正定=》严格凸函数.f(λx+(1−λ)y)=12(λx+(1−λ)y)TG(λx+(1−λ)y)+bT(λx+(1−λ)y)λf(x)+(1−λ)f(y)=λ(12xTGx+bTx)+(1−λ)(12yTGy+bTy)λf(x)+(1−λ)f(y)−f(λx+(1−λ)y)=λ(12xTGx)+(1−λ)(12yTGy)−[12(λx)TG(λx)+12(1−λ)yTG(1−λ)y+12λxTG(1−λ)y+12(1−λ)yTGλx]=12λxTG(1−λ)x+12(1−λ)yTGλy−12λxTG(1−λ)y−12(1−λ)yTGλx2=12λxTG(1−λ)(x−y)+12(1−λ)yTGλ(y−x)=12λ(1−λ)(x−y)TG(x−y)0G正定保障了严格不等式成立。反之，必要性：严格凸函数=》Hesse矩阵G正定.类似，当对任意x̸=y,及任意实数λ∈(0,1)都有f(λx+(1−λ)y)λf(x)+(1−λ)f(y).λf(x)+(1−λ)f(y)−f(λx+(1−λ)y)=λ(12xTGx)+(1−λ)(12yTGy)−[12(λx)TG(λx)+12(1−λ)yTG(1−λ)y+12λxTG(1−λ)y+12(1−λ)yTGλx]=12λxTG(1−λ)x+12(1−λ)yTGλy−12λxTG(1−λ)y−12(1−λ)yTGλx=12λxTG(1−λ)(x−y)+12(1−λ)yTGλ(y−x)=12λ(1−λ)(x−y)TG(x−y)04.若对任意x∈ℜn及实数θ0都有f(θx)=θf(x),证明f(x)在ℜn上为凸函数的充要条件是∀x,y∈ℜn,f(x+y)≤f(x)+f(y)证明：根据严格凸函数定义证明。定义：对任意x̸=y,及任意实数λ∈(0,1)都有f(λx+(1−λ)y)≤λf(x)+(1−λ)f(y).充分条件：∀x,y∈ℜn,有f(x+y)≤f(x)+f(y)对任意x̸=y,及任意实数λ∈(0,1)都有f(λx+(1−λ)y)≤f(λx)+f((1−λ)y)利用f(θx)=θf(x),f(λx+(1−λ)y)≤f(λx)+f((1−λ)y)=λf(x)+(1−λ)f(y).充分性证毕；必要性：f(x)在ℜn上为凸函数=》∀x,y∈ℜn,f(x+y)≤f(x)+f(y)根据定义有对任意x̸=y,及任意实数λ∈(0,1)都有f(λx+(1−λ)y)≤λf(x)+(1−λ)f(y).不妨取λ=12,则f(12x+(1−12)y)≤12f(x)+(1−12)f(y).利用f(θx)=θf(x),f(12(x+y))=12f(x+y)≤12(f(x)+f(y))∀x,y∈ℜn,f(x+y)≤f(x)+f(y)证毕!32第第第二二二章章章线线线搜搜搜索索索算算算法法法-P27习习习题题题2、、、4、、、6第2题：黄金0.618算法：function[s,phis,k,G,E]=golds(phi,a,b,delta,epsilon)%输入：phi是目标函数，a，b是搜索区间的两个端点%delta，epsilon分别是自变量和函数值的容许误差%输出:s,phis分别是近似极小点和极大值，G是n×4矩阵，%其第k行分别是a,p,q,b的第k次迭代值ak,pk,qk,bk,%E=[ds,dphi],分别是s和phis的误差限%%%%%%%%%%t=(sqrt(5)-1)/2;h=b-a;phia=feval(phi,a);phib=feval(phi,b);p=a+(1-t)*h;q=a+t*h;phip=feval(phi,p);phiq=feval(phi,q);k=1;G(k,:)=[a,p,q,b];while(abs(phib-phia)epsilon)|(hdelta)if(phipphiq)b=q;phib=phiq;q=p;phiq=phip;h=b-a;p=a+(1-t)*h;phip=feval(phi,p);elsea=p;phia=phip;p=q;phip=phiq;h=b-a;q=a+t*h;phiq=feval(phi,q);end4k=k+1;G(k,:)=[a,p,q,b];endds=abs(b-a);dphi=abs(phib-phia);if(phip=phiq)s=p;phis=phip;elses=q;phis=phiq;endE=[ds,dphi];运行：[s,phis,k,G,E]=golds(inline(′s3−2∗s+1′),0,3,0.15,0.01);结果ak,pk,qk,bk01.14591.85413.000000.70821.14591.854100.43770.70821.14590.43770.70820.87541.14590.70820.87540.97871.14590.70820.81150.87540.97870.70820.77210.81150.87540.77210.81150.83590.8754(6)[s,phis,k,G,E]=golds(inline(′s3−2∗s+1′),0,3,0.15,0.001);≫GG=501.14591.85413.000000.70821.14591.854100.43770.70821.14590.43770.70820.87541.14590.70820.87540.97871.14590.70820.81150.87540.97870.70820.77210.81150.87540.77210.81150.83590.87540.77210.79650.81150.83590.79650.81150.82080.8359(7)第4题：≫clearall;[s,phis,k,ds,dphi,S]=qmin(inline(′s3−2∗s+1′),0,3,1e−2,1e−4);≫ss=0.8165第6题functionf=fun(x)f=100∗(x(2)−x(1)2)2+(1−x(1))2;functiongf=gfun(x)gf=[−400∗(x(2)−x(1)2)∗x(1)−2∗(1−x(1)),200∗(x(2)−x(1)2)]′;functionmk=armijo(xk,dk)beta=0.5;sigma=0.2;m=0;mmax=20;while(m=mmax)if(fun(xk+betam∗dk)=fun(xk)+sigma∗betam∗gfun(xk)′∗dk)mk=m;break;6endm=m+1;endalpha=betamknewxk=xk+alpha*dkfk=fun(xk)newfk=fun(newxk)clearall;xk=[-1,1]';dk=[1,1]';mk=armijo(xk,dk)alpha=0.0020newxk=-0.99801.0020fk=4newfk=3.9956mk=93第第第三三三章章章最最最速速速下下下降降降法法法和和和牛牛牛顿顿顿法法法P41习习习题题题1，，，2，，，3第1题：functionf=funone(x)7f=3∗x(1)2+2∗x(2)2−4∗x(1)−6∗x(2);functiongf=gfunone(x)gf=[6∗x(1)−4,4∗x(2)−6]′;≫x0=[0,1]';[xvalk]=grad('funone','gfunone',x0)x=0.66671.5000val=-5.8333k=10第2题：(1)牛顿法functionf=funtwo1(x)f=4∗x(1)2+x(2)2−8∗x(1)−4∗x(2);functiongf=gfuntwo1(x)gf=[8∗x(1)−8,2∗x(2)−4]′;x0=[0,1]';[xvalk]=grad('funtwo1','gfuntwo1',x0)x=12val=-88k=2（2）阻尼牛顿法functionHe=Hesstwo(x)n=length(x);He=zeros(n,n);He=[8,0;0,2];≫x0=[0,1]';[xvalk]=dampnm('funtwo1','gfuntwo1','Hesstwo',x0)x=12val=-8k=1第3题.functionf=fun(x)f=(x(1)−2)4+(x(1)−2∗x(2))2;functiongf=gfun(x)gf=[4∗(x(1)−2)3+2∗(x(1)−2∗x(2)),−4∗(x(1)−2∗x(2))]′;≫clearall;≫x0=[03]';[v,val,k]=grad('fun','gfun',x0)9x=2.01391.0070val=3.7685e-008k=21114第第第四四四章章章共共共轭轭轭梯梯梯度度度法法法P51习习习题题题1，，，3，，，6(1)1.证明向量α1=(1,0)T和α2=(3,−2)T关于矩阵A=(2335)(8)共轭.验证αT1Aα2=0.3.设f(x)=12x