ch4一维搜索方法.ppt

第4章 一维搜索方法,1,4.1 一维搜索方法,对n元函数, 给定点x(k), 向量pk, 则f(x)从x(k), 出发沿方向pk的直线上函数值的变化可以表示为一元函数:,该函数只有一个变量, 且每一个值都对应着直线上一个点。,求函数f(x)的解, 就转化为沿直线 求一元函数 的极小值点, 因此本节先介绍一元函数f(x)的极小问题。,2,4.2 二分法,当f(x)连续可导时, 在极小点x*处有 , 因此求一元函数f(x)的极小值点问题就转化为求解方程 的根的问题。称 的点为函数f(x)的驻点。,设根 , 且 , 则有算法,3,算法4.1(二分法),1输入a, b及精度0。,2.,3若 或 , 输出x*=x。否则转4。,4求 , 若 , 则 , 否则,5输出超过最大迭代次数的信息, 停机。,4,4.3 Newton法,假设f(x)二阶连续可导, 对 在xk处展开为Taylor公式,由此有迭代公式：,算法4.2(Newton法求 的根),1对 ; 做到第6步。,2,3若d=0停止计算。,4计算,5若 或 , 输出x, 停机。,6,7若迭代N0次后仍达不到精度要求, 停机。,5,定义4.4.1 设f(x): a, bR 若存在点x*(a, b)使f(x)在a, x*上是单调减小, 在x*, b上是单调增加, 则称a,b 是f(x)的单峰区间。f(x)是a, b上的单峰函数如图所示。其中图(a), 图(c)是单峰函数, 图(b)不是单峰函数。,(a),(b),(c),6,4.4 0.618法(黄金分割法),假设f(x)是单峰函数, 但不知道极小点x*的位置。任取x1, x2a, b, 且x1x2, 则有以下三种情况存在：,(2)f(x1)f(x2)此时 x*x2 , 即x*a, x2见图(b)。,(a),(b),(c),7,(1)f(x1)=f(x2)此时, x*x1, x2见图(a)。,(3)f(x1)f(x2)此时 x* x1 , 即x*x1, b见图(c)。,为计算方便可将情况(1)归结到情况(2)或情况(3)。为了寻找x*, 在初始区间a1, b1内任取两点 ; 且 , 通过比较函数值 , 从而确定极小点x*是在 或者x1, b1内。取小区间代替a1, b1 得新的x*的存在区间, 记为a2, b2, 又任取 且 , 通过比较函数值得新的小区间a3, b3 ,x*的存在区间不断缩小, 最后便可确定出近似的极小点, 为了节省计算函数值的工作量, 永远保证新区间的一个端点和原区间的一个端点重合。,8,设每次迭代的区间长度按比例缩小(01), 设第k次迭代后的区间为ak, bk, 则第k+1次的区间为,或,取,不妨设 , 经迭代后包含极小点的区间为,为了进一步缩短此区间, 取xk+1和 且 ,9,取,同理, 若 可得相同的结论, 故有,定义4.4.2 若实数 满足 则称 为黄金分割数, 黄金分割数在单位长度区间中对应的点称为黄金分割点。,10,算法4.3(0.618法),给定初值 , 误差,1计算,2若 , 得最优解 , 否则转3。,3若 则 , 转4; 若 则 , 转5; 若 则 , 转1。,4计算 , 转2。,5计 算 , 转2。,11,12,4.5 Fibonacci法(分数法),该方法也适用于单峰函数, 与0.618法的区别是每次迭代区间长度的缩短。不是按常数比率进行而是由Fibonacci数确定的, 而且可以预先确定迭代次数。,定义4.5.1 设数列Fn满足,称数列Fn为Fibonacci数列, Fn为第n个Fibonacci数, 相邻两个Fibonacci数之比 Fn-1/Fn称为Fibonacci分数。如下表：,13,用数学归纳法可以证明,且,设第k次迭代时的区间为ak, bk, 取,14,容易验证 且,当 时, 令 。有,当 时, 令 。有,特别当k=n-1时有,15,由此可知, 只要给定了初始区间b1-a1的长度和精度要求, 就可计算出迭代的次数,此时,为了能在第n-1次迭代中使区间缩短, 可在第n-2次迭代后在 的右边或左边取一点, 令 且,16,算法4.4(Fibonacci方法),(1)给定初始区间a, b和误差要求0,(2),(3)若 , 转(4); 否则转(2)。,(4),17,(5)若 转(6); 若 转(7)。,(6),若k=n-2则转(9); 否则计算f(x)转(8)。,(7),若k=n-2则转(9); 否则计算f(x)转(8)。,(8) , 转(5)。,(9) , 若 , 则 ; 否则,(10)输出,例4.1分别用二分法、Newton法、0.618法求解,解: 取精度 , 初值,Newton法的迭代公式为：,计算结果如下表,18,0.618法的计算结果如下表,20,Fibonacci法的计算结果如下表,21,22,若是无约束非线性规划问题, 其一维搜索是使,一维搜索和有效一维搜索可分为两种类型:最优一维搜索和可接受一维搜索。,在 上选取步长因子 使f(x(k+1)f(x(k),若考虑的是约束非线性规划问题, 其一维搜索所得步长因子 , 不仅要满足函数的下降性, 还需保证所得 仍是可行点。即步长因子应在某一有效区间 上选取，称之为有效其一维搜索。,23,(1)最优一维搜索(精确一维搜索),这类搜索所得步长因子 使,即,由于这类搜索是以取得最优步长为目的, 因此称为最优一维搜索或精确一维搜索, 简称为一维搜索, 所得步长称为最优步长。,(2)可接受一维搜索(不精确一维搜索),其特点:不是求精确的最优步长或其近似值, 而是按某一规则选取的步长, 使目标函数f从x(k)沿方向pk能取得可接受的下降量。,常见的一维搜索法还有多项式插值法中的二次插值法和三次插值法, 可接受搜索法中的Goldstein法和Wolfe-Powe