高级运筹学题集及答案(7页).doc

《高级运筹学题集及答案(7页).doc》由会员分享，可在线阅读，更多相关《高级运筹学题集及答案(7页).doc（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、-1.2.3.4. 高级运筹学题集及答案-第 7 页5. 假设有一百万元可以投资到三支股票上，设随机变量表示投资到股票上的一元钱每年能够带来的收益。通过对历史数据分析，知期望收益，三支股票的协方差矩阵为的情况下，风险最小，同时表示为非线性优化的向量形式。解：设，其中分别表示投资组合中的所占的比例，有保证期望收益率不低于0.075：建立如下优化模型：记：表示成向量形式：6. 用伪算法语言描述“成功-失败”搜索方法。解：初始化：, h,0 ：x=；=f(x) ：=f(x+h) ： if go to ;else go to ;end : x=x+h; h=2h : if go to ;else go

2、 to ;end go to . 7. 请简述黄金分割法的基本思想，并尝试导出区间收缩比率0.618.基本思想：黄金分割法就是用不变的区间缩短率，来代替Fibonacci法每次不同的缩短率，因而可以看成是Fibonacci法的近似。在搜索区间a,b内取两点xy，然后在x,y中选取一个作为端点，将搜索区间缩小，直至搜索区间足够小，然后在其内取一点作为最优解的近似。一维搜索时，在区间内取两对称点，作为搜多点，并满足：= a+(1-)(b-a)= a+(b-a)证明：设在第k次迭代时的搜索区间为,， 则在区间内取两对称点，作为探索点，并满足： 由于对称性，即： 在第k+1次迭代中，不妨取收缩区间为

3、这样，收缩率表示为：8. 请简述牛顿（Newton）法的基本原理，并指出可能会出现的“坏现象”。基本思想：牛顿法是二阶近似仿照切线法思想，推导出下降方向 每次计算 ，可看成是椭球范数下的最速下降法。 对于正定二次函数，一次可达最优解。一定条件下，具有二阶收敛速度。坏现象：对初始点的依赖性很大，要求初始点接近极小点。若初始点远离极小点，不能保证收敛，甚至连Newton方向都不一定是下降方向，导致算法达不到极小点。 9. 叙述Powell算法思想.（方向加速法）算法思想：又称方向加速法。是在研究正定二次函数的极小化问题时形成的，由于迭代过程中构造一组共个方向，其本质属于共轭方向法。 每一轮迭代过程

4、中由n+1个相继的一维搜索组成，先依次沿着n个已知的线性无关方向搜索，然后沿本轮迭代的初始点和第n次搜索所得点的连线方向搜索，得到这一轮迭代的最好点并作为下一阶段的起点，再用第n+1个方向（最后的搜索方向）代替前n个方向的一个，开始下一轮的迭代。 10. 简述有约束优化时既约梯度法的基本思想。基本思想：将线性规划的单纯形法推广到带线性约束的非线性问题上。把线性约束优化问题简化为仅在非负限制下的极小化问题其中，B为mm的可逆矩阵，为m维的基向量，为n-m维的非基向量。求出目标函数的梯度，此时的梯度是n-m维函数的梯度，称为的既约梯度。沿负既约梯度方向移动，可使目标函数值降低。 11. 利用罚函数

5、法求解非线性规划的收敛点分别假设初始可行点满足1)； 2) .解：马良书69页12. 设为凸函数，则为凸集。证明：设 ，有为凸函数，则有两边变号即 。R为凸集 13. 设，则收敛阶数为1，且线性收敛。证明：显然，。由于所以由收敛定义和阶收敛知，收敛阶数为=1，且=1/2知为线性收敛。 14. 设，A是对称矩阵。给定初始点，试证明由最速下降法产生的迭代点列有如下公式：其中。证明：由数学分析知，在的领域中，使下降最快的方向是负梯度方向，取下面确定步长：由于为二次函数，故二阶连续可导，作二阶Taylor展开：令可得最优步长为记则15. 试证在最速下降法中，相邻两次搜索方向必正交，即证明：设第k步的步

6、长为，梯度为，则有第k+1步的梯度为即，两次搜索方向必正交。 16. 在凸集内是凸函数的充要条件是对于任意的，在0,1内是凸函数。证明：必要性： 设，由于是凸集，所以对于任意的，有由为上凸函数可知所以，在0,1内是凸函数。 充分性：若对于任意的，在0,1内是凸函数，则有所以是凸函数。 17. 考虑二次函数f(x)=1) 写出它的矩阵向量形式: f(x)=2) 矩阵Q是不是奇异的?|Q|80，非奇异3) 证明: f(x)是正定的显然Q正定，故f(x)正定4) f(x)是凸的吗?由于f(x)正定，所以f(x)是凸的5) 写出f(x)在点=处的支撑超平面(即切平面)方程切平面方程： 即 18. 设是

7、正定二次函数，证明一维问题的最优步长为证明：同（10）题19. 考虑约束优化问题初始点(2,2)，用两种惩罚函数法求解.解：标准化（1）外罚函数法构造罚函数当时，解得：。（2）障碍罚函数法构造障碍罚函数求解两式抵消，得：，代入上式当时，有或，所以取的值为0或者1，对应的取值为0或者3。由于点不在可行域内，所以取为最优点。20. 验证点 与是否是规划问题的K-T点。对K-T点写出相应的Lagrange乘子。解：规划问题标准化记，。下面验证正则点：显然与线性无关，于是为正则点。同样与线性无关，于是也是正则点。下面验证是否满足Kuhn-Tucker条件：得 ，故不满足Kuhn-Tucker条件。得，故不满足Kuhn-Tucker条件。 21. 设集合是凸集，是上的凸函数，令证明也是上的凸函数。证明：设 ，由是S上的凸函数，则存在，使得令其中。其中式等号成立的充要条件是：。即：故f(x)为凸函数。 22. 用最速下降法求解无约束问题 ，取初始点。解：显见，。取，代入得由得因f(X)是二次函数，故得最优步长从而，得显见，所以。 23. 证明：用牛顿法求函数（A为对称正定矩阵）的极小值只需一次迭代。证明：令，得极小值点为方向为： 对比可知，。结论得证。