第四章无约束优化的直接搜索法PPT课件.ppt

机械优化设计 太原科技大学张学良 1 第四章无约束优化的直接搜索法 各种无约束优化方法的区别就在于确定其搜索方向S k 的方法不同 所以搜索方向的构成问题是无约束优化方法的关键 根据构造搜索方向所使用的信息性质的不同 无约束优化方法可以分为两类 X k 1 X k k S k k 0 1 2 一类是只利用目标函数值信息的无约束优化方法 如坐标轮换法 鲍威尔法 称为直接搜索法 另一类是利用目标函数的一阶或二阶导数信息的无约束优化方法 如梯度法 牛顿法 共轭梯度法 变尺度法 称为间接搜索法 2 基本思想 4 1坐标轮换法 变量轮换法 交替法 降维法 将n维无约束优化问题转化为n个沿坐标轴方向ei i 1 2 n 的一维优化问题来求解 并记完成n次一维搜索为一轮 若一轮搜索后未得到满足精度要求的最优点 则继续下一轮迭代搜索 如此反复 直至得到满足精度要求的最优点为止 在每一轮搜索中 每次迭代仅对n元函数的一个变量沿其坐标轴方向进行一维搜索 其余n 1个变量均保持不变 再依次轮换进行一维搜索的坐标轴 直至完成沿n个坐标轴方向的n次一维搜索 3 X0 1 X1 1 X2 1 取初始点X 0 X0 1 x1坐标轴方向的单位向量S1 1 e1 10 T x2坐标轴方向的单位向量S2 1 e2 01 T X1 1 X0 1 1 1 S1 1 X2 1 X1 1 2 1 S2 1 4 判断是否满足迭代收敛准则 X2 1 X0 1 X1 1 X0 1 1 1 e1 1 x1 0 x2 0 T 1 1 10 TX2 1 X1 1 2 1 e2 1 x1 1 x2 1 T 2 1 01 T 第一轮迭代搜索 若满足 则输出最优解 否则 继续下一轮迭代搜索 5 Xi k Xi 1 k i k ei k k 迭代轮次 i k轮迭代的第i次一维搜索 i k 一维搜索求得的最优步长 Xn k X0 k 计算步骤与算法框图 图4 13 1 任选初始点X 0 X0 1 x1 0 x2 0 xn 0 T 给定迭代收敛精度 i 1 k 1 2 置n个坐标轴方向向量为单位向量 即e1 10 0 T e2 010 0 T en 0 01 T 6 3 按如下迭代计算公式进行迭代计算 Xi k Xi 1 k i k ei k k 迭代轮次 i k轮迭代的第i次一维搜索i 1 2 n 4 判断是否满足迭代收敛准则 Xn k X0 k 若满足 则输出最优解 X Xn k f f X 否则 令X0 k 1 Xn k k k 1 返回3 7 举例 作业 用坐标轮换法求目标函数f X x12 x22 x1x2 4x1 10 x2 60的无约束最优解 初始点X 0 00 T 迭代收敛精度 0 1 坐标轮换法搜索过程和收敛情况讨论 X0 1 X X1 1 8 X0 1 X X1 1 9 X0 1 X1 1 X2 1 X 等值线出现脊线的情况 图4 14c 10 4 2鲍威尔 Powell 法 基本思想 它是直接利用函数值来构造共轭搜索方向的一种共轭搜索方向法 又称鲍威尔共轭方向法或方向加速法 由于对于n维正定二次函数 共轭搜索方向具有n次收敛的特性 所以鲍威尔法是直接搜索法中十分有效的一种算法 一般认为对于维数n 20的目标函数它是成功的 鲍威尔法是在研究具有正定对称矩阵H的二次函数的极小化问题时形成的 其基本思想是在不用函数导数信息的前提下 在迭代过程中逐次构造关于H的共轭方向 11 共轭方向的生成 设是X k 和X k 1 为从不同点出发 沿同一方向进行一维搜索而得到的两个极小点 S j S j S k X k X k 1 f X k f X k 1 S j T f X k 0 S j T f X k 1 0 12 具有正定对称矩阵H的二次函数f X 0 5XTHX BTX C在X k 和X k 1 两点处的梯度可以表示为 f X k HX k B 1 f X k 1 HX k 1 B 2 2 1 得 f X k 1 f X k H X k 1 X k 3 3 式两边同时左乘 S j T得 S j T f X k 1 f X k S j TH X k 1 X k 0 13 即 S j TH X k 1 X k 0若取S k X k 1 X k 那么 S k 和S j 关于H共轭 即 S j THS k 0 这说明 沿S j 方向分别对函数做两次一维搜索 得到两个极小点X k 和X k 1 该两点的连线方向S k 与S j 是关于H共轭的方向 14 X k S j X k 1 S k 15 上述生成共轭方向的方法完全可以推广到n维优化问题中 即在n维空间中 按上述方法可以生成n个相互共轭的搜索方向 鲍威尔法的基本原理和迭代过程 1 采用坐标轮换法顺次沿n个坐标轴方向进行一维搜索 然后以初始点X 0 和终点Xn 1 构成一个新的方向S 1 并以此方向为搜索方向再作一维搜索得到极小点Xn 1 1 2 取始点X0 2 Xn 1 1 并去掉原搜索方向组中的第一个方向S1 1 e1 而将第一轮构成的新搜索方向S 1 作为最末一个方向 以此组成第二轮迭代的n个方向 16 依此进行下去 直到获得满足迭代收敛精度要求的近似极小点为止 根据这一原理构造的迭代算法称为鲍威尔基本算法 X1 1 X S1 1 X0 1 S2 1 S 1 X2 1 X3 1 X1 2 X2 2 S 2 17 鲍威尔基本算法的缺点 鲍威尔基本算法仅具有理论意义 不要说对于一般的函数 就是对于二次函数 它也可能失效 因为在迭代过程中的n个搜索方向有时会变成线性相关 而不能形成共轭方向 从而张不成n维空间 导致随后的迭代搜索在降维 退化 的空间中进行 可能求不到极小点 故需进行改进 那么 为什么会产生这种情况呢 又该如何去改进呢 18 鲍威尔条件及鲍威尔修正算法 鲍威尔基本算法中 每一轮迭代都是用连接始点和终点所产生的新搜索方向去机械地替换原方向组中的第一个搜索方向 而不做任何的 好坏 判断 这正是产生向量线性相关而发生 退化 的根本原因所在 为了避免这种 退化 现象的发生 鲍威尔对这一基本算法进行了修正 即在每一轮产生新的搜索方向S k 后 首先判断原搜索方向组是否可以直接用作下一轮迭代的搜索方向组 若可以 则仍用之 否则 还要进一步判断原搜索方向组中哪个方向上函数值下降量最大或贡献最大 然后 19 再用新搜索方向替换这个贡献最大的搜索方向 以保证逐次生成共轭方向 即每一轮迭代的搜索方向组线性无关 对第k轮迭代 记f1 f X0 k f2 f Xn k f3 f 2Xn k X0 k 及 m k max f Xi 1 k f Xi k i 1 2 n 并记Sm k 为与 m k 相对应的搜索方向 S k Xn k X0 k 20 鲍威尔条件 若f3 f1 且 f1 2f2 f3 f1 f2 m k 2 0 5 m k f1 f3 2同时成立 则用S k 替代Sm k 否则 仍用原搜索方向组 这就是鲍威尔修正算法 通常所说的鲍威尔算法就是指这一修正算法 鲍威尔算法的计算步骤及算法框图 图4 18 1 任选初始点X 0 X0 1 给定迭代收敛精度 1 2 取初始基本方向组为单位坐标向量系 即Si 1 ei i 1 2 n 并置迭代轮次k 1 21 2 从X0 k 出发 依次沿Si k i 1 2 n 作一维搜索 得n个极小点Xi k i 1 2 n 构造新的搜索方向S k Xn k X0 k 并沿此方向进行一维搜索得极小点Xn 1 k 3 判断迭代终止条件 Xn 1 k X0 k 1 或 f Xn 1 k f X0 k 2 f Xn 1 k 若满足 则终止迭代并输出最优解 X Xn 1 k 和f f X 否则 则继续下面的迭代计算 22 4 计算f Xi k i 1 2 n 并求 m k max f Xi 1 k f Xi k i 1 2 n fm 1 fm及与之对应的两个点Xm 1 k 和Xm k 1 m n 则第k轮迭代中贡献最大的方向为Sm k Xm k Xm 1 k 5 确定映射点X k 2Xn k X0 k 并计算f X k 记f1 f X0 k f2 f Xn k 及f3 f X k 检验鲍威尔条件 若满足 则转下一步 否则转第7 步 23 6 置第k 1轮迭代的出发点和搜索方向组X0 k 1 Xn 1 k Si k 1 i 1 2 n 即 S1 k Sm 1 k S k Sm 1 k Sn k 并置k k 1 返回第2 步 7 置第k 1轮迭代的出发点和搜索方向组若f2 f3 X0 k 1 Xn k 否则 X0 k 1 X k Si k 1 Si k i 1 2 n 并置k k 1 返回第2 步 24 举例 例4 6 用鲍威尔法求目标函数f X 10 x1 x2 5 2 x1 x2 2的无约束最优解 初始点X 0 00 T 迭代收敛精度 0 001 25 4 3单形替换法 基本思想 通过计算出若干点处的函数值 对其大小进行比较 可以看出函数值变化的大致趋势 从而可以寻求使函数值下降的搜索方向 在n维空间中 由n 1个不同点顺序相连 就可以构成一个具有n 1个顶点的多面体 称之为单纯形 计算函数在这n 1个顶点的函数值 并进行比较 据此来确定有利的搜索方向和步长 找到一个比较好的点来取代单纯形中较差的那个顶点 从而组成了一个新的单纯形 并用之取代原来的单纯形 如此下去 新单纯形不断地向目标函数的极小点靠 26 近 直到搜索到极小点为止 计算步骤 1 构造初始单纯形选初始点X0 和步长h 从X0出发沿各坐标轴方向分别走步长h 得到n个顶点Xi i 1 2 n 与X0构成初始单纯形 27 2 计算各顶点的函数值fi f Xi i 0 1 2 n 3 比较函数值大小 确定最好点XL 最差点XH和次差点XG 即 fL f XL min fi i 0 1 2 n fH f XH max fi i 0 1 2 n fG f XG max fi i 0 1 2 n i H 4 检验是否满足迭代收敛条件 fH fL fL 28 若满足 则结束迭代计算 并输出X XL和f fL 否则 转下一步 5 计算除XH点外的各点的 重心 Xn 1 即Xn 1 Xi XH n计算反射点 Xn 2 2Xn 1 XH和fn 2 f Xn 2 当fL fn 2 fG时 以Xn 2代替XH fn 2代替fH 构造新的单纯形 然后返回到3 29 XH XL XG Xn 1 Xn 2 6 扩张 当fn 2 fL时 取扩张点Xn 3 即Xn 3 Xn 1 Xn 2 Xn 1 1 2 2 0 并计算fn 3 f Xn 3 若fn 3 fn 2 则以Xn 3代替XH fn 3代替fH 构造一个新的单纯形 否则 以Xn 2代替XH fn 2代替fH 构造新的单纯形 然后返回到3 Xn 3 30 7 收缩 当fn 2 fG时 则需收缩 若fn 2 fH 则取收缩点Xn 4 Xn 4 Xn 1 Xn 2 Xn 1 0 5 fn 4 f Xn 4 否则 以XH代替上式中的Xn 2 计算收敛点Xn 4 Xn 4 Xn 1 XH Xn 1 fn 4 f Xn 4 31 若fn 4 fH 则以Xn