第三章一维搜索线性搜索.ppt

第三章 一维搜索方法
概述
确定初始区间
缩小区间
黄金分割法（）
一维搜索的插值方法
第三章一维搜索线性搜索
第3章 一维搜索方法
概述
一维问题是多维问题的基础
求目标函数 f (X)的极小点，从理论上说需要求解方程：
其中
那么如何来求 f (X)的极小点呢？
基本思想:
这种方法是逐次迭代的方法，在电子计算机上很容易实现，因此它在优化设计中被广泛地采用。
第三章一维搜索线性搜索
2
这个过程称为一维搜索过程。
如：
则
当
Sk方向上的任何一点可以表示为
其中α是步长因子，为实系数，此时 Sk 方向上任何一点的目标函数值
为 ，它是参数α的一元函数。那么在沿 Sk 方向求
的极小点，这就是求一元函数 的极小问题，它可表示为：
第三章一维搜索线性搜索
3
一维搜索示意图
第三章一维搜索线性搜索
求多元函数极值点，需要进行一系列的一维搜索。可见一维搜索是优化搜索方法的基础。
求解一元函数 的极小点 ，可采用解析解法，即利用一元函数的极值条件 求
在用函数 的导数求 时，所用的函数 是仅以步长因子 为变量的一元函数，而不是以设计点 x 为变量的多元函数 。
的确定方法
为了直接利用 的函数式求解最佳步长因子 。
把 或它的简写形式 进行泰勒展开，
取到二阶项，即
将上式对 进行微分并令其等于零，给出
极值点 应满足的条件
从而求得
第三章一维搜索线性搜索
这里是直接利用函数 而不需要把它化成步长因
子 。的函数 。不过，此时需要计算 点处
梯度 和海赛矩阵 H 。
解析解法的缺点——需要进行求导计算。
对于函数关系复杂、求导困难或无法求导的情况，使用解析法将是非常不便的。
因此，在优化设计中，求解最佳步长因子 主要采用数值解法，利用计算机通过反复迭代计算求得最佳步长因子的近似值。
数值解法的基本思路是：首先确定 所在的搜索区间，然后根据区间消去法原理不断缩小此区间，从而获得 的数 值近似解。
第三章一维搜索线性搜索
解析法:
① f(X(k) + αS(k) ) 沿S(k) 方向在x(k) 点泰勒展开；
② 取二次近似：
对α求导，令其为零。
④ 求得最优步长
第三章一维搜索线性搜索
数值解法基本思路：
解析解法对于函数关系复杂、求导困难等情况难以实现。在实际优化设计中，数值解法的应用更为有效，且适合计算机的运算特点。
一维搜索也称直线搜索。这种方法不仅对于解决一维最优化问题具有实际意义，而且也是求解多维最优化问题的重要支柱。
一维搜索一般分为两大步骤：
(1)确定初始搜索区间[a，b]，该区间应是包括一维函数极小点在内的单谷区间。
(2)在单谷区间[a,b]内通过缩小区间寻找极小点。
先确定 在的搜索区间，然后根据区间消去法原理不断缩小此区间所，从而获得 的数值近似解。
第三章一维搜索线性搜索
1、确定搜索区间的外推法
在给定区间内仅有一个谷值（或有唯一的极小点）的函数称为单谷函数，其区间称为单谷区间。
函数值：“大—小—大”
图形：“高—低—高”
单谷区间中一定能求得一个极小点。
确定初始区间
第三章一维搜索线性搜索