河海大学研究生最优化考试试卷2016

1、河海大学研究生最优化方法考试范围授课老师：丁根宏（2016年春）考试范围：线性和非线性约束占比70%，多目标和动态规划占30%，题型为计算和证明共8道题，其中一道证明题。线性规划：两阶段法改进单纯形法对偶单纯形法的计算基变换的定理保证对偶理论的证明无约束非线性规划：一维搜索（0.618法，Fibonaci法，牛顿切线法和二次插值法）牛顿法公式及推导计算题（最速下降法、牛顿法和共轭梯度法）步骤简单，主要是思想的比较变尺度法和牛顿法的对比有约束非线性规划：K-T条件及验证求K-T点SUMT方法（外点法和内点法）投影梯度法理论及投影梯度的定义多目标规划：解的定义求Rpa*，Rwp*变量空间和函数空间

2、评价函数的收敛性动态规划：最优性原理步骤（6个概念）泛函方程应用举例（多阶段决策问题包括资源分配问题）函数空间和策略空间迭代法考试试卷（2016年6月3号）1、改进单纯形法，从中间某步继续往下迭代至求出最优解樺例（P66）用改进单纯形法求解问题minf=-3x1-x2-3x32X+x2+x3+x4=2Xj-b2x2+3x3十心=52x+2x2+xj+x6=6比鼻0,i=l,，62、对偶理论的证明3、牛顿切线法的公式及推导4、变尺度法和牛顿法的比较* 1)基本原理律在上述阻尼牛顿法中，«S(k)=-H(X<k>Vvf(X<k)«X(k+lX(k)+XkS(k

3、) Ak：minf(X0)+kS闊)由于逆矩阵H(X何尸的计算量太大”实现困难口拳为了保持牛顿法的优点，试图构造H(X尸”的近似阵帀J不需要求逆矩阵若f(X)为二次函数，其Hessian矩阵H(%)为常数阵，则在緊k+0和X处的梯度之差等于 Vf(X<t+1')-vf(x<k>)=A(X(k+1>-X(k>)* X<k+I)-X<k*=A'1Vf(X<fc+1O-Vf(X<k>)|记G(X)=Vf(X),AG侬匚叫AX)=Xk+1)-X(k>上式又变为AXA-1AG(k)5、K-T条件及验证如果设备(i不属于I)

4、在也可微，则上述条件可改为：,W(卅)+A(>+£y.VA.()=D/=!>1=/=Im悶AO,i-*称对为KT点。乙考察如下问题：min_/Cx)=.打+直；吕”1*丁;+卅了vTLH4LA、A0弊让在最优点L=(4/5-8/5)''处丘-T条件成立丫并求在用'点的Liiriingc乘子6、SUMT外点法(书上例题)律例2用外点法求ininf(X)=x1+it2g1(X)=x11-x30g3(X)=-XjO解：构造罚函数F(丸、M)=.Vj+x2+Mmax(O,xf-x2)|3+|max(O,xjl2当幻丸必"时冷'-1+2Af

5、(KlJt,)+Jt,I=0直FUW曲一斗20dx2得X(皿2(-一t(一1一I2(1+57)斗(1丰2M当灯00时/*二(则7、简述动态规划的使用条件及步骤，用空间迭代法求最短路径-所谓多阶段决策问题，是指一类活动过程，它可以分为互相联系的若干个阶段，在每一阶段都需要作出决策，从而使整个过程达到最优的活动效果。因此，各个阶段决策的选取常依赖于当前面临的状态，又診响下一个阶段的决策，从而影响整个过程的活动路线这种把一个问题看成一个前后关联具有链状结构的多阶段过程就称为段决策过程，也称序贯决策过程口动态规划的最优性原理匸一个(整个过程的)ft优策略所具有的性质是不论过去的状态和决策如何，其余下的

6、诸决策必构成一个最优子策略中h函数空间迭代法*设fD表示由i点出发向N走k步所构成的所有路线中的最短距离.函数空间迭代法求解步骤如下：1°fi(i)=CiN,i=l,2,.,N-lf(N)=02°fQ=min(Cij+站(j)，i=lZ尸“fk(N)=03a反复迭代扩直到fk(i)=lk+1(i)=f®为止，匸.,N23242-例3下图为一街区的单行道交通网路，分别用函数空间迭代法和策略空间迭代法求各点到顶点5的最短路线I解先用画数空间迭代法求解桂为了便于运算，将距离Gj写成下列矩阵的形式，将丘写成列向量的形或，利用函数空间迭代法求解”步骤迭代如下=其中最后一列1

7、1®为i点的最优抉策，于是得到各点到顶点5的最短踣线和最短距离如下表：8、多目标规划，评价函数的收敛性(设?ER,若不存在XeR满足F(X)WF(X臥则称疋为问题(VP)的有效解(或Mrrto解)«有效解的全体记为/-定义3设誉ER,若不存在XER满足F(X)<F(X*),则称心为问题(VP)的有爱(:ParetoMi)弱有效解的全体记为R”出10.设彩口标规划问题为IV-min=(/,r),A(.r)TIK.I,丁二0为F尺英中/i工)=CrI护+1(一一4*就WFJ(.K、=f3V乂W1、丁一乳_r>4SR；*"2和尺评价函数的收敛性*圭丈7若对任意片FWEP,当卜时，都有u(r)<u(FT)成立，则称讥F)是F的心格单调均函馥。-1若对任意FpFEE%当WF时.都有U(F)<U(FT成立,则称U(F)是F的l调増函孤定讯若对讥F)是严格单调