1、 单位代码 03 学 号 最优化方法课程实践 完成时间：2015 年 5 月 30 日星期六 选择题目：题目一 使用优化软件，编写重要算法的程序 1. 第一大题： （1） 学习最优流量工程问题，nonsmooth_MCFP.pdf （2） 问题重述： Figure 1 一个简单的网络拓扑和流量需求 如 Figure 1 所示，网络有 7 个节点，13 条弧，每条弧的容量是 5 个单位 . 此外有四个需求量均为 4 个单位的源目的对（ )，M=4 具体的源节点、目的节点信息如图所示. 这里为了简单，省去了未 用到的弧，此外弧上的数字表示弧的编号。 （3） 极小化 MAU 设定变量 x，为 的向量
2、，其中 即为变量 z。使用531(53)x linprog 函数求解极小化问题得到 x。之前确定三个约束条件。 1、 ，其中 A 为 的矩阵，b 为 的向量。Axb1 2、 ，其中 为 的矩阵， 为 的向量。eqxbAeqA2853eqb281 3、 ，其中 为 的向量ll1 编程计算后得到结果如下： （4） 极小化 FT 成本函数 设定变量 x，为 的向量，其中 即为变量 。使用651(53:6)xlz linprog 函数求解极小化问题得到 x。之前确定三个约束条件。 1、 ，其中 A 为 的矩阵，b 为 的向量。Axb78781 2、 ，其中 为 的矩阵， 为 的向量。eqeq265eq
3、b2 3、 ，其中 为 的向量xll1 编程计算后得到结果如下： 2. 第二大题： 2.1. 习题 5.6 2.1.1. 问题分析 问题 21 12()080)/453qxxx 通过 matlab 画出其等高线为： x1 x2 一 一 一 -2 0 2 4 6 8 10 12 -2 0 2 4 6 8 10 12 2.1.2. 最速下降法 最速下降法中，取值： kpg =()() kkTTgG (1)(kxkpA 2.1.3. 算法流程图如下图所示： | | g ( x ( k + 1 ) ) | | e 选取初始点 x 0 、 e 开始 结束 计算 f ( x 0 ) 、 g ( x 0 )
4、 、 G ( x 0 ) 设定 p = - g 、 a l p h a = - g * p / ( p * G * p ) 更新 x ( k + 1 ) = x ( k ) + a l p h a * p 计算 f ( x ( k + 1 ) ) 、 g ( x ( k + 1 ) ) 计算 r ( k + 1 ) = ( f ( x ( k + 1 ) ) - f * ) / ( f ( x ( k ) ) f * ) 取 r = m a x ( r ( k ) ) 输出最优解 x * 是 否 2.1.4. 初始值（0,0） 编程运行结构为： 收敛过程曲线为： x1 x2 一 一 一 -2
5、0 2 4 6 8 10 12 -2 0 2 4 6 8 10 12 一 一 一 一 一 一 一 一 一 一 一 一 一 一 2.1.5. 初始值（-0.4,0） 编程运行结构为： 收敛过程曲线为： x1 x2 一 一 一 -2 0 2 4 6 8 10 12 -2 0 2 4 6 8 10 12 一 一 一一 一 一 一 一 一 一 一 一 一 一 2.1.6. 初始值（10,0） 编程运行结构为： 收敛过程曲线为： x1 x2 一 一 一 -2 0 2 4 6 8 10 12 -2 0 2 4 6 8 10 12 一 一 一 一 一 一 一 一 一 一 一 一 一 一 2.1.7. 初始值
6、（11,0） 编程运行结构为： 收敛过程曲线为： x1 x2 一 一 一 -2 0 2 4 6 8 10 12 -2 0 2 4 6 8 10 12 一 一 一 一 一 一 一 一 一 一 一 一 一 一 2.2. 习题 5.7 2.2.1. 问题分析 问题 ()94ln(7)fxxg2(7)Gx Matlab 画出在区间(7 10)的函数、一阶导数、二阶导数的变化曲 线为 7 7.5 8 8.5 9 9.5 1070 72 74 76 78 80 82 84 86 x f 一 一 一 一 一 一 7 7.5 8 8.5 9 9.5 10-35 -30 -25 -20 -15 -10 -5 0
7、 5 10 x g 一 一 一 一 g一 一 一 一 7 7.5 8 8.5 9 9.5 100 50 100 150 200 250 300 350 400 x g 一 一 一 一 G一 一 一 一 2.2.2. 牛顿法 牛顿法中，取值： kkGsgA1x 其中，如果 G 不是半正定，则采用修正牛顿法(+)kkIsgA 2.2.3. 算法流程图如下图所示： 开始 结束 设定初始点 x ( 0 ) 计算 f ( x ) 、 g ( x ) 、 G ( x ) 计算迭代步长 s = - g / G 更新 x ( k + 1 ) = x ( k ) + s 迭代次数 k = 5 输出最终的 x 是
8、 否 2.2.4. 初始值 7.40 编程运行结构为： 收敛过程曲线为： 7.39 7.4 7.41 7.42 7.43 7.44 7.45 7.46 70.245 70.25 70.255 70.26 70.265 x f 一 一 一 一 一 一 一 一 一 一 一 一 一 一 一 一 一 一 一 一 一 2.2.5. 初始值 7.20 编程运行结构为： 收敛过程曲线为： 7.1 7.2 7.3 7.4 7.5 7.6 7.7 70.2 70.4 70.6 70.8 71 71.2 71.4 71.6 x f 一 一 一 一 一 一 一 一 一 一 一 一 一 一 一 一 一 一 一 一 一
9、 2.2.6. 初始值 7.01 编程运行结构为： 收敛过程曲线为： 6.85 6.9 6.95 7 7.05 7.1 7.15 7.2 7.25 7.3 7.35 72 74 76 78 80 82 x f 一 一 一 一 一 一 一 一 一 一 一 一 一 一 一 一 一 一 一 一 一 2.2.7. 初始值 7.80 编程运行结构为： 收敛过程曲线为： 7.1 7.2 7.3 7.4 7.5 7.6 7.7 7.8 7.9 70 70.5 71 71.5 72 x f 一 一 一 一 一 一 一 一 一 一 一 一 一 一 一 一 一 一 一 一 一 2.2.8. 初始值 7.88 编程
10、运行结构为： 收敛过程曲线为： 6.8 7 7.2 7.4 7.6 7.8 8 71 72 73 74 75 76 77 78 79 x f 一 一 一 一 一 一 一 一 一 一 一 一 一 一 一 一 一 一 一 一 一 2.2.9. 分析 函数在区间（7，7.8888）内是凸函数，G 恒大于零，所以单 纯牛顿法保证收敛。 2.3. 习题 5.8 2.3.1. 问题分析 问题 12121212()90ln()lnl(50)fxxuxxx Matlab 画出函数在区间 , 和 的等高线如0, Figure 2 所示，发现最优值在（0.5，98）附近，对这个区域集中等 高线，如 Figure
11、3 所示。 x1 x2 一 一 一 10 20 30 40 50 60 70 80 90 100 10 20 30 40 50 60 70 80 90 100 Figure 2 函数等高线 x1 x2 一 一 一 0.5 1 1.5 2 2.5 3 3.5 495 95.5 96 96.5 97 97.5 98 98.5 99 99.5 100 Figure 3 区域放大等高线 2.3.2. 牛顿法 单纯牛顿法中，有 kkGsgA1x 其中，如果 G 不是半正定，则采用修正牛顿法(+)kkIsgA 带线搜索的牛顿法，有 kkGp1xA 其中， (1)()kfkfxgpA 2.3.3. 算法流程
12、图 无线搜索的算法流程图如下： 开始 结束 设定初始点 x ( 0 ) 计算 f ( x ) 、 g ( x ) 、 G ( x ) 计算迭代步长 s = - g / G 更新 x ( k + 1 ) = x ( k ) + s | | g ( x ) | | 0 且 | | s | | = | | x + t * p | | = d e t a 的 t 取使得 q 值较小的 t r ( k + 1 ) = r ( k ) + a * B * p | | r | | e * | | r 0 | | s = x b e t a = r ( k + 1 ) * r ( k + 1 ) / r ( k ) * r ( k ) p ( k + 1 ) = - r ( k + 1 ) + b e t a * p ( k ) 是 否 s = x 否 是 是 否 是 否 是 否 2.7.2. 运行结果 当设定初始 n=10 时，运行结果如下： 当设定初始 n=50 时，运行结果如下： 3. 附注： 所有原程序代码见压缩包中各对应文件夹。
