应用数学第1-11章作业.pdf

最优化方法 习题解答 张彦斌 计算机学院 2015年12月21日 Contents 1第第第一一一章章章最最最优优优化化化理理理论论论基基基础础础 P13习习习题题题1 1 2 4 3 42 2第第第二二二章章章线线线搜搜搜索索索算算算法法法 P27习习习题题题2 4 64 2 1第2题 4 2 2第4题 6 2 3第6题 6 3第第第三三三章章章最最最速速速下下下降降降法法法和和和牛牛牛顿顿顿法法法P41习习习题题题4 5 78 3 1第4题 8 3 2第5题 10 3 3第7题 11 4第第第四四四章章章共共共轭轭轭梯梯梯度度度法法法P51习习习题题题1 3 6 1 11 4 1第1题 11 4 2第3题 11 4 3第6 1 题 12 5第第第七七七章章章非非非线线线性性性最最最小小小二二二乘乘乘问问问题题题P98 1 213 5 1第1题 13 5 2第2题 14 5 3第4题 15 5 4第6题 15 6第第第八八八章章章最最最优优优性性性条条条件件件P112 1 219 6 1第1题 19 6 2第2题 19 6 3第5题 20 6 4第6题 21 7最最最优优优控控控制制制法法法 习习习题题题1 2 22 7 1习题1 22 7 2习题2 23 1 8第第第九九九章章章罚罚罚函函函数数数法法法P132 1 1 2 1 3 3 624 8 1习题1 1 24 8 2习题2 1 25 8 3习题3 1 27 9第第第十十十一一一章章章二二二次次次规规规划划划习习习题题题11 P178 1 1 528 9 1习题1 28 9 2习题5 29 1第第第一一一章章章最最最优优优化化化理理理论论论基基基础础础 P13习习习题题题1 1 2 4 3 4 1 验证下列各集合是凸集 1 S x1 x2 2x1 x2 1 x1 2x2 1 需要验证 根据凸集的定义 对任意的x x1 x2 y y1 y2 S及任意的实数 0 1 都 有 x 1 y S 即 x1 1 y1 x2 1 y2 S 证 由x x1 x2 y y1 y2 S得到 2x1 x2 1 x1 2x2 1 2y1 y2 1 y1 2y2 1 1 把 1 中的两个式子对应的左右两部分分别乘以 和1 然后再相加 即得 2x1 x2 1 2y1 y2 1 x1 2x2 1 y1 2y2 1 2 合并同类项 2 x1 1 y1 x2 1 y2 1 x1 1 y1 2 x2 1 y2 1 3 证毕 2 判断下列函数为凸 凹 函数或严格凸 凹 函数 4 f x 2x2 1 x22 2x23 x1x2 3x1x3 x1 x3 首先二阶导数连续可微 根据定理1 5 f在凸集上是 I 凸函数的充分必要条件是 2f x 对一切x为半正定 II 严格凸函数的充分条件是 2f x 对一切x为正定 2f x 41 3 120 304 4 2 正定矩阵 说明为什么是正定矩阵 3 证明f x 1 2x TGx bTx为严格凸函数当且仅当Hesse矩阵G正定 证明 根据严格凸函数定义证明 对任意x y 及任意实数 0 1 都有f x 1 y 0 G正定保障了严格不等式成立 反之 必要性 严格凸函数 Hesse矩阵G正定 类似 当对任意x y 及任意实数 0 1 都有f x 1 y 0 4 若对任意x n及实数 0都有f x f x 证明f x 在 n上为凸函数 的充要条件是 x y n f x y f x f y 证明 根据严格凸函数定义证明 定义 对任意x y 及任意实数 0 1 都有f x 1 y f x 1 f y 充分条件 x y n 有f x y f x f y 对任意x y 及任意实数 0 1 都有f x 1 y f x f 1 y 利用f x f x 3 f x 1 y f x f 1 y f x 1 f y 充分性证毕 必要性 f x 在 n上为凸函数 x y n f x y f x f y 根据定义有对任意x y 及任意实数 0 1 都有f x 1 y f x 1 f y 不妨取 1 2 则 f 1 2x 1 1 2 y 1 2f x 1 1 2 f y 利用f x f x f 1 2 x y 1 2f x y 1 2 f x f y x y n f x y f x f y 证毕 2第第第二二二章章章线线线搜搜搜索索索算算算法法法 P27习习习题题题2 4 6 2 1第第第2题题题 黄金0 618算法 function s phis k G E golds phi a b delta epsilon 输入 phi是目标函数 a b是搜索区间的两个端点 delta epsilon分别是自变量和函数值的容许误差 输出 s phis 分别是近似极小点和极大值 G是n 4矩阵 其第k行分别是a p q b的第k次迭代值ak pk qk bk E ds dphi 分别是s和phis的误差限 t sqrt 5 1 2 h b a phia feval phi a phib feval phi b 4 p a 1 t h q a t h phip feval phi p phiq feval phi q k 1 G k a p q b while abs phib phia epsilon h delta if phip phiq b q phib phiq q p phiq phip h b a p a 1 t h phip feval phi p else a p phia phip p q phip phiq h b a q a t h phiq feval phi q end k k 1 G k a p q b end ds abs b a dphi abs phib phia if phip phiq s p phis phip else s q phis phiq end E ds dphi 运行 s phis k G E golds inline s3 2 s 1 0 3 0 15 0 01 结果 ak pk qk bk 5 01 14591 85413 0000 00 70821 14591 8541 00 43770 70821 1459 0 43770 70820 87541 1459 0 70820 87540 97871 1459 0 70820 81150 87540 9787 0 70820 77210 81150 8754 0 77210 81150 83590 8754 5 s phis k G E golds inline s3 2 s 1 0 3 0 15 0 001 G G 01 14591 85413 0000 00 70821 14591 8541 00 43770 70821 1459 0 43770 70820 87541 1459 0 70820 87540 97871 1459 0 70820 81150 87540 9787 0 70820 77210 81150 8754 0 77210 81150 83590 8754 0 77210 79650 81150 8359 0 79650 81150 82080 8359 6 2 2第第第4题题题 clear all s phis k ds dphi S qmin inline s3 2 s 1 0 3 1e 2 1e 4 s s 0 8165 2 3第第第6题题题 function f fun x f 100 x 2 x 1 2 2 1 x 1 2 6 function gf gfun x gf 400 x 2 x 1 2 x 1 2 1 x 1 200 x 2 x 1 2 function mk armijo xk dk beta 0 5 sigma 0 2 m 0 mmax 20 while m mmax if fun xk betam dk fun xk sigma betam gfun xk dk mk m break end m m 1 end alpha betamk newxk xk alpha dk fk fun xk newfk fun newxk clear all xk 1 1 dk 1 1 mk armijo xk dk alpha 0 0020 newxk 0 9980 1 0020 fk 4 7 newfk 3 9956 mk 9 3第第第三三三章章章最最最速速速下下下降降降法法法和和和牛牛牛顿顿顿法法法P41习习习题题题4 5 7 3 1第第第4题题题 function f funRosenbrock x f 100 x 2 x 1 2 2 x 1 1 2 function gf gfunRosenbrock x gf 400 x 1 x 2 x 1 2 2 x 1 1 200 x 2 x 1 2 function He HessRosenbrock x n length x He zeros n n He 1200 x 1 2 400 x 2 2 400 x 1 400 x 1 200 clear all x0 1 2 1 x val k dampnm funRosenbrock gfunRosenbrock HessRosenbrock x0 x 0 999999917104049 0 999999819231277 val 2 930227376149613e 014 k 8 20 初值变换 clear all x0 1 2 1 x val k dampnm funRosenbrock gfunRosenbrock HessRosenbrock x0 x 0 999999999964320 0 999999999926145 val 1 895465159084372e 021 k 22 与最速下降法比较 迭代次数多 x0 1 2 1 x val k grad funRosenbrock gfunRosenbrock x0 x 0 999989060890510 0 999978079102611 val 1 198472839392700e 010 k 1435 初值变 x0 1 2 1 x val k grad funRosenbrock gfunRosenbrock x0 x 0 999989152451513 0 999978260000300 val 9 1 178719917790613e 010 k 426 3 2第第第5题题题 设二次函数为f x 1 2x THx bTx 其中H为n阶对称正定矩阵 证明最速下降 法求f x 的极小点时 序列xk由xk 1 xk gT kgk gT kHgk gk k 0 1 2 确立 其 中x0为给定的初始点 gk Hxk b 证明 回顾一下最速下降算法步骤 0 初始条件给出 1 终止条件判定 2 搜索方向确定 dk gk 3 步长因子 k计算 本质上是单变量函数的最优极值确定 4 xk 1 xk kdk 因此 需要证明的是步长因子 k gT kgk gT kHgk 步3中步长因子 k的确定既可以使用精确线搜索方法 也可以使用非精确线 搜索算法 在理论上都能保证其全局收敛性 若采用精确线搜索方法 即 f xk kdk minf xk dk 那么 k应满足 d d f xk dk k f xk kdk Tdk 0 由dk gk f xk 有 f xk 1 f xk 0 新点xk 1处的梯度与旧点xk处的梯度是正交的 也就是说 迭代点列所走的路 线是锯齿型的 故其收敛速度是很缓慢的 至多是线性收敛速度 f x Hx b Hxk 1 b T Hxk b 0 H xk k gk b T Hxk b 0 10 Hxk b T Hxk b H k gk T Hxk b 0 gT kgk H k gk Tgk 0 k gT kgk gT kHgk 证毕 3 3第第第7题题题 给定函数f x 6 x1 x2 2 2 3x1 3x2 x1x2 2 求在点 x 4 6 T处 的最速下降方向和牛顿方向 解答 最速下降方向dk gk 牛顿方向 gk Gkdk 0 4第第第四四四章章章共共共轭轭轭梯梯梯度度度法法法P51习习习题题题1 3 6 1 4 1第第第1题题题 1 证明向量 1 1 0 T和 2 3 2 T关于矩阵 A 23 35 7 共轭 验证 T 1A 2 0 4 2第第第3题题题 3 设f x 1 2x THx bTx 其中 H 42 24 b 3 3 8 1 证明d0 1 0 T与d1 1 2 T关于H共轭 2 以x0 0 0 T为初始点 d0和d1为搜索方向 用精确线搜索求f的极小点 验证 1 dT 0Hd1 0 2 首先 g X f X H X b 42 24 x1 x2 3 3 9 用定理4 1 也就是算法4 1产生的迭代序列 则每一步迭代点xk 1都是f x 在x0和 方向d0 d1 dk所张成的线性流形 Sk x x x0 k i 0 idi i 中的 11 极小点 特别地 xn x G 1b是问题的唯一极小点 精确线搜索得到步长因子 k具有如下性质 gT k 1dk 0 Xk 1 Xk kdk gT k 1dk 0 10 Xk 1 Xk kdk 即 X1 X0 0d0 g X1 g1 g X1 H X1 b gT 1d0 0 0 3 4 X1 3 4 0 T f X1 9 8 同理 利用 10 迭代 即 X2 X1 1d1 gT 2d1 0 11 1 1 4 X2 1 2 1 2 T f X2 3 2 f X2 f X1 定理4 1保证了极小点为 X2 1 2 1 2 T 4 3第第第6 1 题题题 6 1 f x 4x2 1 4x22 4x1x2 12x2 取初始点x0 0 5 1 T g x f x Gx b G x 2f x G 共轭方向的构造过程 取初始方向d0 g0 令x1 x0 0d0 其中 f x1 Td0 gT 1d0 0 在x1处 用f在x1的负梯度方向 g1与d0的组合来生成d1 即d1 g1 0d0 然后选取系数 0 使得d1与d0关于G共轭 即令dT 1Gd0 0确定 0 因 此 0 gT 1Gd0 dT 0Gd0 g1 g0 G x1 x0 0Gd0 利用定理4 1可知gT 2di 0 i 0 1 计算过程 g x Gx b 8 4 48 x1 x2 0 12 12 G 8 4 48 13 d0 g x0 Gx b 8 4 48 0 5 1 0 12 8 2 14 12 x1 x0 0d0 0 5 1 0 8 2 8 0 0 5 2 0 1 15 f x1 Td0 gT 1d0 0 gT 1d0 8 4 48 8 0 0 5 2 0 1 0 12 T 8 2 0 16 0 17 104 x1 21 26 69 52 T 0 80769 1 32692 T g1 15 13 60 13 T 0 gT 1Gd0 dT 0Gd0 225 676 0 33284 d1 g1 0d0 3315 2197 23205 4394 T 1 5088757 5 281065 T x2 x1 1d1 f x2 Td1 gT 2d1 0 x2 255 1 169 21 26 1785 1 338 69 52 17 g2 15 13 1530 1 169 6120 1 169 60 13 18 由此可以求出 1 0 127450980392157 极值点为X2 1 2 T 5第第第七七七章章章非非非线线线性性性最最最小小小二二二乘乘乘问问问题题题P98 1 2 5 1第第第1题题题 1 设有非线性方程组 f1 x x3 1 2x22 1 0 f2 x 2x1 x2 2 0 19 1 列出求解这个方程组的非线性最小二乘问题的数学模型 最小二乘问题的数学表达式 minx Rnf x 1 2 F x 1 2 m i 1f 2 i x 2 写出求解该问题的高斯 牛顿法迭代公式的具体形式 13 Jk F x k F1 x k Fm x k T 3x2 1 k 4x2 k 21 20 dGN k JT kJk 1JT kF xk 3x2 1 k 2 4x2 k1 3x2 1 k 4x2 k 21 1 3x2 1 k 2 4x2 k1 x3 1 k 2x 2 2 k 1 2x1 k x2 k 2 21 3 初始点取为x0 2 2 T 迭代三次 迭代公式 Xk 1 Xk dGN k X1 X0 dGN 0 3 107142857142859 3 785714285714287 X2 X1 dGN 1 5 157431640715118 7 685136718569831 X3 X2 dGN 2 8 766682264589718 16 466635470820520 5 2第第第2题题题 2 解答 1 测得的t1 t2和y一共5组数据 分别代入关系式 y x1x3t1 1 x1t1 x2t2 22 14 0 13 x1x3 1 x1 x2 0 22 2x1x3 1 2x1 x2 0 08 x1x3 1 x1 2x2 0 13 2x1x3 1 2x1 2x2 0 19 0 1x1x3 1 0 1x1 23 F1 x x1x3 0 13 1 x1 x2 F2 x 2x1x3 0 22 1 2x1 x2 F3 x x1x3 0 08 1 x1 2x2 F4 x 2x1x3 0 13 1 2x1 2x2 F5 x 0 1x1x3 0 19 1 0 1x1 24 1 最小二乘问题模型表示为minx Rnf x 1 2 F x 1 2 m i 1F 2 i x 2 高斯牛顿迭代公式的具体公式为 dGN k JT kJk 1JT kF xk 5 3第第第4题题题 思路 求一阶导数和二阶导数 利用第一章一阶必要条件定理 局部极小点判 断 首先判断函数f是否为凸函数 or局部凸函数 求 f x 0得出 0 0 5 T 1 46557 2 1479 T 2 3 7 54 T 判断 2f x 在 0 0 5 T 1 46557 2 1479 T 2 3 7 54 T附近是否正定 5 4第第第6题题题 6 利用LM方法的matlab程序求解minf x 1 2 5 i 1r 2 i x 其中 r1 x x2 1 x22 x23 1 r2 x x1 x2 x3 1 r3 x x2 1 x22 x3 2 2 1 r4 x x1 x2 x3 1 r5 x x3 1 3x22 5x3 x1 1 2 36t 25 t为参数 可取t 0 5 1 5等 注意当t 1时 x 0 0 1 T是全局极小 点 这时问题为零残量 比较不同参数的计算效果 function x val k lmm Fk JFk x0 功能 用L M方法求解非线性方程组 F x 0 输入 x0是初始点 Fk JFk 分别是求F xk 及F xk 的函数 15 输出 x val分别是近似解及 F xk 的值 k是迭代次数 maxk 1000 给出最大迭代次数 0 55 0 4 k norm feval Fk x0 k 0 epsilon 1e 6 n length x0 while k maxk fk feval Fk x0 计算函数值 jfk feval JFk x0 计算Jacobi阵 gk jfk fk dk jfk jfk k eye n gk 解方程组Gk dk gk 计算搜索方向 if norm gk epsilon break end 检验终止准则 m 0 mk 0 while m 20 用Armijo搜索求步长 newf 0 5 norm feval Fk x0 m dk 2 oldf 0 5 norm feval Fk x0 2 if newf x0 1 1 1 x val k lmm Fk JFk x0 x 0 339361063668441 0 200183578804671 0 714384339944574 17 val 0 486062168183995 k 9 II t 1 注意 这里x 0 0 1 T是全局极小点 这时问题为零残量 clearall x0 1 1 1 x val k lmm Fk JFk x0 x 0 000000000000080 0 000000000000087 0 999999999999985 val 2 815888304992978e 027 k 8 III t 5 clearall x0 1 1 1 x val k lmm Fk JFk x0 x 0 490713830929549 0 103144026198463 2 384345136824180 val 14 450411547247533 k 14 18 6第第第八八八章章章最最最优优优性性性条条条件件件P112 1 2 6 1第第第1题题题 1 验证 x 2 1 T是否为下列最优化问题的KT点 minf x x1 3 2 x2 2 2 s t x2 1 x22 5 x1 2x2 4 x1 x2 0 26 验证 计算 f x 2 x1 3 2 x2 2 x x 2 2 h x 1 2 27 g1 x 2x1 2x2 4 2 g2 x 1 0 g3 x 0 1 28 令 f x h x 1 g1 x 0 即 2 2 1 2 1 4 2 2 1 0 3 0 1 0 29 令 2 0 3 0 解得 2 3 1 1 3 所以 f x h x 3 i 1 i gi x 0 igi x 0 i 0 i 1 2 3 30 这表明 x是KT点 x 是KT对 其中 2 3 1 3 0 0 T 6 2第第第2题题题 2 对于最优化问题 minf x 4x1 3x2 s t x1 3 2 x2 1 0 4 x1 x2 0 x2 7 0 31 19 求满足KT条件的点 解 类似第1题 f x 4 3 x x 4 3 h x 0 0 32 g1 x 2 x1 3 1 g2 x 1 1 g3 x 0 1 33 令 f x h x 3 i 1 i gi x 0 igi x 0 i 0 i 1 2 3 34 即 4 3 1 2 x1 3 1 2 1 1 3 0 1 0 1 x1 3 2 x2 1 0 2 4 x1 x2 0 3 x2 7 0 i 0 i 1 2 3 35 取 3 0 4 x1 x2 0 x2 4 x1 代入 x1 3 2 x2 1 0 x1 3 2 4 x1 1 0 x1 1或 x1 4 当 x1 4时 x2 0 1 7 3 2 2 3 不满足 i 0舍去 当 x1 1时 x2 3 1 7 3 2 16 3 满足 i 0 6 3第第第5题题题 5 利用KT条件推出线性规划 minz cTx s t Ax b x 0 36 20 的最优化条件 解 f x 2 i 1 i gi x 0 igi x 0 i 0 i 1 2 37 g1 x A g2 x I 其拉格朗日函数为 L x 1 2 cTx T 1 b Ax T2x 对上述函数关于x求极小 令 xL x 1 2 c 2 AT 1 0 由 37 2g2 x 2x 0 令 2 0 因此最优性条件为 c AT 1 0 1 b Ax 0 1 0 38 6 4第第第6题题题 6 设二次规划 minf x 1 2x THx cTx s t Ax b 39 其中H为n阶对称正定矩阵 矩阵A行满秩 求其最优解并说明解的唯一 性 解 首先写出该问题的拉格朗日函数为 L x 1 2x THx cTx T Ax b 21 对上述函数关于x求极小 由于H对称正定 故函数L x 关于x为凸函数 令 xL x Hx c AT 0 H对称正定 以及等式约束条件Ax b Hx c AT 0 x H 1c H 1AT 0 Ax AH 1c AH 1AT 0 b AH 1c AH 1AT 0 H对称正定 A行满秩 因此 AH 1AT可逆 需要简单证明 AH 1AT 1 b AH 1c 因此有拉格朗日乘子的唯一性解 也就有了最优解x H 1c H 1AT 的唯一性 7最最最优优优控控控制制制法法法 习习习题题题1 2 7 1习习习题题题1 设一阶系统方程为 x t u t x t0 x0 性能指标取为 J 1 2cx 2 tf 1 2 tf t0 u2 t dt 式中常数c 0 t0 tf给定 x tf 自由 试求使J取极小值的最优控制和相应的性能指标 解 引进伴随变量 t 构造哈米顿函数 H L x t t f x u t 1 2u 2 u 伴随方程 t H x 0 边界条件 tf 1 2cx 2 tf x tf cx tf 22 由必要条件 H u u 0 得 u cx tf 代入求得状态方程为 x t cx tf t t0 x0 令t tf 则有 x tf x0 1 c tf t0 则最优控制 u cx tf cx0 1 c tf t0 性能指标 1 2cx 2 tf 1 2c 2x2 tf tf t0 1 2x 2 tf c c2 tf t0 7 2习习习题题题2 设二阶系统方程为 x1 t x2 t x2 t u t 性能指标取为 J 1 2 1 0 u2 t dt 求系统由已知初始状态x1 0 0 x2 0 0在tf 1转移到目标集x1 1 x2 1 1 且使J取极小的最优控制和最优轨迹 解 引进伴随变量 t 1 2 T 构造哈米顿函数 H L x t t Tf x u t 1 2u 2 1x2 2u 伴随方程 协态方程 1 t H x1 0 2 t H x2 1 t 其解 1 t a1 2 t a1t a2 边界条件 x1 0 0 x2 0 0 x1 1 x2 1 1 23 横截条件 t 1 T x tf T 1 1 T 其中 x1 x2 1 由极值必要条件 H u u 2 0 得 u 2 a1t a2 代入求得状态方程为 x1 x2 x2 u a1t a2 则有 x1 1 6a1t 3 1 2a2t 2 a3t a4 x2 1 2a1t 2 a2t a3 由边界条件x1 0 0 x2 0 0 x1 1 x2 1 1 知道a3 a4 0 2 3a1 3 2a2 1 由横截条件知a1 a1 a2 因此a1 3 7 a2 6 7 则最优控制 u 2 a1t a2 3 7t 6 7 最优轨迹 x 1 1 14t 3 3 7t 2 x 2 3 14t 2 6 7t 8第第第九九九章章章罚罚罚函函函数数数法法法P132 1 1 2 1 3 3 6 8 1习习习题题题1 1 1 1 用外罚函数法求解下列约束优化问题 minf x x1 x2 s t x2 1 x22 1 40 解 24 由等式约束得x2 1 x2 1 代入目标函数得到一个无约束的单变量极小 化问题 min x1 x1 1 x2 1 其全局极小点为x1 1 2 从而得到原问题的全局极小点为 1 2 1 2 现在要使构造的罚函数P x 满足 P x 0 x2 1 x22 1 0 0 x2 1 x22 1 0 41 只要令 P x x2 1 x22 1 2即可 现在考察目标函数和上述罚函数的组合 P x f x P x x1 x2 P x 其中 0是充分大的正数 称为罚因子 罚参数 求这个组合函数的极 小点 由 P x x1 P x x2 0 得 1 4 x1 x2 1 x22 1 0 1 4 x2 x2 1 x22 1 0 42 由此可得x1 x2 0 因此x1 2x2 1 1 1 4 当 x1 0 舍去 和x1 1 2 所以x1 x2 1 2 minf x 2 8 2习习习题题题2 1 2 1 用内点法求解下列约束优化问题 1 minf x x1 x2 s t x2 1 x2 0 x1 0 43 更正 minf x x1 x2 s t x2 1 x2 0 x1 0 44 25 解 令g1 x x2 1 x2 g2 x x1 给出增广目标函数为 H x x1 x2 ln x2 1 x2 ln x1 令 H x1 1 2 x1 x2 1 x2 x1 0 H x2 1 x2 1 x2 0 45 x2 1 x2 1 2x1 x1 0 x1 1 1 8 4 0 x1 0或x1 1 2 x2 1 x2 x2 0或x2 1 4 当x1 1 2 x2 1 4时min f x 1 4 更正 解 令g1 x x2 1 x2 g2 x x1 给出增广目标函数为 H x x1 x2 ln x2 1 x2 ln x1 令 H x1 1 2 x1 x2 1