机械优化设计第四章PPT课件.pptx

第四章无约束优化方法 一 概述 1 无约束优化方法的意义 1 实际问题多数是有约束的 但也确实存在无约束优化问题 2 即使是有约束优化问题 在接近极小点时也可按无约束处理 3 有约束优化问题可以通过一系列无约束优化来处理 2 问题的提法及其直接解法 求n维设计变量 使目标函数 解法 即 求解非线性方程组 困难大 不如直接用数值方法求解 2020 3 18 1 第四章无约束优化方法 3 无约束优化方法分类 1 利用目标函数的一阶或二阶导数的无约束优化方法 如最速下降法 共扼梯度法 牛顿法及变尺度法等 2 只利用目标函数值的无约束优化方法 如坐标轮换法 单形替换法及鲍威尔 PDwell 法等 本章将分别讨论上述两类无约束优化方法 2020 3 18 2 第四章无约束优化方法 无约束优化问题算法的粗框图 2020 3 18 3 第四章无约束优化方法 二 最速下降法 最速下降法是以负梯度方向作为搜索方向 因此最速下降法又称为梯度法 2020 3 18 4 第四章无约束优化方法 在最速下降法中 相邻两个选代点上的函数梯度相互垂直 而搜索方向就是负梯度方向 因此相邻两个搜索方向互相垂直 这就是说在最速下降法中 迭代点向函数极小点靠近的过程 走的是曲折的路线 这一次的搜索方向与前一次的搜索方向互相垂直 形成 之 字形的锯齿现象 如图所示 最速下降法搜索路径 2020 3 18 5 第四章无约束优化方法 2020 3 18 6 第四章无约束优化方法 解 取初始点 则初始点的函数值和梯度分别为 沿负梯度方向进行一维搜索 有 2020 3 18 7 第四章无约束优化方法 经7次迭代可接近极值点 0 0 2020 3 18 8 第四章无约束优化方法 2020 3 18 9 第四章无约束优化方法 function x minf k minFD f x0 var eps formatlong ifnargin 3eps 1 0e 6 endsymsl tol 1 k 0 gradf jacobian f var whiletol epsv subs gradf var x0 tol norm v y x0 l v yf subs f var y a b minJT yf 0 0 1 xm minHJ yf a b x1 x0 xm v x0 x1 k k 1 endx x1 minf subs f var x formatshort 最速下降法的函数M文件 2020 3 18 10 第四章无约束优化方法 symsx1x2 f x1 2 4 x2 2 x mf k minFD f 2 2 x1 x2 x 1 0e 007 0 45150 4517mf 1 0198e 014k 16 symsx1x2 f x1 2 x2 2 x1 x2 10 x1 4 x2 60 x mf k minFD f 0 0 x1 x2 x 8 00006 0000mf 8 0000C DocumentsandSettings AllUsers 桌面 MATLABR2008b lnkk 19 2020 3 18 11 第四章无约束优化方法 三 牛顿型方法 Newton Raphson法 牛顿方法和最速下降法一样 是求解极值问题古老的算法之一 一维情况下的牛顿迭代公式 2020 3 18 12 第四章无约束优化方法 根据极值的必要条件 即 得 这就是多元函数求极值的牛顿迭代公式 对于二次函数 上述泰勒展开式精确的 海塞斯矩阵式常数 无论从哪点出发只需一步就可找到极小点 若某一迭代方法能使二次函数在有限次迭代内达到极小点 则称此迭代法为二次收敛的 牛顿方法就是二次收敛的 2020 3 18 13 第四章无约束优化方法 解 取初始点 则初始点的梯度 海塞斯矩阵及其逆阵分别为 2020 3 18 14 第四章无约束优化方法 代入牛顿迭代法公式 得 从而经过一次迭代即求得极小点及其函数值 从牛顿法迭代公式的推演中可以看到 迭代点的位置是按照极值条件确定的 其中并未含有沿下降方向搜寻的概念 因此对于非二次函数 如果采用上述牛顿法迭代公式 有时会使函数值上升 即出现的现象 为此 需对上述牛顿法进行改进 引入数学规划法的搜寻概念 提出所谓 阻尼牛顿法 2020 3 18 15 第四章无约束优化方法 阻尼牛顿法 2020 3 18 16 第四章无约束优化方法 2020 3 18 17 第四章无约束优化方法 function x minf minMNT f x0 var eps formatlong ifnargin 3eps 1 0e 6 endtol 1 x0 transpose x0 symsl gradf jacobian f var jacf jacobian gradf var kkk 0 whiletol epskkk kkk 1v subs gradf var x0 tol norm v pv subs jacf var x0 p inv pv transpose v y x0 l p yf subs f var y a b minJT yf 0 0 1 xm minHJ yf a b x1 x0 xm p x0 x1 endx x1 minf subs f var x formatshort 2020 3 18 18 第四章无约束优化方法 clcclearsymsstf s 2 t s t 2 2 x minf minMNT f 13 ts x 1 0e 007 0 0563 0 1690minf 2 0000 2020 3 18 19 第四章无约束优化方法 这样 原来的牛顿法就相当于阻尼牛顿法的步长因子取成固定值1的情况 由于阻尼牛顿法每次迭代都在牛顿方向上进行一维搜索 这就避免了迭代后函数值上升的现象 从而保持了牛顿法二次收敛的特性 而对初始点的选取并没有苛刻的要求 这类方法的主要缺点是每次迭代都要计算函数的二阶导数矩阵 并对该矩阵求逆 这样工作量很大 持别是矩阵求逆 当维数高时工作量更大 而最速下降法的收敛速度比牛顿法慢 针对这些缺点 人们研究了很多改进的算法 如针对最速下降法 梯度法 提出只用梯度信息 但比最速下降法收敛速度快的共轭梯度法 针对牛顿法提出变尺度法等 2020 3 18 20 第四章无约束优化方法 四 共轭方向法 conjugatedirectionmethod 1 共轭方向 以后几节都是从二次函数出发 引入有关算法 对二次函数 正定对称 有极小值 等值线 面 是椭圆 球 为了直观 考虑二元二次函数 对其进行一维搜索 2020 3 18 21 第四章无约束优化方法 由于 则 在极值点处 即 即 上式左乘 2020 3 18 22 第四章无约束优化方法 共轭方向的性质 共轭向量是线性无关的 2 n维问题最多只有n个独立的共轭向量 3 n维问题沿共轭向量方向搜索 最多n次到达极值点 2020 3 18 23 第四章无约束优化方法 求解共轭方向的格拉姆 斯密特 Gram Schmidt 方法 任意选择一组线性无关n个n维向量系 取 令 由共轭 解得 再令 由共轭 解得 则 2020 3 18 24 第四章无约束优化方法 例4 4 1求如下矩阵的一组共轭向量系 解 取三个坐标轴上的单位向量作为一组线性无关向量系 即 取 令 2020 3 18 25 第四章无约束优化方法 则 得 设 2020 3 18 26 第四章无约束优化方法 得 2020 3 18 27 第四章无约束优化方法 则 可以验证 2020 3 18 28 第四章无约束优化方法 源程序 即Matlab的M文件 clccleare0 100 e1 010 e2 001 H 2 10 12 1 0 12 d0 e0 b10 d0 H e1 d0 H d0 d1 e1 b10 d0 b21 d1 H e2 d1 H d1 b20 d0 H e2 d0 H d0 d2 e2 b21 d1 b20 d0 d0 d1 d2 计算结果 d0 100d1 0 50001 00000d2 0 33330 66671 0000 共轭向量系并不唯一 根据构建方法不同 形成不同的优化方法 而 Gram Schmidt 方法 需要计算海塞斯矩阵 不常用 2020 3 18 29 第四章无约束优化方法 2020 3 18 30 第四章无约束优化方法 五 共轭梯度法 conjugategradientmethod 1 相邻两点的梯度差 一维搜索 相邻位移 相邻梯度 左乘共轭得 结论 相邻梯度差与共轭向量正交 2020 3 18 31 第四章无约束优化方法 2 共轭梯度法步骤 计算 2 找共轭方向 共轭条件 即 解得 于是 令 2020 3 18 32 第四章无约束优化方法 递推公式 证明 已知 令 共轭条件 穷举下去得递推公式 2020 3 18 33 第四章无约束优化方法 解 取初始点 则 取 沿其进行一维搜索 得 2020 3 18 34 第四章无约束优化方法 求得 则 而 则求得第二个共轭方向 再进行一维搜索 2020 3 18 35 第四章无约束优化方法 求得 则 梯度为零说明已经是极值点 无需再算 所以 极小点 极小值 2020 3 18 36 第四章无约束优化方法 2020 3 18 37 第四章无约束优化方法 源程序 function x minf k minGETD f x0 var eps formatlong ifnargin 3eps 1 0e 6 endx0 transpose x0 n length var symsl gradf jacobian f var v0 subs gradf var x0 p transpose v0 k 0 while1v subs gradf var x0 tol norm v iftol epsx x0 break endy x0 l p yf subs f var y a b minJT yf 0 0 1 xm minHJ yf a b x1 x0 xm p vk subs gradf var x1 tol norm vk iftol epsx x1 break end 2020 3 18 38 第四章无约束优化方法 ifk 1 nx0 x1 continue elselamda dot vk vk dot v v p transpose vk lamda p k k 1 x0 x1 endendminf subs f var x formatshort 2020 3 18 39 第四章无约束优化方法 x 4 00002 0000mf 8 0000k 2 clearclcsymsx1x2 f x1 2 2 x2 2 4 x1 2 x1 x2 x mf k minGETD f 11 x1x2 2020 3 18 40 第四章无约束优化方法 六 变尺度法 1 尺度矩阵的概念变量的尺度变换是放大或缩小各个坐标 通过尺度变换可以把函数的偏心程度降低到最低限度 尺度变换技巧能显著地改进几乎所有极小化方法的收敛性质 2020 3 18 41 第四章无约束优化方法 H称为尺度矩阵 2020 3 18 42 第四章无约束优化方法 2 变尺度矩阵的建立 我们知道阻尼牛顿法为 我们把G的逆矩阵用尺度矩阵来代替 这样阻尼牛顿法为 是正定对称矩阵 我们不用求逆得到 而在迭代中逐步趋近 令 校正矩阵 满足拟牛顿条件 即 迭代公式 令 即 2020 3 18 43 第四章无约束优化方法 3 DFP Davidon Fletcher Powell 算法 校正矩阵取下列形式 代入拟牛顿条件 因为待定 可取 即 得 2020 3 18 44 第四章无约束优化方法 这意味着 即 代入校正公式 得 其中k 0 1 2 3 2020 3 18 45 第四章无约束优化方法 4 变尺度DFP算法的一般步骤 2020 3 18 46 第四章无约束优化方法 2020 3 18 47 第四章无约束优化方法 2020 3 18 48 第四章无约束优化方法 2020 3 18 49 第四章无约束优化方法 2020 3 18 50 第四章无约束优化方法 2020 3 18 51 第四章无约束优化方法 2020 3 18 52 第四章无约束优化方法 2020 3 18 53 第四章无约束优化方法 function x minf k minDFP f x0 var eps formatlong ifnargin 3eps 1 0e 6 endx0 transpose x0 n length var symsl H eye n n gradf jacobian f var v0 subs gradf var x0 p H transpose v0 k 0 while1v subs gradf var x0 tol norm v iftol epsx x0 break endy x0 l p yf subs f var y a b minJT yf 0 0 1 xm minHJ yf a b x1 x0 xm p vk subs gradf var x1 tol norm vk iftol epsx x1 break end 2020 3 18 54 第四章无约束优化方法 ifk 1 nx0 x1 k k 1 continue elsedx x1 x0 dgf vk v dgf transpose dgf dxT transpose dx dgfT transpose dgf mdx dx dxT mdgf dgf dgfT fz H dgf dgfT H H H mdx dxT dgf inv dgfT H dgf fz p H transpose vk k k 1 x0 x1 endendminf subs f var x formatshort 2020 3 18 55 第四章无约束优化方法 clearclcsymsx1x2 f x1 2 2 x2 2 4 x1 2 x1 x2 x mf k minDFP f 11 x1x2 x 4 00002 0000mf 8 0000k 2 clearclcsymsx1x2 f x1 2 x2 2 10 x1 x1 x2 4 x2 60 x mf k minDFP f 00 x1x2 x 8 00006 0000mf 8 0000k 3 2020 3 18 56 第四章无约束优化方法 作业 2020 3 18 57 第四章无约束优化方法 七 坐标轮换法 坐标轮换法是每次搜索只允许一个变量变化 其余变量保持不变 即沿坐标方向轮流进行搜索的寻忧方法 它把多变量的优化问题轮流地转化成单变量 其余变量视为常量 的优化问题 因此又称这种方法为变量轮换法 在搜索过程中可以不需要目标函数的导数 只需目标函数值信息 这比前面所讨论的利用目标函数导数信息建立搜索方向的方法要简单得多 2020 3 18 58 第四章无约束优化方法 2020 3 18 59 第四章无约束优化方法 2020 3 18 60 第四章无约束优化方法 2020 3 18 61 第四章无约束优化方法 clcclearsymsaf X0 1010 ee 0 0001 n 2 e1 10 e2 01 d0 e1 k 1 forkk 1 1 100X1b X0 af d0 faf X1b 1 2 2 X1b 2 2 4 X1b 1 2 X1b 1 X1b 2 qq diff faf af 1 af0 solve qq X1 subs subs X1b af0 af0 ifk nifnorm X1 X0 eebreakelseX0 X1 d0 e1 k 1 endelsek k 1 d0 e2 X0 X1 endff X1 1 2 2 X1 2 2 4 X1 1 2 X1 1 X1 2 kk X1 ffend 2020 3 18 62 第四章无约束优化方法 八 鲍威尔方法 鲍威尔法是直接利用函数值来构造共轭方向的一种共扼方向法 这种方法是在研究具有正定矩阵G的二次函数 的极小化问题时形成的 其基本思想是在不用导数的前提下 在迭代中逐次构造G的共轭方向 1 共轭方向的生成 2020 3 18 63 第四章无约束优化方法 两式相减得 因而有 令 2020 3 18 64 第四章无约束优化方法 对于二维问题 f x 的等值线为一族椭圆 A B为沿着x1轴上的两个极小点 分别位于等值线与x1轴方向的切点上 如图所示 根据上述分析 则A B连线就是与x1轴一起对H共轭的方向 沿此方向做一维搜索就可以找到极小点 2020 3 18 65 第四章无约束优化方法 2 基本算法 现在针对二维情况来描述鲍威尔的基本算法 如图所示 对于目标函数是n维的来说 3 从开始按方向进行搜索 得到极值点 连接和形成新的共轭方向 循环下去就可以得到极值点 2020 3 18 66 第四章无约束优化方法 3 改进的算法 上述算法仅具有理论意义 就是对二次函数 这个算法也可能失败 因为在迭代中的n个搜索方向有时可能会变成线性相关而不能形成共轭方向 张不成n维空间 这样就得不到极小点 改进算法具体步骤 邓乃扬等无约束最优化计算方法 如下 分别称作这一轮迭代的始点 终点和反射点 2020 3 18 67 第四章无约束优化方法 始点 终点和反射点所对应的函数值分别为 各中间点函数值分别记为 i 0 1 2 n 并计算n个函数值之差 i 0 1 2 n 其中最大者记作 3 判别条件 2020 3 18 68 第四章无约束优化方法 下一轮迭代的始点取为沿方向进行一维搜索的极小点 2020 3 18 69 第四章无约束优化方法 2020 3 18 70 第四章无约束优化方法 2020 3 18 71 第四章无约束优化方法 2020 3 18 72 第四章无约束优化方法 2020 3 18 73 第四章无约束优化方法 2020 3 18 74 第四章无约束优化方法