北航最优化方法习题2015版(下)

数学规划基础部分习题参考解答刘红英编北京航空航天大学数学与系统科学学院2015年6月内容简介本书是《数学规划基础》(刘红英，夏勇，周水生，北京航空航天大学出版社，2012.10)的配套教学辅导材料，较详细地给出了该教材各章后部分习题的参考解答.前言本习题解答自2008年春季开始编写，当时由硕士研究生阎凤玉提供部分习题解答，经讨论和确认后，由作者首次录入排版.后来陆续参加习题解答修订的硕士研究生包括王浩、欧林鑫、朱丽媛、易彩霞和杨茜，其中的数值结果由欧林鑫提供.作者在此向他们的辛勤劳动表示衷心的感谢.本解答得到了？项目的资助，在此表示感谢.由于这些参考解答尚未经过特别严格的校对，仅供参考.任何意见、建议或其它反馈都可以发送至[e-mail]，在此深表感谢.刘红英2015.6于北京目录第七章约束优化：理论1第八章约束优化：线性约束规划13第九章约束优化：非线性约束规划155第七章约束优化：理论习题设计说明：1.KKT条件的理解和应用：习题7.1-习题7.3，习题7.5，习题7.7，习题7.21(凸规划).2.深刻理解KKT条件：KKT条件中的约束规范的作用(习题7.6，习题7.7(a))；La-grange乘子的意义(习题7.4)；如果积极约束是线性无关的，即LICQ成立，如何设计数值稳定的算法得到Lagrange乘子(习题7.8)；非积极约束对问题局部解和全局解的影响(习题7.20).3.二阶最优性条件：习题7.9.4.凸函数的性质与次梯度：习题7.10-习题7.11.5.Lagrange对偶：习题7.12-习题7.14(如何写对偶)，其中习题7.13体会写对偶时的灵活性(即确定那些约束松弛到目标中)，习题7.15(结合具体例子理解对偶定理).6.SDP的相关练习：习题7.16(SDP中常用的事实)，习题7.17(熟悉SDP的对偶理论)，习题7.18(该结论在工程中很常用).7.表述练习：习题7.19给出了工程中常用的三种最优化问题，所给问题是非光滑函数的无约束最优化，常用的软件不能求解这些问题.利用解决习题2.2和习题2.3时的技巧，可以把这些问题重新表述成光滑的约束最优化，从而利用常用的优化软件进行求解.7.3考虑问题minimizex∈R2(x1−94)2+(x2−2)2subjectto−x21+x2≥0x1+x2≤6x1≥0,x2≥0.(a)写出KKT条件,并验证点x∗=(32,94)T满足这些条件.(b)给出x∗处KKT条件的几何解释.(c)说明x∗是该问题的最优解.解:(a)L(x,)=(x1−94)2+(x2−2)2+λ1(x21−x2)+λ2(x1+x2−6)+λ3(−x1)+λ4(−x2).∇xL(x,)=[2(x1−94)+2λ1x1+λ2−λ32(x2−2)−λ1+λ2−λ4].12第7章约束优化:理论KKT条件:2(1+λ1)x1+λ2−λ3−92=02x2−λ1+λ2−4=0x21−x2≤0x1+x2−6≤0x1≥0,x2≥0λ1(−x21+x2)=0λ2(6−x1−x2)=0λ3x1=0,λ4x2=0λi≥0,i=1,2,3,4.首先，因为x∗=(32,94)T满足约束条件，且有I(x∗)={1},所以由互补条件有λ∗2=λ∗3=λ∗4=0.再将g∗=(−32,12)T,a∗1=(3,−1)T.代入上边的梯度条件，即KKT条件的前两个方程，解得λ∗1=12.从而x∗满足KKT条件.(b)在x∗处，c1(x)=x21−x2为积极约束，且梯度a∗1=(3,−1)T，而g∗=(−3/2,1/2)T，易见g∗=−12a∗1.所以x∗处目标函数与积极约束的梯度共线，且方向相反.(c)目标函数显然为凸函数.c1(x)=x21−x2为凸函数，其余约束是线性函数，所以此问题为凸规划，从而KKT点即是全局解.所以x∗是该问题的全局解.7.4计划修建一个长x1,高x2,宽x3(单位:m),容积1500m3的仓库.每平方米的修建费用是:墙4元,屋顶6元,地板加地面处理共12元.由于美学原因,长应该是高的两倍.为了寻找花费最小的设计方案,(a)将该问题表述成优化问题,写出KKT条件,并由KKT条件确定解x∗和Lagrange乘子∗;(b)从所得优化问题中消去x1和x3,说明距所得解最近的整数x2=10使得费用最小,然后回代算出x1和x3;(c)设容积约束为c1(x)=0.在问题中将容积约束变成c1(x)=ϵ时,用(a)中的方法求出f(x)在所得解处的改变量h(ϵ)并验证h′(0)=−λ∗1，计算目标值的改变量h(−150)，即将所需容积缩减10%时成本的改变量;比较h(−150)与由Lagrange乘子得到的估计值−λ∗1ϵ.解:(a)设费用为f(x)，依据题意，得minimizef(x)=8x1x2+8x2x3+18x1x3subjecttox1x2x3−1500=0x1−2x2=0.Lagrange函数L(x,)=8x1x2+8x2x3+18x1x3+λ1(x1x2x3−1500)+λ2(x1−2x2).习题73KKT条件为8x2+18x3+λ1x2x3+λ2=0,8x1+8x3+λ1x1x3−2λ2=0,8x2+18x1+λ1x1x2=0,x1x2x3−1500=0,x1−2x2=0.由两个等式约束得x1=2x2,x3=750x22,从而原问题可既约为minimize16x22+33000x2subjecttox20.求稳定点，得x∗2=103√3332.将x∗代入KKT条件中的梯度条件(第一个和第三个方程)，解得Lagrange乘子∗=(λ∗1,λ∗2)T=(−22x2,−8x∗2+3000x22)T.(b)x∗2=103√33/32∈(10,11).由于f(x)=16x22+33000x2在[0,103√33/32]上递减，且f(10)=4900,在[103√33/32,∞]上递增且f(11)=4936，从而x2=10使得费用最小.此时x1=20,x3=7.5，这样，我们得到一个实用的设计方案(20,10,7.5).(c)若将c1(x)=0改变为c1(x)=ε，得扰动问题minimizef(x)=8x1x2+8x2x3+18x1x3subjecttox1x2x3−1500=εx1−2x2=0.类似于(a)中的解法，可得x2(ε)=3√33000+2232,x1(ε)=2x2,x3(ε)=1500+2x22.代入目标函数，得h(ε)=f(x(ε))−f(x∗)=16(x2(ε))2+221500+εx2(ε)−16(x∗2)2−33000x∗2关于ε求导数，得h′(0)=(32x∗2−33000(x∗2)2)x′2(0)+22x∗2,其中x′2(0)表示x2(ε)关于ε的导数在0处的值.由x∗2的求法知32x∗2−33000(x2)2=0，所以h′(0)=−λ∗1.这验证了教材上的式(7.2.9)所给出的结论.当容积减到1350m3时，ε=−150，此时x2=9.7544,h(−150)=−332.3333.根据灵敏度分析，我们也可以得到h(−150)≈−λ∗1(−150)=(−150)22x∗2=−326.6324.(7.1)4第7章约束优化:理论比较这个近似值与精确值，发现近似程度是很高的.这表明：利用灵敏度分析，我们不用求容积改变后的新问题，而直接利用近似式(7.1)知道容积减少10%后，成本将近似减少326.6324元.7.6考虑找曲线(x−1)3=y2上哪个点离原点最近(在Euclidean范数意义下)的问题.可以将该问题表述为minimizex;yf(x,y)=x2+y2subjectto(x−1)3=y2.(a)用图解法求解该问题.消去y求解问题,所得到的函数有极小点吗？给出结果不一致的可能原因.消去x求解问题,得到怎样的结果?(b)对于该问题,找到所有的KKT点.LICQ成立吗?请给出结果可能的解释.解:(a)问题的可行集和目标函数的等值线如图7.1，其中目标函数的等值线是以圆点为中心的同心圆，易见问题的最优解x∗=1,y∗=0.−1012−2−1012(x−1)3=y2xy0.312contouroff(x,y)=x2+y2[1,0]图7.1:使用消元法需要注意的问题由等式约束得到y2=(x−1)3，将其代入目标函数，得到minxx2+(x−1)3，此时问题无界；这种消元法在将y2=(x−1)3代入目标函数时忽略了x≥1这个等式约束所蕴含的条件.由等式约束得到x=y2=3+1，将其代入目标函数，得到miny(y2=3+1)2+y2.易见最优解y∗=0，于是得原问题的解x∗=1,y∗=0.(b)该问题的Lagrange函数L(x,y,λ)=x2+y2+λ((x−1)3−y2).KKT条件为：2x+3λ(x−1)2=02y−2λy=0(x−1)3−y2=0.第二个方程可写成2y(1−λ)=0.对其分情况讨论可求解该方程组.具体地，若习题75y=0,则x=1,此时第一个方程无解；若λ=1,此时第一个方程无解.所以该问题没有KKT点！在该问题的最优解x∗=1,y∗=0处，约束梯度a∗=(0,0)T，它不满足LICQ，故不能保证问题的解x∗=1,y∗=0一定满足KKT条件.注记:该问题的(a)说明消元时需要谨慎，否则可能会忽略掉一些隐含条件；从而得出错误的结论；(b)说明引入约束规范的意义，即对于一个优化问题，当最优解处约束规范不成立时，即使是最优解，也可能不满足KKT条件，即不存在Lagrange乘子.7.7考虑问题minimizex∈R2−x1subjecttox21+x22≤1,(x1−1)3−x2≤0.(a)说明线性无关约束规范(LICQ)条件在点x∗=(1,0)T处成立.(b)说明点x∗=(1,0)T是一个KKT点.该点是全局极小点吗？请给出理由.(c)考虑盒子(界)约束优化问题minimizex∈Rnf(x)subjecttoli≤xi≤ui,i=1,2,···,n,(7.2)其中li,ui(i=1,2,···,n)是给定的常数，f(x)是连续可微函数.请问该问题一定有KKT点吗?为什么？如果有KKT点，它一定是问题的最优解吗？请给出理由.解：(a)由a1(x)=(2x1,2x2)T,a2(x)=(3(x1−1)2,−1)T得，a∗1=(2,0)T,a∗2=(0,−1)T.明显地，a∗1,a∗2线性无关，所以LICQ条件成立.(b)原问题的Lagrange函数是L(x,)=−x1+λ1(x21+x22−1)+λ2[(x1−1)3−x2].因为x∗是可行点，积极约束指标集I∗={1,2}，g∗=(−1,0)T，从而判断KKT条件是否成立简化为判断关于的方程组∇xL(x∗,)=g∗+λ1a∗1+λ2a∗2=0是否有非负解.解之得∗=(12,0)，得到非负的Lagrange乘子，且显然满足互补条件，从而x∗是KKT点.此外，由约束x21+x22−1≤0可知−1≤x1≤1，所以目标函数−x1在边界1上取最小值，因而x∗是全局极小点.(c)问题(7.2)的约束集是有界闭集，从而若目标函数f(x)连续，则连续函数必可在有界闭集上取到极小值.从而(7.2)存在极小点.因为这个问题的所有约束是线性的，故满足线性约束规范(LCQ)条件，从而极小点必是KKT点.从而当f(x)连续时，必存在KKT点.假设x∗是KKT点，它不一定是问题的最优解.仅当这个问题是凸规划时，x∗才是问题的全局最优解.此外，当KKT点惟一时，它也是问题的全局极小点.6第7章约束优化:理论7.9利用一阶和二阶最优性条件找到函数f(x)=x1x2在单位圆x21+x22=1上的极小点，并用图解法求解该问题.解:问题的可行集和目标函数的等值线如图7.2，其有两个局部极小点，分别是(√22,−√22)T和(−√22,√22)T.−2−1012−2−1012x12+x22=1x1x2−0.5−1−20.512−0.50.512−1−20contouroff(x)=x1x2x(1)x