62一维搜索1118

1、第九章 一维搜索9.19.1、一维搜索的基本概念、一维搜索的基本概念 下降方向下降方向： nep 0设， 若存在 ，使得当 时，有 ，则称 为 在处的下降方向下降方向。00)()(000xfdxf0d)(xf0x下降迭代法的基本思想下降迭代法的基本思想 ：若该点的序列收敛于 ，在一定条件下， 就是极点。 *x*x下降迭代算法步骤下降迭代算法步骤（1）给出初始点）给出初始点0 x，令，令0 k；（2）按照某种规则确定下降搜索方向）按照某种规则确定下降搜索方向kd；（3）按照某种规则确定搜索步长）按照某种规则确定搜索步长k ，使得，使得)()(kkkkxfdxf ；（4）令）令kkkkdxx 1，

2、1: kk；（5）判断）判断kx是否满足停止条件。是则停止，否则转第是否满足停止条件。是则停止，否则转第2步。步。搜索步长确定方法：搜索步长确定方法：)(min)(kkkkkdxfdxf 称称0)( ktkkkddxf 。k 为最优步长，且有为最优步长，且有终止条件终止条件)(31kkkkxxxx)(41kkkkxfxfxfxf1111)()()(kkkkkkxfxfxfxxx22)(kkxxf1111)()(kkkkxfxfxx2.4.1.11kkxx21)()(kkxfxf3.5.最可靠法则最可靠法则：收敛速度收敛速度则称则称 的收敛阶为的收敛阶为 。设算法设算法a所得的点列为所得的点列为

3、kx，如果，如果,|*1 xxxxkk .0, kx)0(,kkkkdxdx在射线再找一个搜素下降方向给定点等价于求一元函数找一个下降的点).()(,11kkkkkkxfxfdxx)()(kkdxf的极值问题，即)()(min0kkdxf,k若极值点为)(min0长。故称的步长因子，简称为步为沿方向称kkd为一维搜索。.)2(kkd的步长因子沿方向上述下降算法关键在于求：(1)给定点的下降方法dk为一个下降方向。则若kktkddxf, 0)() 1 (为函数逼近法。一类是试探法；另一类方法大体分为两类：求步长因子k)2(题即求解一元函数极值问求步长因子,k)()(min0kkdxf.) 1 (

4、视极值点逐步缩小，最后得到近将这个区间到极值点所在的区间，比较它们的函数值，得些试探点，按照一定的方法找出一试探法的基本思想是：的极值点。作为将的极值点通过求，的逼近函数是找函数逼近法的基本思想)(min,)()()()2(0kk进退法等法；法；常用方法有)3()2(618. 0) 1 (fibonacci抛物线法等割线法；牛顿法；常用方法有)3()2() 1 (下降迭代算法的框图。 给出初始点 x0及，并置 k=0 计算梯度f(xk) 满足停止准则否？ 确定 xk处的下降方向 dk 确定k,计算下降点 xk+1=xk+dk k=k+1 得极小点 xk 结束 是 否 9.1. 一维搜索问题一维

5、搜索问题下降迭代算法中最优步长的确定下降迭代算法中最优步长的确定)(min)(kkkkkdxfdxf .kxkd.k 一维最优化问题：一维最优化问题：)(minxfrxts .极值点的必要条件：极值点的必要条件：0)( xf 第第2节节 一维搜索算法一维搜索算法 一、单峰函数及性质一、单峰函数及性质 设 是定义在闭区间 上的一元实函数， 是 在 上的极小点，并对任意的 ，且 ，满足: 当 时， ；当 时， ，则称 是闭区间 上的单峰函数单峰函数。)(xf,baxf,ba,21baxx21xx xx 2)()(21xfxf1xx )()(21xfxff,ba例如图6-11 中（a）是单峰函数，（

6、b）不是单峰函数。 (a) (b)1. 单峰函数单峰函数定义定义：设：设)(xf是区间是区间,ba上的一元函数，上的一元函数，x是是)(xf在在,ba上的极小点，且对任意的上的极小点，且对任意的, ,2121xxbaxx 有有（a）当当xx 2时，时，; )()(21xfxf （b）当当时，时，xx 1. )()(21xfxf a.b.x.1x2x则称则称 是单峰函数。是单峰函数。)(xf.性质：通过计算区间性质：通过计算区间,ba内两个不同点的函数值，就可以内两个不同点的函数值，就可以确定一个包含极小点的子区间。确定一个包含极小点的子区间。推论设设是区间是区间,ba上的一元函数，上的一元函数

7、，x是是)(xf在在,ba上的极小点。任取点上的极小点。任取点)(xf, ,badc 则有则有（1）如果）如果)()(dfcf ，则，则; ,bcx （2）如果）如果, )()(dfcf 则则。,dax a.b.x.cd2. 黄金分割法黄金分割法思想通过选取试探点使包含极小点的区间不断缩短，通过选取试探点使包含极小点的区间不断缩短，直到区间长度小到一定程度，此时区间上各点的函数直到区间长度小到一定程度，此时区间上各点的函数值均接近极小值。值均接近极小值。下面推导黄金分割法的计算公式。下面推导黄金分割法的计算公式。上单峰，上单峰，在在设设,)(11baxf.,11bax 极小点极小点假设进行假设

8、进行次迭代前次迭代前第第 k,kkbax ,kkkkba 取取规定规定.kk , )()(kkff 和和计计算算分两种情况：分两种情况：, )()(. 1kkff 若若,1kka 则令则令;1kkbb , )()(. 2kkff 若若,1kkaa 则令则令.1kkb ？与与如何确定如何确定kk kkkkab . 1比率相同，即比率相同，即每次迭代区间长度缩短每次迭代区间长度缩短. 2)0()(11 kkkkabab)1()2(）可得：）可得：）与（）与（由式（由式（21 )()(1(kkkkkkkkabaaba )3()4(件：件：要求其满足以下两个条要求其满足以下两个条kakbk ku？取值

9、的确定取值的确定 通过确定通过确定 的取值，使上一次迭代剩余的迭代点恰与下一次迭代的一个迭代点的取值，使上一次迭代剩余的迭代点恰与下一次迭代的一个迭代点重合，从而减少算法的计算量。重合，从而减少算法的计算量。 , )()()1(kkuffk 次迭代时有次迭代时有设在第设在第则有则有。,11kkkkuaba ,111k kuk 次迭代时选取次迭代时选取在第在第）有）有则由（则由（4)(1111 kkkkabau )(2kkkaba 。不必重新计算不必重新计算因此因此则则，如果令如果令112,1 kkkuu 618. 021512 。次迭代时有次迭代时有若在第若在第)()()2(kkuffk 同理

10、可得。同理可得。9.2.1-19.2.1-1、黄金分割法（、黄金分割法（golden section methodgolden section method）计算步骤）计算步骤 黄金分割法的基本思想是：通过取试探点使包含极小点的区间（不确定区间）不断缩短，当区间长度小到一定程度时，区间上各点的函数值均接近极小值，因此任意一点都可作为极小值点的近似。 黄金分割法计算公式 )(618. 0)(382. 0kkkkkkkkabaaba黄金分割法又称0.618法 算法步骤：算法步骤：0.,. 111 精度要求精度要求给定初始区间给定初始区间ba. 1: k令令),(382. 01111aba 令令),

11、(618. 01111aba ).()(11 ff与与并计算并计算,. 2 kkab若若停止，停止，.2kkabx 且且否则，否则，；时，转时，转当当3)()(kkff . 4)()(时，转时，转当当kkff ,. 31kka 令令,1kkbb ,1kk ),(618. 01111 kkkkaba ),(1 kf 计算计算。转转 2,. 41kkaa 令令,1kkb ,1kk ),(382. 01111 kkkkaba ),(1 kf 计算计算, 1: kk令令。转转 2, 1: kk令令黄金分割法的迭代效果：第黄金分割法的迭代效果：第k次后迭代后所得区间长度为次后迭代后所得区间长度为初始区间

12、长度的初始区间长度的。倍倍k)215( 其它的试探点算法：其它的试探点算法：fibonacci算法。算法。例例9.2.1 用0.618法求解下列问题 初始区间 =-1，1，精度12)(min2xxxf,11ba16. 0解解 易于验证)(xf是单峰函数，且-1，1为极小值所在区间。 按上面的计算步骤，经 6 次迭代后，16. 0111. 077 ab，满足精度要求，极小点 所 在 区 间 为279. 0 ,168. 0， 取23. 0)279. 0168. 0(21x。实际上，问题的精确解25. 0*x。计算过程见表 6-1。 表表 6-1 k ka kb k k )(kf )(kf 1 -1

13、 1 -0.236 0.236 -0.653 -1.125 2 -0.236 1 0.236 0.528 -1.125 -0.970 3 -0.236 0.528 0.056 0.236 -1.050 -1.125 4 0.056 0.528 0.236 0.348 -1.125 -1.106 5 0.056 0.348 0.168 0.236 -1.112 -1.125 6 0.168 0.348 0.236 0.279 -1.125 -1.123 7 0.168 0.279 nfunction x,eval=gold(a,b)epsilon=10-4;a1=a;a3=b;x=a1+0.38

14、2*(a3-a1);y=a1+0.618*(a3-a1);f1=liti1(x);f2=liti1(y);while abs(y-x)=epsilon if f1f2 a1=x; x=y; y=a1+0.618*(a3-a1); f1=f2; f2=liti1(y); else a3=y; y=x; f2=f1; x=a1+0.382*(a3-a1); f1=liti1(x); endendxyxmin=0.5*(x+y);fmin=liti1(xmin);x=xmin;eval=fmin;例题1 用0.618法求解下列问题精度16. 0初始区间1 , 1,11 ba12)(min2xxxfx

15、,eval=gold(-1,1)x = 0.25008293838988eval = -1.12499997236155解：利用0.618法程序 x,eval=gold(a,b)求解所给函数在区间a,b上的极小值，运行程序得：的图形的图形下面画出函数下面画出函数12)(2 xxxfx=-1:0.001:1;f=2*x.2-x-1;plot(x,f)hold ongrid on-1-0.8-0.6-0.4-0.200.20.40.60.81-1.5-1-0.500.511.520.150.20.250.30.35-1.3-1.25-1.2-1.15-1.1-1.05-1-0.95由图形可以看出最

16、优解为x=0.25分数法,又称fibonacci法。该方法与黄金分割法类似，用于单峰函数，在计算过程中，也是第一次需要计算两个试点，以后每次迭代只需新算一点，另一点取自上次迭代。fibonacci法与黄金分割法的主要区别有两点：其一，需先计算出迭代次数 ；其二，区间收缩的比率不是常数，它由fibonacci数列确定的。9.2.2、分数（、分数（fibonacci）法）法 设有数 列满足条件：，则称 为fibonacci数列， kf, 2 , 111110kfffffkkkkf012345678911121123581321345589144233如表6-2所示。表表6-26-210分数法计算试

17、点的公式： （6-1）其中迭代次数 不包括初始区间端点的计算。)()(111kkknknkkkkknknkkabffaabffa1, 2 , 1nkn经过 次迭代后得到的区间长度：1n )(1121nnnnabffab)(1113221abffffffnn)(111abfn(1) 给定初始区间,11ba（要保证函数在该区间上是单峰的） 及精度要求0 ；计算迭代次数 n，使11abfn； 置辨别常数0；按公式 6-17 计算试点1和1， 计算函 数值)(1f和)(1f；令k=1。 (2) 若)()(kkff时，转第（3）步；否则，转第（4）步。 (3) 置 kkkkkkbba111, )(111

18、11kkknknkkabffa若2 nk，则转第（6）步； 否则，计算函数值)(1kf,转第（5）步。 fibonacci法的计算步骤如下法的计算步骤如下：（4）置kkkkkkbaa111, )(11211kkknknkkabffa 若2 nk，则转第（6）步；否则，计算函数值)(1kf， 转第（5）步。 （5）置1 kk，返回第（2）步。 （6）令11,nnnn，计算)(nf和)(nf。 若)()(nnff，则令1,nnnnbba； 否则令nnnnbaa,1，停止计算，极小点含于,nnba ，可取其中点或函数值较小的端点作为近似极小点。 分数法的区间收缩比率的极限 618. 0lim1nnn

19、ff例例9.2.2 试用斐波那契法求函数 的近似极小点和极小值，要求缩短后的区间不大于初始区间-1，3的0.08倍。2)(2xxxf解解 容易验证： 在此区间上函数2)(2xxxf为单峰函数。 为了进行比较， 我们给出其精确解75. 1)(, 5 . 0*xfx。 3, 111ba，5 .1208. 0/1,08. 0)1(3(nf，查表 6-2，; 6n 462. 1) 13(1381)(538. 0) 13(1351)(116511116411abffaabffa 675. 22462. 1462. 1)(751. 12538. 0538. 0)(2121ff 由于)()(11ff，故取5

20、38. 0,462. 1, 1222ba 083. 22)077. 0()077. 0()(077. 0) 1462. 1 (831)(22225322fabffa 进退法，又称成功失败法，其基本思想是： 从某一点出发，任选一个方向和步长，向前试探性走一步，求出该点的函数值。如果有利（指该点函数值较小），就向前走一步，并加大步长再向前试探一步； 否则，就缩小步长反方向（后退方向）试探一步。如此反复搜索，当步长缩小到一定程度时停止。最后确定高-中-高的三点，中间点即为近似极值点。9.2.4、进退法、进退法例例9.2.4 试用进退法求下列一维优化问题 12)(min3 xxxf2, 1000 th

21、x，搜索区间取0, 1, 1, 0000 kfhx解：解： 步步1 初始化初始化第一次搜索第一次搜索3, 0, 10111转步转步fffx 次搜索次搜索进行第进行第加步搜索加步搜索2, 1, 0, 1, 0,20001 kfxxhh步2 步3第二次搜索22, 3222 fx步步4312转步转步步步ff 0,min, 042 xxak步步 3,max2 xxb得到最小值所在区间0,3-2-1.5-1-0.500.511.52-3-2-1012345画函数a=-2:0.001:2;b=a.3-2*a+1;plot(a,b)12)(3 xxxf由图形可以看出，极由图形可以看出，极小值点在区间小值点在

22、区间0,3中中9.39.3、函数逼近法、函数逼近法1. 牛顿法（牛顿法（newton method）牛顿法的基本思想是：在估计点 附近使 线性化，并求出该线性函数的零点。用该零点作估计 点。 kx)(xf 1kx迭代公式为 )()(1kkkkxfxfxx 牛顿法的计算步骤如下：（1）给定初始点0 x及允许误差0，置0k. （2） 若)(kxf， 则停止迭代， 得到极小点kx. （3）计算点 )()(1kkkkxfxfxx ，置1: kk，转第（2）步。 2. 割线法（割线法（secant method） 割线法的基本思想：用割线逼近目标函数的导数曲线 ，把割线 的零点作为目标函数驻点的估计。)

23、(kxfy迭代公式为 )()()(111kkkkkkkxfxfxfxxxx设 存在连续三阶导数， 满足 且 ，若 充分接近 ，则割线法产生的序列 收敛于 ， 且收敛阶为1.618。)(xfx0)( xf0)( xf21,xxx kxx关于割线法的收敛性，有下面的结论， 3. 抛物线法（抛物线法（parabolic method） 抛物线法的基本思想是：在极小点附近，用二次三项式逼近目标函数)(xf，令)(x与)(xf在321xxx三点处有相同的函数值，并假设)()(, )()(3221xfxfxfxf， 令cbxaxx2)(，用代定系数法可求得 )()()()()()()()(13322132

24、1213132xxxxxxxfxxxfxxxfxxa )()()()()()()()(133221322212212312322xxxxxxxfxxxfxxxfxxb 为求)(x得极小点，令02)(baxx，得)(x得驻点，记作x )()()()()()()()()()()()(21321213132322212212313322xfxxxfxxxfxxxfxxxfxxxfxxx 把x作为)(xf极小点的一个估计。 现从 4点中找出最小点，并以这点作为新的x2,并记为x(k)其左右两点分别作为新的x1和x3，继续迭代,直到 满足xxxx321, )()1(kkxx为允许误差 抛物线法的计算步骤

25、：抛物线法的计算步骤：4. 三次插值法（三次插值法（cubic interpolation method） 两 点 三 次 插 值 法 的 基 本 思 想 是 ： 取 两 个 初 始 点1x和2x)(21xx ， 使得0)(1 xf及0)(2 xf， 则区间),(21xx内存在极小点。构造一个三次多项式 dxxcxxbxxax)()()()(12131 使得 )()()()()()()()(22112211xfxxfxxfxxfx 用这个多项式)(x的极小点x作为)(xf极小点的一个估计。 迭代公式 （6-18） )2)()()(1)(122121wxfxfwvxfxxxx)()()()( 3

26、211212xfxfxxxfxfv)()(212xfxfvw其中00.511.5-0.200.20.40.60.811.21.4f(x)=x3-2x+1函数f(x)=x3-2x+1的图像a=0:0.001:1.5;y=a.3-2*a+1;plot(a,y)grid onsqrt(2/3)ans =0.816496580927最优解为x=0.816496两点三次插值法的计算步骤是：（1） 给定允许误差 ，及初始点 ，计算 、 、 及 ，要求满足条件 及 。（2） 按公式（6-18）计算 。（3） 若 ，或者 时，停止计算，得 到极小点 ；否则，转向第（4）步。（4） 计算 。若 ，则令 ；否则

27、令 转向第（2）步。021xx )(1xf)(2xf)(1xf )(2xf 0)(1 xf0)(2 xfx|12xx0)( xfx)(),(xfxf0)( xfxx 1xx 2例例6-7 求函数 的极小点和极小值。解解 方法1：用牛顿法求解 取初始点 ， ，经过3次迭代,得极小 点为， 极小值为 。 xexfx5)(1x001. 0609438. 1* x04719. 3)(*xf方法 2：用割线法求解 取初始点5, 010 xx，0001. 0，经过 9 次迭代,得极小点为609429. 1*x，极小值为04719. 3)(*xf。中间结果略。 方法 3：用抛物线法求解 取初始点4, 2, 0321xxx，0001. 0，经过 4 次迭代,得极小点为60744. 1*x，极小值为04718.