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

格式：ppt
大小：1.97 MB
文档页数：68

下载文档原格式

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

不断缩小此区间所，从而获得 k 的数值近似解。
一维搜索一般分为两大步骤： (1)确定初始搜索区间[a，b]，该区间应是包括一维函数极小点在内的单谷区间。 (2)在单谷区间[a,b]内通过缩小区间寻找极小点。
一维搜索也称直线搜索。这种方法不仅对于解决一维最优化问题具有实际意义，而且也是求解多维最优化问题的重要支柱。
可得初始搜索区间 a, b 0.4, 1.6.
运用进退法确定出初始搜索区间[a,b]后，便可采用一维优化方法来求出函数f(x)在区间内的最优点x*。
20
2. 程序框图
初始进退距
给定x1、h0 h=h0
h=-h
x3=x1 y3=y1
y1=f(x1)、x2=x1+h、y2=f(x2)
否
y1≥y2
是
这个过程称为一维搜索过程。
如： F(X ) x12 x22 8x1 12x2 52
当
X 0 0 0T , d0 1 1T
X
0 0
1 1
则 F x12 x22 8x1 12x2 52 22 20 52
X k1 X k S k (k 0,1,2 )
一维搜索示意图
3.1.2 的确定方法
解:
kh
x1
y1
x2
y2
x3
y3
0.1 1.8 12.096 1.9 14.377 1
-0.2 1.9 14.377 1.8 12.096 1.6 8.488
2 -0.4 1.8 12.096 1.6 8.488 1.2 4.584
3 -0.8 1.6 8.488 1.2 4.584 0.4 5.992
h=2h
x1=x2 y1=y2 x2=x3 y2=y3

第三章一维搜索法

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 黄金分割法
一维搜索试探方法的基本思想：一维搜索试探方法的基本思想：在确定了搜索区间的前提下，不断缩小搜索区间，前提下，不断缩小搜索区间，同时保持搜索区间内函数值 “大-小-大”的走势，直到区间的宽度小于预定的精度。小大的走势，直到区间的宽度小于预定的精度。黄金分割法基本思想：黄金分割法基本思想：在搜索区间内插入两个黄金分割点，将区间分成三段。利用函数的单谷性质，通过函数值割点，将区间分成三段。利用函数的单谷性质，大小的比较，删去其中一段。大小的比较，删去其中一段。在保留下来的区间上作同样的处置，如此往复送代，使搜索区间缩小到精度范围内，处置，如此往复送代，使搜索区间缩小到精度范围内，得到极小点的近似解。极小点的近似解。

机械优化设计第三章一维搜索方法

(b a)，故
Fn
b
a 。由Fn即可从斐波那契数列表或按F0
F1
1, Fn
Fn1
Fn2 (n
2, 3,
)
推算出相应的n。
3）确定试点并计算相应的函数值，在区间a, b内的两个试点：
x2
a
Fn1 Fn
(b
a),
x1
b
Fn1 Fn
(b
a),
f1 f (x1),
f2 f (x2 )
第三章一维搜索方法
1.若f (a1) f (b1)，则取[a,b1]为缩短后的搜索区间； 2.若f (a1) f (b1)，则取[a1,b]为缩短后的搜索区间。
第三章一维搜索方法
第二节搜索区间的确定与区间消去法原理
间接
假定在搜索区间[a, b]内取一点x, 并计算它的导数值 f '(x)，可能出现三种情况：
x2 a b x1, f2 f (x2 )
5）检查迭代终止条件：bn1 an1
，若满足，则输出最优解x*
1 (a b), 2
ห้องสมุดไป่ตู้
f*
f (x*)，
若不满足，则转入（4），继续进行迭代。
1. f (a1) f (b1)，由于函数的单峰性，极小点一定在[a, b1 ]内； 2. f (a1) f (b1)，极小点一定在[a1,b]内； 3. f (a1) f (b1)，极小点一定在[a1,b1]内。
第三章一维搜索方法
第二节搜索区间的确定与区间消去法原理
直接法
假定在搜索区间[a,b]内任取两点a1和b1，且a1 b1，并计算f (a1)和f (b1)，可能出现三种情况：
f (x1) f (x) f (x2)

《一维搜索方法》课件

1
原理
根据斐波那契数列生成黄金分割比例，用于确定搜索范围的分割点。
2
思路
根据斐波那契数列的值，确定左右指针在搜索范围内的位置，直到找到最接近目标值的点。
3
优缺点
迭代次数逐渐趋近于黄金分割点，但对搜索范围要求较高。
黄金分割法搜索方法的原理和思路
1
原理
将搜索范围按黄金分割点分割，选择较小的一部分作为新的搜索范围。
2
思路
通过反复按黄金分割点计算和调整搜索范围，逐步逼近最接近目标值的点。
3
优缺点
迭代次数相对较少，但需要较复杂的计算公式。
三分搜索方法的原理和思路
1
原理
将搜索范围分割为三等份，并判断目标值位于左、中、右三个部分，逐步缩小搜索范围。
2
思路
根据目标值与分割点的大小关系，决定下一步搜索的范围，直到找到最接近目标值的点。
3
优缺点
对于非单调函数，能更快地找到目标值，但需要较多的判断。
多点搜索方法的原理和思路
1
原理
同时使用多个起始点进行搜索，通过不断比较找到最接近目标值的点。
2
思路
根据多个起始点的初始值和搜索步长，逐步调整并比较得到最优解。
3
优缺点
相比于单点搜索，能更准确地找到目标值，但需要同时处理多个起始点的迭代。
2
思路
从起始点开始，依次向右增加或向左减小搜索范围，直到找到最接近目标值的点。
3
优缺点
简单易懂，但需要较多的迭代次数。
二分搜索方法的原理和思路
1
原理
将搜索范围一分为二，并判断目标值位于左半部分还是右半部分，逐步缩小搜索范围。
2
思路

一维搜索方法工程优化课件

当步长足够小（小于允许误差）时，搜索
停止，得到问题的近似解。
例：考虑图中函数f(x)的最小值点。初始点为 x0，初始步长为h。为简单起见，以符号来描述运算过程：若成功记为V，若失败记为 F;I→J表示从第I点到第J点的搜索过程，其步
长标注在→的下边。具体过程为：
x0 V h x1 2 Fh x2,失败，退回到x1,下一步反向，改变步长。
为方便起见初始迭代时一般取区间为x1x3区间中点为x2求出一个极值点x4后在以上4个点中选出3个点使它们构成的新区间比上一步短同时3个点的函数值在新区间内呈现两头大中间小的特点
第三章一维搜索方法一维搜索可用于：
①求一元函数的最优解（一般指：极小点、极小值）； ②多维优化设计时，在第k次迭代中，求最优步长。即把目标函数看成是步长α的一元函数。
例：用黄金分割法求 f()2710
的最优解。迭代精度为0.35。
实际工程中目标函数往往不能用简单的函数来表示，很难通过函数求导来解上述问题。由前面例题知，单峰区间为[2,8].（通过 excel求解）
3.4二次插值法（抛物线法）基本原理：在搜索区间内，任取1点，连同2 个端点，用这3个点构造一个二次插值多项式 p(a)，用p(a)的极小点作为目标函数的近似极小点。不断缩短搜索区间，进行多次插值运
x3 hF/ 2x1 ，失败，仍回到x1,下一步再反向，再
改变步长
x 1 h V /8 x 4 h V /4 x 5 h F /2 x 6
x7 hF/ 8x5
，迭代失败，回到x5，下一步…

实际工程中，函数的形态可能并不清楚，但只要是一维函数，通过成功—失败法就可以找到其最小值点。这个过程可以通过计算机程序来实现。以下是一个matlab程序。

《一维搜索方法》课件

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 ) ，

一维搜索

非线性规划非线性规划问题是比线性规划问题更一般的数学规划问题，它的目标函数或约束函数中至少含有一个非线性函数，非线性规划就是研究非线性规划问题的有关理论和方法的学科。

非线性规划是运筹学的一个重要分支，它在军事、经济、工程、管理以及最优设计等方面都有着广泛的应用。

本部分介绍无约束非线性规划和约束非线性规划的基本理论和方法。

第三章无约束优化方法无约束非线性规划问题是指可行域是整个决策空间的非线性规划问题。

本章首先分析无约束非线性规划问题的一阶和二阶最优性条件，包括必要条件和充分条件，然后讨论一维搜索问题，最后介绍无约束优化的求解方法，包括最速下降法，Newton 法共轭梯度法和拟Newton 法等。

补充：最优性条件现在考虑无约束非线性规划问题)(min x xf (UNP)其中决策变量n R ∈x ，目标函数1:R R f n →。

我们先引进下降方向的概念，并研究其充分条件，由此建立(UNP)的一阶和二阶最优性条件。

补.1 下降方向定义补.1 设函数1:R R f n →，n R ∈x ，nR ∈s 是非零方向。

若存在δ>0，使()(f f λ+<x s x ，(0,)λδ∀∈则称s 是f 在x 处的下降方向。

注补.1 设*x 是(UNP)的局部最优解，则f 在*x 处不存在下降方向。

定理补.1 设)(x f 在x 处可微，nR ∈s 是非零方向。

若()Tf ∇x s <0，则s 是f 在x 处的下降方向。

证明：对任意的λ>0，因为)(x f 在x 处可微，故由)(x f 在x 处的一阶Taylor 展开式知，()()()()()[()()/]T T f f f o f f o λλλλλλ+=+∇+=+∇+x s x x s x x s (补.1)根据条件()Tf ∇x s <0和0()lim0o λλλ→=知，存在δ>0，使()()0T o f λλ∇+<x s ，(0,)λδ∀∈代入(补.1)并由λ>0得到，()(f f λ+<x s x ，(0,)λδ∀∈由此知s 是f 在x 处的下降方向。

04工程优化第3章-2常用一维搜索牛顿法

解： f '( x) 4 x3 12 x 2 12 x 16, f ''( x) 12 x 2 24 x 12,
f '( x0 ) f '(6) 89 x1 x0 6 6 4.75 f ''( x0 ) f ''(6) 69
f '( x1 ) f '(4.75) 84.94 102 , 继续迭代； f '( x1 ) x2 x1 f ''( x1 ) f '(4.75) 84.94 4.75 =4.75 =4.163 f ''(4.75) 144.75 f '( x2 ) f '(4.163) 14.666 102 , 继续迭代；
3.若 x2 x ，则迭代结束，取 x* x ，否则在点
x1 , x2 , x3 , x 中，选取使f (x) 最小的点作为新的x2，并使新的
x 1 ， x3各是新的x2近旁的左右两点，继续进行迭代，直到满足终止准则。
例
用二次插值法求函数f(x)=3x3-4x+2的极小点，给定 x0=0, h=1, ε=0.2。
应继续迭代。
(2) 在新区间，相邻三点及其函数值: x1=0, x2=0.555, x3=1;
根据公式计算差值多项式的极小点 f1=2, f2=0.292, f3=1.
1 c1 x a1 / 2a2 ( x1 x3 ), f1 f 2 2 c2 c1 f1 f 3 x1 x2 c1 , c2 x1 x3 x2 x3
Newton法----算例
f '( x2 ) x3 x2 f ''( x2 )

线搜索算法_一维搜索

k 1 k搜索成功 , 步骤3：若 , 转步骤4；否则，搜索失败，
转步骤5。
步骤4： k : k 1 ,
停止迭代。
h : 2h, k k 1 转步骤 2。
步骤5：反向搜索，若 k 0, 令 h h ，转步骤2；否则
一、精确一维搜索—初始区间例 1：利用进退法求函数 f ( x) x3 2 x 1 的搜索区间， 1 1 取初始点，步长 x h . 2 2 解： 1 15 1 1 f ( x) f ( ) , f ( x h) f ( ) f (0) 1, 2 8 2 2 因为f ( x) f ( x h)，搜索成功，步长加倍； 1 1 计算 f ( x h+2h) f ( x 3h) f ( 3 ) f (1) 0, 2 2 搜索成功，步长加倍；因为f ( x h) f ( x 3h)，
一、精确一维搜索—初始区间确定初始区间的方法---进退法 ① 已知搜索起点和初始步长； ② 然后从起点开始以初始步长向前试探，如果函数值变大，则改变步长方向； ③ 如果函数值下降，则维持原来的试探方向，并将步长加倍。
一、精确一维搜索—初始区间
进退法算法流程
步骤1：选取初始点 x∈R , 初始步长 h > 0 及精度ε> 0，计算 0 f ( x). 并记 k : 0 步骤2：令 k 1 k h ，计算 k 1 f (k 1 ).
一、一维搜索—分类非精确的一维搜索：通过计算少量的函数值，得到一步长 k ，使得后续迭代点 xk 1 x k k d k 满足
f ( xk 1 ) f ( xk ) ，即使目标函数要“充分”下降。
Goldstein准则 Armijo准则 Wolfe准则

1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

,L
, xn )T
那么如何来求 f (X)的极小点呢？
基本思想:
X 0 , X1,L , X k , X k1
f ( X 0 ) f ( X1) ,L , f ( X k ) f ( X k1)
这种方法是逐次迭代的方法，在电子计算机上很容易实现，
因此它在优化设计中被广泛地采用。
2
Sk方向上的任何一点可以表示为
第三章一维搜索方法
3.1 概述 3.2 确定初始区间 3.3 缩小区间 3.4 黄金分割法（0.618法） 3.5 一维搜索的插值方法
第3章一维搜索方法
3.1 概述
3.1.1 一维问题是多维问题的基础
求目标函数 f (X)的极小点，从理论上说需要求解方程：
f (X ) 0
其中
X
(
x 1
,
x2
为了直接利用
的函数式求解最佳步长因子。
把
或它的简写形式
进行泰勒展开，
取到二阶项，即
将上式对进行微分并令其等于零，给出极值点应满足的条件
从而求得
这里是直接利用函数而不需要把它化成步长因
子。的函数
。不过，此时需要计算
点处
梯计算。
对于函数关系复杂、求导困难或无法求导的情况，使用解析法将是非常不便的。
④ 求得最优步长
(k)
[
[f ( S ( k ) ]T
x(k ) G(
)]T x(k
S ))
(k
S
) (k
)
解析解法对于函数关系复杂、求导困难等情况难以实现。在实际优化设计中，数值解法的应用更为有效，且适合计算机的运算特点。数值解法基本思路：
先确定 k 在的搜索区间，然后根据区间消去法原理
② 取二次近似：
f x(k) S (k) f (x(k) ) [f (x(k) )]T S (k) 1 2[S (k) ]T G(x(k) )S (k) 2
③ 对α求导，令其为零。 d f (x(k ) S (k ) ) 0 d
[f ( x(k ) )]T S (k ) [S (k ) ]T G( x(k ) )S (k ) 0
区间的始点、中间点依次沿试探方向移动一步。
此过程一直进行到函数值再次上升时为止，即可找到搜索区间的终点。
最后得到的三点即为搜索区间的始点、中间三点和终点，形成函数值的“高－低－高”趋势。
单谷区间
说明：单谷区间内，函数可以有不可微点，也可以是不连续函数；
f (x)
f (x)
0 α1
α
α3
X k1 X k ak S k
其中α是步长因子，为实系数，此时 Sk 方向上任何一点的目标函数值
为f X k k S k ，它是参数α的一元函数。那么在沿 Sk 方向求 f (X )
的极小点，这就是求一元函数 f X k k S k 的极小问题，它可表示为：
: min f X k k S k
这个过程称为一维搜索过程。
如： F(X ) x12 x22 8x1 12x2 52
当
X 0 0 0T , d0 1 1T
X
0 0
1 1
则 F x12 x22 8x1 12x2 52 22 20 52
X k1 X k S k (k 0,1,2 )
一维搜索示意图
3.1.2 的确定方法
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]。
右图表示沿的正向试探。
每走一步都将区间的始点、中间点沿试探方向移动一步
求多元函数极值点，需要进行一系列的一维搜索。可见一维搜索是优化搜索方法的基础。
求解一元函数 ( )的极小点 *，可采用解析解法，即利用一元函数的极值条件 '( *) 0 求 * 在用函数 ( ) 的导数求 * 时，所用的函数( )
是仅以步长因子为变量的一元函数，而不是以
设计点 x 为变量的多元函数 f (x) 。
不断缩小此区间所，从而获得 k 的数值近似解。
一维搜索一般分为两大步骤： (1)确定初始搜索区间[a，b]，该区间应是包括一维函数极小点在内的单谷区间。 (2)在单谷区间[a,b]内通过缩小区间寻找极小点。
一维搜索也称直线搜索。这种方法不仅对于解决一维最优化问题具有实际意义，而且也是求解多维最优化问题的重要支柱。
0
α1
α3
外推方法
基本思想：对 f (x)任选一个初始点 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之间。 3）产生新的探测点a3=a2+h，y3=f(a3)；
因此，在优化设计中，求解最佳步长因子主要采用数值解法，利用计算机通过反复迭代计算求得最佳步长因子的近似值。
数值解法的基本思路是：首先确定所在的搜索区间，然后根据区间消去法原理不断缩小此区间，从而获得的数值近似解。
f ( xk1) f ( xk k sk ) (k )
解析法:
① f(X(k) + αS(k) ) 沿S(k) 方向在x(k) 点泰勒展开；
3.2 确定初始区间
1、确定搜索区间的外推法
在给定区间内仅有一个谷值（或有唯一的极小点）的函数称为单谷函数，其区间称为单谷区间。
函数值：“大—小—大” 图形：“高—低—高” 单谷区间中一定能求得一个极小点。
从
开始，以初始步长向前试探。
如果函数值上升，则步长变号，即改变试探方向。
如果函数值下降，则维持原来的试探方向，并将步长加倍。
y1
y2→y1 y3→y2
（进行换名）。经过三步最
后确定搜索间 1,3 ，
并且得到区间始点、中间点
O
a1 a2→a1 a3→a2
a
a3
和终点 1 2 3
所对
h0
h0
2h0

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

合集下载