最优化习题答案及复习资料

1最优化习题答案最优化习题答案最优化习题答案最优化习题答案第一章一、考虑二次函数()2211221223fXxxxxxx=++-+1)写出它的矩阵—向量形式:()fX=12TTQxxxb+2)矩阵Q是不是奇异的?3)证明:f(x)是正定的4)f(x)是凸的吗?5)写出f(x)在点x=()2,1T处的支撑超平面(即切平面)方程解:1)f(x)=xxxxxx2122212132+-++=xx21216222xx21+11T-xx21其中x=xx21,Q=6222,b=-112)因为Q=6222,所以|Q|=6222=80即可知Q是非奇异的3)因为|2|0,6222=80,所以Q是正定的,故f(x)是正定的4)因为2()fx∇=6222,所以|)(2xf∇|=80,故推出)(2xf∇是正定的,即)(2xf∇是凸的5)因为)(xf∇=2121(2x2-1,261)xxxT+++,所以)(xf∇=(5,11)所以()fx在点x处的切线方程为5(21-x)+11(12-x)=0二、求下列函数的梯度问题和Hesse矩阵1)()fx=2x12+xxxxx23923121+++xxx2322+2)()fx=2212()21nlxxxx++解:1))(xf∇=(,94321xxx++26321+++xxx,xx219+)2)(2xf∇=0191619142))(xf∇=(xxxxxx112221221+++,xxxxxx112221221+++))(2xf∇=----------++++++++)()()()(2221212222212142221214222121222222121222212122221212212122xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx三、设f(x)=xxxxxxx323223322122--+++,取点)1,1,1()1(Tx=.验证d)1(=(1,0,-1)是f(x)在点x)1(处的一个下降方向,并计算0mintf(x)1(+td)1()证明:)(xf∇=)124,123,x2(233221-+-+xxxxT)5,4,2()(1Txf=∇d)(1xf∇=(1,0,-1)542=-30所以d)1(是f(x)在x)1(处的一个下降方向f(x)1(+td)1()=f((1+t,1,1-t))=433)1(1)1(221(222)1()1+-=----+++-+tttttt∇f(x)1(+td)1()=6t-3=0所以t=0.50所以0mintf(x)1(+td)1()=3*0.25-3*0.5+4=3.25四、设,,iiiabc（j=1,2,….,n）考虑问题Minf(x)=∑=njjjxc13s.t.bnjjjxa=∑=10≥xj(j=1,2,….,n)1)写出其KuhnTuker条件2)证明问题最优值是])([12112∑=njjjbca解：1）因),....,1(njxj=为目标函数的分母故0xj所以λ*j（j=1,…,n）都为0所以KuhnTuker条件为0)()(=∇+∇xhxfμ即---xcxcxcnn2222211M+aaanM21μ=02）将acxjjjμ=代入h(x)=0只有一点得2211()njjjnbnjjjbacacμ==⇒=∑=∑故有accaxjjnjjjjb∑==1所以最优解是21211()njjjbac=∑.五、使用KuhnTuker条件，求问题minf(x)=)2()1(2122--+xx4s.t.0,021212112≥≥=+=-xxxxxx的KuhnTuker点，并验证此点为问题的最优解解：x=(1/2,3/2)0≠故1λ*，λ*2=0则0)()()(2211=+∇+∇xxxfhhμμ即0111142222121=+-+--μμxx⇒120,1μμ==-而=∇2002)(2xf()210gx*∇=()220gx*∇=()210hx*∇=()220hx*∇=,()()()()()()()22222211221122Hxfxgxgxhxhxfxλλμμ***********=∇+∇+∇+∇+∇=∇(){}{}12121213|00|1020,22TTTxyhyhyyyyyy*=∇=∇==-+-=+-==故08)(2=∇xxfxT,即其为最优解.第二章一、设f(x)为定义在区间[a,b]上的实值函数，x*是问题min{f(x)|abx≤≤}的最优解。证明：f(x)是[a,b]上的单谷函数的充要条件是对任意xxxxba2121],,[,≠∈满足f(xx21)1(λλ-+)max{f(x1),f(x2)},)1,0(∈λ证明：不妨设x1x2,则x1xxx221)1(-+λλ“必要性”若xxx*-+21)1(λλ则由单谷函数定义知)())1((121xxxff-+λλ故有)}(),(max{))1((2121xxxxfff-+λλ5“充分性”由x1，x2的任意性取x1=x*时，f(x2)f(x1)则x2xx21)1(λλ-+x1=x*且f(xx21)1(λλ-+)f(x2)若取x2=x*时,f(x1)f(x2)x1xx21)1(λλ-+x2=x*且f(xx21)1(λλ-+)f(x1)满足单谷函数的定义二、设x1x2,0)(,0)(21′′xxff1)证明:满足条件)()(),()(),()(221111xxxxxxfff′=′′=′=φφφ的二次函数)(xφ是（严格）凸函数2）证明：由二次插值所得f(x)的近似极小值点（即)(xφ的驻点）是)()()()(122122xxxxxxfffx′-′′--=或者)()()()(121121xxxxxxfffx′-′′--=证明：1）设)(xφ=cbxax++2（0≠a）则baxx+=′2)(φ由)(2)()(2)(222111xxxxxxfbafba′=+=′′=+=′φφ得)())()(()(,0)(2)()(1212111212xxxxxxxxxxfffbffa-′-′-′=-′-′=或)())()(()(121222xxxxxxfffb-′-′-′=故1）得证2）)(xφ的驻点为)()()()(2121121xxxxxxfffabx′-′′--=-=或-=xx2)()()()(12212xxxxxfff′-′′-6三、设f(x)=0,21=++QcxQxQbxTTT试证：共轭梯度法的线性搜索)()()()()()(0mindtxdxkkkkktftf+=+≥中，有dddgtkTkTkkQk)()()()(-=，其中)()(xgkkf∇=证明：由已知，得bQxxf+=∇)(令=)(tφ)()()(dxkktf+为t的凸二次函数。要使tk是)(tφ的极小点即为驻点，故满足0)(=′tkφ而∇=′)(tkφ)()()(dxkktf+dk)(=dbdtxQkTkk)(])([)()(++=ddtQbxQkTkk)(][)()(++=dddgkTkTkQkt)())((+）（故有0)(()()=+ddtdgkTkkTkQk）（得dddgtkTkTkkQk)()()()(-=四、用共轭梯度法求解：minf(x)=xxxxx121222122123--+,xR2∈取初始点)4,2()1(-=Tx解：易知--=1113A-=02b第一次迭代：),23(1221)(xxxxTxf---=∇)6,12()(11-=∇=Txgf)6,12()()1()1(-=-∇=Txdf7线性搜索得步长1756121113)6,12(612)6,12()1()1()1(11)(=-------=-=dddgATTα从而dxx)1(1)1()2(α+==3826171第二次迭代：)1712,176()()2(Txf=∇=g2)1712,176(T=β12981)1()1()1(2)(=-dddgAATT--=+-=28921028990)1(12)2(dgdβ线性搜索得步长：7.12=α=+=11)2(2)2()3(dxxα)0,0()()3(3Txgf=∇=所以最优解为)1,1(*Tx=五、用拟Newton法求解：minRxxxxxxxf21212221,422)(∈--+=取初始点)1,1()1(Tx=解：1）DFC法取初始对称矩阵=10011H第一次迭代：计算得)2,4(1-=Tg，8)2,4(111-=-=TgHd经一维线性搜索得：α1=0.25)25.0,2(1112Tdxx=+=α)5.0,1(1-=Tδ)4,3(1-=Ty)2,1(2--=Tg2.011111==yHyyTTrδ置==2.0002.011HHr--=-+=472.0704.0204.0728.01111111111112yHyHyyHyyHHTTTTδδ第二次迭代)24.0,32.0(222TgHd=-=经一维线性搜索得：α1=6.25)2,4(2223Tdxx=+=α)0,0(3Tg=故最优解为：)2,4(3*Txx==2）BFGS法取定初始对称矩阵=10011H第一次迭代：计算得)2,4(1-=Tg，)2,4(111-=-=TgHd经一维线性搜索得：α1=0.259)25.0,2(1112Tdxx=+=α同DFP法，初始修正矩阵=2.0002.01H=--++=14.002.002.036.0)1(11111111111111112yHyyHyyHyHHTTTTTδδδδδδ第二次迭代：)3.0,4.0(222TgHd=-=经一维线性搜索得：52=α)2,4(2223Tdxx=+=α)0,0(3Tg=故最优解为：)2,4(3*Txx==第三章一、给定问题minxxxxxxxf212221211462)(--++=s.t.0,0,032232121321≥≥≥≤+-=++xxxxxxxx取初始点)0,1,1()1(Tx=，用简约梯度法求其最优解解：约束条件为0,0,032232121321≥≥≥≤+-=++xxxxxxxx则)0,1,1()1(Tx=，-=10210111A)0014462(2121)(-+-+=∇xxxxTxf()00931--=Tg10{}211=I-=2111B=1001N)(1)()(xfxfBTNNNBg∇∇--===----25933131313200-=40dN-=-=-34341TNBdBdN)403434()1(--=Td()ddxdxTff)1()1()1()()1()1()(αααφ+∇=+′=′=0324964=-α得89=α21}42min{max=--=α得21},min{max1==ααα)003531()1(1)1()2(Tdxx=+=α--=0073112Tg}2,1{2=I-=2111B=1001N=----=91094373113131313200gN=00dN=-=-001dBdNBN0)2(=d11故)003531