03一维搜索方法

1、1第三章一维优化方法一维优化方法2 数值迭代算法的过程可表示为：数值迭代算法的过程可表示为： 当搜索方向一定后，目标函数成为当搜索方向一定后，目标函数成为k的一元函数，即在直的一元函数，即在直线上求函数的极小点，这种运算过程称为一维搜索，或线性搜线上求函数的极小点，这种运算过程称为一维搜索，或线性搜索索(linear search)。v一维优化问题是基础，大多数多维问题可以是一系列一维一维优化问题是基础，大多数多维问题可以是一系列一维问题的搜索。问题的搜索。v一维优化方法可分为两类：直接法和解析法一维优化方法可分为两类：直接法和解析法)()()1()()()()(xx)x()x(minkkkk

2、kkkkkssfsf ks kx ks1kx33.1 3.1 确定初始区间的进退法确定初始区间的进退法 首先保证搜索区间函数具有单峰性，也就是在区间首先保证搜索区间函数具有单峰性，也就是在区间a, b中，函数是凸函数，具有高中，函数是凸函数，具有高低低高或低高或低高高低的特性，在区间低的特性，在区间a, b上有惟一的极小值或极大值。上有惟一的极小值或极大值。 1.1.基本思想基本思想x)(xfiii1a2a3a42.2.程序流程图程序流程图初始步长初始步长h取的过大，有取的过大，有可能出现不收敛的情况，可能出现不收敛的情况，初始步长值一般应给出较初始步长值一般应给出较小的值，如取收敛精度的小的

3、值，如取收敛精度的1010倍左右。倍左右。53.2 3.2 黄金分割法黄金分割法( (golden section method) ) 1.1.基本思想基本思想 黄金分割法是通过不断缩短单峰区间的长度来搜索黄金分割法是通过不断缩短单峰区间的长度来搜索极小点的一种有效方法，它是搜索区间按比例缩小，极小点的一种有效方法，它是搜索区间按比例缩小，通过计算和比较函数值，以确定取舍区间，因按黄通过计算和比较函数值，以确定取舍区间，因按黄金分割原理，故此法又称金分割原理，故此法又称0.6180.618法。法。n区间变化图区间变化图: :abcd)(a)(babcd)(cabcd6n黄金分割比例黄金分割比例

4、=0.6180.618n黄金比例应用广泛黄金比例应用广泛 2.2.迭代公式及迭代过程迭代公式及迭代过程 c=a+0.382(b-a) d=a+0.618(b-a) xfaxcdb终止条件：终止条件：(b-a)ex*=(a+b)/2 xfaxc)(cd)(dbf(c)f(d)(dc xf)(caxdbf(c)f(d)7 3.3.程序流程图程序流程图83.3 3.3 牛顿法牛顿法 (newtons method) 一一. .基本思想基本思想 牛顿法在一维探索中的应用，是用切线代替弧逐渐牛顿法在一维探索中的应用，是用切线代替弧逐渐逼近函数根值的方法。当目标函数逼近函数根值的方法。当目标函数f (x)

5、有一阶连续导有一阶连续导数且二阶导数大于零时，在曲线数且二阶导数大于零时，在曲线y= = f (x)上作一系列上作一系列切线，使之与切线，使之与x轴的交点轴的交点x(0)(0), , x(1)(1), , x(3)(3), , , ,逐渐趋逐渐趋于于f (x)=0的根。的根。)(xf )()0()0(xfx*x)2(xxa) 1 (x)0(xbo9 二二. .迭代公式迭代公式 三三. .程序流程图程序流程图 )()()( )()(1kkkkxfxfxx 四四. .特点特点 1.1.牛顿法的优点是收敛快，牛顿法的优点是收敛快，尤其在开始的时候。尤其在开始的时候。 2.2.需计算函数的一阶、二需计

6、算函数的一阶、二阶导数，因而增加了每次迭代阶导数，因而增加了每次迭代的工作量。的工作量。 3.3.另外另外, ,要求初始点选择不要求初始点选择不能离极值点太能离极值点太“远远”。 103.4 3.4 二次插值法二次插值法 (quadratic interpolation method) 一一. .基本思想基本思想 插值法是多项式逼近法的一种。是利用目标函数在若干点的插值法是多项式逼近法的一种。是利用目标函数在若干点的信息（包括函数值、导数值等），构成一个与原目标函数值相信息（包括函数值、导数值等），构成一个与原目标函数值相接近的低次插值多项式，然后用该多项式的最优解作为函数的接近的低次插值多项

7、式，然后用该多项式的最优解作为函数的近似最优解，随着区间的逐次缩短，多项式函数的最优点与原近似最优解，随着区间的逐次缩短，多项式函数的最优点与原函数的最优点之间的距离渐减小，直到满足一定的精度要求时函数的最优点之间的距离渐减小，直到满足一定的精度要求时迭代终止。迭代终止。 二、二次插值法的公式推导二、二次插值法的公式推导 二次插值法是用区间二次插值法是用区间a, b上的三个点的函数值构成二次多上的三个点的函数值构成二次多项式去逼近原函数，项式去逼近原函数，如果函数性态接近抛物线，能够比较快的如果函数性态接近抛物线，能够比较快的收敛，也称收敛，也称抛物线法抛物线法。 11 xf xp xp xf

8、2xmx3xxo1x*x 目标函数在三个点目标函数在三个点x1, x2, x3的函数值为的函数值为f1, f2, f3满足满足 x1x2f2 f3 利用利用x1, x2, x3三点作二次多项式三点作二次多项式 p(x)=a0+a1x+a2x2 式中式中, a0,a1,a2为待定系数。为待定系数。332323103222222102112121101)()()()()()(fxfxaxaaxpfxfxaxaaxpfxfxaxaaxp)()()()()()()()()()(13322121313232121332212221321232232211xxxxxxxxfxxfxxfaxxxxxxxxf

9、xxfxxfa12 插值多项式插值多项式p(x) 的极值点满足的极值点满足 p (x)=a1+2 a2x=0 可求得极小点可求得极小点 代入代入a1,a2可得到可得到 三、迭代过程及程序框图三、迭代过程及程序框图 四、其它插值法四、其它插值法 元代朱世杰的插值公式：元代朱世杰的插值公式： f(nf(n)=n)=n+n(n-1)+n(n-1)2 2+n(n-1)(n-2)+n(n-1)(n-2)3 3+n(n-1)(n-2)(n-+n(n-1)(n-2)(n-3)3)4 4+ 212aaxm)()()( 2213132321222132123223221xxfxxfxxfxxfxxfxxfxm13 五、一维搜索方法的比较五、一维搜索方法的比较 牛顿法收敛快牛顿法收敛快, ,但要求其一阶、二阶导数但要求其一阶、二阶导数, ,对初始点的选择要对初始点的选择要求较高求较高; ;二次插值法充分利用了函数的性态二次插值法充分利用了函数的性态, ,如目标函数本身就如目标函数本身就具有良好的性质具有良好的性质( (如二次，三次曲线等如二次，三次曲线等) )能够很快的收敛能够很