高级运筹学题集及答案

假设有一百万元可以投资到三支股票上，设随机变量Ri表示投资到股票,上的一元钱每年能够带来的收益。通过对历史数据分析，知期望收益 E(Ri)-0.09，「0.200.030.04「0.030.200.05E(R2)二0.07，E(R3)二0.06，三支股票的协方差矩阵为h040.050.15_1。假设使用股票涨跌稳定性来评测风险，试构建优化模型，在保证期望年收益率不低于0.075的情况下，风险最小，同时表示为非线性优化的向量形式。解：设X=(x,x,x)t，其中x,x,x分别表示投资组合中R,R,R的所占的比TOC\o"1-5"\h\z1 2 3 1 2 3 1 2 3例，有x+x+x=1 ①123保证期望收益率不低于0.075：xE(R)+xE(R)+xE(R)>0.075……②1 1 2 2 3 3建立如下优化模型：minf(X)=0.20x2+0.20x2+0.15x2+0.06xx+0.08xx+0.10xx1 2 3 1213 23stx+x+x=11230.09x+0.07x+0.06x123>0.075x,x,x>0123「0.200.030.04「记：A=0.030.200.050.040.050.15表示成向量形式：minf(X)二XtAXS.tXT1=1丄'0.09'XT0.07>0.075、0.06丿x,x,x>0

123用伪算法语言描述“成功-失败”搜索方法。解：s:初始化：x,h,8>010

s：x=x；20f1=f(x)s：3f=f(x+h)2s：4：iff2vf121gotos5；elsegotos；6ends5:x=x+h;h=2hs:ifIhl<£6gotos7;elsegotos;8ends:x*=xh4h4；s:h=8gotos. □3请简述黄金分割法的基本思想，并尝试导出区间收缩比率0^0.618.基本思想：黄金分割法就是用不变的区间缩短率申,来代替Fibonacci法每次不同的缩短率，因而可以看成是Fibonacci法的近似。在搜索区间［a,b］内取两点xvy,然后在x,y中选取一个作为端点，将搜索区间缩小，直至搜索区间足够小，然后在其内取一点作为最优解的近似。一维搜索时，在区间内取两对称点九，九'作为搜多点，并满足：11九广a+(l-P)(b-a)

九1=a+p(b-a)P取近似值0.6l8证明：设在第k次迭代时的搜索区间为［a,b］，kk则在区间内取两对称点九，九’作为探索点，并满足：TOC\o"1-5"\h\zk+1 k+1九=a+(1—p)(b—a) ①k+1 k kk九'=a+p(b一a) ②k+1 k kk

由于对称性，即：九一a二b一九'k+1kkk+1在第k+i次迭代中，不妨取收缩区间为Lak，入k+1」p(b一p(b一a)k k■b一akk九'-a

p= kb一akk请简述牛顿(Newton)法的基本原理，并指出可能会出现的“坏现象”。基本思想：牛顿法是二阶近似仿照切线法思想，推导出下降方向Xk+1二Xk—H(Xk)-1Vf(Xk)每次计算Dk二H(Xk)-1Vf(Xk)，可看成是椭球范数ll・IID下的最速下D降法。对于正定二次函数，一次可达最优解。一定条件下，具有二阶收敛速度。坏现象：对初始点的依赖性很大，要求初始点接近极小点。若初始点远离极小点，不能保证收敛，甚至连Newton方向—V2f(x(k))一1Vf(x(k))都不一定是下降方向，导致算法达不到极小点。 □叙述Powell算法思想.(方向加速法)算法思想：又称方向加速法。是在研究正定二次函数的极小化问题时形成的，由于迭代过程中构造一组共个方向，其本质属于共轭方向法。每一轮迭代过程中由n+1个相继的一维搜索组成，先依次沿着n个已知的线性无关方向搜索，然后沿本轮迭代的初始点和第n次搜索所得点的连线方向搜索，得到这一轮迭代的最好点并作为下一阶段的起点，再用第n+1个方向(最后的搜索方向)代替前n个方向的一个，开始下一轮的迭代。 口简述有约束优化时既约梯度法的基本思想。基本思想：将线性规划的单纯形法推广到带线性约束的非线性问题上。把线性约束优化问题minf(X)简化为仅在非负限制下的极小化问题minF(X)NIX=B・1b-B-1NX>0

S.t<B NIX>0N

其中，A二(B,N),X=bXNB为m其中，A二(B,N),X=bXNBNn-m维的非基向量。求出目标函数F(X)的梯度，此时的梯度是n-m维函数的梯度，称为f(X)的既约梯N度r(X)=VF(X)=Vf[X(X),X]-(B-1N)tVf[X(X),X]。X沿负既约N N XNBNN XB BNN N梯度方向 -r(X)移动，可使目标函数值降低。N□利用罚函数法求解非线性规划的收敛点minf(X)=x+x12[g(X)=一x2+x>0s.t<1 1 2[g(X)=x>021分别假设初始可行点满足1)g1)g1(X)<0,g2(X)<0；解：马良书69页2)&1(X)<0,g2(X)>°・设-gj(X)(j=】，2…,1)为凸函数，则R={X1gj(X)>0,j=▽l}为凸集。证明：设x,yeR,ae(0,1)，有g(x)>0,g(y)>0， j=1,2,…,1—g/X)(j=12，1)为凸函数，则有—g[ax+(1—a)y]<—ag(x)—(1-a)g(y)，j=1,2,…,Ijjj两边变号g[ax+(1-a)y]>ag(x)+(1-a)g(y)>0,j=1,2,…,1jjj即 ax+(1-a)yeR 。R为凸集□TOC\o"1-5"\h\zx=2-kk=12 {x}设k ，则'』收敛阶数为1，且线性收敛。证明：显然，X*=0。由于十IIX(k+1)—X*II十2-(k+1) 1lim =lim =一kt011X(k)—X*11 kt02-k 2所以由收敛定义和a阶收敛知，{x}收敛阶数为a=1，且卩=1/2知为线性收敛。k设f(X)=-XtAX+bTX+c,A是对称矩阵。给定初始点X，试证明由最速下20降法产生的迭代点列｛Xk｝有如下公式：Xk+1—Xk—(gk)Tgkgk，k—0,1,2,3,…(gk)TAgk其中gk=AXk+b。证明：由数学分析知，在Xk的领域中，使f(X)下降最快的方向是负梯度方向，取P(K)=-Vf(Xk)……①下面确定步长九:k由于f(X)为二次函数，故二阶连续可导，作二阶Taylor展开:f(Xk+九P(k))沁f(Xk)+Vf(Xk)T(XP(k))+1(XP(k))tA(XP(k))2d_xVf(Xk)tP(k)+X(P(k))tAP(k)=0可得最优步长为Vf(Xk)tP(k)X————

k (P(k))TAP(k)记gk—Vf(Xk)—AXk+b则(gk)Tgkk=0,1,2,3,Xk+1—Xk—XVf(Xk)—Xk— gk=0,1,2,3,k (gk)TAgk5试证在最速下降法中，相邻两次搜索方向必正交，即Vf(Xk+1)TVf(Xk)=0证明：设第k步的步长为X，梯度为Pk，则有第k+1步的梯度为kP(k+1)=b—AX(k+1)=b—A(X(k)+XP(k))k=b—AX(k)—XAP(k)k=P(k)—XAP(k)kIIP(k)||2 (P(k),P(k))X= —k(P(k))TAP(k) (AP(k),P(k))

(P(k+1),P(k))=(P(k),P(k))一九(AP(k),P(k))=0k即Vf(Xk+1)TVf(Xk)=0，两次搜索方向必正交。 口f(x)在凸集R内是凸函数的充要条件是对于任意的x,ygR,g(a)=f[ax+(1-a)y]在[0,1]内是凸函数。证明：必要性：设a,九，卩g[0,1]，由于R是凸集，所以对于任意的x,ygR，有ax+(1—a)ygR，卩x+(1—卩)ygRg[^a+(1一九)卩]=f([九a+(1—九)卩]x+{1一[^a+(1—九)卩]}y)=f[九ax+(1—九)Px+y—九ay—Py+XPy]=f[九ax+九(1—a)y+(1—九)Px+(1—九)(1—P)y]=f(Max+(1—a)y]+(l—九)[Px+(1—P)y])由f(x)为R上凸函数可知g[九a+(1-九)P]<九f[ax+(l-a)y]+(l—九)f[Px+(1-卩)y]=九g(a)+(1-九)g(卩)所以，g(a)=f[ax+(1—a)y]在[0,1]内是凸函数。充分性：若对于任意的x,ygR，g(a)=f[ax+(1—a)y]在[0,1]内是凸函数，则有f[ax+(1—a)y]=g(a)=g[a+(1—a)・°]<ag(1)+(1—a)g(0)=af(x)+(1—a)f(y)所以f(x)是凸函数。 口13.考虑二次函数f(x)=x2+2xx+3x2—x+x1122121)写出它的矩阵一向量形式：f(x)=lx1)写出它的矩阵一向量形式：f(x)=lxtQx+bTx2’2<2f(x)=2XTX+(—1,1)X2)矩阵Q是不是奇异的?2)IQI=8#0,非奇异证明：f(x)是正定的显然Q正定，故f(x)正定f(x)是凸的吗？由于f(x)正定，所以f(x)是凸的5)写出f(x)在点7=(2,1)T处的支撑超平面(即切平面)方程f(X)二10f(X)二10,a2、「1]X+<26>J丿Vf(X)二切平面方程：f(X)-f(X)=Vf(X)T(X-X)艮卩x2+2xx+3x2一6x一10x+11=0 □11221214.设f(x)=1xtGx+rTx+6是正定二次函数，证明一维问题2min申(a)=f(xk+adk)的最优步长为ak的最优步长为ak=Vf(xk)TdkdkTGdk证明：同（10）题15.考虑约束优化问题minf(x)=x2+4x212s.t3x+4x>1312初始点（2,2），用两种惩罚函数法求解.解：标准化minf(x)=x2+4x212s.t g(x)=3x+4x-13>0112（1）外罚函数法构造罚函数P(X,M)=x2+4x2+M{min(0,3x+4x一13)2}1212当g(x)<0时,112P(X,M)=x2+4x2+M(3x+4x-13)21212dP=2xdP=2x+6M(3x+4x-13)=0,12dx 11兰=8x+8M(3x+4x-13)=0Rx2 1 2解得：X=（3,1）。M（2）障碍罚函数法构造障碍罚函数P(X,r)=x2+4x2+1 2 3x+4x-1312求解

QP 3r 门 QPc 4r 门2x— =0， =8x— =0Qx 1(3x+4x—13)2 Qx 2(3x+4x—13)2112112两式抵消，得：x=3x，代入上式122x(13x—13)2=r22当rT0时，有xT0或xT1，所以取x的值为0或者1,对应的x取值为0或者3。2221由于点(0,0)不在可行域内，所以取(3,1)为最优点。1+JT71_佰、( )T16.验证点2 ' 2 与(°厂3)t是否是规划问题minf(x)=x2+x12S・tx2+x2<minf(x)=x2+x12S・tx2+x2<9

12—x—x+1n012的K-T点。对K-T点写出相应的Lagrange乘子。解：规划问题标准化minf(x)=x2+x12st g(X)=9一x2一x2>0112—x+1n012(2x)(—2x)(-1]I1I，Vg(X)=I1I，Vg(X)=.—1丿1<—2x丿2Vf(X)=g2(X)—x1记〔节记X(1)=I ,_I，X⑵=I字J①下面验证正则点：(-1-，Vg2(X⑴)二叫X(1))二—1+'0、<—3丿1+J71-小7、(—-—,—-—)T显然Vg(X(1))与Vg(X(1))线性无关，于是 2 2为正则点。12(0](—1]<—6丿，Vg(X⑵)二J—1丿2叫X⑵)二同样Vg(X(2))与Vg(X(2))线性无关，于是(0,-3)t也是正则点。12②下面验证是否满足Kuhn-Tucker条件：Vf(X(1))-f2YVg(X(1))=jjj=Vf(X(1))-f2YVg(X(1))=jjj=1Y=-S<0,22'1+肩、b丿'(1+备1171)(, )T故22 不满足Kuhn-Tucker条件。—Y1—Y(0「-Y(0]-Y「1〕=r0〕J1丿1<-6丿2J-1丿<0丿jjj=1得Y=-—<0，16Y=0，故(0,得Y=-—<0，16217.设集合SuRn是凸集，f1(x),・・・fk(x)是S上的凸函数，令f(x)=max{f(x),…f(x)}xeSTOC\o"1-5"\h\z1 k证明f（x）也是S上的凸函数。证明：设X,YeS，由f(x),…,f(x)是S上的凸函数，则存在九e(0,1)，使得1 kf[九X+(1-九)Y]<xf(X)+(1-九)f(Y), i=1,2,…,ki i i令f(X)=f(X)=max{f(X)，…,f(X)}s 1 kf(Y)=f(Y)=max{f(Y)，…,f(Y)}t 1 k其中s,t=1,2,…,k。f[九X+(1-九)Y]=max (1-九)Y]}1 k<max X)+(