《数值解单变量最优化p》由会员分享，可在线阅读，更多相关《数值解单变量最优化p（21页珍藏版）》请在金锄头文库上搜索。
1、4.5.2 无约束最优化问题的数值解法 4.5.2.1 单变量最优化问题的数值解法（一维搜索）,一、消去法的基本概念 1 消去法的基本思想 利用单峰函数在可行域内只有一个极值点的特点，设法逐步缩小搜索最优点的区间，直至找到最优点，并达到允许的精度为止。消去法分为：,同时消去法：同时计算一批点的函数值，然后比较各函数值的大小，再消去一部分区间，直至达到精度要求。 序贯消去法：从第二个点起，每计算一个点的函数值，就与前一个点的函数值进行比较，消去部分区间后再安排下一个计算点，如此序贯进行，直至达到精度要求。,2 序贯法缩小搜索区间 设：一元函数y(x)在区间a0,b0内为单峰函数，若首先在a0,b
2、0内任取两点x1，x2 (x1x2)，并计算函数值y(x1)，y(x2)，这时可能的三种情况为：,（1） y(x1) y(x2) 则 x*在a0, x2之内,（2） y(x1) y(x2) 则 x*在x1, b0之内,（3）y(x1) = y(x2) 则 x*在x1, x2之内,根据上面分析，可将搜索区间缩小。在余下的区间内继续选择新点，比较新点的函数值，直至区间缩小到精度要求，找到最优点。,3 不定区间,当进行n次函数值的计算与比较后，可以得出这n个函数值中的最小值，f(xm)及最小点xm以及其左右的邻点xk、xr，而真正的最小点x*必落在xr与xk之内。 将xr与xk之间的区间称为不定区间
3、ln，且ln=xrxk,不定区间的影响因素： 与计算次数n有关；l0=b0a0一定时，n ln 与计算点的分布方式有关，即与xi的确定方法有关 显然， ln 越小，则xm与x*越接近，用xm近似x*越可靠，即精度越高。,ln=xrxk,4 区间缩短率 n次函数值的计算与比较后，不定区间与原始区间的比值 当l0一定时，En ln 相同计算次数下，En越小的方案越好,二 对无约束函数的搜索求单峰所在区间的进退算法,消去法的应用基础是目标函数f(x)在a0,b0内为单峰函数。 问题： （1）怎样确定f(x)为单峰函数 （2）怎样确定f(x)的单峰所在区间a0,b0 一般采用进退算法解决这两个问题。,
4、1、进退算法的基本思想,由单峰函数的性质可知，对于存在极小值的单峰函数，在极小点左边，函数值严格下降，而在极小点右边，函数值应严格上升。,据此，可以从某个给定的初始点出发，沿着函数值下降的方向逐步前进（或后退）直至发现函数值开始上升为止。由两边高中间低的三点函数值，就可以确定极小值所在的初始区间a0，b0,2、进退算法,(1) 选定初始点a0与步长h (2) 计算并比较y（a0）和y（a0+h），根据比较结果有前进和后退两种可能： 前进计算： 后退运算：,前进计算：若y（a0）y（a0+h），则步长加倍，计算y（a0+3h）。 若y（a0+h）y（a0+3h），则令a0=a0，b0=a0+3h,若y（a0+h） y（a0+3h） ，令a0=a0+h，h=2h，重复上述前进运算。,后退运算：若y（a0）y（a0+h）,则后退计算y（a0-h）; 若y（a0-h）y（a0），则令a0=a0-h，b0=a0+h，停止运算。 否则继续后退。,例：,求函数 的极小所在区间 初始点a0=1，步长h=1 解： h =a0=1,所以应后退,应继续后退，后退时步长加倍，所以计算,后退，计算,找到了函数值大（ ）、小（ ）、大（ ）的三点，即a0=a0-3h=-2，b0=a0=1 用进退算法找到了初始搜索区间a0，b0为-2，1,
