工程优化敏第三章

1、第三章第三章 常用的一维搜索算法常用的一维搜索算法1 搜索算法概述搜索算法概述2 0.618法（黄金分割法）法（黄金分割法）3 “成功成功-失败失败”法法4 牛顿法牛顿法5 插值法插值法 设设 (1) (1) 为为D的一个内点的一个内点; ; (2) (2) 在在 可微可微; ; (3) (3) 为为 的极值点的极值点; ; 则则 。:nfDRR 0f x ( )f xx 求无约束的某可微函数的最优解，求无约束的某可微函数的最优解，根据一阶必要条件，根据一阶必要条件，可令函数的梯度等于零，由此求得驻点；可令函数的梯度等于零，由此求得驻点；然后用充分条件进行判别，求出所要的解然后用充分条件进行判

2、别，求出所要的解:nfDRR n元函数元函数min( )nx Rf x 求解无约束优化问题求解无约束优化问题x x ( )f x 设设 (1) (1) 为为D D的一个内点的一个内点; ; (2) (2) 在在 二次连续可微二次连续可微; ; (3) ; (3) ; (4) (4) 正定正定; ;则则 为为 的严格局部极小点。的严格局部极小点。:nfDRR 2f x ( *)0f x ( )f xx ( )f xx x 对某些较简单的函数，这样做有时是可行的；对某些较简单的函数，这样做有时是可行的； 但对一般但对一般n元函数元函数 f(x) 来说，由条件来说，由条件 得到的是一得到的是一个非线

3、性方程组，解它相当困难。个非线性方程组，解它相当困难。 对于不可微函数，当然谈不上使用这样的方法。对于不可微函数，当然谈不上使用这样的方法。 为此，常直接使用迭代法。为此，常直接使用迭代法。( )0f x0 x10( )( )f xf xkx，*x ，*lim0kkxx ，为了求函数为了求函数f(x)的最优解，的最优解，然后按某种规划然后按某种规划(即算法即算法)找出比找出比更好的解更好的解再按此种规则找出比再按此种规则找出比更好的解更好的解如此即可得到一个解的序列如此即可得到一个解的序列若这个解序列有极限若这个解序列有极限则称它收敛于则称它收敛于x*。 若算法是有效的，则它产生的解序列收敛于

4、该问题的最优解。若算法是有效的，则它产生的解序列收敛于该问题的最优解。 计算机只能进行有限次迭代，一般很难得到准确解，而只能得计算机只能进行有限次迭代，一般很难得到准确解，而只能得到近似解。当达到满足的精度要求后，即可停止迭代。到近似解。当达到满足的精度要求后，即可停止迭代。0 x1x，1x2x ，首先给定一个初始估计首先给定一个初始估计x* ( )( *)f xf x ，*.xx根据相继两次迭代的结果根据相继两次迭代的结果（1）根据相继两次迭代的绝对误差）根据相继两次迭代的绝对误差（2）根据相继两次迭代的相对误差）根据相继两次迭代的相对误差（3）根据目标函数梯度的模足够小根据目标函数梯度的模

5、足够小11()(),kkkkf xf xxx11()(),()kkkkkkf xf xxxf xx()kf x011*(1)kkxxxx101 设序列设序列 收敛于收敛于 ，若存在与迭代次数，若存在与迭代次数 k 无关的数无关的数时，称超线性收敛。时，称超线性收敛。时，称线性收敛或一阶收敛。时，称线性收敛或一阶收敛。 成立，就称成立，就称 收敛的阶为收敛的阶为 ，或者称，或者称 阶收敛。阶收敛。 kx*x 和和 ，使，使k从某个从某个k0开始，都有开始，都有 kx kx当当12当当 ，且，且具有二阶收敛速度。具有二阶收敛速度。 kx当当2时，称为二阶收敛，也可说时，称为二阶收敛，也可说找初始点

6、找初始点判断当前点是否满判断当前点是否满足终止条件足终止条件找下一个迭代点找下一个迭代点最优解最优解(a) 找初始点找初始点(b) 终止条件终止条件(c) 迭代格式迭代格式从当前点出发，按照某从当前点出发，按照某种规则找下一个迭代点种规则找下一个迭代点是是否否循循环环可行算法：所有迭代点都是可行点据迭代点的可行性 11,()(),()(),()()下降：根据目标函数的下降特性非单调下降算法：算法kkkkkkk lkk f xf xk f xf xlf xf x 不可行算法： 至少有一个迭代点不是可行点直接法：不需要导数信息根据是否计算目标函数和约束函数的导数： 需要导数信息非直接法 ： 迭代点

7、沿某方向产生根据迭代点是否沿某个方向产生信赖域方法： 迭代点在某区域内搜索产线搜索方法生 kx现假定已迭代到点现假定已迭代到点则从则从都不能使目标函数值下降。都不能使目标函数值下降。若若 是一局部极小点，是一局部极小点， 若从若从 出发至少存在一个方向出发至少存在一个方向可使目标函数值有所下降，可使目标函数值有所下降，图图 1 出发沿任何方向移动出发沿任何方向移动,kxkxkd,kx如图如图1示示1kx1()( )kkf xf xkkxxd1kkkkxxdkdk 若从若从 出发至少存在一个方向出发至少存在一个方向 可使目标函数值有所下可使目标函数值有所下降，可选定这个方向降，可选定这个方向 ，

8、 这相当于在射线这相当于在射线其中，其中，称为搜索方向；称为搜索方向；称为步长或步长因子。称为步长或步长因子。图图 1kxkd 沿这个方向迈进适当的一步，得到下一个迭代点沿这个方向迈进适当的一步，得到下一个迭代点 ，使使 。上选定新点上选定新点kd0 x:0;k ;kdkxk1;kx:1kk(1) 选定某一初始点选定某一初始点，并令，并令(2) 确定搜索方向确定搜索方向(3) 从从出发，沿方向出发，沿方向求步长求步长，以产生下一个迭代点，以产生下一个迭代点(4) 检查得到的新点检查得到的新点是否为极小点或近似极小点。是否为极小点或近似极小点。，转回，转回(2)继续进行迭代。继续进行迭代。 在以

9、上步骤中，选取搜索方向在以上步骤中，选取搜索方向是最关键的一步。是最关键的一步。 各种算法的区分，主要在于搜索方向各种算法的区分，主要在于搜索方向 的不同的不同。 若是，则停止迭代。若是，则停止迭代。否则，令否则，令kd1kxkd找初始点找初始点判断当前点是否满判断当前点是否满足终止条件足终止条件下一个迭代点下一个迭代点 最优解最优解(a) 找初始点找初始点(b) 终止条件终止条件(c) 迭代格式迭代格式是是否否循循环环1kkkkxxdkkd1kxkdkd各种算法的区各种算法的区 分，主要在于确定搜索方向的方法不同。分，主要在于确定搜索方向的方法不同。 后面介绍各种后面介绍各种 算法时会给出一

10、个明确的选取算法时会给出一个明确的选取 的方法。的方法。kdkd k(1) 令它等于某一常数令它等于某一常数(例如令例如令1k)，这样做不能保证目标，这样做不能保证目标函数值下降。函数值下降。(2) 第二种称为可接受点算法，只要能使目标函数值下降，可第二种称为可接受点算法，只要能使目标函数值下降，可 任意选取步长。任意选取步长。 : argmin ()kkkf xd()kkf xdk求目标函数求目标函数 f(x) 的极小：的极小：这项工作是求以这项工作是求以 为变量的一元函数为变量的一元函数的极小点的极小点，故常称这一过程为，故常称这一过程为（精确）一维搜索或（精确）一维搜索或（精确）线搜索或

11、一维最优化（精确）线搜索或一维最优化，确定的步长为，确定的步长为。 (3) 第三种方法的思路是：沿搜索方向使目标函数值下降最多，第三种方法的思路是：沿搜索方向使目标函数值下降最多， 即沿射线即沿射线kkxxd( )f x1kx1argmin ()kkkkkkkf xdxxd1 T()0.kkf xd 设目标函数设目标函数具有一阶连续偏导数，具有一阶连续偏导数，规则产生规则产生则有则有按下述按下述函数函数 ，则得，则得( )()kkf xd min k0( )k( ) k+1 T().kkf xd ()kT()kkkkf xdd (1) 试探法：按某种方式找试探点，通过比较一系列试探点的函试探法

12、：按某种方式找试探点，通过比较一系列试探点的函 数值的大小确定极小点。数值的大小确定极小点。(2) 区间收缩法：用某种分割技术缩小最优解所在的区间区间收缩法：用某种分割技术缩小最优解所在的区间(称称 为搜索区间为搜索区间)。(3) 函数逼近法：用比较简单函数的极小值点近似代替原函数的函数逼近法：用比较简单函数的极小值点近似代替原函数的 极小值点。从几何上看是用比较简单的曲线近似代替原极小值点。从几何上看是用比较简单的曲线近似代替原 来的曲线，用简单曲线的极小值点代替原曲线的极小点。来的曲线，用简单曲线的极小值点代替原曲线的极小点。 Newton法、二次插值法、三次插值法法、二次插值法、三次插值

13、法“成功成功-失败失败”法法二分法、二分法、0.618法法第三章第三章 常用的一维搜索算法常用的一维搜索算法1 搜索算法概述搜索算法概述2 0.618法（黄金分割法）法（黄金分割法） 3 “成功成功-失败失败”法法4 牛顿法牛顿法5 插值法插值法 常用的区间收缩法主要利用常用的区间收缩法主要利用单峰函数的消去性质单峰函数的消去性质，从某个，从某个初始搜索区间出发，逐步缩小搜索区间，直到满足精度要求初始搜索区间出发，逐步缩小搜索区间，直到满足精度要求为止。为止。：设设 f(x) 是定义在是定义在a, b上的函数，若上的函数，若 1） x* a, b 是是f(x)在在a, b上的最小点上的最小点

14、， 2） 若对任意若对任意 x1 , x2, a x1 f (x2); 2 若若x* x1 ，则，则 f (x1) f (x2).则称则称 f(x) 为为a, b上的单峰函数。上的单峰函数。 f(x)xab连续单峰函数f(x)xab不连续单峰函数f(x)xab离散单峰函数f(x)xa b非单峰函数定理：定理：设设f(x)是区间是区间a,b上的一个单峰函数，上的一个单峰函数，x*a,b是其极小点，是其极小点， x1 和和x2是是a, b上的任意两点，且上的任意两点，且ax1 x2b，那么比较，那么比较f(x1)与与f(x2)的值后，可得出如下的值后，可得出如下结论：结论：f(x)xab(I) 消

15、去a, x1 x*x1x2f(x)xab(II) 消去x2, bx*x2x1(II) 若f(x1) f(x2), x*a,x2在单峰函数的区间内，计算两个点的函数值，比较大小后，就能把搜索区在单峰函数的区间内，计算两个点的函数值，比较大小后，就能把搜索区间缩小。在已缩小的区间内，仍含有一个函数值，若再计算另一点的函数间缩小。在已缩小的区间内，仍含有一个函数值，若再计算另一点的函数值，比较后就可进一步缩小搜索区间值，比较后就可进一步缩小搜索区间 . .（I） 若f(x1)f(x2)，x*x1,b单峰函数具有一个重要的消去性质单峰函数具有一个重要的消去性质 通过上述定理：通过上述定理： 1去坏留好

16、原则：去坏留好原则：选二点选二点 x1 x2 , 比较比较 f (x1 ) 与与 f (x2 ) ,可去掉可去掉 a , x1 或者或者x2 , b. 2对称原则：对称原则： x1 a = b- x2 (1) （使（使“坏坏”的情况去掉，区间长度不小于的情况去掉，区间长度不小于“好好”的情况）的情况） 3保持缩减比原则保持缩减比原则 t =(保留的区间长度原区间长度保留的区间长度原区间长度) 不变。不变。 （使每次保留下来的节点，（使每次保留下来的节点， x1或或 x2 ，在下一次的比较中成，在下一次的比较中成 为一个相应比例位置的节点为一个相应比例位置的节点 ）。）。 推导缩减比推导缩减比

17、t : 如图设第一次保留如图设第一次保留a, x2 (去掉去掉x2 , b), 第二次保第二次保留的长度为留的长度为a, x1 , 则则 x1 x2 b212(2)xaxatbaxa1x2xab1x，2x，a2x为了简化计算，使得计算为了简化计算，使得计算量减少，我们希望已经计量减少，我们希望已经计算的迭代点可以在下次迭算的迭代点可以在下次迭代的时候重复利用。代的时候重复利用。1212, xxxxab21xabxtbaba12(1)()()xat baxat ba12122, xxxxax，1222(1)()()xat xaxat xa，(1) ()at t ba2()at ba11xx，若2

18、1xx，若 (1) ()(1)()t t bat ba 1t5 1 0.6182t2 ()(1)()t bat ba（不满足要求）（不满足要求）x1 = a+(1-t)(b-a)=a+0.328(b-a)x2 = a+t(b-a)= a+0.618(b-a)当区间当区间的长度充分小时，可将的长度充分小时，可将区间区间中点取做极小点的近似中点取做极小点的近似点。点。 步骤步骤1：给定初始区间：给定初始区间a,b及允许误差及允许误差 ，根据公式计算，根据公式计算x1和和 x2 以及以及f(x1)和和f(x2 )；步骤步骤2：若：若b-af(x2 )时，转步时，转步3，当，当f(x1)0 2/ )

19、15(tx1 = + （1- t）(b - )x2 = +t (b - )b - 0?No= x1 , x1 = x2 x2 = +t ( b )yesb= x2 , x2 = x1x1 = + （1-t）( b - )No x1 x2 b x2 b x1 x2 b x1 优点：不要求函数可微，且每次迭代只需计算一优点：不要求函数可微，且每次迭代只需计算一 个函数值，计算量小，程序简单个函数值，计算量小，程序简单缺点：收敛速度慢。缺点：收敛速度慢。黄金分割法（黄金分割法（0.618 法）的优缺点法）的优缺点 ：试用试用0.618法求目标函数法求目标函数 的最优解。的最优解。 给定初始区间给定初

20、始区间0,2，收敛精度，收敛精度第一次区间缩短计算过程：第一次区间缩短计算过程：计算两点及对应函数值：计算两点及对应函数值： 作数值比较，可见作数值比较，可见 ,再做置换：再做置换：3( )21f xxx2:1.236,bx=0.002.0,2ab10.382()0.764,xaba1 ()0.0821, f x20.618()1.236,xaba2()0.4162,f x12()()f xf x1.2360.002ba20.764,x2 ()0.0821, f x , 0,1.236,a b第二次区间缩短计算过程：第二次区间缩短计算过程： 作数值比较，作数值比较， , ,再做置换：再做置换：

21、10.382()0.472,xaba1 ()0.1612,f x12()()f xf x1:0.472,ax0.7880.002;ba第三次区间缩短计算过程：第三次区间缩短计算过程： 作数值比较，作数值比较， , ,再做置换：再做置换：2:0.944,bx20.618()0.944,xaba2 ()0.0468, f x12()()f xf x0.4720.002ba22 , 0,1.236,0.764,()0.0821,a bxf x , 0.472,1.236,a b 110.764,( )0.0821,xf x 220.764,()0.0821,xf x , 0.472,0.944,a

22、b 各次的迭代结果如下：各次的迭代结果如下：迭代次数迭代次数x1x2f(x1)f(x2)a,b|b-a|第第1次次0.7641.236-0.08210.41260,1.2361.236第第2次次0.4720.7640.1612-0.0821 0.472,1.236 0.788第第3次次0.7640.944-0.0821 -0.0468 0.472,0.944 0.472第第4次次0.6520.764-0.0268 -0.0821 0.652,0.944 0.292第第5次次0.7640.832-0.0821 -0.0881 0.764,0.944 0.230第第6次次0.8320.906-0.

23、0881 -0.0683 0.764,0.906 0.124缺点：收敛速度慢缺点：收敛速度慢优点：不要求函数可微，且每次迭代只需计算一个函数优点：不要求函数可微，且每次迭代只需计算一个函数 值，计算量小值，计算量小第三章第三章 常用的一维搜索算法常用的一维搜索算法1 搜索算法概述搜索算法概述2 0.618法（黄金分割法）法（黄金分割法） 3 “成功成功-失败失败”法法4 牛顿法牛顿法5 插值法插值法 进退算法进退算法 ( (或称成功或称成功- -失败法失败法) )如何确定包含极小点在内的初始区间如何确定包含极小点在内的初始区间 ?（一）基本思想：（一）基本思想：由单峰函数的性质可知，函数值在极

24、小点左边严格下降，在右边严格上升。由单峰函数的性质可知，函数值在极小点左边严格下降，在右边严格上升。f(x)xabx*x0 x1x2从某个初始点出发，沿函数值下降的方向前进，直至发现函数值上升为止。从某个初始点出发，沿函数值下降的方向前进，直至发现函数值上升为止。由两边高，中间低的三点，可确定极小点所在的初始区间。由两边高，中间低的三点，可确定极小点所在的初始区间。（二）（二）设给定初始点设给定初始点为为 a 及初始步长为及初始步长为 h, 求搜索区间求搜索区间c, d1、选定初始点、选定初始点a 和步长和步长h;f(x) x2、计算并比较、计算并比较f(a)和和f(a+h)；有前进；有前进(

25、1)和后退和后退(2)两种情况：两种情况：(1) 前进运算：若前进运算：若f(a) f(a+h), (2) 后退运算：若后退运算：若f(a) 0 及精度及精度 0，步骤步骤2：计算：计算步骤步骤3：若：若 搜索成功搜索成功, 转步骤转步骤4；否则，搜索失败，；否则，搜索失败， 转步骤转步骤5。步骤步骤4：令：令 x:= x + h, 转步骤转步骤 2。步骤步骤5：判断：判断 若若 停止迭代，停止迭代， ；否则令；否则令 转步骤转步骤 2。缺点：效率低，缺点：效率低， h 选择要适当，初始步长不能选得太小。选择要适当，初始步长不能选得太小。优点：可以求优点：可以求搜索区间搜索区间。1( ).f

26、x2().f xh21,12:,:2hh?hh ，*xx,4hh （三）求极小点计算步骤（三）求极小点计算步骤 ：利用利用“成功成功-失败失败”法求函数法求函数 的搜索区间，的搜索区间， 取初始点取初始点 ，步长，步长取初始点取初始点 ，步长，步长3( )21f xxx115 ( )(),28f xf( )()f xf xh因为，12x 1.2h 12x 1,2h 11 ()()(0)1,22f xhff搜索成功，步长加倍；11 (+2 )(3 )(3)(1)0,22f xhhf xhff计算()(3 )f xhf xh因为， 搜索成功，步长加倍；11 (3 +4 )(7 )(7)(3)22,

27、22f xhhf xhff计算(3 )(7 )f xhf xh因为， 搜索失败，停止迭代；,7 0,3.xh xh得到搜索区间为得到搜索区间为 设设 f (x)在在 a ,b上可微，求函数上可微，求函数f在在a,b的极小点，就是求的极小点，就是求函数导数为零的点。函数导数为零的点。 如果如果 则在则在(a,b)内一定存在一点内一定存在一点x，使得，使得 。 为求极小点，可取为求极小点，可取 ， 若若 , x 为最小点为最小点, x0 = x* ; , x0 在上升段在上升段, x* x0，去掉，去掉a, x0 .00fx00fx00fx 0,0,fafb 0fx02abx用用 或者或者 作新的

28、区间作新的区间a,b，继续这个过程，继续这个过程，逐步将区间逐步将区间a,b缩小，缩小，当区间当区间a,b的长度充分小时，可将的长度充分小时，可将a,b的中点取做极小的中点取做极小点的近似点的近似点。点。 0, a x0,x b优点：计算量较少，而且总能收敛到一个局部极小点。优点：计算量较少，而且总能收敛到一个局部极小点。缺点：收敛速度较慢缺点：收敛速度较慢0=2abx步骤步骤1：计算：计算步骤步骤2：若：若 ，令，令 ，转步骤，转步骤3； 若若 ，令，令 ，转步骤，转步骤3； 若若 ，停止，停止， 。步骤步骤3：若：若 ，则，则 ，停止，否则，转步，停止，否则，转步1.0ax00fx00fx

29、00fx0bx0*xx|ba*2abx ：试用二分法求目标函数试用二分法求目标函数 的最优解。的最优解。 给定初始区间给定初始区间0,2，收敛精度，收敛精度在在0,2内有极小点。内有极小点。3( )21f xxx0:1,bx故=0.004.(0)=2,(2)=10,ff01,2abx10.004;ba , 0,1,a b 第一次区间缩短计算过程：第一次区间缩短计算过程：2( )32,fxx因为因为所以函数所以函数3( )21f xxx0()= (1)10fxf ，第二次区间缩短计算过程：第二次区间缩短计算过程：第三次区间缩短计算过程：第三次区间缩短计算过程：2 , 0,1,( )32,a bf

30、xx1 , ,1,2a b 01:,2ax故01,22abx10.004;2ba015()= ()024fxf ，3 , ,1,4a b 03:,4ax故03,24abx10.004;4ba035()= ()0416fxf ，各次的迭代结果如下：各次的迭代结果如下：迭代迭代9次后，次后，|b-a|=0.003910.004, 故故迭代次数迭代次数x0=(a+b)/2f(x0)a,b|b-a|第第1次次x0=110,11第第2次次x0=1/2-5/41/2,11/2第第3次次x0=3/4-5/163/4,11/4第第4次次x0=7/819/643/4,7/81/8第第5次次x0=13/16-0.

31、019513/16,7/81/16第第6次次x0=27/320.013613/16,27/321/32第第7次次x0=53/640.057413/16,53/641/64第第8次次x0=105/1280.018413/16,105/1281/128第第9次次x0=209/256-0.0004209/256,105/1281/256*0.81836.x 第三章第三章 常用的一维搜索算法常用的一维搜索算法1 搜索算法概述搜索算法概述2 0.618法（黄金分割法）法（黄金分割法）3 “成功成功-失败失败”法法4 牛顿法牛顿法5 插值法插值法对对 f (x) 在在 x k 点二阶泰勒展开：点二阶泰勒展

32、开：略去高阶项得略去高阶项得两边对两边对x求导，求导，令令 ，得到，得到 牛顿法是一种函数逼近法，牛顿法是一种函数逼近法，基本思想是：基本思想是：在极小点附近用在极小点附近用函数的二阶泰勒多项式近似代替目标函数，从而求得目标函数函数的二阶泰勒多项式近似代替目标函数，从而求得目标函数的极小点的近似值。的极小点的近似值。221( )()()()()()() )2kkkkkkf xf xfxxxfxxxo xx21( )()()()()()2kkkkkf xf xf xxxfxxx( )()()()kkkf xf xfxxx( )=0f x()()kkkf xxxfx当当 f 是二次函数时，一次迭代

33、就是二次函数时，一次迭代就可得到极小点。可得到极小点。取取 作为新的迭代点，继续迭代，直到达到精度，这样就得到了作为新的迭代点，继续迭代，直到达到精度，这样就得到了函数函数 f 的一个驻点的一个驻点 。以上过程以上过程即即Newton法法。在一定条件下（例如在一定条件下（例如 ），这个驻点是极小点。），这个驻点是极小点。1()=()kkkkf xxxfx( *)0fx*x步骤步骤1：给定初始点：给定初始点 令令 。步骤步骤2：计算：计算 。步骤步骤3：若：若 ，停止，停止， ，否则转步骤，否则转步骤4。步骤步骤4：计算：计算 令令 ，转步骤，转步骤2。10,xR，1k (),()kkf xfx

34、()kf x*kxx1()=()kkkkf xxxfx1kk 特点：收敛速度快，局部二阶收敛。特点：收敛速度快，局部二阶收敛。缺点：须计算二阶导数，工作量大；对初始点要求高，要求初缺点：须计算二阶导数，工作量大；对初始点要求高，要求初 始点离极小点不太远，否则有可能使极小化发散或收敛到非极始点离极小点不太远，否则有可能使极小化发散或收敛到非极 小点；局部收敛。小点；局部收敛。 ：试用试用Newton法求函数法求函数 的最优解。的最优解。432( )46164f xxxxx206,10 x0100()()fxxxfx(6)89664.75(6)69ff1211()()fxxxfx(4.75)84

35、.944.75=4.75=4.163(4.75)144.75ff21()(4.75)84.9410,fxf继续迭代；22()(4.163)14.66610,fxf继续迭代；32( )4121216,fxxxx2( )122412,fxxx2322()()fxxxfx(4.163)14.6664.1634.1634.010(4.163)96.055ff3433()()fxxxfx(4.010)0.84364.010=4.010=4.00004(4.010)84.7212ff24.163x 33()(4.010)0.843610,fxf继续迭代；24()(4.00004)0.003410,fxf得

36、到近似解得到近似解*4.00004.x 第三章第三章 常用的一维搜索算法常用的一维搜索算法1 搜索算法概述搜索算法概述2 0.618法（黄金分割法）法（黄金分割法） 3 “成功成功-失败失败”法法4 牛顿法牛顿法5 插值法插值法 用用 在在2 个或个或3 个点的函数值或导数值，构造个点的函数值或导数值，构造2 次或次或3次多项式作为次多项式作为 的近似值，以这多项式的极小点作为一个的近似值，以这多项式的极小点作为一个试探点。试探点。 3点点2次，次，2点点2次，次，2点点3次，次，3点点3次，次，2点点3次等插值法次等插值法. 下面以下面以3点点2次插值法（二次插值法）为例：次插值法（二次插值

37、法）为例： f x f x 给定一个初始的最优区间，找到两个试探点，通过比较这两给定一个初始的最优区间，找到两个试探点，通过比较这两个点函数值的大小，缩短最优区间，当区间个点函数值的大小，缩短最优区间，当区间的长度充分小时，的长度充分小时，可将可将区间区间中点取做极小点的近似中点取做极小点的近似点。点。 可用成功失败法寻找可用成功失败法寻找初始的最优区间初始的最优区间， 可作可作为一个试探点，只需找到另外一个试探点即缩短最优区间。为一个试探点，只需找到另外一个试探点即缩短最优区间。123xxx，2x另外一个试探点利用插值法寻找另外一个试探点利用插值法寻找区间收缩法区间收缩法下面以下面以3点点2

38、次插值法（抛物线法）为例：次插值法（抛物线法）为例：利用利用 在区间在区间 的函数值的函数值123xxx yf x 123fxfxfx作出如下的二次插值多项式作出如下的二次插值多项式 P xaxbxc2它应满足条件它应满足条件 P xaxbxcffx211111(1) P xaxbxcffx222222 P xaxbxcffx233333(2)(3)从极值的必要条件从极值的必要条件 求得求得 Pxaxb20 bxa2 求出系数求出系数 和和 ，就可得到极小点的表达式。，就可得到极小点的表达式。ab b xxa xxff22232323 b xxa xxff22121212, P xaxbxcf

39、fx211111（1） P xaxbxcffx222222 P xaxbxcffx233333（2）（3） b xxa xxffb xxa xxff2222121212232323, xxfxxfxxfbxxxxxx222222231312123122331 xxfxxfxxfaxxxxxx231312123122331 P xaxbxc2联立方程组（联立方程组（1）、（）、（2）、（）、（3） xxfxxfxxfbxaxxfxxfxxf2222222313121232313121231(4)22 当当x1 ,x2 , x3 等距时，等距时，即即x2 -x1 = x3-x2 =h时，上面的式子

40、可化简时，上面的式子可化简所以所以 2122223123(2)22122hxh fh xhxh fhxh fxhfhfhf 132123(- )1+(5)22h f fxfff 1. 寻找满足如下条件的点（成功失败法寻找），成为两头大寻找满足如下条件的点（成功失败法寻找），成为两头大中间小的点：中间小的点： x 1 x 2 f (x2 ), f (x2 ) 0 , 则则 为为P(x)的极小值点，且的极小值点，且3.若若 ，则迭代结束，取，则迭代结束，取 ，否则在点，否则在点 中中，选取使，选取使f (x) 最小的点作为新的最小的点作为新的x2，并使新的并使新的x 1 ， x3各是新的各是新的x

41、2近旁的左右两点，继续进行迭代，直到满近旁的左右两点，继续进行迭代，直到满足终止准则。足终止准则。x13,xx x2xx*xx123,x x x x算法思路：算法思路：cbxxxacffcffxxccxxxx113212113121213231()22(6),. 联立方程组（联立方程组（1）、（）、（2）、（）、（3）, 可得可得 ffba xxcxx1313113:, ffba xxcxx1212312: 从而从而 b xxa xxff22131313, b xxa xxff22121212所以所以 bca xx113,因此因此ffffccccxxxxacxxxxxx121211131212

42、2323223=: cbxxxacffcffxxccxxxx113212113121213231()22(6),. xxfxxfxxfbxaxxfxxfxxf2222222313121232313121231(4)22 2）用二次插值法逼近极小点）用二次插值法逼近极小点(1) 相邻三点及其函数值相邻三点及其函数值: x1=0, x2=1, x3=2; f1=2, f2=1, f3=18. 11321()22 ,bcxxxac例用二次插值法求函数例用二次插值法求函数f(x)=3x3-4x+2的极小点，的极小点， 给定给定 初始区间初始区间0,2, =0.2。解：解：1）确定初始搜索区间）确定初始

43、搜索区间初始区间初始区间a,b=0,2, 另有一中间点另有一中间点x2=1。1211312121323,ffcffxxccxxxx0 5550 292xf x.,( ).,根据公式计算差值多项式的极小点根据公式计算差值多项式的极小点 (2) 在新区间，相邻三点及其函数值在新区间，相邻三点及其函数值: x1=0, x2=0.555, x3=1; f1=2, f2=0.292, f3=1.故新区间故新区间a,b=a,x2=0,1， 应继续迭代。应继续迭代。0 5550 292xf x.,( ).,x1=0, x2=1, x3=2; f1=2, f2=1, f3=18220 2921,0.5551,

44、f xfxx( ).由于由于210.5550.4450.2,xx 11321()22 ,bcxxxac1211312121323,ffcffxxccxxxx0 6070 243xf x.,( ).,根据公式计算差值多项式的极小点根据公式计算差值多项式的极小点故新区间故新区间a,b=x2,b=0.555,1， 迭代终止。迭代终止。x1=0, x2=0.555, x3=1; f1=2, f2=0.292, f3=1220 2430.292,0.6070.555,f xfxx( ).由于由于20.6070.5550.0520.2,xx0 6070 243xf x.,( ).,故故*0 6070 24

45、3.xxff x.,( ).已知已知f(x1)=f1， f (x1)=f1 ， f(x2)=f2 ，做二次插值多项式，做二次插值多项式P(x) ，可得到最小值点为可得到最小值点为已知已知f(x1)=f1， f (x1)=f1 (0)及二次函数的极小值及二次函数的极小值fm，做二次，做二次插值多项式插值多项式P(x) ，可得到最小值点为，可得到最小值点为已知已知f (x1)=f1 ， f (x2)=f2 (f1 f2) ，做二次插值多项式，做二次插值多项式P(x) ，可得到最小值点为可得到最小值点为xxfxxffxxf2211121211()1.2 ()() mffxxf1112. fxxxxf

46、f222112(). 基本思想与二次插值法类似：用四个已知值（如两个点函数值及其导数值）基本思想与二次插值法类似：用四个已知值（如两个点函数值及其导数值）构造一个三次多项式构造一个三次多项式P3(x)，用，用P3(x)的极小点近似目标函数的极小点的极小点近似目标函数的极小点x* 利用函数在两点的函数值和导数值：利用函数在两点的函数值和导数值： 32111p xA xxB xxC xxD 三次插值三次插值三次插值法的收敛速度比二次插值法要快，达到三次插值法的收敛速度比二次插值法要快，达到2阶收敛速度。阶收敛速度。10fx20fx fx p x1x2xx*x求出：11322212121211222121232p xDfxp xA xxB xxC xxDfxpxCfxpxA xxB xxCfx21211232121212122111()()()2()()()3()()()()2()()()()xxfxfxf xf xAxxf xf xxxfxfxBxxCfxDf x极值的条件极值的条件： 211320dp xA xxB xxCdx1/ 2xxCB21303BBACxxAA若0A 若极值充分条件为：将极值点方程带入上式 212620d p xA xxBdx222122112333333(0)300, 23 BBACBBACB