ch4一维搜索方法

1、第4章 一维搜索方法 14.1 一维搜索方法 对n元函数, 给定点x(k), 向量pk, 则f(x)从x(k), 出发沿方向pk的直线上函数值的变化可以表示为一元函数: 该函数只有一个变量, 且每一个值都对应着直线上一个点。 求函数f(x)的解, 就转化为沿直线 求一元函数 的极小值点, 因此本节先介绍一元函数f(x)的极小问题。 24.2 二分法 当f(x)连续可导时, 在极小点x*处有 , 因此求一元函数f(x)的极小值点问题就转化为求解方程 的根的问题。称 的点为函数f(x)的驻点。 设根 , 且 , 则有算法 3算法4.1(二分法) 1输入a, b及精度0。2. 3若 或 , 输出x*

2、=x。否则转4。 4求 , 若 , 则 , 否则5输出超过最大迭代次数的信息, 停机。 44.3 Newton法 假设f(x)二阶连续可导, 对 在xk处展开为Taylor公式 由此有迭代公式： 算法4.2(Newton法求 的根) 1对 ; 做到第6步。 2 3若d=0停止计算。 4计算 5若 或 , 输出x, 停机。 67若迭代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), 图(

3、c)是单峰函数, 图(b)不是单峰函数。 (a)(b)(c) 64.4 0.618法(黄金分割法) 假设f(x)是单峰函数, 但不知道极小点x*的位置。任取x1, x2a, b, 且x1x2, 则有以下三种情况存在： (2)f(x1)f(x2)此时 x*f(x2)此时 x* x1 , 即x*x1, b见图(c)。 为计算方便可将情况(1)归结到情况(2)或情况(3)。为了寻找x*, 在初始区间a1, b1内任取两点 ; 且 , 通过比较函数值 , 从而确定极小点x*是在 或者x1, b1内。取小区间代替a1, b1 得新的x*的存在区间, 记为a2, b2, 又任取 且 , 通过比较函数值得新

4、的小区间a3, b3 x*的存在区间不断缩小, 最后便可确定出近似的极小点, 为了节省计算函数值的工作量, 永远保证新区间的一个端点和原区间的一个端点重合。 8 设每次迭代的区间长度按比例缩小(00,(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法的迭代公式为： 计算结果如

5、下表 18迭代次数二分法Newton法02.252.2511.8752.071428622.06252.008403431.968752.000137842.01562551.992187562.003906271.998361882.00113991.99975040.618法的计算结果如下表 20迭代次数ak, bkxkf(xk)00, 31.1458981.8541020.988936830.1042317211.145898, 31.8541022.2917960.104231720.7313779421.145898, 2.2917961.5836291.8541020.552945

6、090.1042318531.158359, 2.2917961.8541022.0212860.104231850.0279636341.854102, 2.2917962.0212862.1246120.027963630.1093716551.854102, 2.1246121.9574282.0212860.02670890.0027963661.975743, 2.1246122.0212862.0607530.027963630.398031271.957428, 2.0212861.9968942.0212860.000576320.0027963681.996894, 2.02

7、12861.9818191.9968940.00193550.0005763291.981819, 2.0212861.9968942.0062110.000576320.0012228Fibonacci法的计算结果如下表 21迭代次数ak, bkxkf(xk)00, 31.1460761.8539330.988899840.10444482911.1460673, 31.8539332.2921350.104448290.7333586921.146067, 2.2921351.8539331.8539330.551791690.10444482931.584270, 2.2921351.8

8、539332.0224720.104448290.0031214441.893933, 2.2921352.0224722.1284340.003121440.1167360951.853933, 2.1284341.9568702.0224720.010557980.0031214461.956870, 2.0598082.0224722.0590800.003121440.0021215671.956870, 2.0598081.9911832.0224720.000460970.0021214481.956870, 2.0224721.9787381.9911830.002632760.

9、0004609791.978738, 2.0224721.9911832.0063250.00460970.00002744 22若是无约束非线性规划问题, 其一维搜索是使 一维搜索和有效一维搜索可分为两种类型:最优一维搜索和可接受一维搜索。在 上选取步长因子 使f(x(k+1)f(x(k) 若考虑的是约束非线性规划问题, 其一维搜索所得步长因子 , 不仅要满足函数的下降性, 还需保证所得 仍是可行点。即步长因子应在某一有效区间 上选取，称之为有效其一维搜索。 23(1)最优一维搜索(精确一维搜索)这类搜索所得步长因子 使即由于这类搜索是以取得最优步长为目的, 因此称为最优一维搜索或精确一维搜索, 简称为一维搜索, 所得步长称为最优步长。(2)可接受一维搜索(不精确一维搜索) 其特点:不是求精确的最优步长或其近似值, 而是按某一规则选取的步长, 使目标函数f从x(k)沿方向pk能取得可接受的下降量。 常见的一维搜索法还有多项式插值法中的二次插值法和三次插值法, 可接受搜索法