高级运筹学题集及答案.doc

1. 假设有一百万元可以投资到三支股票上，设随机变量表示投资到股票上的一元钱每年能够带来的收益。通过对历史数据分析，知期望收益，三支股票的协方差矩阵为。假设使用股票涨跌稳定性来评测风险，试构建优化模型，在保证期望年收益率不低于0.075的情况下，风险最小，同时表示为非线性优化的向量形式。解：设，其中分别表示投资组合中的所占的比例，有 保证期望收益率不低于0.075： 建立如下优化模型： 记：表示成向量形式： 2. 用伪算法语言描述“成功-失败”搜索方法。解：初始化：, 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 to ;end : : ; go to . 3. 请简述黄金分割法的基本思想，并尝试导出区间收缩比率0.618.基本思想：黄金分割法就是用不变的区间缩短率，来代替Fibonacci法每次不同的缩短率，因而可以看成是Fibonacci法的近似。在搜索区间a,b内取两点xy，然后在x,y中选取一个作为端点，将搜索区间缩小，直至搜索区间足够小，然后在其内取一点作为最优解的近似。一维搜索时，在区间内取两对称点，作为搜多点，并满足：= a+(1-)(b-a)= a+(b-a)取近似值0.618证明：设在第k次迭代时的搜索区间为,， 则在区间内取两对称点，作为探索点，并满足： 由于对称性，即： 在第k+1次迭代中，不妨取收缩区间为 这样，收缩率表示为： 4. 请简述牛顿（Newton）法的基本原理，并指出可能会出现的“坏现象”。基本思想：牛顿法是二阶近似仿照切线法思想，推导出下降方向 每次计算 ，可看成是椭球范数下的最速下降法。 对于正定二次函数，一次可达最优解。一定条件下，具有二阶收敛速度。坏现象：对初始点的依赖性很大，要求初始点接近极小点。若初始点远离极小点，不能保证收敛，甚至连Newton方向都不一定是下降方向，导致算法达不到极小点。 5. 叙述Powell算法思想.（方向加速法）算法思想：又称方向加速法。是在研究正定二次函数的极小化问题时形成的，由于迭代过程中构造一组共个方向，其本质属于共轭方向法。 每一轮迭代过程中由n+1个相继的一维搜索组成，先依次沿着n个已知的线性无关方向搜索，然后沿本轮迭代的初始点和第n次搜索所得点的连线方向搜索，得到这一轮迭代的最好点并作为下一阶段的起点，再用第n+1个方向（最后的搜索方向）代替前n个方向的一个，开始下一轮的迭代。 6. 简述有约束优化时既约梯度法的基本思想。基本思想：将线性规划的单纯形法推广到带线性约束的非线性问题上。把线性约束优化问题简化为仅在非负限制下的极小化问题 其中，B为mm的可逆矩阵，为m维的基向量，为n-m维的非基向量。求出目标函数的梯度，此时的梯度是n-m维函数的梯度，称为的既约梯度。沿负既约梯度方向移动，可使目标函数值降低。 7. 利用罚函数法求解非线性规划的收敛点分别假设初始可行点满足1)； 2) .解：马良书69页8. 设为凸函数，则为凸集。证明：设 ，有， 为凸函数，则有，两边变号, 即 。R为凸集 1.2.3.4.5.6.7.8.9.9. 设，则收敛阶数为1，且线性收敛。证明：显然，。由于所以由收敛定义和阶收敛知，收敛阶数为=1，且=1/2知为线性收敛。 10. 设，A是对称矩阵。给定初始点，试证明由最速下降法产生的迭代点列有如下公式：，其中。证明：由数学分析知，在的领域中，使下降最快的方向是负梯度方向，取 下面确定步长：由于为二次函数，故二阶连续可导，作二阶Taylor展开：令 可得最优步长为 记则 ， 11. 试证在最速下降法中，相邻两次搜索方向必正交，即证明：设第k步的步长为，梯度为，则有第k+1步的梯度为 即，两次搜索方向必正交。 12. 在凸集内是凸函数的充要条件是对于任意的，在0,1内是凸函数。证明：必要性： 设，由于是凸集，所以对于任意的，有，由为上凸函数可知所以，在0,1内是凸函数。 充分性：若对于任意的，在0,1内是凸函数，则有 所以是凸函数。 13. 考虑二次函数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)在点=处的支撑超平面(即切平面)方程 ， 切平面方程： 即 14. 设是正定二次函数，证明一维问题的最优步长为证明：同（10）题15. 考虑约束优化问题初始点(2,2)，用两种惩罚函数法求解.解：标准化（1）外罚函数法构造罚函数当时， 解得：。（2）障碍罚函数法构造障碍罚函数求解，两式抵消，得：，代入上式当时，有或，所以取的值为0或者1，对应的取值为0或者3。由于点不在可行域内，所以取为最优点。16. 验证点 与是否是规划问题的K-T点。对K-T点写出相应的Lagrange乘子。解：规划问题标准化 ， ， 记，。下面验证正则点：，显然与线性无关，于是为正则点。，同样与线性无关，于是也是正则点。下面验证是否满足Kuhn-Tucker条件：得 ，故不满足Kuhn-Tucker条件。得，故不满足Kuhn-Tucker条件。 17. 设集合是凸集，是上的凸函数，令证明也是上的凸函数。证明：设 ，由是S上的凸函数，则存在，使得 令其中。 其中式等号成立的充要条件是：。即：故f(x)为凸函数。 18. 用最速下降法