运筹学与最优化方法第4章.ppt

第四章 最优化搜索算法的结构与一维搜索 4 1常用的搜索算法结构 一 收敛性概念 考虑 fs 设迭代算法产生点列 x k S 1 理想的收敛性 设x S是g opt 当x x k 或x k x k 满足时 称算法收敛到最优解x 4 1常用的搜索算法结构 由于非线性规划问题的复杂性 实用中建立下列收敛性概念 2 实用收敛性 定义解集S x x具有某种性质 例 S x x g opt S x x l opt S x f x 0 S x f x 为给定的实数 称为阈值 4 1常用的搜索算法结构 一 收敛性概念 考虑 fs 2 实用收敛性 续 收敛性 设解集S x k 为算法产生的点列 下列情况之一成立时 称算法收敛 1 x k S 2 x k S k X k 任意极限点 S 全局收敛 对任意初始点x 1 算法均收敛 局部收敛 当x 1 充分接近解x 时 算法才收敛 4 1常用的搜索算法结构 二 收敛速度设算法产生点列 x k 收敛到解x 且x k x k 1 线性收敛 当k充分大时成立 2 超线性收敛 3 二阶收敛 0 是使当k充分大时有 4 1常用的搜索算法结构 二 收敛速度 续 定理 设算法点列 x k 超线性收敛于x 且x k x k 那么证明只需注意 x k 1 x x k x x k 1 x k x k 1 x x k x 除以 x k x 并令k 利用超线性收敛定义可得结果 4 1常用的搜索算法结构 三 二次终结性 一个算法用于解正定二次函数的无约束极小时 有限步迭代可达最优解 则称该算法具有二次终结性 二次终结性 共轭方向 精确一维搜索 共轭方向 定义 设An n对称正定 d 1 d 2 Rn d 1 0 d 2 0 满足d 1 TAd 2 0 称d 1 d 2 关于矩阵A共轭 共轭向量组 d 1 d 2 d m Rn均非零 满足d i TAd j 0 i j 4 1常用的搜索算法结构 三 二次终结性 续 当A I 单位矩阵 时 d 1 TAd 2 d 1 Td 2 0 即正交关系 当d 1 d 2 d m 关于正定矩阵A两两共轭时 d 1 d 2 d m 线性无关 proof 设d 1d 1 2d 2 md m 0 j 1 2 m d j TAd jd j TAd j 0 d j TAd j 0 故 j 0 即线性无关 超线性收敛和二次终结性常用来讨论算法的优点 4 1常用的搜索算法结构 四 下降算法模型考虑 fs 常用一种线性搜索的方式来求解 迭代中从一点出发沿下降可行方向找一个新的 性质有改善的点 下降方向 设 S d Rn d 0 若存在 使 称d为在点的下降方向 4 1常用的搜索算法结构 四 下降算法模型 续 可行方向 设 S d Rn d 0 若存在 使 称d为点的可行方向 同时满足上述两个性质的方向称下降可行方向 4 1常用的搜索算法结构 模型算法 线性搜索求 新点使x k 1 S yes no 4 2一维搜索 一元函数求极小及线性搜索均为一维搜索 常用于求 minf x k d k s t SS有3种情况 或 0 或 a b 一 缩小区间的精确一维搜索 考虑问题 P min s t R R1 不确定区间及单峰函数 不确定区间 含 的最小点 但不知其位置 4 2一维搜索 一 缩小区间的精确一维搜索 续 定义 设 R 是 在 上的最小点 若对任意 1 2 1 2 2 若 1 则 1 2 则称 在 上强单峰 若只有当 1 2 时 上述1 2 式才成立 则称 在 上单峰 4 2一维搜索 一 缩小区间的精确一维搜索 续 若对任意 1 2 1 2 2 若 1 则 1 2 则称 在 上强单峰 若只有当 1 2 时 上述1 2 式才成立 则称 在 上单峰 4 2一维搜索 一 缩小区间的精确一维搜索 续 定理 设 R R在 上单峰 那么1 若 则 如左下图2 若 则 如右下图 4 2一维搜索 一 缩小区间的精确一维搜索 续 Proof 1 反证 设 为最小点 及 使 矛盾 假设 若 由定义及 矛盾 条件 于是结论成立 2 的证明类似 略 注 上述定理为缩短区间的算法提供了理论根据 4 2一维搜索 一 缩小区间的精确一维搜索 续 2 黄金分割法 0 618法 通过上述定理 选二点 比较 与 可去掉 或者 考虑条件 1 对称 使 坏 的情况去掉 区间长度不小于 好 的情况 2 保持缩减比t 保留的区间长度 原区间长度 不变 使每次保留下来的节点 或 在下一次的比较中成为一个相应比例位置的节点 推导缩减比t 如图设第一次保留 去掉 那么第二次保留的长度为 则 4 2一维搜索 一 缩小区间的精确一维搜索2 黄金分割法 0 618法 续 整理 t t 结合 式 t2 t 1 0故t 0 618注意上式有t2 1 t 故有 t 1 t 算法框图见下页 4 2一维搜索 一 缩小区间的精确一维搜索之黄金分割法 0 618法 算法 4 2一维搜索 3 中点法 设 在 上可微 且当导数为零时是解 取 2 那么 0时 为最小点 0时 在上升段 去掉 自己画算法框图 4 2一维搜索 4 进退法求初始不确定区间找三点使两端点的函数值大于中间点的函数值 思路 任取 0 步长 0 取 1 0 1 若 0 0 则停 2 1 图1 2 若 0 1 令 2 2 1 若 2 1 则停 0 2 图2 4 2一维搜索 4 进退法求初始不确定区间 续 自己画算法框图 注意 1 选择要适当 太大含多个单峰区间 太小迭代次数增加 2 单调时无结果 加迭代次数限制 3 可与中点法结合寻找单调区间 思考 4 2一维搜索 二 牛顿法 Newton 和插值法1 Newton法 对 在 k点展开 k k k 1 2 k k 2 o k 2取二次式 略去高阶项 qk k k k 1 2 k k 2 4 2一维搜索 二 牛顿法 Newton 和插值法1 Newton法 续 用qk 作为 的近似 当 k 0时 其驻点为极小点 q k k k k 0得 k 1 k k k 取 k 1为新的迭代点 以上过程即Newton法 特点 二阶 局部收敛 算法框图见下页 4 2一维搜索 Newton法算法框图 4 2一维搜索 二 牛顿法 Newton 和插值法1 Newton法 续 Ex 求min arctantdt解 arctan 1 1 2 迭代公式 k 1 k 1 2 arctan k取 1 1 计算结果 k k k 1 k 110 785422 0 5708 0 51871 325830 1169 0 11641 01374 0 001095 0 001095 4 0取 1 2 计算结果如下 4 2一维搜索 二 牛顿法 Newton 和插值法1 Newton法 续 k k k 1 k 121 107152 3 5357 1 295213 50313 95不收敛 2 插值法 用 在2或3个点的函数值或导数值 构造2次或3次多项式作为 的近似值 以这多项式的极小点为新的迭代点 3点2次 2点2次 4点3次 3点3次 2点3次等以3点2次为例 取 1 2 3 求出 1 2 3 4 2一维搜索 二 牛顿法 Newton 和插值法2 插值法 续 设二次插值多项式 a 2 b c a 12 b 1 c 1 a 22 b 2 c 2 a 32 b 3 c 3 解得a b 4 2一维搜索 三 不精确一维搜索 minf x 考虑从x k 点出发 沿方向d k 寻找新迭代点 x k kd k 要求 1 f x k kd k 0不能太小 总体希望收敛快 每一步不要求达到精确最小 速度快 虽然步数增加 则整个收敛达到快速 一个实用方法 为了方便 省去上标 设f Rn R 在x取方向d 有 fT x d 0 即d为下降方向 求 使1 f x