第四章一维搜索法

第四章 一维搜索法 由第一章关于求解最优化问题概述中我们知道 从已知迭代点 n k RX 出发按照基本 迭代公式 kkkk PtXX 1 来求解最优化问题 其关键在于如何构造一个搜索方向 n k RP 和确定一个步长 1 Rtk 使下一迭代点 1 k X处的目标函数值下降 即 1kk XfXf 现在我们来讨论 当搜索方向 k P已经确定的情况下 如何来确定步长 k t 步长因子的选取有多种方法 如取步长为常数 但这样选取的步长并不最好 如何选 取最好步长呢 实际计算通常采用一维搜索来确定最优步长 对无约束最优化问题 minXf n RX 当已知迭代点 k X和下降方向 k P时 要确定适当的步长 k t使 1k Xf kkk PtXf 比 k Xf有所下降 即相当于对于参变量t的函数 kk tPXft 要在区间 0 上选取 k tt 使 1kk XfXf 即 0 kkkkk XfPtXft 由于这种从已知点 k X出发 沿某一下降的探索方向 k P来确定步长 k t的问题 实质上是单 变量函数 t 关于变量t的一维搜索选取问题 故通常叫做一维搜索 按这种方法确定的 步长 k t又称为最优步长 这种方法的优点是 它使目标函数值在搜索方向上下降得最多 今后为了简便起见 我们用记号 1kkk PXlsX 4 1 表示从点 k X出发沿 k P方向对目标函数 Xf作直线搜索所得到的极小点是 1 k X 其中 l和s分别是 Linear search 直线搜索 两词的词首 在目标函数 Xf已确定的条件下 4 1 等价于如下两式 kkkk t kk t kkk PtXX ttPXfPtXf 1 min min 下面进一步解释迭代点 kkkk PtXX 1 的空间位置 容易证明 若从 k X出发 沿 k P方向进行一维搜索得极小点 kkkk PtXX 1 则该点 1 k XX处的梯度方向 1 k Xf与搜索方向 k P之间应满足 0 1 k T k PXf 4 2 事实上 设 kk tPXft 对t求导有 k T kk PtPXft 令0 t 即0 k T kk PtPXf 所以0 1 k T k PXf 式 4 2 的几何意义是明显的 从某一点 k X出发沿 k P方向对目标函数 Xf作直线 搜索 所得到的极小点为 1 k X 式 4 2 指出 梯度 1 k Xf必与搜索方向 k P正交 又 因为 1 k Xf与目标函数过点 1 k X的等值面 1 k XfXf正交 所以进一步看到 搜 索方向 k P与这个等值面在点 1 k X处相切 如图 4 1 所示 4 1 搜索区间及其确定方法 一 搜索区间 设一维最优化问题为 min max 0 t tt 4 3 为了求解问题 4 3 我们引入如下的搜索区间概念 定义 4 1 设 0 0 max 11 tttRR 并且 min max 0 tt tt 若存在闭区间 0 0 max tbaba 使 bat 则称 ba 是问题 4 3 的搜索区间 简言之 一个一维最优化问题的搜索区间 就是包含该问题最优解的一个闭区间 通 常 在进行一维搜索时 一般要先确定出问题的一个搜索区间 然后在此区间中进行搜索 求解 二 加步探索法 下面 介绍一个确定问题 4 3 的搜索区间的简单方法 这个方法的思想是 先选定一 个初始点 0 0 max00 ttt 或 和初始步长 0 0 h 然后 沿着t轴的正方向探 索前进一个步长 得到新点 00 ht 若目标函数在新点处的值是下降了 即 000 tht 则下一步就从新点 00 ht 出发加大步长 再向前探索 若目标函数在新点处的 函数值上升 即 000 tht 则下一步仍以0 t 为出发点以原步长开始向t轴的负方向同样探索 当达到目标函数上升的 点时 就停止探索 这时便得到问题 4 3 的一个搜索区间 这种以加大步长进行探索来 寻找探索区间的方法叫做加步探索法 加步探索法算法的计算步骤 1 选取初始数据 选取初始点 0 0 max00 ttt 或 计 算 00 t 给出初始步长 0 0 h 加步系数 1 令 0 k 2 比较目标函数值 令 kkk htt 1 计算 11 kk t 若 kk 1 转 3 否则转 4 3 加大探索步长 令 kk hh 1 同时 令k tt 1 kk tt 1kk 1kk 转 2 4 反向探索 若 0 k 转换探索方向 令 1 kkk tthh 转 2 否则 停 止迭代 令 图 4 1 11 min max kk at tbt t 输出 ba 加步探索法算法的流程图如图 4 2 所示 在加步探索法中 一般建议 2 若能估计问题 4 3 的最优解的大体位置的话 初始点0 t 要尽量取接近于问题 4 3 的最优解 在具体运用上述加步探索法时 有时还要 考虑一些细节问题 例如 当探索得到新点处的目标函数值和出发点处相同时 以及初始 步长应如何选取等 都需作适当处理 三 单谷区间与单谷函数 由于以后要介绍的一些维搜索方法 主要适用于问题 4 3 在搜索区间中只有唯一的 最优解的情况 为此 我们再给出下面单谷区间与单谷函数概念 定义 4 2 设 11 RR 闭区间 1 Rba 若存在点 bat 使得 t 在 ta 上严格递减 t 在 bt 上严格递增 则称 ba 是函数 t 的单谷区间 t 是 ba 上单谷函数 开始 选取初始点 t0 初始步长 h0 0 加步系数 1 令 k 0 0 t0 比较目标函数值 tk 1 tk hk k 1 tk 1 a min t tk 1 b max t tk 1 结束 N Y N Y k 1 k hk 1 hk t tk tk tk 1 k k 1 k k 1 k 0 hk hk k k 1 图 4 2 由定义 4 2 易知 一个区间是某函数的单谷区间意味着 在该区间中函数只有一个 凹谷 极小值 例如 图 4 3 中的 ba 是 t 的单谷区间 也即 t 是 ba 上的 单谷函数 图 4 4 中的 ba 不是 t 的单谷区间 即 t 不是 ba 上的单谷函数 另外 从定义 4 2 还可知 某区间上的单谷函数在该区间上不一定是连续函数 而凸 函数在所给区间上必然是单谷函数 如图 4 3 所示 由定义 4 1 和定义 4 2 知 函数 t 的单谷区间总是相应问题 4 3 的一个搜索区间 如图 4 3 所示 但反之不然 如图 4 4 所示 图 4 3 图 4 4 单谷区间和单谷函数有如下有用的性质 定理 4 1 设 11 baRR 是 t 的单谷区间 任取 21 batt 并且 12 tt 1 若有 12 tt 则 1 ta 是 t 的单谷区间 2 若有 12 tt 则 2 bt 是 t 的单谷区间 证明略 定理 4 1 说明 经过函数值的比较可以把单谷区间缩短为一个较小的单谷区间 换句 话说 利用这个定理可以把搜索区间无限缩小 从而求出极小点 以下介绍的几种 一维 搜索方法都是利用这个定理通过不断地缩短搜索区间的长度 来求得一维最优化问题的近 似最优解 4 2 对分法 一 对分法基本原理 求解一维最优化问题min t 一般可先确定它的一个有限搜索区间 ba 把问题化为 求解问题 mint bta 然后通过不断缩短区间 ba 的长度 最后求得最优解 设 11 RR 在已获得的搜索区间 ba 内具有连续的一阶导数 因为 t 在 ba 上可微 故 t 在 ba 上连续 由此知 t 在 ba 上有最小值 令 0 t 总可求得极小点 t 不妨设 t 在 ta 上是单减函数 在 bt 上是 单增函数 所以 tat 时 0 t 故 0 a 当 btt 时 0 t 亦即 0 b 对分法的原理如图 4 5 所示 二 对分法迭代步骤 已知 t t 表达式 终止限 1 确定初始搜索区间 ba 要求 0 0ab 2 计算 ba 的中点 2 1 bac 3 若 0 c 则 ca 转 4 若 0 c 则 图 4 5 ct 转 5 若 0 c 则 cb 转 4 4 若 ba 则 2 1 bat 转 5 否则转 2 5 打印 t 结束 对分法的计算流程如图 4 6 所示 三 对分法有关说明 对分法每次迭代都取区间的中点 若这点的导数值小于零 说明 0 t 的根位于右 半区间中 如图 4 5 所示 因此去掉左半区间 若中点导数值大于零 则去掉右半区间 若中点导数值正好等于零 则该点就是极小点 因为每次迭代都使原区间缩短一半 所以 称为对分法或二分法 Y 开始 确定 a b 要 求 0 0ab c a b 2 b c t a b 2 输出 t 结束 t c N a c N 0c 0c Y N 0c 0c Y ab 图 4 6 4 3 Newton 切线法 一 Newton 切线法基本原理 设 11 RR 在已获得的搜索区间 ba 内具有连续二阶导数 求 mint bta 因为 t 在 ba 上可微 故 t 在 ba 上有最小值 令 0 t 下面不妨设在区间 ba 中经过k次迭代已求得方程 0 t 的一个近似根k t 过 kk tt 作曲线 ty 的切线 其方程是 kkk tttty 4 4 然后用这条切线与横轴交点的横坐标 1 k t 作为根的新的近似 如图 4 7 所示 它可由方程 4 4 在令 0 y 的解出来 即 1 k k kk t t tt 这就是 Newton 切线法迭代公式 二 Newton 切线法迭代步骤 已知 t t 表达式 终止限 1 确定初始搜索区间 ba 要求 0 0ab 2 选定 0 t 3 计算 000 tttt 4 若 0 tt 则 tt 0 转 3 否则转 5 5 打印 tt 结束 Newton 切线法的计算流程如图 4 8 所示 三 Newton 切线法有关说明 这种方法如果初始点选得适当 收敛 速度很快 通常经过几次迭代就可以得到 满足一般精度要求的结果 但是它也有缺 点 第一 需要求二阶导数 如果在多维 最优化问题的一维搜索中使用这种方法 就要涉及 Hesse 矩阵 一般是难于求出 的 第二 当曲线 ty 在 ba 上有较 复杂的弯曲时 这种方法也往往失效 如 图 4 9 所示的迭代 210 ttt 结果 2 t 跳出 ba 迭代或 者发散 或者找到的根并不是我们想要的 结果 第三 即使曲线比较正常 在 ba 中或者上凹或者下凹 初始点的选取 也必须适当 在图 4 10 a 的情况下 曲 线上凹 应选点 b 作为初始点 而在图 4 10 b 的情况下 曲线下凹 应选点 a 为初始点 否则都可能失败 图 4 7 000 tttt 输出 t 开始 结束 0 tt Y N 0 tt 00 ttt 选定 t0 确定 a b 要 求 0 0ab 图 4 9 图 4 8 图 4 10 4 4 黄金分割法 一 黄金分割法基本原理 要介绍黄金分割法有必要回顾一下古老的黄金分割问题 所谓黄金分割就是将一线段 分为二段时 要求整段长 L 与较长段 x 的比值正好等于较长段 x 与较短段 xL 的比值 如 图 4 11 所示 即 xL x x L 于是有 0 22 LLxx 解出其正根 LLx618 0 2 15 由此可见长段的长度应为全长的 0 618 倍 而短段的长度应为全长的 0 382 倍 因为古代的 人们认为按 0 618 的比率来分割线段是最协调 胜似黄金 故称之为黄金分割 图 4 11 用黄金分割法进行一维搜索 其基本思想是在单谷区间 ba 内适当插入两点21 tt 由此把区间 ba 分为三段 然后再通过比较这两点函数值大小 就可以确定是删去最左 段还是最右段 或者同时删去左右两段保留中间段 如此继续下去可将单谷区间无限缩 小 二 黄金分割法迭代步骤 现在提出一个问题 就在 ba 上如何选取二点21 tt 使得迭代次数最小而区间缩短最 快 要解决这个问题 人们想到对区间 ba 选二点21 tt 等价于将区间长度 ab 进行黄金 分割 也就是将第一个搜索点1 t 取在 ba 的 0 618 处 第二个搜索点2 t 取成1 t 的对称点即 ba 的 0 382 处 如图 4 12 所示 亦即 618 0 1 abat 382 0 2 abat 计算 1 t 与 2 t 的值 并根据 1 t 与 2 t 的值的大小关系分情况讨论 1 若 21 tt 说明1 t 是好点 于是把区间 2 ta 划掉 保留 2 bt 则 2 bt 内有一保留点1 t 置新的区间 211 btba 2 若 21 tt 说明2 t 是好点 于是应将 1 bt 划掉 保留 1 ta 则 1 ta 内有保留点2 t 置新的区间 111 taba 3 若 21 tt 则应具体分析 看极小点可能在哪一边再决定取舍 在一般情 况下 可同时划掉 2 ta 和 1 bt 仅保留中间的 12 tt 置新的区 间 1211 ttba 接下来是在留下的区间 11 ba 内找好点 重复上 面的步骤 直到搜索区间 ii ba 小于给定的允许误差 0 为止 这样就得到黄金分割法迭代算法 已知 t 常数 0 382 终止限 1 确定 t 的初始搜索区间 ba 2 计算 222 tabat 3 计算1 211 tabtt 4 若 21 tt 则打印 2 21 tt t 结束 否 则转 5 5 判别是否满足 21 若满足 则置 12122 ttta 然后转 3 否则 置 22221211 tabttttb 然后转 4 黄金分割法算法流程如图 4 13 所示 三 黄金分割法有关说明 黄金分割法是通过所选试点的函数值而逐步缩短单谷区间来搜索最优点 t 该方法适 用于单谷区间 ba 上的任何函数 甚至可以是不连续函数 因此这种算法属于直接法 适 用相当广泛 图 4 12 4 5 抛物线插值法 一 抛物线插值法基本原理 考虑一维搜索问题 min 21 t ttt 假设其中 t 是定义在区间 21 tt 上的单谷函数 首先用试探法在 21 tt 上找一点0 t 使 之满足 0201 tttt 通过目标函数曲线上的三个点 220011 tttttt 作它的二次拟合曲线 如 图 4 14 所示 2 210 tataatP t 开始 确定 a b 51 2 2 tba 22 12 tabt 11 t 2 21 2 bt tt 12 2ttt t 结束 N Y N Y 12 tt 11212 attt 222 tbat 12 图 4 13 图 4 14 由于上述三个点既是目标函数曲线 t 上的点 又是二次拟合曲线 tP 上的点 故有 方程组 2 2 222102 0 2 020100 1 2 121101 ttataatP ttataatP ttataatP 4 5 将方程组 4 5 中的0 a 消去 得 22 11021010 22 10220202 a tta tttt a tta tttt 4 6 从方程组 4 6 可解出待定系数 122001 2 2 0 2 10 2 1 2 21 2 2 2 0 1 tttttt ttttttttt a 4 7 122001 201012120 2 tttttt ttttttttt a 4 8 对于二次拟合函数 2 210 tataatP 我们很容易求得它的极小值点 令 0 dt tdP 即 02 21 taa 从中解出 2 1 2a a t 4 9 即为二次拟合函数 tP 的极小值点 将式 4 7 与式 4 8 代入式 4 9 得 2 1 2 201012120 2 2 0 2 10 2 1 2 21 2 2 2 0 2 1 ttttttttt ttttttttt a a t 4 10 用区间 21 tt 上二次拟合函数 tP 的这个极小值点t作为目标函数 t 在该区间极小值点 的一个估计值 若t和0 t 已充分接近 即对给定的允许误差 0 使 0 tt 4 11 成立时 t就可被看作是 t 在区间 21 tt 内近似最优解 否则应缩短区间 按照 t 值 保持两头大 中间小的原则构成新的三点 继续上述过程 直至不等式 4 11 成立为 止 二 抛物线插值法迭代步骤 下面具体介绍一下缩短区间 构成新三点的方法 由式 4 15 得到的点t 在区间 21 tt 内既可能在点0 t 的左侧 即 0 tt 又可能在 0 t 的右侧 即 0 tt 分别对应这两种情形比较 t 和 0 t 的大小 又有