数值解单变量最优化ppt课件.ppt

4 5 2无约束最优化问题的数值解法4 5 2 1单变量最优化问题的数值解法 一维搜索 一 消去法的基本概念1消去法的基本思想利用单峰函数在可行域内只有一个极值点的特点 设法逐步缩小搜索最优点的区间 直至找到最优点 并达到允许的精度为止 消去法分为 1 同时消去法 同时计算一批点的函数值 然后比较各函数值的大小 再消去一部分区间 直至达到精度要求 序贯消去法 从第二个点起 每计算一个点的函数值 就与前一个点的函数值进行比较 消去部分区间后再安排下一个计算点 如此序贯进行 直至达到精度要求 2 2序贯法缩小搜索区间设 一元函数y x 在区间 a0 b0 内为单峰函数 若首先在 a0 b0 内任取两点x1 x2 x1 x2 并计算函数值y x1 y x2 这时可能的三种情况为 3 1 y x1 y x2 则x 在 a0 x2 之内 4 2 y x1 y x2 则x 在 x1 b0 之内 5 3 y x1 y x2 则x 在 x1 x2 之内 6 根据上面分析 可将搜索区间缩小 在余下的区间内继续选择新点 比较新点的函数值 直至区间缩小到精度要求 找到最优点 7 3不定区间 当进行n次函数值的计算与比较后 可以得出这n个函数值中的最小值 f xm 及最小点xm以及其左右的邻点xk xr 而真正的最小点x 必落在xr与xk之内 将xr与xk之间的区间称为不定区间ln 且ln xr xk 8 不定区间的影响因素 与计算次数n有关 l0 b0 a0一定时 n ln 与计算点的分布方式有关 即与xi的确定方法有关显然 ln越小 则xm与x 越接近 用xm近似x 越可靠 即精度越高 ln xr xk 9 4区间缩短率n次函数值的计算与比较后 不定区间与原始区间的比值 当l0一定时 En ln 相同计算次数下 En越小的方案越好 10 二对无约束函数的搜索 求单峰所在区间的进退算法 消去法的应用基础是目标函数f x 在 a0 b0 内为单峰函数 问题 1 怎样确定f x 为单峰函数 2 怎样确定f x 的单峰所在区间 a0 b0 一般采用进退算法解决这两个问题 11 1 进退算法的基本思想 由单峰函数的性质可知 对于存在极小值的单峰函数 在极小点左边 函数值严格下降 而在极小点右边 函数值应严格上升 12 据此 可以从某个给定的初始点出发 沿着函数值下降的方向逐步前进 或后退 直至发现函数值开始上升为止 由两边高中间低的三点函数值 就可以确定极小值所在的初始区间 a0 b0 13 2 进退算法 1 选定初始点a0与步长h 2 计算并比较y a0 和y a0 h 根据比较结果有前进和后退两种可能 前进计算 后退运算 14 前进计算 若y a0 y a0 h 则步长加倍 计算y a0 3h 若y a0 h y a0 3h 则令a0 a0 b0 a0 3h 15 若y a0 h y a0 3h 令a0 a0 h h 2h 重复上述前进运算 16 后退运算 若y a0 y a0 h 则后退计算y a0 h 若y a0 h y a0 则令a0 a0 h b0 a0 h 停止运算 否则继续后退 17 例 求函数的极小所在区间初始点a0 1 步长h 1解 h a0 1 18 所以应后退 19 应继续后退 后退时步长加倍 所以计算 后