无约束优化方法(白版).ppt

第四章无约束优化方法 4 1最速下降法 梯度法 4 2牛顿类方法 4 3变尺度法 4 4共轭方向法 4 5鲍威尔方法 4 6其它方法 如坐标轮换法 单纯形法 第1章所列举的机械优化设计问题 都是在一定的限制条件下追求某一指标为最小 它们都属于约束优化问题 工程问题大都如此 为什么要研究无约束优化问题 1 有些实际问题 其数学模型本身就是一个无约束优化问题 2 通过熟悉它的解法可以为研究约束优化问题打下良好的基础 3 约束优化问题的求解可以通过一系列无约束优化方法来达到 所以无约束优化问题的解法是优化设计方法的基本组成部分 也是优化方法的基础 4 对于多维无约束问题来说 古典极值理论中令一阶导数为零 但要求二阶可微 且要判断海赛矩阵为正定才能求得极小点 这种方法有理论意义 但无实用价值 和一维问题一样 若多元函数F X 不可微 亦无法求解 但古典极值理论是无约束优化方法发展的基础 目前已研究出很多种无约束优化方法 它们的主要不同点在于构造搜索方向上的差别 1 间接法 要使用导数 如梯度法 阻尼 牛顿法 变尺度法 共轭梯度法等 2 直接法 不使用导数信息 如坐标轮换法 鲍威尔法单纯形法等 无约束优化问题是 求n维设计变量 使目标函数 搜索方向的构成问题乃是无约束优化方法的关键 用直接法寻找极小点时 不必求函数的导数 只要计算目标函数值 这类方法较适用于解决变量个数较少的 n 20 问题 一般情况下比间接法效率低 间接法除要计算目标函数值外 还要计算目标函数的梯度 有的还要计算其海赛矩阵 4 1梯度法 基本思想 函数的负梯度方向是函数值在该点下降最快的方向 将n维问题转化为一系列沿负梯度方向用一维搜索方法寻优的问题 利用负梯度作为搜索方向 故称最速下降法或梯度法 搜索方向s取该点的负梯度方向 最速下降方向 使函数值在该点附近的范围内下降最快 为了使目标函数值沿搜索方向能够获得最大的下降值 其步长因子应取一维搜索的最佳步长 即有 根据一元函数极值的必要条件和多元复合函数求导公式 得 在最速下降法中 相邻两个迭代点上的函数梯度相互垂直 而搜索方向就是负梯度方向 因此相邻两个搜索方向互相垂直 这就是说在迭代点向函数极小点靠近的过程 走的是曲折的路线 形成 之 字形的锯齿现象 而且越接近极小点锯齿越细 图4 2最速下降法的搜索路径 方法特点 1 初始点可任选 每次迭代计算量小 存储量少 程序简短 即使从一个不好的初始点出发 开始的几步迭代 目标函数值下降很快 然后慢慢逼近局部极小点 2 任意相邻两点的搜索方向是正交的 它的迭代路径为绕道逼近极小点 当迭代点接近极小点时 步长变得很小 越走越慢 沿负梯度方向进行一维搜索 有 为一维搜索最佳步长 应满足极值必要条件 例4 1求目标函数的极小点 解取初始点则初始点处函数值及梯度分别为 算出一维搜索最佳步长 第一次迭代设计点位置和函数值 继续作下去 经10次迭代后 得到最优解 这个问题的目标函数的等值线为一簇椭圆 迭代点从走的是一段锯齿形路线 见下图 将上例中目标函数引入变换 其等值线由椭圆变成一簇同心圆 仍从即出发进行最速下降法寻优 此时 沿负梯度方向进行一维搜索 则函数f X 变为 y1 x1 y2 5x2 由 从而算得一步计算后设计点的位置及其目标函数 经变换后 只需一次迭代 就可找到最优解 这是因为经过尺度变换 等值线由椭圆变成圆 梯度法的特点 1 理论明确 程序简单 对初始点要求不严格 2 对一般函数而言 梯度法的收敛速度并不快 因为最速下降方向仅仅是指某点的一个局部性质 3 梯度法相邻两次搜索方向的正交性 决定了迭代全过程的搜索路线呈锯齿状 在远离极小点时逼近速度较快 而在接近极小点时逼近速度较慢 4 梯度法的收敛速度与目标函数的性质密切相关 对于等值线 面 为同心圆 球 的目标函数 一次搜索即可达到极小点 4 2牛顿法及其改进 设为的极小点 这就是多元函数求极值的牛顿法迭代公式 对于二次函数 海赛矩阵H是一个常矩阵 其中各元素均为常数 因此 无论从任何点出发 只需一步就可找到极小点 例4 2求目标函数的极小点 解取初始点 从牛顿法迭代公式的推演中可以看到 迭代点的位置是按照极值条件确定的 其中并未含有沿下降方向搜寻的概念 因此对于非二次函数 如果采用上述牛顿迭代公式 有时会使函数值上升 阻尼牛顿法 阻尼因子 沿牛顿方向进行一维搜索的最佳步长 由下式求得 经过一次迭代即求得极小点 函数极小值 阻尼牛顿法程序框图 方法特点 1 初始点应选在X 附近 有一定难度 2 尽管每次迭代都不会是函数值上升 但不能保证每次下降 3 若迭代点的海赛矩阵为奇异 则无法求逆矩阵 不能构造牛顿法方向 4 不仅要计算梯度 还要求海赛矩阵及其逆矩阵 计算量和存储量大 此外 对于二阶不可微的F X 也不适用 虽然阻尼牛顿法有上述缺点 但在特定条件下它具有收敛最快的优点 并为其他的算法提供了思路和理论依据 一般迭代式 梯度法 牛顿法 阻尼牛顿法 梯度法与牛顿法 4 3变尺度法 DFP变尺度法首先有戴维顿 Davidon 与1959年提出 又于1963年由弗莱彻 Fletcher 和鲍维尔加以发展和完善 成为现代公认的较好的算法之一 DFP法是基于牛顿法的思想又作了重要改进 这种算法仅用到梯度 不必计算海赛阵及其逆矩阵 但又能使搜索方向逐渐逼近牛顿方向 具有较快的收敛速度 基本思想变量的尺度变换是放大或缩小各个坐标 通过尺度变换可以把函数的偏心程度降到最低限度 例如在用最速下降法求的极小 值时 需要进行10次迭代才能达到极小点 如作变换 y1 x1 y2 5x2 消除了函数的偏心 用最速下降法只需一次迭代即可求得极小点 梯度法构造简单 只用到一阶偏导数 计算量小 初始点可任选 且开始几次迭代 目标函数值下降很快 其主要缺点是迭代点接近X 时 即使对二次正定函数收敛也非常慢 牛顿法收敛很快 对于二次函数只需迭代一次便达到最优点 对非二次函数也能较快迭代到最优点 但要计算二阶偏导数矩阵及其逆阵 对维数较高的优化问题 其计算工作和存储量都太大 能不能将两种算法的优点综合起来 扬长避短 Ak是需要构造n n的一个对称方阵 如Ak I 则得到梯度法 变尺度法的关键在于尺度矩阵Ak的产生 对于二次函数 进行尺度变换 在新的坐标系中 函数f x 的二次项变为 目的 减少二次项的偏心 如G是正定 则总存在矩阵Q 使得 用矩阵Q 1右乘等式两边 得 用矩阵Q左乘等式两边 得 所以 上式说明 二次函数矩阵G的逆阵 可以通过尺度变换矩阵Q来求得 牛顿迭代公式 记 搜索方向 迭代公式 A称为变尺度矩阵 在例4 2中 如取 求得 构造尺度矩阵Ak 从初始矩阵A0 I 单位矩阵 开始 通过对公式 因此 一旦达到最优点附近 就可望达到牛顿法的收敛速度 1 DFP法 Davidon Fletcher Powell 式中 2 BFGS算法 Broyden Fletcher Goldfrob Shanno DFP算法由于舍入误差和一维搜索不精确 有可能导致构造矩阵的正定性遭到破坏 以至算法不稳定 BFGS算法对于维数较高问题具有更好的稳定性 例4 3 用DFP算法求下列问题的极值 解 1 取初始点 为了按DFP法构造第一次搜寻方向d0 需计算初始点处的梯度 取初始变尺度矩阵为单位矩阵A0 I 则第一次搜寻方向为 沿d0方向进行一维搜索 得 为一维搜索最佳步长 应满足 得 2 再按DFP法构造点x1处的搜寻方向d1 需计算 代入校正公式 第二次搜寻方向为 再沿d1进行一维搜索 得 为一维搜索最佳步长 应满足 3 判断x2是否为极值点 梯度 海赛矩阵 梯度为零向量 海赛矩阵正定 可见点满足极值充要条件 因此为极小点 4 4共轭方向法 1 共轭方向 设G为n n阶实对称正定矩阵 如果有两个n维向量d0和d1满足 则称向量d0与d1关于矩阵G共轭 当G为单位矩阵时 假设目标函数f x 在极值点附近的二次近似函数为 对二维情况 任选取初始点x0沿某个下降方向d0作一维搜索 得x1 因为是沿d0方向搜索的最佳步长 即在点x1处函数f x 沿方向d0的方向导数为零 考虑到点x1处方向导数与梯度之间的关系 故有 如果按最速下降法 选择负梯度方向为搜索方向 则将发生锯齿现象 取下一次的迭代搜索方向d1直指极小点x 如果能够选定这样的搜索方向 那么对于二元二次函数只需顺次进行d0 d1两次直线搜索就可以求到极小点x 即有 那么这样的d1方向应该满足什么条件呢 对于前述的二次函数 当时 x 是f x 极小点 应满足极值必要条件 故有 将等式两边同时左乘得 有 就是使d1直指极小点x d1所必须满足的条件 两个向量d0和d1称为G的共轭向量 或称d0和d1对G是共轭方向 2 共轭方向的性质 性质1若非零向量系d0 d1 d2 dm 1是对G共轭 则这m个向量是线性无关的 性质2在n维空间中互相共轭的非零向量的个数不超过n 性质3从任意初始点出发 顺次沿n个G的共轭方向d0 d1 d2 进行一维搜索 最多经过n次迭代就可以找到的二次函数f x 极小点 关键 新的共轭方向确定 在无约束方法中许多算法都是以共轭方向作为搜索方向 它们具有许多特点 根据构造共轭方向的原理不同 可以形成不同的共轭方向法 3 共轭梯度法 共轭梯度法是共轭方向法中的一种 该方法中每一个共轭向量都是依赖于迭代点处的负梯度而构造出来 从xk出发 沿负梯度方向作一维搜索 设与dk共轭的下一个方向dk 1由dk和点xk 1的负梯度的线形组合构成 即 共轭条件 则 解得 令 为函数的泰勒二次展开式 则 上两式相减 并代入 将式 与式 两边相乘 并应用共轭条件 得 因此 已知初始点 1 1 T 例题4 4求下列问题的极值 解 1 第一次沿负梯度方向搜寻计算初始点处的梯度 为一维搜索最佳步长 应满足 迭代精度 得 2 第二次迭代 代入目标函数 得 因 收敛 由 从而有 4 5鲍威尔方法 鲍威尔法是以共轭方向为基础的收敛较快的直接法之一 是一种十分有效的算法 1964年 鲍维尔提出这种算法 其基本思想是直接利用迭代点的目标函数值来构造共轭方向 然后从任一初始点开始 逐次沿共轭方向作一维搜索求极小点 并在以后的实践中进行了改进 对函数 基本思想 在不用导数的前提下 在迭代中逐次构造G的共轭方向 1 共轭方向的生成 设xk xk 1为从不同点出发 沿同一方向dj进行一维搜索而到的两个极小点 梯度和等值面相垂直的性质 dj和xk xk 1两点处的梯度gk gk 1之间存在关系 另一方面 对于上述二次函数 其xk xk 1两点处的梯度可表示为 因而有 取 这说明只要沿dj方向分别对函作两次一维搜索 得到两个极小点xk和xk 1 那么这两点的连线所给出的方向dk就是与dj一起对G共轭的方向 2 基本算法 二维情况描述鲍威尔的基本算法 1 任选一初始点x0 再选两个线性无关的向量 如坐标轴单位向量e1 1 0 T和e2 0 1 T作为初始搜索方向 2 从x0出发 顺次沿e1 e1作一维搜索 得点 两点连线得一新方向d1 沿d2作一维搜索得点x2 即是二维问题的极小点x 方法的基本迭代格式包括共轭方向产生和方向替换两主要步骤 用d1代替e1形成两个线性无关向量d1 e2 作为下一轮迭代的搜索方向 再从出发 沿d1作一维搜索得点 作为下一轮迭代的初始点 3 从出发 顺次沿e2 d1作一维搜索 得到点 两点连线得一新方向 把二维情况的基本算法扩展到n维 则鲍威尔基本算法的要点是 在每一轮迭代中总有一个始点 第一轮的始点是任选的初始点 和n个线性独立的搜索方向 从始点出发顺次沿n个方向作一维搜索得一终点 由始点和终点决定了一个新的搜索方向 用这个方向替换原来n个方向中的一个 于是形成新的搜索方向组 替换的原则是去掉原方向组的第一个方向而将新方向排在原方向的最后 此外规定 从这一轮的搜索终点出发沿新的搜索方向作一维搜索而得到的极小点 作为下一轮迭代的始点 这样就形成算法的循环 上述基本算法仅具有理论意义 因为在迭代中的n个搜索方向有时会变成线性相关而不能形成共轭方向 这时组不成n维空间 可能求不到极小点 所以上述基本算法有待改进 3 改进的算法 在鲍威尔基本算法中 每一轮迭代都用连结始点和终点所产生出的搜索方向去替换原向量组中的第一个向量 而不管它的 好坏 这是产生向量组线性相关的原因所在 在改进的算法中首先判断原向量组是否需要替换 如果需要替换 还要进一步判断原向量组中哪个向量最坏 然后再用新产生的向量替换这个最坏的向量 以保证逐次生成共轭方向 为此 要解决两个关键问题 1 dk 1是否较好 是否应该进入新的方向组 即方向组是否进行更新 2 如果应该更新方向组 dk 1不一定替换方向 而是有选择地替换某一方向 令在k次循环中 分别称为一轮迭代的始点 终点和反射点 则在循环中函数下降最多的第m次迭代是 记 相应的方向为 为了构成共轭性好的方向组 须遵循下列准则 在k次循环中 若满足条件 和 则选用新方向dk 并在第k 1迭代中用dk替换对应于的方向 否则 仍然用原方向组进行第k 1迭代 因此 这样重复迭代的结果 后面加进去的向量都彼此对G共轭 经n轮迭代即可得到一个由n个共轭方向所组成的方向组 对于二次函次 最多n次就可找到极小点 而对一般函数 往往要超过n次才能找到极小点 这里 n 表示设计空间的维数 例4 5用改进的鲍威尔法求目标函数 解 1 第1轮迭代计算 沿e1方向进行一维搜索 得 以为起点 沿第二坐标轴方向e2进行一维搜索 得 确定此轮中的最大下降量及其相应方向 反射点及其函数值 检验Powell条件 由于满足Powell条件 则淘汰函数值下降量最大的方向e1 下一轮的基本方向组为e2 构成新的方向 沿方向一维搜索得极小点和极小值 此点为下轮迭代初始点 按点距准则检验终止条件 需进行第二轮迭代机算 2 第2轮迭代计算 此轮基本方向组为e2 分别相当于 起始点为 沿e2方向进行一维搜索得 以为起点沿方向一维搜索得 确定此轮中函数值最大下降量及其相应方向 反射点及其函数值 检验Powell条件 淘汰函数值下降量最大的方向e2 下一轮的基本方向组应为 构成新的方向 沿方向进行一维搜索得 检验终止条件 3 第3轮迭代计算 此轮基本方向组为 起始点为 先后沿 方向 进行一维搜索 得 故最优解 检验终止条件 实际上 前两轮迭代的 为共轭方向 由于本例目标函数是二次函数 按共轭方向的二次收敛性 故前两轮的结果就是问题的最优解 但每一轮迭代都需要进行n 1次迭代 前面介绍的许多优化方法 除鲍威尔 Powell 法外 都需要计算目标函数的导数 而在实际工程的最优化问题中 目标函数的导数往往很难求出或者根本无法求出 下面所介绍的方法只需要计算目标函数值 无需求其导数 因此计算比较简单 其几何概念也比较清晰 属于直接法的无约束最优化方法 这类方法适用于不知道目标函数的数学表达式而仅知其具体算法的情况 这也是直接法的一个优点 4 6其它方法 如坐标轮换法 单纯形法 坐标轮换法 坐标轮换法的基本思想 是将一个n维优化问题转化为依次沿n个坐标方向反复进行一维搜索问题 这种方法的实质是把n维问题的求优过程转化为对每个变量逐次进行一维求优的循环过程 每次一维搜索时 只允许n个变量的一次改动 其余 n 1 个变量固定不变 故坐标轮换法也常称单变量法或变量交错法 坐标轮换法 此法的效能在很大程度上取决于目标函数的性质 1 计算量少 程序简单 不需要求函数导数的直接探索目标函数最优解的方法 2 探索路线较长 问题的维数愈多求解的效率愈低 当维数n 10时 则不应采用此法 仅适用于n较少 n 10 的目标函数求优 3 改变初始点重新迭代 可避免出现病态 方法特点 步长加速法 Hook Reeves算法 一 步长加速法原理步长加速法也称之为离散步长的Hook Reeves算法 是一种不使用导数的直接搜索算法 其算法过程可分成两个基本阶段 坐标循环试探及模矢加速搜索 见下图 从初始探点Y0出发 依次沿n个坐标方向用固定步长 进行试探 寻找更好的点 而模矢加速搜索 就是沿模矢方向加大步长前进 以得到第k 1次迭代的出发点Y0 这样就完成了一次迭代 然后再从新的Y0出发 进行下一轮坐标循环试探 如此重复进行 使目标值不断减小 二 步长加速法算法 设问题为 X0为初始点 个坐标轴的单位方向向量 初始坐标循环试探的步长为 0 模矢加速搜索的加速步长因子为a 1 通常取a 2 迭代终止准则为 为预先确定的正数 1 2 否则转 6 否则 令 6 5 单纯形方法 一 基本思想单纯形替换法也是一种不使用导数的求解无约束极小化问题的直接搜索方法 与前面几种方法不同的是 单纯形替换法不是利用搜索方向从一个点迭代到另一个更优的点 而是从一个单纯形迭代到另一个更优的单纯形 定义 单纯形n维空间中的恰好有n 1个顶点 极点 的有界的凸多面体称之为一个单纯形 根据定义 可知 一维空间中的单纯形是线段 二维空间中的单纯形是三角形 而三维空间中的单纯形则是四面体 在单纯形替换算法中 从一个单纯形到另一个单纯形的迭代主要通过反射 扩张 收缩和缩边这4个操作来实现 下面以二维问题为例来对4种操作进行说明 参见下图 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 且有 如果出现 表示反射完全失败 应退回到介于X4与X1之间的某个点X8 3 收缩 在得到反射点X5之后 如果有 表示反射部分成功 方向 X5 X1 虽然是有利方向 但X5前进过远 应收缩到介于X4与X5之间的某个点X7 上述两种从反射点向X1方向后退的过程都称之为收缩 如果收缩点优于原来的最劣点X1 称收缩成功 并以收缩点取代原最劣点 构成新单纯形 X7 X2 X3 或 X8 X2 X3 否则 称之为收缩失败 舍弃收缩点 4 缩边 若收缩失败 则应压缩当前单纯形的边长 令最优点X3不动 而其余顶点向X3方向压缩 使边长缩短 通常缩短一半 以产生新单纯形 如下图所示 点X1压缩到点X9 点X2压缩到点X10 得新单纯形 X9 X10 X3 这一过程称之为缩边 二 单纯形替换算法设初始点为X0 初始边长h ei为坐标轴方向的单位向量 预定正数 2 比较各项点Xi的函数值 挑出其中的最优点 记为XL 最劣点 记XH 次差点 记为Xw 3 求反射中心 其中 a 0 通常取a 1 输出XL 为原问题近似极小点 否则 转 2 5 如果满足 表1无约束优化方法搜索方向之间的相互联系 间接法 海赛矩阵的逆阵 无约束优化方法 间接法总结 1 梯度法方向负梯度用到一阶导数适合于精度不高或用于复杂函数寻找一个好的初始点2 牛顿法用到一阶导数和海色矩阵 具有二次收敛性要求海色矩阵奇异 且维数不宜太高3 共轭梯度法用到一阶导数 具有二次收敛性4 变尺度法收敛快 效果好 被认为是目前最有效的无约束优化方法 适用于维数较高 具有一阶偏导数的目标函数 1 坐标轮换法计算效率较低适合维数较低 目标函数无导数或导数较难求得2 步长加速法同坐标轮换法 对目标函数的性态的适应性更好3 Powell法具有二次收敛性 收敛速度较快 可靠性高 被认为是直接法中最有效的方法之一4 单纯形法思路清楚 收敛慢 无约束优化方法 直接法总结 无约束优化上机 Powell法优化设计程序 与一维搜索黄金分割法组合 题目 编程求解函数 的极小点x 初始点x0 1 1 T 迭代精度 上机地点 4109 材控 装控 4211 机自 时间 周一晚6 00 9 30