最优化方法大作业.doc

单位代码 03 学 号 最优化方法课程实践 完成时间：2015年5月30日星期六选择题目：题目一 使用优化软件，编写重要算法的程序1. 第一大题：（1） 学习最优流量工程问题，nonsmooth_MCFP.pdf（2） 问题重述：Figure 1一个简单的网络拓扑和流量需求如Figure 1所示，网络有7 个节点，13 条弧，每条弧的容量是5 个单位. 此外有四个需求量均为4个单位的源目的对（)，具体的源节点、目的节点信息如图所示. 这里为了简单，省去了未用到的弧，此外弧上的数字表示弧的编号。（3） 极小化MAU设定变量x，为的向量，其中即为变量z。使用linprog函数求解极小化问题得到x。之前确定三个约束条件。1、，其中A为的矩阵，b为的向量。2、，其中为的矩阵，为的向量。3、，其中为的向量编程计算后得到结果如下：（4） 极小化FT成本函数设定变量x，为的向量，其中即为变量。使用linprog函数求解极小化问题得到x。之前确定三个约束条件。1、，其中A为的矩阵，b为的向量。2、，其中为的矩阵，为的向量。3、，其中为的向量编程计算后得到结果如下：2. 第二大题：2.1. 习题5.62.1.1. 问题分析问题 通过matlab 画出其等高线为：2.1.2. 最速下降法最速下降法中，取值： 2.1.3. 算法流程图如下图所示：2.1.4. 初始值（0,0）编程运行结构为：收敛过程曲线为：2.1.5. 初始值（-0.4,0）编程运行结构为：收敛过程曲线为：2.1.6. 初始值（10,0）编程运行结构为：收敛过程曲线为：2.1.7. 初始值（11,0）编程运行结构为：收敛过程曲线为：2.2. 习题5.72.2.1. 问题分析问题Matlab画出在区间(7 10)的函数、一阶导数、二阶导数的变化曲线为2.2.2. 牛顿法牛顿法中，取值：其中，如果G不是半正定，则采用修正牛顿法2.2.3. 算法流程图如下图所示：2.2.4. 初始值7.40编程运行结构为：收敛过程曲线为：2.2.5. 初始值7.20编程运行结构为：收敛过程曲线为：2.2.6. 初始值7.01编程运行结构为：收敛过程曲线为：2.2.7. 初始值7.80编程运行结构为：收敛过程曲线为：2.2.8. 初始值7.88编程运行结构为：收敛过程曲线为：2.2.9. 分析 函数在区间（7，7.8888）内是凸函数，G恒大于零，所以单纯牛顿法保证收敛。2.3. 习题5.82.3.1. 问题分析问题 Matlab画出函数在区间,和 的等高线如Figure 2所示，发现最优值在（0.5，98）附近，对这个区域集中等高线，如Figure 3所示。Figure 2 函数等高线Figure 3 区域放大等高线2.3.2. 牛顿法单纯牛顿法中，有其中，如果G不是半正定，则采用修正牛顿法带线搜索的牛顿法，有其中， 2.3.3. 算法流程图无线搜索的算法流程图如下：具有线搜索的牛顿法的算法流程图如下：2.3.4. 无线搜索（）：2.3.5. 无线搜索（）：2.3.6. 线搜索：2.3.7. 线搜索：2.3.8. 分析：线搜索能够保证搜索在有效范围之内，具有更加可实现性。2.4. 习题 5.92.4.1. 问题分析问题Matlab画出函数等高曲线为：Figure 4 Rosenbrock函数登高曲线 Figure 5 Rosenbrock函数登高曲线2.4.2. 回溯最速下降法：（1）算法 （2）流程（3）计算结果初始值为（1.2,1.2）初始值为（-1.2,1）2.4.3. 回溯牛顿法中（1）算法如果G不是半正定，则采用修正牛顿法其中， （2）流程（3）计算结果2.5. 习题 5.192.5.1. 算法流程根据题意算法流程图如下：2.5.2. N=5运行结果2.5.3. N=8运行结果2.5.4. N=12运行结果2.5.5. N=20运行结果2.6. 习题 5.272.6.1. 问题分析问题 2.6.2. 修正的高斯牛顿法2.6.3. 运行结果2.7. 习题 6.42.7.1. 流程图根据题意设计算法流程图如下共