第05章 一维搜索方法

1、优化设计方法(Optimization Method)交通与车辆工程学院交通与车辆工程学院 刚宪约刚宪约2022年年4月月2日日 本节要讨论的问题是求解一元函数的极小值问题 )(min 当)(可微时，理论上说，这个问题的最优解可由方程式0)( 求得。但是，这个方程往往是高度非线性的，很难求出解析解，更严重的是在很多实际问题中，)(不可微，或无法写出其导数表达式， 因此一般地说就要用迭代的方法数值求解上列极小化问题，这就是所谓的一维搜索。 如果对于给定的初始点1，已经求出)(1、)( 1和)( 1，则在1邻近可以用二次函数)(q近似)(，且保证)(q近似)(在1点有相同的函数及一、二阶导数值：

2、211111)( 21)( )()(q 代替求)(的极小点。我们来求)(q的极小点2，它应满足 0)( )( )( 111q 由此 )( )( 1112 当得到2后又可以计算利用同样的方法计算3、4，直至收敛。 主要优点：收敛速度快，在最优解附近至少是二阶收敛。 主要缺点：初始点选择对收敛影响很大，需要计算二阶导数。如果必须用数值方法求二阶导数，则计算时的舍入误差和近似误差就会对算法的效率影响很大。 假定我们已经定出一个区间21,，已知 0)( 1，0)( 2 两点格式的核心就是逐步缩小区间21,，直到以足够的精度求出目标函数的最小值。缩小区间的方法是每次迭代时利用下列公式求得一个最小值的新估

3、计： )(1223 式中， 1 , 0是根据所采用的插值公式而决定的实数。 决定的方法常见的有弦位法和两分法 弦位法是利用1点的)( 1和2点的)( 2，在1和2之间对)( 进行线性插值，即 )()( )( )( )( 112121 该式给出0)( 的点*的近似值3 )()( )( )( 1212223 由此可见)( )( )( 122。 0.618 法又叫做黄金分割法，是不用导数的一维搜索方法中比较常用的一种方法。 设0为允许的最后的搜索区间长度， 令618. 0， 则 0.618法的计算步骤如下： (1) 计算 )(1 (1111aba，)(1 )(1111aba，)(1 令1k。 2)

4、若kkab，则计算结束，最优解,*kkab，可取2/ )(*kkab ； 否 则 ， 若)()(kk， 则 转 3) ，)()(kk，则转 4） 。 3) 令kka1，kkbb1，再令kk1，)(1111kkkkaba，计算)(1k，转 5)。 4) 令kkaa1，kkb1，再令kk1，)(1 (1111kkkkaba，计算)(1k，转 5)。 5) 令1 kk，返回 2)。 41664)( min234xxxxxf 前面讲的一维搜索方法，有的需要从一个初始的搜索区间出发，逐次进行迭代计算；大多数算法，都要从一个初始点出发，逐次进行迭代。下面给出一种进退算法，它可以同时确定初始的搜索区间和初始

5、点。 (1) 选定初始点的一个估计值0t，初始步长0h，计算)(0t； (2) 令htt02，计算)(2t； (3) 若)()(02tt，转第 4 步；否则，若)()(02tt，令hh，转第 4 步； (4) 令htt01，计算)(1t； (5) 若)()(01tt，则令hh2，02tt ，10tt ，转第 4 步；否则，若)()(01tt，转第 6 步。 (6) 令),min(21tta ，),max(21ttb ，则,ba即为所求的初始区间，而2/ )(0abt可作为所求的初始点，计算结束。 在实际计算中，一般做不到精确的一维搜索，实际上，也没有必要做到这一点。因为精确的一维搜索需要付出较

6、高的代价，而对加速收敛作用不大。所以，不精确一维搜索方法收到广泛的重视和欢迎。 设要求)()()(minkkfsx，在不精确一维搜索中，通过要求)1( kf x比)(kf x下降一定的数量，而且在新点)()() 1(kkksxx处沿)(ks的方向导数比在)(kx点沿)(ks的方向导数值大一定的数量。 通常采用的是 Wolfe-Powell 不精确一维搜 索 准 则 ， 简 称 Wolfe-Powell 准 则 ， 即 对 给 定 的 常 数1,021cc，要求k满足如下条件： a. )()(1) 1()(kkkkkfcffsxxxT b. )()(2)()1(kkkkfcfsxsxTT 根据计算经验，常取1 . 01c，5 . 02c。 不精确一维搜索算法的计算步骤： 设点)(kx， 搜索方向)(ks已求得，为书写简便，令)(kkffx,)1(1kkffx，)(kkf xg, ) 1(1kkf xg。求出kf，kg。 (1) 给定1 , 01c，1 ,12cc ，令0, 1, 0jba。 (2) 令kkksxx)()1(， 计算1kf，1kg， 若满足条件 a、 b，则令k，