数值解单变量最优化p.ppt

《数值解单变量最优化p.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、4.5.2无约束最优化问题的数值解法4.5.2.1单变量最优化问题的数值解法（一维搜索）一、消去法的基本概念1消去法的基本思想利用单峰函数在可行域内只有一个极值点的特点，设法逐步缩小搜索最优点的区间，直至找到最优点，并达到允许的精度为止。消去法分为：同时消去法：同时计算一批点的函数值，然后比较各函数值的大小，再消去一部分区间，直至达到精度要求。序贯消去法：从第二个点起，每计算一个点的函数值，就与前一个点的函数值进行比较，消去部分区间后再安排下一个计算点，如此序贯进行，直至达到精度要求。2序贯法缩小搜索区间设：一元函数y(x)在区间[a0,b0]内为单峰函数，若首先

2、在[a0,b0]内任取两点x1，x2(x1y(x2)则x*在[x1,b0]之内（3）y(x1)=y(x2)则x*在[x1,x2]之内根据上面分析，可将搜索区间缩小。在余下的区间内继续选择新点，比较新点的函数值，直至区间缩小到精度要求，找到最优点。a0b0091011121334567812X1’x13不定区间当进行n次函数值的计算与比较后，可以得出这n个函数值中的最小值，f(xm)及最小点xm以及其左右的邻点xk、xr，而真正

3、的最小点x*必落在xr与xk之内。将xr与xk之间的区间称为不定区间ln，且ln=xr–xk不定区间的影响因素：①与计算次数n有关；l0=b0–a0一定时，n↑ln↓②与计算点的分布方式有关，即与xi的确定方法有关显然，ln越小，则xm与x*越接近，用xm近似x*越可靠，即精度越高。ln=xr–xk4区间缩短率n次函数值的计算与比较后，不定区间与原始区间的比值①当l0一定时，En↓ln↓②相同计算次数下，En越小的方案越好二对无约束函数的搜索——求单峰所在区间的进退算法消去法的应用基础是目标函数f(x)在[a0,b0]内为单峰函数。问题：（1）怎样确定f(x)为单

4、峰函数（2）怎样确定f(x)的单峰所在区间[a0,b0]一般采用进退算法解决这两个问题。1、进退算法的基本思想由单峰函数的性质可知，对于存在极小值的单峰函数，在极小点左边，函数值严格下降，而在极小点右边，函数值应严格上升。据此，可以从某个给定的初始点出发，沿着函数值下降的方向逐步前进（或后退）直至发现函数值开始上升为止。由两边高中间低的三点函数值，就可以确定极小值所在的初始区间[a0，b0]2、进退算法(1)选定初始点a0与步长h(2)计算并比较y（a0）和y（a0+h），根据比较结果有前进和后退两种可能：①前进计算：②后退运算：前进计算：若y（a0）≥y（a0+

5、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用进退算法找到了初

6、始搜索区间[a0，b0]为[-2，1]