《最优化方法 尹秋响课件第五章.ppt》由会员分享，可在线阅读，更多相关《最优化方法 尹秋响课件第五章.ppt（50页珍藏版）》请在金锄头文库上搜索。
1、本章要点 单纯形单纯形搜索法的基本思想共轭方向 共轭方向法的基本定理Powell共轭方向法的基本思想最速下降法的基本思想及特点Newton法基本思想及特点牛顿方向Marquardt法基本思想最小二乘问题共轭梯度法基本思想拟Newton法的基本思想 第五章无约束非线性问题的解法 5 1直接搜索法 优点 计算不太复杂 易于实施与快速调试 所需的准备时间较少 5 1 1单纯形搜索法 1962年由Spendley Hext和Himsworth提出 80年代得到证明 一 单纯形 空间中最简单 其 维数 与空间维数相同的图形 n维空间中具有n 1个顶点的 n维超多面体 称为n维单纯形 如果各顶点间的距离
2、棱长 相等 则称为正规单纯形 二 单纯形法的基本思想 初始单纯形 以minf x1 x2 为例 说明迭代过程 fH fG fL 反射PR fR fG反射成功 fR fG反射失败 fE fR扩张成功PS PE fE fR扩张失败PS PR PS fS fG压缩成功PS fS fG压缩失败 对n元函数f x 可取n维空间中n 1个点x 0 x 1 x n 构成一个初始单纯形 这n 1个点应使x 1 x 0 x 2 x 0 x n x 0 线性无关 否则是退化的单纯形 例如 对二维 三点不能在一条直线时 对三维 四点不能在同一平面上 三 单纯形搜索法的算法 给定一个最大迭代次数KM 令迭代次数计数变
3、量K 0 1 给定初始点x 0 用下列两种方法之一构造初始单纯形 棱长为h的正规单纯形 2 计算函数值fi f x i i 0 1 2 n 并比较大小 找出最差点x H 次差点x G 和最好点x L 即 计算除去x H 后的形心x F 3 按终止准则判断是否已达到精度要求 若已达到 停止计算 否则转4 4 求反射点x R 5 将fR与fL fG和fH作比较 1 若fR fL 反射成功 进行扩张 扩张点x E 若fE fL 扩张成功 令x H x E 转向2否则 扩张失败 令x H x R 转向2 2 若fL fR fG 反射成功 但改进不大 不进行扩张 x H x R 转向2 3 若fG fR
4、 fH 反射不太成功 在x F 与x R 之间压缩 4 若fR fH 反射失败 在x H 与x F 之间压缩 6 若fS fH 压缩成功 令x H x S 转向2否则 进行收缩 几点说明 1 关于初始步长h的选取 一般可取0 5 h 15 1 开始取h为1 6 2 2 进行到发现fH fL已很小 但尚未达到精度 这时取x 0 x L 重新开始 并取步长为 当离精度要求已不远时 h 0 5 1 当离精度要求还很远时 h 2 2 终止准则P109 3 扩张因子r 1 2 2 例5 1 1用单纯形搜索法求解minf x 60 10 x1 4x2 x12 x22 x1x2设x 0 0 0 T e 1
5、1 0 T e 2 0 1 T 取h 2 0 5 2 1 终止准则为 fH fL fL 0 001 5 1 3Powell共轭方向法 方向加速法 1964年由Powell提出 后经Zangwoll 1967年 和Brent 1973年 改进 是迄今为止最有效的直接搜索法 该算法有效地利用了迭代过程中的历史信息 建立起能加速收敛的方向 有理论基础 以二次对称函数f x c bTx 1 2xTAx为模型进行研究 为什么选择二次函数作为模型 1 在非线性目标函数中 最简单的是二次函数 故任何对一般函数有效的方法首先应对二次函数有效 2 在最优点附近 非线性函数可用一个二次函数作近似 故对二次函数使用
6、良好的方法 通常对一般函数也有效 3 很多实际问题的目标函数是二次函数 一 共轭方向 设A是n n阶对称正定矩阵 p 0 p 1 为两个n维向量 若成立p 0 TAp 1 0则称向量p 0 与p 1 为A共轭或A正交 称该两向量的方向为A共轭方向 若A I 单位矩阵 p 0 Tp 1 0 即p 0 与p 1 是正交的 共轭 是 正交 概念的推广 p 0 p 1 cos 例 共轭方向有什么用 二 共轭方向法的基本定理 定理5 1 1 设A为n n阶对称正定矩阵 p 0 p 1 p n 1 为n个相互A共轭的n维非零向量 即p i 0 i 0 1 n 1 且p i TAp j 0 i j 则此向量
7、系必线性无关 推论 在n维空间中 互相共轭的非零向量的个数不超过n个 定理5 1 2 若p 0 p 1 p n 1 是n个非零的A共轭向量 则二次目标函数f x c bTx 1 2xTAx的最优点x 为 可得到非二次函数最优点的一个近似点 其中A是Hesse矩阵 上式用于非二次函数 可否得到最优点 定理5 1 3 设A为n阶对称正定矩阵 对于二次目标函数f x c bTx 1 2xTAx 从任意初始点x 0 出发 逐次进行一维搜索 即minf x i tp i f x i tip i i 0若搜索方向p 0 p 1 p n 1 是非零的A共轭向量 则至多进行n次迭代必可得到极小点x 即有x i
8、 1 x i tip i i 0 1 n 1x x k 0 k n 上述搜索方法具有二次收敛性 对非二次函数 采用上述方法 n次迭代是否也可得到极小点 如何简便地找出n个A共轭的向量 定理5 1 4 假设1 n元函数f x c bTx 1 2xTAx中的矩阵A是对称正定的 2 向量p 0 p 1 p m 1 m n 是互相A共轭的 3 x 0 x 1 是不同的任意两点 分别从x 0 x 1 出发 依次沿p 0 p 1 p m 1 作一维精确搜索 设最后一次一维搜索的极小点分别为x 0 和x 1 那么 向量p x 0 x 1 与p 0 p 1 p m 1 互为A共轭 已知前m个共轭方向 就可以找
9、到第m 1个共轭方向 三 Powell共轭方向法的基本思想 一边搜索 一边找共轭方向 共分n个阶段 每一阶段都进行n 1次搜索 最后产生一个共轭方向 二维空间中的Powell方法示意 以二次函数f x1 x2 为例 对于二次函数 x 即为极小点 四 Powell方法的原始算法 开始 几点说明 1 迭代中逐次产生的是共轭方向 是较好的搜索方向 所以Powell法又称方向加速法 2 原始算法仅有理论意义 因为只有在每次搜索均为一维完全精确搜索的条件下 每个阶段产生的方向才是相互共轭的方向 但实际一维搜索都是近似的 产生的方向不一定共轭 有时甚至是线性相关的 导致搜索空间降维 这时将找不到真正的极小
10、点 对于一般函数 n个阶段迭代后一般得不到极小点 但由于共轭方向的个数只有n个 如果继续按上述方法迭代 产生的方向就不再是相互共轭方向了 收敛速度会变慢 五 原始算法一种简便改进 重新开始 每进行n个阶段的迭代 或当收敛速度变慢时 以当前点为起点 回到第一步重新开始 六 改进的Powell算法 1 基本思想 为克服搜索方向的线性相关问题 Powell对原始算法进行了改进 如何判定方向组是 最相互共轭 的 定理5 1 5设A是n阶对称正定矩阵 方向组p 0 p 1 p n 1 按下式意义是规范化的 p i TAp i 1 i 0 1 n 1 置Q p 0 p 1 p n 1 则方向组p 0 p
11、1 p n 1 相互A共轭的充要条件为 行列式 Q 的值达到它的最大值 改进Powell算法的理论基础 在每个阶段产生新的方向p后 更换方向组的方法不是一律去掉第一个方向p 0 而是有选择地去掉某个方向p J 原则是使新的方向组 最相互共轭 5 2梯度法 直接搜索法收敛速度一般比较慢 需要计算大量的函数值 梯度反映了函数值变化的规律 充分利用梯度信息构造算法 能加速收敛 使用函数的梯度 一阶导数 或Hesse矩阵 二阶导数 的优化算法称为梯度法 目标 求出平稳点 满足 f x 0的x 由于 f x 0一般是非线性方程组 解析法往往行不通 所以梯度法通常也是逐次逼近的迭代法 假定 f x 和 2
12、f x 连续存在 5 2 1最速下降法 Cauchy法 1847年Cauchy提出 特点是直观易懂 但收敛速度慢 一 基本思想 x k 1 x k tkp k 瞎子下山 由于他看不到哪里是山谷 不可能沿直接指向山谷的路线走 他只能在当前位置上 靠手杖作局部探索 哪里最陡就往哪里前进一步 然后在新的位置上再用手杖寻找最陡方向 再下降一步 这就是最速下降法的形象比喻 多变量最优化迭代解法的一般迭代公式 迭代公式x k 1 x k tk f x k 二 算法 开始 两维情形下最速下降法搜索路径 三 最速下降法的搜索路径呈直角锯齿形 tk 1 优点 计算简单 需记忆的容量小 对初始点要求低 稳定性高
13、远离极小点时收敛快 常作为其它方法的第一步 2 缺点 收敛速度较慢 线性或不高于线性 原因是最速下降方向只有在该点附近有意义 尤其当目标函数等值面是很扁的椭圆 椭球或类似图形时 收敛更慢 例5 2 1用最速下降法求函数f x1 x2 x12 4x22的极小点 迭代两次 并验证相邻两个搜索方向是正交的 初始点取为x 0 1 1 T 解 梯度 f x 2x1 8x2 T 1 第一次迭代 f x 0 2 8 T x 1 x 0 t0p 0 x 0 t0 f x 0 1 1 T t0 2 8 T 用一维搜索求t0 对简单f x 可用解析法求解 设 0 t f x 1 f 1 1 T t 2 8 T 1
14、 2t 2 4 1 8t 2 0 t 520t 68 0t0 0 130769 x 1 0 738462 0 046152 T 2 第二次迭代 f x 1 1 476924 0 369216 T 1 t f x 2 0 738462 1 476924t 2 4 0 046152 0 369216t 2 1 t 2 317625t 5 453173t 0t1 0 45005 x 2 0 110762 0 110767 T f x 2 0 221524 0 886136 T 3 验证相邻两个搜索方向是正交的 f x 0 T f x 1 2 8 1 476924 0 369216 T 0 00012
15、 0 f x 1 T f x 2 1 476924 0 369216 0 221524 0 886136 T 0 000001 0 5 2 2Newton法 二阶方法 由最速下降法可知 从全局角度来看 负梯度方向一般不是一个特别好的方向 有没有更好的方向 f x 在x k 处的二次近似函数 一 基本Newton法 取f x x k 的平稳点作为f x 最优点的一个近似点 f x x k f x k 2f x k x 0 x x k x 2f x k 1 f x k Newton迭代公式 x k 1 x k 2f x k 1 f x k 或x k 1 x k H x k 1g x k 当f x
16、是二次函数时 一次迭代就可达到平稳点 当f x 是单变量函数时 本方法即为Newton Raphson法 基本Newton法的算法 开始 例5 2 2用基本Newton法求函数f x1 x2 8x12 4x1x2 5x22的极小点 初始点取为x 0 10 10 T 解 f x 16x1 4x2 4x1 10 x2 T x 1 x 0 H x 0 1 f x 0 因为f x 是二次函数 所以一步迭代就达到平稳点 又因为H x 1 是正定矩阵 所以x 1 是极小点 说明 1 基本Newton法要求Hesse矩阵具有逆矩阵 如果H x k 是正定的 则H x k 1必存在 从而算法是可行的 并且保证求得的平稳点是极小点 然而在迭代过程中要求H x k 是正定的这一条件不一定能保证 只有当初始点合适时才能满足 一般在极小点附近的Hesse矩阵容易为正定的 所以基本Newton法在极小点附近才比较有效 2 Newton法的搜索方向 H x 1 f x 不一定是下降方向 因为若是下降方向 则应有 f x T H x 1 f x 0 但由于H x 1不一定是正定的 所以上式不一定成立 3 Newto
