最优化方法复习题含答案推荐文档

附录5《最优化方法》复习题11、设A壬Rn如是对称矩阵，b€Rn,cER,求f(x)=^xTAx+bTx+c在任意点x处的梯度和Hesse矩阵.解'f(x)=Axb八2f(x)=A.2、设:()=f：x d),其中f ：Rn》R二阶可导，Rn,d• Rn,t R，试求，(t).解：(t)八f(xtd)Td,:(t)二dT'、2f(xtd)d.3、设方向dRn是函数f(x)在点x处的下降方向，令ddT'f(x)'f(x)T

dTif(x) '、f(x)Tif(x)，其中I为单位矩阵，证明方向p--H'f(x)也是函数f(x)在点x处的下降方向.证明由于方向d是函数f(x)在点x处的下降方向，因此\f(x)Td<0，从而'f(x)Tp-f(x)THIf(x)ddTFf(x)\f(x)=_Vf(x)(Idbf(x)、(x)Tif(x)二亠、f(x)Sf(x)'f(x)Td0，所以,方向p是函数f(x)在点x处的下降方向.4、s-Rn是凸集的充分必要条件是-m_2, S, )1,Xm的一切凸组合都属于S.证明充分性显然.下证必要性.设S是凸集，对m用归纳法证明.当m=2时,由凸集的定义知结论成立，下面考虑m二k1时的情形.令x-7、x，Hi其中xiS,\-0,^1,2J||,k1，且a\ .不妨设'k (不然x=Xk1•S，i=1” k入 —结论成立)，记y=送;为，有x=(1-人十)y中人十Xk十，i#1一z-k4rk又—tzzL，则由归纳假设知，y・S,而Xk「s，且S是凸集，故xS.5、设S Rn为非空开凸集，f:S>R在S上可微，证明：f为S上的凸函数的充要条件是f(X2)_f(Xi)If(Xi)T(X2-Xi),-Xi,X2S.证明必要性.设f是S上的凸函数，贝U-Xi,X^S及…(0,1)，有f(，x2(1-，)xj_，f(x2)(1-，)f(X)，于是f(Xi ©7))-心儿似)_f(Xi)，因S为开集，f在S上可微，故令•》0,，得'、f(Xi)T(X2 -Xi)乞f(X2)-f (Xi)，即f(X2)—f(Xi) \、f(Xi)T(X2 -Xi),-Xi,X2 S.充分性.若有f(X2)—f(Xi)If(Xi)T(X2-Xi),-Xi,X2S，则-■ [0,I]，取X•(i-■)x2•S，从而f(Xi)一f(x)'、f(x)T(Xi-x)，f(X2)一f(x)'、、f(x)T(X2-x)，将上述两式分别乘以，和i-■后，相加得■f(x1)(i-'；)f(x2)_f(x)'f(x)t(■捲(i )x2-x)=f(x)=f(Xi(i-■)X2)，所以f为凸函数.6证明：凸规划minf(x)的任意局部最优解必是全局最优解.证明用反证法.设0S为凸规划问题minf(x)的局部最优解，即存在X的某个：邻域N(x)，使f(x^lf(x),-XN、G)nS.若X不是全局最优解，则存在XS，使f(X)：：：f(x).由于f(x)为S上的凸函数，因此一'(0,1)，有f(■X(1-■)X)「f(X)(1-■)f(X)：：f(x).当■充分接近1时，可使・x•(1—，)x，N」x)ns，于是f(x)_f(，x•(1一，)x),矛盾•从而x是全局最优解.7、设sRn为非空凸集，f:S>R是具有一阶连续偏导数的凸函数，证明：x是问题minf(x)的最优解的充要条件是：if(x)T(x-X)_0,-x・S.X手证明必要性.若x为问题minf(x)的最优解.反设存在xs，使得x：S、f(x)T(x-x)：：：0，则d=x-x是函数f(x)在点x处的下降方向，这与x为问题minf(x)的最优解矛盾•故'f(x)T(x-x)_0,-x•S.充分性•若'、f(x)T(x-x)_0,-xS.反设存在x=S，使得f(*)：：f(x).f(x (x-x))-f(x)_f(x(i-)x)-f(x)Jf(x)(1」)f(x)—f(x)=f(x)-f(x»0(「(0,i)，z因S为凸集，f在S上可微，故令•》0,，得if(x)T(x-x)乞f(*)-f(x)::0，这与已知条件矛盾，故x是问题minf(x)的最优解.8、设函数f(x)具有二阶连续偏导数，xk是f(x)的极小点的第k次近似，利用f(x)在点Xk处的二阶Taylor展开式推导Newton法的迭代公式为Xki二Xk-[I2f(Xk)]'、f(xk).证明由于f(x)具有二阶连续偏导数，故1f(x) ：(x)二f(Xk)If(Xk)T(x-Xk)?(x-Xk)T'、2f(Xk)(X-Xk).且「f(Xk)是对称矩阵，因此 ：(x)是二次函数.为求 (X)的极小点，可令I「(x)二0,即'f(Xk)飞2f(xk(x夕k=0，若V2f(Xk)正定，则上式解出的(x)的平稳点就是(X)的极小点，以它作为f(X)的极小点的第k1次近似，记为Xk1，即Xk^Xk 2f(Xk)]f(Xk)，这就得到了Newton法的迭代公式.9、 叙述常用优化算法的迭代公式.

(1)0.618法的迭代公式：k7〈「)43,Jk(2)Fibonacci法的迭代公式:■k=3k•F^Wk-aQ,F「 (k",2,山，(1)0.618法的迭代公式：k7〈「)43,Jk(2)Fibonacci法的迭代公式:■k=3k•F^Wk-aQ,F「 (k",2,山，n-1).占(bk-aQFn_k1(3)Newton一维搜索法的迭代公式:tk—tk』(tk)(4)1最速下降法用于问题minf(x)=-xTQx•bTxc的迭代公式:2叫)Eg軒&)vf(Xk)TQf(Xk)(k)(5)Newton法的迭代公式：Xk1二Xk「八2f(xj］亠、f(xj.(6)1共轭方向法用于问题minf(x^-xTQxbTxc的迭代公式:2可f(Xk)Td—兀1一Xk- — dk.dgdk10、已知线性规划:minf(x)=2%-x2x3;s.t3x1x2x^-60,为_2x2+2x3兰10,M+x2—x3兰20,N，X2，X3一0.(1)用单纯形法求解该线性规划问题的最优解和最优值;(2)写出线性规划的对偶问题;(3)求解对偶问题的最优解和最优值.解(1)引进变量X4,X5,X6，将给定的线性规划问题化为标准形式:minf(x)=2为一x2+x3;s.t3x1+X2+x3十X4=60,彳 为一2x2+2x3+X5=10,为+X2—X3+x6=20,M,X2」II,X6^0.

XiX2X3X4X5X6X431110060X51-2201010X611*-100120f-21-10000X420210-140X530001250X211-100120f-30000-1-20所给问题的最优解为X二(0,20,0)T，最优值为f.-20•所给问题的对偶问题为：(1)"maxg(y)=~60%—10y2—20y3；S.t_3yi_y2_y3(1)“ -yrH2y^y^-1,-yi-2y2+y3"[yi,y2,y3X0.将上述问题化成如下等价问题：minh(y)=60yi+10y2+20y3；s.t-3y)_y2_y3_2,< -yrH2y^y3<-1,—yi—2y?+y3兰i,yi,y2,y3-0.引进变量y4,y5,y6，将上述问题化为标准形式:minh(y)=60%+i0y2+20y3;s.t—3% -办*y4=2,< —yi+2y?—y3+y5=T,—yi—2y2+y3+y6=1,I yi,y2,川,y6^0.

y1y2y3y4y5y6y4-3-1-11002y5-12-1*010-1y6-1-210011h-60-10-200000y4-2-301-103y31-210101y6-2000110h-40-5000-20020问题(2)的最优解为y=(o,o,i)T，最优值为匸=20(最小值).问题(1)的最优解为y=(0,0,1)T，最优值为g=-20(最大值).0.2，初11、用0.618法求解min「(t)=(t-3)0.2，初始区间取[0,10]•解第一次迭代：取⑻力]=[0,10],；=0.2.确定最初试探点、，丄1分别为\=印0.382(0-印)=3.82，-、二q0.618(0-印)=6.18.求目标函数值：：(J=(3.82-3)2=0.67， =(6.18-3)2=10.11.比较目标函数值：(1厂：.比较J1 =6.18-00.2二；.第二次迭代：a2=a1=0,①二J1=6.18,"2=1=3.82,("2)=「1)=0.67.2=a20.382(6—a2)=0.382(6.18-0)=2.36,(2)=(2.36-3)2=0.4.第三次迭代：a3=a?=0,d="2二3.82,■13-'2-2.36,「(％)=(①)=°・4.2、3二a30.382(b3-a3)=0.382(3.82-0)=1.46,3)=(1.46-3)2二2.37.「3)(切，bs—‘3=3.82—1.46•；.第四次迭代：a4=■3-1.46,b4=b=3.82,，4=」3=2.36,「(*)=(丄3)=0.4.町=a40.618(b4-a4)=1.460.0.618(3.82-1.46)=2.918,(」4)=0.0067.「4) V4),b4-4=3.82-2.36•；.第五次迭代：a^%-2.36,b5-b4-3.82,5=F=2.918,「(■5)=护(叮)=0.0067.-a50.618(b5-a5)=3.262,(I)=0.0686.('5) Y5=3.262-2.36 ；.第六次迭代：a6二a5=2.36,b6二=3.262, =2.918,”6)=：('5)=0.0067.■6=a60.382(1^—a6)=2.7045,(6)=0.087.(6) (%),b6-6=3.262-2.7045 ；.第七次迭代：a7=-6=2.7045,by=b6=3.262,，7=%=2.918,(7)=(」6)=0.0067.J7二a70.618(6—a7)=3.049,：(」7)=0.002.(，厂C),b7「；.第八次迭代：a8 =2.918,b8=b7=3.262,8=二7=3.049,：('8)—：(，7)=0.002.-a80.618(b8—a8)=3.131,(J8^0.017.―宀),—•；.

第九次迭代：a9=a8=2.918,b9-」8=3.131,需9=3.049,(馬)=「8)=0.002.9二a90.382(b9-a9)=2.999, (9^0.000001.「9)：：「(％),「9—a?=3.049—2.918：：：；.故乂二匕9-3.024.212、用最速下降法求解 minf(x) 2x1X22x；-4捲-3x2，取x(0)=(1,1)T，迭代两次.解'f(x)二(2片2x2_4,2片4x2_3)T,TOC\o"1-5"\h\z2、 H将f(x)写成f(x)=-xTQx+bTx的形式，则Q= ,b=<24丿 「3丿第一次迭代：(0)、T (0)(1)=X(0)Vf(x^0))TQf^(0)/f((1)=X(0)(0,3)'013丿(0,3)'013丿(0,3)Z22丫0*3丿<24人3」14丿第二次迭代:'=3/2(一3/2,0)f…c、J—、110丿-3/27/4J/4丿22、'"-3/2'\0丿J/4」X. Z(-3/2,0)1X. JX. X<24丿10丿13、用FR共轭梯度法求解11min(x)=(X1 -X2 • X3)2 •(-X1 • x2 X3)2• (x1 X2 -X3)2，取x(0^C2,1,-)T，迭代min两次.若给定；=0.01,判定是否还需进行迭代计算.解f(x)=3(X12X22X32)-2(X1X2X1X3X2X3)，

再写成f(x) xt再写成f(x) xtGx,G二26-2-2-26-2—2、-2，Vf(x)=Gx.6」第一次迭代:\f(x(0))=(0,4,0)t，令doj'f(x(0))=(O,-4,0)t,从x(O)出发，沿do进行一维搜索，即求minf(x(o)匚血)=2-16；：48-2的最优解,■O=1/6,x⑴，odo=(1/2,1/3,1/2)T.\f(x⑴)\f(x⑴)\f(x⑴)=(4/3,O,4/3)T.：o二TOC\o"1-5"\h\z()( ) "(X®)dj- f(x⑴)七切。=(-4/3,-8/9,-4/3)丁.广14, -2-2'2fij318.6-2——扎39-26」:14.236__九)’—22*236__九)’—22*」\—239'23minf(x⑴ dj二(1一418 1439'23J 2 3的最优解，得*1/2"丄3J/3"1/3十—-8/9<1/2;8日/3」二(0,0,0)t.此时'、f(x⑵)=(0,0,0)T,、f(x⑵)=0-0.01=；.得问题的最优解为x=(O,O,O)T，无需再进行迭代计算.14、用坐标轮换法求解 minf(x)=x：+2x；-4为-2X1X2，取x(0)=(1,1)t，迭代一步.解从点x(0)=(1,1亍出发，沿e=(1,O)T进行一维搜索,即求mFf(x⑼+8)」2-4-3的最优解，得■0=2,x⑴二x(0) =(3,1)丁.再从点X⑴出发，沿62=(0,1)丁进行一维搜索，即求minf(x⑴：*佥)=2，2-2，-7的最优解，得■!=1/2,x⑵=X(1) *2=(3,3/2)T.15、用Powell法求解minf(x)=xi2•x；-3xi-xiX2，取x®=(0,0)T，初始搜索方向组d。=(0,1)T,d1=(1,0)T，给定允许误差；=0.1(迭代两次).解第一次迭代：令y®=x(0)=(0,0)T，从点y(0)出发沿d0进行一维搜索，易得(1) (0) T0=0,yy-咖0=(0,0)；接着从点y⑴出发沿d1进行一维搜索，得i=|,y(2)卄⑴也定,0)丁22由此有加速方向. (2) (0) /3Td^y(-y(-F,0).2因为Id2=3/2AJ所以要确定调整方向.由于f(y®)=0,f(y⑴)=0,f(y⑵)=-9，按(8.4.17)式有4f(y⑴)-f(y⑵)=max{f(y(j)^f(y(j1))|j=0,1}，因此m=1，并且(m) (m1) (1) (2) 9f(y)-f(y)=f(y)-f(y厂4又因f(2y⑵-y(0))=0，故(8.4.18)式不成立.于是，不调整搜索方向组，并令x⑴二y(2)=(|,0)T.第二次迭代：取y(0)=x⑴=(|,0)T，从点y(0)出发沿d0作一维搜索，得

TOC\o"1-5"\h\zr 3 (1) (0)丄r」 /3 3\T"亍y曲謎七冷).接着从点y⑴出发沿方向/r