数值解单变量最优化

4.5.2无约束最优化问题的数值解法

4.5.2.1单变量最优化问题的数值解法〔一维搜索〕一、消去法的根本概念1消去法的根本思想利用单峰函数在可行域内只有一个极值点的特点，设法逐步缩小搜索最优点的区间，直至找到最优点，并到达允许的精度为止。消去法分为：1整理ppt同时消去法：同时计算一批点的函数值，然后比较各函数值的大小，再消去一局部区间，直至到达精度要求。序贯消去法：从第二个点起，每计算一个点的函数值，就与前一个点的函数值进行比较，消去局部区间后再安排下一个计算点，如此序贯进行，直至到达精度要求。2整理ppt2序贯法缩小搜索区间设：一元函数y(x)在区间[a0,b0]内为单峰函数，假设首先在[a0,b0]内任取两点x1，x2(x1<x2)，并计算函数值y(x1)，y(x2)，这时可能的三种情况为：3整理ppt〔1〕

y(x1)<y(x2)那么x*在[a0,x2]之内4整理ppt〔2〕

y(x1)>y(x2)那么x*在[x1,b0]之内5整理ppt〔3〕y(x1)=y(x2)那么x*在[x1,x2]之内6整理ppt根据上面分析，可将搜索区间缩小。在余下的区间内继续选择新点，比较新点的函数值，直至区间缩小到精度要求，找到最优点。a0b0091011121334567812X1’x17整理ppt3不定区间当进行n次函数值的计算与比较后，可以得出这n个函数值中的最小值，f(xm)及最小点xm以及其左右的邻点xk、xr，而真正的最小点x*必落在xr与xk之内。将xr与xk之间的区间称为不定区间ln，且ln=xr–xk8整理ppt不定区间的影响因素：①

与计算次数n有关；l0=b0–a0一定时，n↑ln↓②与计算点的分布方式有关，即与xi确实定方法有关显然，ln越小，那么xm与x*越接近，用xm近似x*越可靠，即精度越高。ln=xr–xk9整理ppt4区间缩短率n次函数值的计算与比较后，不定区间与原始区间的比值①当l0一定时，En↓ln↓②相同计算次数下，En越小的方案越好10整理ppt二对无约束函数的搜索——求单峰所在区间的进退算法

消去法的应用根底是目标函数f(x)在[a0,b0]内为单峰函数。问题：〔1〕怎样确定f(x)为单峰函数〔2〕怎样确定f(x)的单峰所在区间[a0,b0]一般采用进退算法解决这两个问题。11整理ppt1、进退算法的根本思想由单峰函数的性质可知，对于存在极小值的单峰函数，在极小点左边，函数值严格下降，而在极小点右边，函数值应严格上升。12整理ppt据此，可以从某个给定的初始点出发，沿着函数值下降的方向逐步前进〔或后退〕直至发现函数值开始上升为止。由两边高中间低的三点函数值，就可以确定极小值所在的初始区间[a0，b0]13整理ppt2、进退算法

(1)选定初始点a0与步长h(2)计算并比较y〔a0〕和y〔a0+h〕，根据比较结果有前进和后退两种可能：①

前进计算：②后退运算：14整理ppt前进计算：假设y〔a0〕≥y〔a0+h〕，那么步长加倍，计算y〔a0+3h〕。

假设y〔a0+h〕≤y〔a0+3h〕，那么令a0=a0，b0=a0+3h15整理ppt假设y〔a0+h〕≥y〔a0+3h〕，令a0=a0+h，h=2h，重复上述前进运算。

16整理ppt后退运算：假设y〔a0〕≤y〔a0+h〕,那么后退计算y〔a0-h〕;假设y〔a0-h〕≥y〔a0〕，那么令a0=a0-h，b0=a0+h，停止运算。否那么继续后退。17整理ppt例：求函数的极小所在区间初始点a0=1，步长h=1解：h=a0=118整理ppt所以应后退19整理ppt应继续后退，后退时步长加倍，所以计算后退，计算20整理ppt找到了函数值大〔〕、小〔