最优化_第3章 一维搜索方法ppt课件.ppt

《最优化_第3章 一维搜索方法ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章一维搜索方法3.3一维搜索的试探法3.1搜索区间的确定3.2区间消去法原理3.4一维搜索的插值法求解一维目标函数f(X)最优解的过程，称为一维优化(一维搜索)，所使用的方法称为一维优化方法。由前数值迭代法可知，求某目标函数的最优值时，迭代过程每一步的格式都是从某一定点X(k)出发，沿着某一使目标函数下降的规定方向S(k)搜索，以找出此方向的极小点X(k+1)。这一过程是各种最优化方法的一种基本过程。一维搜索方法一般分两步进行：■首先确定一个包含函数极小点的初始区间，即确定函数的搜索区间，该区间必须是单峰区间；■然后采用缩小区间或插值逼近的方法得到最优步长

2、，最终求出该搜索区间内的一维极小点。§3.1搜索区间的确定根据函数的变化情况，可将区间分为单峰区间和多峰区间。所谓单峰区间，就是在该区间内的函数变化只有一个峰值，即函数的极小值。即在单峰区间内的极小值点X*的左侧：函数呈下降趋势，而在单峰区间内的极小值点X*的右侧：函数呈上升趋势。也就是说，单峰区间的函数值呈“高-低-高”的变化特征。§3.1搜索区间的确定x*abx0f(x)目前在一维优化搜索中确定单峰区间常用的方法是进退试算法。进退试算法的基本思想为：1)按照一定的规律给出若干试算点，2)依次比较各试算点的函数值的大小，3)直到找到相邻三点函数值按“高-低-

3、高”变化的单峰区间为止§3.1搜索区间的确定进退试算法的运算步骤如下：(2)将α0及α0+h代入目标函数f(x)进行计算并比较大小(1)给定初始点α0和初始步长h§3.1搜索区间的确定f(x)x0aba0f(a0)a0+hf(a0+h)a0+3hf(a0+3h)f(x)x0aba0-hf(a0-h)a0f(a0)a0+hf(a0+h)若f(α0+h)≤f(α0+3h)，则所计算的相邻三点的函数值已具“高-低-高”特征，这时可确定搜索区间(3)若f(α0)>f(α0+h)，则表明极小点在试算点的右侧，需做前进试算。否则，将步长再加倍，并重复上述运算。§3.1搜索

4、区间的确定在做前进运算时，为加速计算，可将步长h增加2倍，并取计算新点为α0+h+2h=α0+3h(4)若f(α0)f(α0)，则搜索区间可取为否则，将步长加倍，继续后退，重复上述步骤，直到满足单峰区间条件为止。§3.1搜索区间的确定f(b1)f(a1)f(b1)f(a1)f(b1)af(a1)搜索区间确定之后，采用区间消去法逐步缩短搜索区间，找到极小点的数值近似解。假定在搜索区间内[a,b]任取两点a1、b1,且

5、a1f2f1f2,新区间为[a1,b](3)f1=f2,新区间为[a1,b1]对于上述缩短后的新区间，可在其内再取一个新点，然后将此点和该区间内剩下的那一点进行函数值大小的比较，以再次按照上述方法，进一步缩短区间，这样不断进行下去，直到所保留的区间缩小到给定的误差范围内，而得到近似最优解。新区间为[a1,b]f(b1)af(a1)a1b1bf(b1)f(a1)

6、a1abb1f(b1)f(a1)a1bab1一、适用范围适用于[a,b]区间上的任何单谷函数求极小值问题。对函数除要求“单峰”外不作其他要求，甚至可以不连续。适应面相当广。基本原理为区间消去法§3.3黄金分割法黄金分割法插入两点：f(a2)af(a1)a1a2bf(a2)af(a1)a1ba2黄金分割法还要求在保留下来的区间内再插入一点所形成的区间新三段，与原来区间的三段具有相同的比例分布。§3.3黄金分割法λα2α1λ2ab11-λα1α3λ(1-λ)α2λa黄金分割法程序框图开始输入a,b,,YN结束YNaf(x2)f(x1)bx1x2bx2f(x2)x1

7、例3-1用黄金分割法求函数f(x)=3x3-4x+2的极小点，初始点x0=0,步长h=1,精度ε=0.2。解：1）确定初始区间x1=x0=0,f1=f(x1)=2x2=x0+h=0+1=1f2=f(x2)=1由于f1>f2,应继续向前探测x3=x0+2h=0+2=2f3=f(x3)=18由于f2

8、0+0.618×(2-0)=1.236