3-2非精确一维搜索资料课件.ppt

1、非精确一维搜索非精确一维搜索基本思想基本思想n Armijo-Goldstein 非精确一维搜索方法非精确一维搜索方法n Wolf-Powell 非精确一维搜索方法非精确一维搜索方法n 后退法后退法基本方法基本方法 前面介绍的几种线搜索方法，前面介绍的几种线搜索方法，都是为了获得一元函数的都是为了获得一元函数的最优解，所以习惯上称为最优解，所以习惯上称为精确线搜索精确线搜索在解非线性规划问在解非线性规划问题中，线搜索一般很难得到真正的精确值因此，题中，线搜索一般很难得到真正的精确值因此，非精确非精确的线搜索的线搜索开始日益受到重视开始日益受到重视在在kx点确定了下降点确定了下降方向方向kd后后

2、，只需后继只需后继 .1kkxfxf 继迭代点继迭代点x xk k+1+1= =x xk k+ + 使得目标函数有满意的下降量即使得目标函数有满意的下降量即可可, , 即即kd 大大节省计算量，大大节省计算量， 提高效率提高效率. . 在实际计算中，在实际计算中，我们不仅要求函数值下降，而且对下降量我们不仅要求函数值下降，而且对下降量有一定的要求有一定的要求非精确一维搜索非精确一维搜索基本公式基本公式Armijo-Goldstein 非精确一维搜索方法非精确一维搜索方法设设 xf可微，可微，取取,21, 0 选取选取0 k 使使： 2 . 2 . 3 )(kTkkkkkkdxfxfdxf3 .

3、 2 . 3 )()1 (kTkkkkkkdxfxfdxf非精确一维搜索非精确一维搜索几何解释几何解释Armijo-Goldstein 非精确一维搜索方法非精确一维搜索方法x xk k此准则下的此准则下的可接受区间可接受区间为为 b b, , c c 非精确一维搜索非精确一维搜索算法步骤算法步骤Armijo-Goldstein 非精确一维搜索方法非精确一维搜索方法非精确一维搜索非精确一维搜索Wolfe-Powell 非精确一维搜索方法非精确一维搜索方法问题问题 Armijo-Goldstein 准则有可能把最优步长排除在可接受区间外准则有可能把最优步长排除在可接受区间外面为此，面为此，Wo1f

4、ePowell给出了一个更简单的条件代替给出了一个更简单的条件代替(3.2.3)式式.基本公式基本公式 ,1 ,21, 0 设设 xf可微，可微， 取取选取选取0 k 使使： 2 . 3 . 3 )(kTkkkkkkdxfxfdxf4 . 3 . 3)(kTkkTkkkdxfddxf或用下面更强的条件代替（或用下面更强的条件代替（3.3.43.3.4）式：）式：bdxfdpxfkTkkTkkk4 . 3 . 3非精确一维搜索非精确一维搜索Wolfe-Powell 非精确一维搜索方法非精确一维搜索方法基本公式基本公式非精确一维搜索非精确一维搜索Wolfe-Powell 非精确一维搜索方法非精确一

5、维搜索方法几何解释几何解释此准则下的可接此准则下的可接受区间为受区间为 e e, , c c 非精确一维搜索非精确一维搜索Wolfe-Powell 非精确一维搜索方法非精确一维搜索方法几何解释几何解释更强的条件更强的条件bdxfdpxfkTkkTkkk4 . 3 . 3 k 可接受点处的切线的斜率可接受点处的切线的斜率 不能不能“正正”的太大的太大非精确一维搜索非精确一维搜索算法步骤算法步骤Wolfe-Powell 非精确一维搜索方法非精确一维搜索方法解：解： Tkx0, 0 例例 用不精确线搜索求用不精确线搜索求RosenbrockRosenbrock函数：函数： 2122121100 xx

6、xxf 在点在点沿方向沿方向 Tkp0, 1 的近似步长的近似步长.k ,20012400212112212 xxxxxxxf . 2,0, 2, 10, 0 kTkTkkpggffWolfe-Powell 非精确一维搜索方法非精确一维搜索方法非精确一维搜索非精确一维搜索举例举例Step1Step1：给定给定. 5 . 0,1 . 0 令令0, 1, 0 jba Step2Step2： .1000, 1,0 , 111 ffpxxkTkkk 因为因为, 2 . 0991 kTkkkpgff 所以（所以（3.3.23.3.2）不成立，转）不成立，转Step3.Step3.Step3Step3：令

7、令 , 5 . 02/012/, 1 ab转转Step2,Step2,重新计算重新计算1 kxWolfe-Powell 非精确一维搜索方法非精确一维搜索方法非精确一维搜索非精确一维搜索举例举例计算过程见下表：计算过程见下表：成立成立0.7900.12513不成立0.9530.2512不成立6.250.511不成立100110条件(2)条件(1)jkxkf1kx1kf T0, 0T0, 0T0, 0T0, 0T0, 1T0, 5 . 0T0,25. 0T0,125. 0Wolfe-Powell 非精确一维搜索方法非精确一维搜索方法举例举例与黄金分割法对比：初始区间与黄金分割法对比：初始区间0,1

8、,0,1,精度精度0.0010.0010.7780.7750.1800.1460.090,0.23640.7750.8340.1460.0900,0.23630.7750.7900.1460.1250.090,0.18050.8940.7750.2360.1460,0.38222.5110.8940.3820.2360,0.618114.7322.5110.6180.3820,10迭代次数ba,1x2x1f2fWolfe-Powell 非精确一维搜索方法非精确一维搜索方法举例举例0.7710.7710.1640.1620.159,0.167100.7710.7710.1620.1590.154

9、,0.16790.7710.7720.1590.1540.146,0.16780.7720.7710.1670.1590.146,0.18070.7710.7740.1590.1460.125,0.1806迭代次数ba,1x2x1f2fWolfe-Powell 非精确一维搜索方法非精确一维搜索方法举例举例与黄金分割法对比：初始区间与黄金分割法对比：初始区间0,1,0,1,精度精度0.0010.001非精确一维搜索非精确一维搜索后退法后退法 在实际中有时仅采用准则在实际中有时仅采用准则(3.3.2)(3.3.2)式，并要求式，并要求不太小我们把仅利用准则不太小我们把仅利用准则(3.3.2)(3.3.2)式的做法叫做式的做法叫做简单准则简单准则利用简单准则的非精确一维搜索方法称为利用简单准则的非精确一维搜索方法称为后退法后退法. .提出提出基本思想基本思想非精确一维搜索非精确一维搜索算法步骤算法步骤后退法后退法