在搜索区间[a,b]内适当插入两点x1,x2 ， 并计算其函数值。 x1,x2 将区间分为三段，通 过比较函数值的大小，删除其中的一段，使搜 索区间缩短。然后再在保留下来的区间上作同 样处理，如此迭代下去，使搜索区间无限缩小， 从而得到极小点的近似值。
插入点x1,x2的位置相对于区间[a,b]两 端点有对称性要求，即
第三章-一维优化方法
一维搜索方法概述
x2 (k)S(k)
S(k)
x(k+1) x(k)
x*
F(x(k))
o
F(x(k+1))
x1
二维优化第三章问-一题维优化中方法的一维搜索
初始搜索区间的确定
在一维搜索时，需要确定一个搜索区间[a,b]，
此区间必须包含函数的极小点 x*，因此搜索区间 必须是单峰区间，即该区间内的函数值呈现
有（1- ）/ = 故：1- = 2 2 + -1=0
由此可得： =0.618
黄金分割法可使相邻两次搜索区间都具有相同 的缩短率0.618。
x1=a+ 0.382(b-a) x2=a+ 0.618(b-a)
第三章-一维优化方法
第三章-一维优化方法
格点法
一、格点法的原理
设一维函数为f(x)，搜索区间为[a,b]，一维收敛
精度为。
在区间[a,b]的内部取n个等分点： x1 , x2 , … ,
xn。x区1间被a分为b nn +a11等k分，(个k分点1坐,标2为,...,n)
对应各点的函数值为y1 , y2 , … , yn。比较其大小，取 最小者ym=min{yk , k=1,2,…,n}，则在区间[x m-1 , x m+1]内必包含极小点，取[x m-1 , xm+1]为缩短后新 区间，若新区间满足收敛条件x m+1- x m+1 ，则最 优解为x* xm ， y* ym
2、若y2>y3，则继续后退搜索，各点变换 如下： x1 x2 ，y1 y2
x2 x3 ，y2 y3 然后步长加倍，取新点x3，重复上述比较y2与 y3的大小，直至出现y1> y2<y3时，令a x3， b x1，从而构成搜索区间[a,b]
第三章-一维优化方法
四、进退法确定搜索区间的流程图
第三章-一维优化方法
第三章-一维优化方法
黄金分割法
除对称性要求外，保留的区间内再插入一 点所形成的区间新三段，与原来区间的三段应 具有相同的比例分布。设原区间长度为l如图
3.8所示，保留区间长度为，区间缩短率为 。
进行第二次缩短时，新点为x3 ,设y1>f(x3)则 新区间为[a,x1]为保持相同的区间缩短率，应
一维优化方法
• 一维搜索方法概述 • 初始搜索区间的确定 • 一维搜索的最优化方法
1、格点法 2、黄金分割法 3、二次插值法 教学要求：
1、掌握初始搜索区间的确定方法 2、掌握黄金分割法 3、掌握二次插值法
第三章-一维优化方法
一维搜索方法概述
在优化设计的迭代运算中，在搜索方向
s(k)上寻求最优步长 (k) 的方法称一维搜索法。
1、若y2<y3，则有y1> y2<y3，此时函数 f(x)在[x1,x3]必有极小点，故令a x1，b x3，从而构成搜索区间[a,b]
2、若y2>y3，则继续前进搜索，各点变换 如下： x1 x2 ，y1 y2
x2 x3 ，y2 y3 然后步长加倍，取新点x3，重复上述比较y2与 y3的大小，直至出现y1> y2<y3时，令a x1， b x3，从而构成搜索区间[a,b]
第三章-一维优化方法
第三章-一维优化方法
一维搜索的最优化方法
在确定了搜索区间以后，一维优化的任务 是采用某种方法将此区间逐步缩小，在满足收 敛精度或迭代精度的情况下，使其达到包含极 小点的一个很小的邻域，以取得一个近似的最 优点。
一维优化的方法有如下几种： 1、格点法 2、黄金分割法 3、二次插值法
“高-低-高”的趋势。如图所示，通过将搜索 区间[a,b]逐渐缩小，直至足够小，就可以得到近似
最优点。
第三章-一维优化方法
确定初始搜索区间的进退法
一、试探搜索极小点位置
设函数为 y=f(x) ,给定初始点为x1 ，选定 的初始步长为h0。
由初始点x1沿x轴正向取x2点，x2=x1+h0， 计算x1 、x2的函数值y1 、y2 ，比较y1 、y2 的
若不能满足精度要求，把当前区间作为初始搜索区间， 重复上述步骤直至满足精度为止。
第三章-一维优化方法
格点法
y1
新区间
yn
ym-1
ym
ym+1
a x1
xm-1 xm
xm+1
xn b
格点法的区间缩短 第三章-一ቤተ መጻሕፍቲ ባይዱ优化方法
格点法流程图
第三章-一维优化方法
黄金分割法
黄金分割法适用于[a,b]区间上的任何单 峰函数求极小值问题。对函数除要求单峰外不 作其它要求，甚至可以不连续。因此，这种方 法的适应面相当广。 一、黄金分割法的原理
第三章-一维优化方法
确定初始搜索区间的进退法
三、后退搜索
令h -h0，并将x1与 x2对调，使步长加 倍h2h，取得x3点，x3 x2+h，其函数值 y3与y2比较有如下情况：
1、若y2<y3，则有y1> y2<y3，此时函数 f(x)在[x3,x1]必有极小点，故令a x3，b x1，从而构成搜索区间[a,b]
大小，则极小点的位置有如图所示两种情况
1、若y2 <y1 ，则极小点位于x1点右方，
应继续前进搜索。
2、若y2>y1 ，则极小点位于x1点左方，
应反向后退搜索。
第三章-一维优化方法
确定初始搜索区间的进退法
第三章-一维优化方法
确定初始搜索区间的进退法
二、前进搜索
令h h0，并使步长加倍h2h，取得前 进方向的x3点，x3 x2+h=x2+2h0，其函 数值y3与y2比较有如下情况：
实际上一维搜索法就是一元函数极小化的数值 迭代算法，其求解过程称为一维搜索。
一维搜索法是非线性优化方法的基本算法， 多元函数的迭代算法都可以归结为在一系列逐 步产生的下降方向上的一维搜索。例如：下图 所示的二维优化的例子。
注意：二维优化问题的一维搜索方向s(k)
是由具体的优化方法决定的，迭代公式
x(k+1)=x(k)+(k)s(k) 因此，二维优化问题min f(x1, x2)就可以表示 为一维优化问题min f( )