机械优化设计无约束优化方法PPT课件.ppt

第四章无约束优化方法 4 1最速下降法 梯度法 4 2 牛顿类方法 4 3 变尺度法 4 4 共轭方向法 4 5 鲍威尔方法 4 6其它方法 如坐标轮换法 单纯形法 1 第1章所列举的机械优化设计问题 都是在一定的限制条件下追求某一指标为最小 它们都属于约束优化问题 工程问题大都如此 为什么要研究无约束优化问题 1 有些实际问题 其数学模型本身就是一个无约束优化问题 2 通过熟悉它的解法可以为研究约束优化问题打下良好的基础 3 约束优化问题的求解可以通过一系列无约束优化方法来达到 所以无约束优化问题的解法是优化设计方法的基本组成部分 也是优化方法的基础 2 4 对于多维无约束问题来说 古典极值理论中令一阶导数为零 但要求二阶可微 且要判断海赛矩阵为正定才能求得极小点 这种方法有理论意义 但无实用价值 和一维问题一样 若多元函数F X 不可微 亦无法求解 但古典极值理论是无约束优化方法发展的基础 3 目前已研究出很多种无约束优化方法 它们的主要不同点在于构造搜索方向上的差别 1 间接法 要使用导数 如梯度法 阻尼 牛顿法 变尺度法 共轭梯度法等 2 直接法 不使用导数信息 如坐标轮换法 鲍威尔法 单纯形法等 无约束优化问题是 求n维设计变量 使目标函数 4 搜索方向的构成问题乃是无约束优化方法的关键 用直接法寻找极小点时 不必求函数的导数 只要计算目标函数值 这类方法较适用于解决变量个数较少的 n 20 问题 一般情况下比间接法效率低 间接法除要计算目标函数值外 还要计算目标函数的梯度 有的还要计算其海赛矩阵 5 4 1梯度法 基本思想 函数的负梯度方向是函数值在该点下降最快的方向 将n维问题转化为一系列沿负梯度方向用一维搜索方法寻优的问题 利用负梯度作为搜索方向 故称最速下降法或梯度法 搜索方向s取该点的负梯度方向 最速下降方向 使函数值在该点附近的范围内下降最快 6 为了使目标函数值沿搜索方向能够获得最大的下降值 其步长因子应取一维搜索的最佳步长 即有 根据一元函数极值的必要条件和多元复合函数求导公式 得 7 在最速下降法中 相邻两个迭代点上的函数梯度相互垂直 而搜索方向就是负梯度方向 因此相邻两个搜索方向互相垂直 这就是说在迭代点向函数极小点靠近的过程 走的是曲折的路线 形成 之 字形的锯齿现象 而且越接近极小点锯齿越细 图4 2最速下降法的搜索路径 8 9 方法特点 1 初始点可任选 每次迭代计算量小 存储量少 程序简短 即使从一个不好的初始点出发 开始的几步迭代 目标函数值下降很快 然后慢慢逼近局部极小点 2 任意相邻两点的搜索方向是正交的 它的迭代路径为绕道逼近极小点 当迭代点接近极小点时 步长变得很小 越走越慢 10 sk 11 沿负梯度方向进行一维搜索 有 为一维搜索最佳步长 应满足极值必要条件 例4 1求目标函数的极小点 解取初始点则初始点处函数值及梯度分别为 12 算出一维搜索最佳步长 第一次迭代设计点位置和函数值 继续作下去 经10次迭代后 得到最优解 13 这个问题的目标函数的等值线为一簇椭圆 迭代点从走的是一段锯齿形路线 见图4 3 14 将上例中目标函数引入变换 其等值线由椭圆变成一簇同心圆 仍从即出发进行最速下降法寻优 此时 沿负梯度方向进行一维搜索 则函数f X 变为 y1 x1 y2 5x2 15 由 从而算得一步计算后设计点的位置及其目标函数 16 经变换后 只需一次迭代 就可找到最优解 这是因为经过尺度变换 等值线由椭圆变成圆 17 梯度法的特点 1 理论明确 程序简单 对初始点要求不严格 2 对一般函数而言 梯度法的收敛速度并不快 因为最速下降方向仅仅是指某点的一个局部性质 3 梯度法相邻两次搜索方向的正交性 决定了迭代全过程的搜索路线呈锯齿状 在远离极小点时逼近速度较快 而在接近极小点时逼近速度较慢 4 梯度法的收敛速度与目标函数的性质密切相关 对于等值线 面 为同心圆 球 的目标函数 一次搜索即可达到极小点 18 前面介绍的许多优化方法 除鲍威尔 Powell 法外 都需要计算目标函数的导数 而在实际工程的最优化问题中 目标函数的导数往往很难求出或者根本无法求出 下面所介绍的方法只需要计算目标函数值 无需求其导数 因此计算比较简单 其几何概念也比较清晰 属于直接法的无约束最优化方法 这类方法适用于不知道目标函数的数学表达式而仅知其具体算法的情况 这也是直接法的一个优点 4 6其它方法 如坐标轮换法 单纯形法 19 坐标轮换法 坐标轮换法的基本思想 是将一个n维优化问题转化为依次沿n个坐标方向反复进行一维搜索问题 这种方法的实质是把n维问题的求优过程转化为对每个变量逐次进行一维求优的循环过程 每次一维搜索时 只允许n个变量的一次改动 其余 n 1 个变量固定不变 故坐标轮换法也常称单变量法或变量交错法 20 坐标轮换法 此法的效能在很大程度上取决于目标函数的性质 21 1 计算量少 程序简单 不需要求函数导数的直接探索目标函数最优解的方法 2 探索路线较长 问题的维数愈多求解的效率愈低 当维数n 10时 则不应采用此法 仅适用于n较少 n 10 的目标函数求优 3 改变初始点重新迭代 可避免出现病态 方法特点 22 23 步长加速法 Hook Reeves算法 一 步长加速法原理步长加速法也称之为离散步长的Hook Reeves算法 是一种不使用导数的直接搜索算法 其算法过程可分成两个基本阶段 坐标循环试探及模矢加速搜索 见下图 从初始探点Y0出发 依次沿n个坐标方向用固定步长 进行试探 寻找更好的点 而模矢加速搜索 就是沿模矢方向加大步长前进 以得到第k 1次迭代的出发点Y0 这样就完成了一次迭代 然后再从新的Y0出发 进行下一轮坐标循环试探 如此重复进行 使目标值不断减小 24 二 步长加速法算法 设问题为 X0为初始点 个坐标轴的单位方向向量 初始坐标循环试探的步长为 0 模矢加速搜索的加速步长因子为a 1 通常取a 2 迭代终止准则为 为预先确定的正数 25 1 2 否则转 6 否则 令 6 5 26 27 单纯形方法 一 基本思想单纯形替换法也是一种不使用导数的求解无约束极小化问题的直接搜索方法 与前面几种方法不同的是 单纯形替换法不是利用搜索方向从一个点迭代到另一个更优的点 而是从一个单纯形迭代到另一个更优的单纯形 28 定义 单纯形n维空间中的恰好有n 1个顶点 极点 的有界的凸多面体称之为一个单纯形 根据定义 可知 一维空间中的单纯形是线段 二维空间中的单纯形是三角形 而三维空间中的单纯形则是四面体 在单纯形替换算法中 从一个单纯形到另一个单纯形的迭代主要通过反射 扩张 收缩和缩边这4个操作来实现 下面以二维问题为例来对4种操作进行说明 参见下图 29 1 反射 设除了最劣点X1以外的基余顶点的中心为X4 作X1关于点X4的对称点X5 称X5为X1的反射点 求反射点的过程称之为反射 2 扩张 在得到反射点X5之后 如果X5优于原单纯形的最劣点 即有 表明反射方向 X5 X1 是有利方向 反射成功 若进一步有 可沿反射方向前进适当的距离到点X6 X6称之为扩张点 求扩张点的过程称之为扩张 扩张之后 若扩张点X6优于反射点X5 则扩张成功 以X6取代X1 得新单纯形 X6 X2 X3 否则 扩张失败 舍弃扩张点 以反射X5点取代X1 得新单纯形 X5 X2 X3 设当前的单纯形的顶点为X1 X2 X3 且有 30 如果出现 表示反射完全失败 应退回到介于X4与X1之间的某个点X8 3 收缩 在得到反射点X5之后 如果有 表示反射部分成功 方向 X5 X1 虽然是有利方向 但X5前进过远 应收缩到介于X4与X5之间的某个点X7 上述两种从反射点向X1方向后退的过程都称之为收缩 如果收缩点优于原来的最劣点X1 称收缩成功 并以收缩点取代原最劣点 构成新单纯形 X7 X2 X3 或 X8 X2 X3 否则 称之为收缩失败 舍弃收缩点 31 4 缩边 若收缩失败 则应压缩当前单纯形的边长 令最优点X3不动 而其余顶点向X3方向压缩 使边长缩短 通常缩短一半 以产生新单纯形 如下图所示 点X1压缩到点X9 点X2压缩到点X10 得新单纯形 X9 X10 X3 这一过程称之为缩边 32 二 单纯形替换算法设初始点为X0 初始边长h ei为坐标轴方向的单位向量 预定正数 2 比较各项点Xi的函数值 挑出其中的最优点 记为XL 最劣点 记XH 次差点 记为Xw 3 求反射中心 其中 a 0 通常取a 1 输出XL 为原问题近似极小点 否则 转 2 5 如果满足 33 34 35 表1无约束优化方法搜索方向之间的相互联系 间接法 海赛矩阵的逆阵 36 无约束优化方法 间接法总结 1 梯度法方向负梯度用到一阶导数适合于精度不高或用于复杂函数寻找一个好的初始点2 牛顿法用到一阶导数和海色矩阵 具有二次收敛性要求海色矩阵奇异 且维数不宜太高3 共轭梯度法用到一阶导数 具有二次收敛性4 变尺度法收敛快 效果好 被认为是目前最有效的无约束优化方法 适用于维数较高 具有一阶偏导数的目标函数 37 1 坐标轮换法计算效率较低适合维数较低 目标函数无导数或导数较难求得2 步长加速法同坐标轮换法