当前位置：文档之家 › 第三章 一维搜索(线性搜索)

第三章 一维搜索(线性搜索)

  • 格式：ppt
  • 大小：2.04 MB
  • 文档页数：1

下载文档原格式

  / 1

合集下载

第三章 一维搜索法

第三章 一维搜索法
x
0
x1 x2
x3
3-1 确定初始区间的进退法
探测初始空间的进退法步骤: 探测初始空间的进退法步骤 (1)给定初始点 x0 ,初始步长 h ,令 x1 = x0 ,记: f1 = f ( x1 ) 给定初始点 初始步长 令 记 (2)产生新的探测点 x2 = x1 + h ，记 f 2 = f ( x2 ) 产生新的探测点 (3)比较函数值 f1 和 f 2 的大小 确定向前或向后探测的策略 比较函数值 的大小,确定向前或向后探测的策略 则加大步长,令 若: f1 > f 2 则加大步长 令 h = 2h ,转(4)向前探测 转 向前探测 (4)产生新的探测点 x3 = x0 + h ,令 f 3 = f ( x3 ) 产生新的探测点 令 (5)比较函数值 f 2 和 f 3 的大小 比较函数值 则调转方向,令 若: f1 < f 2 则调转方向 令 h = − h ,转(4)向后探测 转 向后探测
3-1 确定初始区间的进退法
f (x ) f ( x1 )
f ( x2 )
f ( x1 ) > f ( x2 ) > f ( x3 )
极小点在右端点的
f (x3 ) (x
x
x3 右侧
0
x1
x2 x3
3-1 确定初始区间的进退法
f (x ) f ( x1 ) f ( x2 )
f ( x3 )
f ( x1 ) < f ( x2 ) < f ( x3 )
h=-h；x2=x0+h；f2=f(x2)； ； ； ； End
3-2 黄金分割法
一维搜索试探方法的基本思想： 一维搜索试探方法的基本思想：在确定了搜索区间的 前提下，不断缩小搜索区间， 前提下，不断缩小搜索区间，同时保持搜索区间内函数值 “大-小-大”的走势，直到区间的宽度小于预定的精度。 小 大 的走势，直到区间的宽度小于预定的精度。 黄金分割法基本思想： 黄金分割法基本思想 ： 在搜索区间内插入两个黄金分 割点，将区间分成三段。利用函数的单谷性质，通过函数值 割点，将区间分成三段。利用函数的单谷性质， 大小的比较，删去其中一段。 大小的比较，删去其中一段。在保留下来的区间上作同样的 处置，如此往复送代，使搜索区间缩小到精度范围内， 处置，如此往复送代，使搜索区间缩小到精度范围内，得到 极小点的近似解。 极小点的近似解。

第三节一维搜索方法

第三节一维搜索方法

a3 a2 , y3 y2 a2 ap , y2 yp
特点：程序结构简单容易理解可靠性好。但计算 效率偏低，使用于低维优化的一维搜索。
三、二次插值法（抛物线法）
(1)基本思想：在寻求目标函数 f (x ) 极小点的区间 内取三个点的函数值来构造一个二次插值多项式 p(x )用它的极小点近似地作为原目标函数的极小 点。若近似程度不满足精度要求时，可反复使用 此法随着区间的缩短，二次插值多项式的极小点 就逼近原目标函数的极小点一维函数 f (x ) 在搜索 区间[a b] 内为单峰函数，在区间内取三点 x1 x2 x3 且 x1 x2 x3 三点的函数值为 f1 f (x1) f2 f (x2 ) f3 (x3 ) 且 f1 f2 f3 即满足函数值是大—小—大变化。原目
1、基本原理： 通过不断缩短搜索区间的长度来寻求一维函数
f (x ) 的极小点原理。
a
x1 x2
b
a
x1 x2
b
它是一种等比例缩短区间的直接搜索方法。
设目标函数 f (x) 在搜索区间 [a,b] 内 为单峰函数，区间长设为 l
在区间内按如下规则对 称地取两点 x1和 x2
x1 a 0.382(b a) x2 a 0.618(b a)
x b 2a
x*p

1 2
(x22 x32 ) f1 (x32 x12 ) f2 (x12 x22 ) f3 (x2 x3 ) f1 (x3 x1 ) f2 (x1 x2 ) f3
c1

f3 x3
f1 x1
c2

(
f2

f1 ) (x2
x2 x3

《现代机械优化设计》第3章 一维搜索

《现代机械优化设计》第3章 一维搜索

a xp, f (a) f (xp ), f (a) f (xp )
b xp, f (b) f (xp ), f (b) f (xp )
计算 f (x*p ), f (x*p )
否
f (x*p ) 0 是
否
f (x*p )
x xp , f f (xp )
是
结束
否
是
K>0
否
xp-xp0 ≤ε
是
x*=x2, f*=f2
是
x*=xp,f*=fp
xp
1 2
f1(x22 x32 ) f2 (x32 x12 ) f3(x12 x22 ) f1(x2 x3) f2 (x3 x1) f3(x1 x2 )
结束
由于区 间缩到很 小时因计 算机舍入 误差引起， 可取中间 点输出。
x3
ⅱ) (xP x1)(x3 xP ) 0
f1
x1
f2
f3
x2 x3
补充 §3-5 格点法
一）基本思路
先将搜索区间分成若干等分，计算出当中的n个等分 点的目标函数值. 再通过比较,找出其中的最小点，则该 点的两个邻近点围成缩短了的新区间。
f
a
xmx1 m xm1 b
x
二）每轮迭代区间的缩短率
ⅰ)A=0
f1(x2 x3 ) f2 (x3 x1) f3 (x1 x2 ) 0
f1[( x2 x1) (x3 x1)] f2 (x3 x1) f3(x1 x2 ) 0
f2 f1 f3 f1 这表明此时三个插值点共线。 x2 x1 x3 x1
f2
f3
f1
x1
x2
a=x3、b=x1
x3=x2+h、y3=f(x3)

《一维搜索方法》课件

《一维搜索方法》课件

02
线性搜索
线性搜索的定义
线性搜索是一种基本的搜索算法，它 从列表的第一个元素开始，逐个检查 每个元素，直到找到目标元素或遍历 完整个列表。
在线性搜索过程中，我们假设列表中 的元素是按顺序排列的，并且我们不 知道目标元素的确切位置，只知道它 存在于列表中。
线性搜索的步骤
初始化
选择一个起始位置，通常为列表的第一个元素。
抛物线搜索的步骤
3. 比较中间元素与目标值
2. 计算当前区间的中间元 素。
1. 初始化当前搜索区间为 整个数组。
01
03 02
抛物线搜索的步骤
01 如果中间元素等于目标值，返回该位置。
02
如果目标值小于中间元素，将左半部分区 间作为新的当前区间。
03
如果目标值大于中间元素，将右半部分区 间作为新的当前区间。
04
4. 重复步骤2和3，直到找到目标值或当前 区间为空。
抛物线搜索的时间复杂度
最坏情况下，抛物线搜索的时间复杂度为O(n)，其中n为数 组长度。
平均情况下，由于每次比较都可以将搜索区间缩小一半，因 此时间复杂度为O(log n)。
THANKS
THANK YOU FOR YOUR WATCHING
的单峰函数。
一维搜索方法的重要性
解决实际问题
一维搜索方法广泛应用于各种实 际问题中，如参数优化、函数逼 近、插值等。
算法基础
一维搜索方法是许多算法的基础 ，如梯度下降法、牛顿法等都需 要用到一维搜索方法来寻找迭代 步长。
理论分析
一维搜索方法在数学分析中也有 重要应用，如中值定理、单调函 数性质等都需要用到一维搜索方 法。
常用的一维搜索方法
线性搜索

常用的一维搜索方法

常用的一维搜索方法

称为搜索方向；
k 称为步长或步长因子。
图1
线搜索迭代法的步骤
0 x (1) 选定某一初始点 ，并令 k : 0;
(2) 确定搜索方向 d
k
k
;
k
(3) 从 x 出发，沿方向 d x k 1; (4) 检查得到的新点
求步长 λ
k
，以产生下一个迭代点
x
k 1
是否为极小点或近似极小点。
若是，则停止迭代。 否则，令 k :k1，转回(2)继续进行迭代。 在以上步骤中，选取搜索方向是最关键的一步。 各种算法的区分，主要在于搜索方向 d
最优解
从当前点出发，按照某 种规则找下一个迭代点 注：迭代格式 不同，对应着 不同的算法
找下一个迭代点
迭代法的分类
可 行 算 法 ： 所 有 迭 代 点 都 是 可 行 点 据 迭 代 点 初始点不好找 的 可 行 性 不 可 行 算 法 ： 至 少 有 一 个 迭 代 点 不 是 可 行 点 初始点任意选取
k k k Tk kk
T k T k g d g k 1 k d,
其中
(, 1 ) ,0 1 .
常用的一维搜索方法
我们主要介绍下面几种方法





“成功—失败”法 0.618法（黄金分割法） 二分法 牛顿法（Newton）和插值法 Armiji-Goldstein 准则 Wolfe-Powell 准则
注意: 1. h 选择要适当.(太大含多个单峰区间,太小迭代次数多)； 2. f (x)单调时无结果, (加迭代次数限制)；
“成功—失败”法----算例
3 例 ：利用“成功-失败”法求函数 f( x )x 2 x 1 的搜索区间， 1 取初始点 x 1 ，步长 h . 2 21 1 h , 解：取初始点 x ，步长 2 2 1 1 5 11 f (x ) f ( ) , f ( x h ) f ( ) f ( 0 ) 1 , 2 8 22 搜 索 成 功 ， 步 长 加 倍 ； 因 为 f () x f ( x h ) ， 1 1 计 算 f ( x h + 2 h ) f ( x 3 h ) f ( 3 ) f ( 1 ) 0 , 2 2 搜 索 成 功 ， 步 长 加 倍 ； 因 为 fxh ( ) fx ( 3 h ) ， 1 1 计 算 f ( x 3 h + 4 h ) f ( x 7 h ) f ( 7 ) f ( 3 ) 2 2 , 2 2 搜 索 失 败 ， 停 止 迭 代 ； 因 为 fx ( 3 h ) fx ( 7 h ) ，

第3章迭代终止准则及一维搜索方法

第3章迭代终止准则及一维搜索方法

11d
K
f1 f ( X )
a1 a11 a11 a12 f1 f 2
a12 a1 ( a3 a1 ) X X ( K ) 12 d ( K ) f2 f ( X ) a3 a12 ; a12 a11 f 2 f1 a11 a3 (a3 a1 )
搜索区间的确定
外推法确定搜索区间
入口 t0 f0 0.01 , f ( X ), d ( I , J ) d
k
t1 0, t t 0 , f1
t2 t1 t , f 2
f0
f (X )
f
2

f1
YES
NO
确定搜索区间的程序原理
t t , t3 t1 , f 3
令
df ( ) 0 d
得：
4 (1 2 ) 0
将（3-3）代入（3-2）得：
1 2
（3-3）
x
因为
(1)
1 1 2 0 2
f ( x(1) ) 2x x0 0
满足准则1所以
x* x(1) 0
f ( x* )
=0
多维搜索
对于多维搜索，因为
出口
二次插值法 二次插值法的原理是用一个二次多项式(抛物线)来逼近目标函数 P( )=a+b +c
2
dp( ) b 2c d
b p* 2c
二次插值法原理
p*
的求法
( 22 32 ) f1 (32 12 ) f 2 (12 2 2 ) f3 b (1 2 )( 2 3 )(3 1 )
X
( k 1)

常用一维搜索算法

常用一维搜索算法常用一维算法一维算法是解决一维问题的常用方法。

一维算法主要通过在一维数据集中查找目标元素来解决问题。

以下是一些常用的一维算法：1. 线性（Linear Search）：线性算法是一种最简单的算法，也是最基本的一维算法。

它从头到尾依次检查数据集中的每个元素，直到找到目标元素或遍历完整个数据集。

线性算法的时间复杂度为O(n)。

2. 二分（Binary Search）：二分算法是一种高效的算法，但它要求数据集必须是有序的。

算法通过将数据集分成两半，并与目标元素进行比较，从而确定目标元素在哪个半部分中。

然后，它将重复这个过程，直到找到目标元素或数据集被划分为一个元素。

二分算法的时间复杂度为O(log n)。

3. 插值（Interpolation Search）：插值算法是改进的二分算法，它根据目标元素与数据集中元素的相对位置来确定的起始位置。

它使用目标元素与数据集首尾元素之间的比例来估计目标元素的位置。

插值算法在数据集分布均匀的情况下具有较好的性能。

4. 斐波那契（Fibonacci Search）：斐波那契算法基于斐波那契数列来确定的起始位置。

它通过比较目标元素与斐波那契数列中的元素来确定的范围，并将数据集划分成两部分。

然后，它在适当的部分中重复这个过程，直到找到目标元素。

斐波那契算法的时间复杂度为O(log n)。

5. 插入（Interpolation Search）：插入算法是一种改进的线性算法，它使用了数据集中元素的顺序信息来提高效率。

与线性算法一样，它从头到尾依次检查数据集中的每个元素，但是当元素不满足条件时，它会根据元素的顺序信息来确定的方向，从而减少的次数。

6. 哈希（Hash Search）：哈希算法使用哈希函数将数据集中的元素映射到哈希表中的索引。

然后，它通过查找哈希表中的索引来确定目标元素的位置。

哈希算法通常具有很高的效率，但是它需要额外的内存空间来存储哈希表。

上述算法是一维问题的常用解决方法。

三章节一维搜索方法


f x ad f x adTf x 1 ad T G ad
2
f x dTf x 1 2dTGd
2
上式求α旳极值，即求α导数为零。
dTf x *d TGd 0
则
*
dTf x
d T Gd
从上式看，需要求导进行计算，对于函数关系复杂旳， 解析法十分不便。
数值法旳基本思绪：拟定 *旳搜索区间，在不断缩小
a2 a3 y1 a3 a1 y2 a1 a2
a1 a2 a2 a3 a3 a1
y3
所以
p
a1
/
2a2
1 2
a22 a32 a2 a3
y1 a32 a12 y1 a3 a1
y2 a12 a22 y2 a1 a2
y3 y3
令
c1
y3 a3
y1 a1
一、牛顿法（切线法）
一维搜索函数 y f ，假定一给出极小点旳一种很好旳近
似点0 ，因为一种连续可微旳函数在极小点附近与一种二次 函数很接近，所以，在0 点附近用一种二次函数 逼近。
f
f
0
f
0
0
1 2
f
0
0 2
求二次函数 旳极小点作为f 极小点旳新近似点1
1 0 即 f 0 f 0 0 0
P a0 a1 a2 2
它应满足条件 P 1 a0 a11 a212 y1 f 1 （1）
P 2 a0
a12
a2
2 2
y2
f
2
P 3
a0
a13
a2
ห้องสมุดไป่ตู้
2 3
y3
f
3
从极值旳必要条件求得

第三章-一维搜索方法

解析解法对于函数关系复杂、求导困难等情况难以 实现。在实际优化设计中，数值解法的应用更为有效， 且适合计算机的运算特点。
数值解法基本思路：
先确定 k 所在的搜索区间，然后根据区间消去法原理 不断缩小此区间，从而获得 k 的数值近似解。
一维搜索一般分为两大步骤： (1)确定初始搜索区间[a，b]，该区间应是包括一维函数 极小点在内的单谷区间。 (2)在单谷区间[a,b]内通过缩小区间寻找极小点。
x2 a 0.618(b a), y2 f (x2 )
否 ba
是
x 0.5(a b)
止
f f (x)
b x2, x2 x1, y2 y1 x1 a 0.382(b a), y1 f (x1)
f
也可采用迭代次数是否大于或等于 k 作终止准则。
y1 y2 x a x1 x2 b
当方向 d k 给定，求最佳步长 k 就是求一元函数
f x k1 f xk kd k k
的极值问题。这一过程被称为一维搜索。
第三章 一维搜索方法
f (x (k+1) ) = min. f (x (k) + α S (k) ) = f (x (k) + α(k) S ( k) )
一维搜索是优化搜索方法的基础。
第三章 一维搜索方法
求解一元函数 a 的极小点 a* ，可用解析法。 f x ad f x adTf x 1 ad T G ad
2
f x dTf x 1 2dTGd
2
上式求α的极值，即求α导数为零。
dTf x *dTGd 0
则
*
dTf x
d T Gd
第三章 一维搜索方法
5
-1.386 -1.111 -0.940 -0.665

完整版一维搜索方法


f (? 1 ) f (? 2 )
o
?1 ?2
?
6
2) 若f1≤ f2 ，如下图所示, 则作后退计算。 令 h=-h, 将α1、 f1与α2、 f2对调，转入第3)步。
f (? )
f (? 2 )
f (? 1)
o
?1 ?2 ?
7
3)计算第3个试点α3 ＝α2+h, 计算函数值f3＝f(α3), 并 比较f2 和 f3 ，有如下两种情况 :
1
? 一维优化一般可分为两大步骤： ?确定初始搜索区间[a,b]; 该区间应为包含一维优化目标函数的极小点在内的单 峰区间。 ?在搜索区间[a,b]内寻找极小点。
优化算法的基本迭代公式：
X k?1 ? X k ? ? k S k , k ? 0, 1, 2,?
当迭代初始点 Xk 及搜索方向Sk 确定后，迭代所得的新点 Xk?1 取
作代换： α1 ＝α2 ， f1＝f2； α2 ＝α3 ， f2 ＝ f3。 继续计算
α3 （即步骤 3) ）；如此重复该过程，总能找到相继3试点 的函数值符合“大－小－大” 变化的要求。左端点为a,
右端点为b，从而找到了搜索区间[a, b]。
f (? )
f (? 1) f (? 2 )
f (? 3 )
a＝min( α1 ,α3 ), b=max ( α1 ,α3 )
h=2h, α3＝ α2+h, 计算f(α3)
N
作代换 α1 =α2 ， α2 =α3 ， f(α1)= f(α2) ， f(α2)= f( α3) ， α3＝ α2+h, 计算f(α3)
结束
10
? 进退法确定搜索区间的步骤：
2. 方法二 (1) 给定初始点α0和初始步长h0; (2) 令α1 ＝α0, h=h0， α2 ＝α1+h, 得： 两试点α1 ，α2 ，计算 f1 ＝f(α1), f2 ＝f(α2);
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。


的正向试探。
y1 y2→y1 y3→y2
每走一步都将区间的始点、
中间点沿试探方向移动一步
（进行换名）。经过三步最 后确定搜索间 1 , 3
1 2 3
，
O
并且得到区间始点、中间点 和终点 所对
a1 h0
a2→a1 a3→a2 h0 2h0
a
a3
应的函数值 y1 y2 y3
3）产生新的探测点a3=a2+h，y3=f(a3)；
4）比较函数值y2和y3：
a）如果y2>y3 ，加大步长h=2h，a1=a2,a2=a3,转（3）继 续探测； b）如果y2<y3，则初始区间得到： a=min[a1,a3],b=max[a1,a3]，函数最小值所在区间为 [a,b]。
右图表示沿
图3-3 反向搜索的外推法
前进搜索步骤表 k 0 1 2 3 h h0 2h0 4h0 8h0 x1 初始点 初始点 初始点+ h0 初始点+3h0 x2 初始点+ h0 初始点+ h0 初始点+3h0 初始点+7h0 初始点+3h0 初始点+7h0 初始点+15h0 x3
后退搜索步骤表 k
0
h
x3=x2+h、y3=f(x3)
f
y1
y2
y3
x1 x2 x3
x
x1 x2 x3
前进计算
f
x1=x2 y1=y2 x2=x3 y2=y3 a=x3、b=x1
是
y2≥y3 否 是 a=x1、b=x3
否
h>0
x1 x2 x3 x2 x1 x3 x2 x1
后退计算
x
结束
21
3.3 区间消去方法
搜索区间确定之后，采用区间消去法逐步缩
解：
k 1 2
h 0.1 0.2 0.4
x1 0 0.1
y1 9 8.203
x2 0.1 0.3
y2 8.203
x3 0.3
y3 6.681 4.429
6.681
0.7
3
0.8
0.3
6.681
0.7
4.429
1.5
7.125
a, b 0.3, 1.5. 可得初始搜索区间
19
例3 2：用进退法确定函数 f ( x) 3x 3 8 x 9的一维优化初始区间 , 给定初始点x1 1.8, 初始进退距h0 0.1.
①
若 f (a1 ) f (b1 ) ， 则取[a,b1]为
缩小后的搜索区间。 若 f (a1 ) f (b1 ) ，则取[a1,b]为
②
缩小后的搜索区间。
3 一维搜索方法分类
从前面的分析可知，每次缩短区间，只需要在区间
内再插入一点并计算其函数值。
而插入点的位置，可以由不同的方法来确定。就形 成了不同的一维搜索方法。
* ( ) 求解一元函数 的极小点 ，可采用解析解法，
' * ( )0 即利用一元函数的极值条件
求 *
在用函数 ( ) 的导数求 * 设计点 x 为变量的多元函数
时，所用的函数 ( )
是仅以步长因子 为变量的一元函数，而不是以
f ( x)
。
为了直接利用 的函数式求解最佳步长因子 。 把 或它的简写形式 进行泰勒展开， 取到二阶项，即
单谷区间
说明：单谷区间内，函数可以有不可微点，也可以是不 连续函数；
f (x)
f (x)
0
α1
α3
α
0
α1选一个初始点 a1 及初始步长 h ， 通过比较这两点函数值的大小，确定第三点位置，比较这 三点的函数值大小，确定是否为“高—低—高”形态。 步骤： 1）选定初始点a1，初始步长h=h0，计算y1=f(a1)和y2=f(a1+h) 2）比较y1和y2； a）如果y1>y2，向右前进，加大步长h=2h0，转（3）向前； b）如果y1<y2，向左后退， h=-2h0，将a1和a2,y1和y2的值互 换。转（3）向后探测； c）如果y1=y2，极小点在a1和a1+h之间。
数值解法的基本思路是：首先确定 所在的搜索区间， 然后根据区间消去法原理不断缩小此区间，从而获得 的数 值近似解。
f ( x ) f ( x k s ) ( k )
k 1 k k
解析法:
① ②
f x
f(X(k) + αS(k) ) 沿S(k) 方向在x(k) 点泰勒展开； 取二次近似：
2 F x12 x2 8 x1 12 x2 52 2 2 20 52
X k 1 X k S k (k 0,1,2 )
一维搜索示意图
3.1.2 的确定方法
求多元函数极值点，需要进行一系列的一维搜索。可见一 维搜索是优化搜索方法的基础。
一维搜索一般分为两大步骤： (1)确定初始搜索区间[a，b]，该区间应是包括一维函数 极小点在内的单谷区间。 (2)在单谷区间[a,b]内通过缩小区间寻找极小点。
一维搜索也称直线搜索。这种方法不仅对于解决 一维最优化问题具有实际意义，而且也是求解多维最优 化问题的重要支柱。
3.2 确定初始区间
1、确定搜索区间的外推法
解:
k 1 2 3
h 0.1 -0.2 -0.4 -0.8
x1
y1
x2 1.9 1.8 1.6 1.2
y2 14.377 12.096 8.488 4.584
x3 1.6 1.2 0.4
y3 8.488 4.584 5.992
1.8 12.096 1.9 14.377 1.8 12.096 1.6 8.488
。
图3-2 正向搜索的外推法
右图所表示的情况是：开始 是沿 的正方向试探，但
y1←y2 y3 y1←y2←y1 y2←y3
由于函数值上升而改变了试
探方向，最后得到始点，中
间点和终点 们的对应函数值 从而形成单谷区间为一维搜 索区间 。
2h0
及它
a3 a2←a3
O
a1←a2
a
a1←a2←a1
h0 h0
其中
为待定常数。
1 b (b a) 2 a (b a)
2）黄金分割法还要求在保留下来的区间内再插入一点所 形成的区间新三段，与原来区间的三段具有相同的比 例分布。 即每次缩小所得的新区间长度与缩小前区间长度 之比（即：区间收缩率）为定值。
第三章
3.1 概述
一维搜索方法
3.2 确定初始区间
3.3 缩小区间 3.4 黄金分割法（0.618法） 3.5 一维搜索的插值方法
第3章 一维搜索方法
3.1 概述
3.1.1 一维问题是多维问题的基础
求目标函数 f (X)的极小点，从理论上说需要求解方程：
f ( X ) 0
基本思想:
其中
X ( x1 , x2 ,, xn )T
④ 求得最优步长
(k )
[f ( x ( k ) )]T S ( k ) [ S ( k ) ]T G ( x ( k ) ) S ( k )
解析解法对于函数关系复杂、求导困难等情况难以 实现。在实际优化设计中，数值解法的应用更为有效， 且适合计算机的运算特点。 数值解法基本思路： 先确定 k 在的搜索区间，然后根据区间消去法原理 不断缩小此区间所，从而获得 k 的数值近似解。
f 2 f (b1 )
(1)f（a1）<f（b1）, 则极小点必在区间[a，b1]内; (2)f（a1）>f（b1）, 则极小点必在区间[α 1，b]内;
f 1 f (a1 )
f 2 f (b1 )
(1)f（a1）<f（b1）, 则极小点必在区间[a，b1]内; (2)f（a1）>f（b1）, 则极小点必在区间[α 1，b]内; (3)f（a1）=f（b1）, 则极小点必在区间[α 1，b1]内 可以总结为两种情况：
a, b 0.4, 1.6. 可得初始搜索区间
运用进退法确定出初始搜索区间[a,b]后，便可采用一维优化方 法来求出函数f(x)在区间内的最优点x*。
20
2. 程序框图
初始进退距
给定x1、h0 h=h0 y1=f(x1)、x2=x1+h、y2=f(x2) h=-h x3=x1 y3=y1 否 y1≥y2 是 h=2h
试探法 一维搜索方法分类
插值法
黄金分割法
二次插值法
3.4 黄金分割法（0.618法）
1. 黄金分割法 2. 黄金分割法的搜索过程
3.4 黄金分割法（0.618法）
概述
在实际计算中，最常用的一维搜索试探方法是黄金分割法， 又称作0.618法。我们可以通过学习黄金分割法来了解一 维搜索试探方法的基本思想。 在搜索区间 [a,b]内适当插入两点α 1、α 2，并计算其函 数值。α 1、α 2将区间分成三段。应用函数的单谷性质， 通过函数值大小的比较，删去其中一段，使搜索区间得以 缩短。然后再在保留下来的区间上作同样的处置，如此迭 代下去，使搜索区间无限缩小，从而得到极小点的数值近 似解。
h0
x1 初始点
x2 初始点+ h0
x3
1
2h0
初始点+ h0
初始点 初始点-2h0
初始点
初始点-2h0 初始点-6h0
初始点-2h0
初始点-6h0 初始点-14h0
2
4h0
3
8h0
例3 1 : 用进退法确定函数 f ( x) 3x 3 8 x 9的一维优化初始区间 , 给定初始点x1 0, 初始进退距h0 0.1.