第四章无约束优化方法 1.概述 2.最速下降法 3.牛顿型方法 4.梯度法及共轭梯度法 5.DFP变尺度法 6.坐标轮换法; 7.鲍威尔法; 2021/2/20
2021/2/20 1 第四章 无约束优化方法 6. 坐标轮换法; 7. 鲍威尔法; 4. 梯度法及共轭梯度法; 5. DFP变尺度法. 1. 概述 2. 最速下降法 3. 牛顿型方法
1概述 有些实际问题,其数学模型本身就是 个无约東优化问题可以按无约束问题来 处理 通过熟悉无约束优化问题的解法可以为 研究约束优化问题打下良好的基础 约束优化问题的求解可以通过一系列无 约束优化方法来达到 2021/2/20 2
2021/2/20 2 1.概述 • 有些实际问题，其数学模型本身就是一 个无约束优化问题可以按无约束问题来 处理 • 通过熟悉无约束优化问题的解法可以为 研究约束优化问题打下良好的基础 • 约束优化问题的求解可以通过一系列无 约束优化方法来达到
·无约束优化问题 x x 2: 使f(x)③min ·对于无约束优化问题的求解,可以直接就用第 章讲述的极值条件来确定极值点位置。这就 是把求函数极值的问题变成求解方程 f 0 ·数值求解 x'+ ard 0,1,2,L) 各种无约束优化方法的区别就在于确定其搜索 方向的方法不同 2021/2/20
2021/2/20 3 • 无约束优化问题 • 对于无约束优化问题的求解，可以直接就用第 三章讲述的极值条件来确定极值点位置。这就 是把求函数极值的问题变成求解方程 • 数值求解 • 各种无约束优化方法的区别就在于确定其搜索 方向的方法不同。 T 1 2 [ , , , ] ( ) min x x x xn f x = ® L 使 ? f 0 1 ( 0,1, 2, ) k k k x x d k ak + = + = L
开始 无约束优化方法的分类 给定xd的初始值 类是利用目标函数的 阶或二阶导数的无约 计算a 束优化方法 使∫(x+ad)最小 最速下降法、共轭梯度法 x? x ad 牛顿法及变尺度法等。 否 >另一类是只利用目标函 是/满足收敛条 件? 数值的无约束优化方法 结束 给定新的d 坐标轮换法,单形替换法 及鲍威尔( Powel)法等。 图10无约束极小化算法的粗框图 2021/2/20
2021/2/20 4 • 无约束优化方法的分类 ➢一类是利用目标函数的 一阶或二阶导数的无约 束优化方法 • 最速下降法、共轭梯度法、 牛顿法及变尺度法等。 ➢另一类是只利用目标函 数值的无约束优化方法 • 坐标轮换法，单形替换法 及鲍威尔（Powell）法等。 开始 给定 x d 的初始值 计算a * 使 f a (x d + )最小 a * x x d ? 满足收敛条 件？ 结束 给定新的 d 图 10 无约束极小化算法的粗框图 是 否
2.最速下降法 目标函数值fx)→min 从某点x出发,其搜索方向d取该点的负梯度方向(最速 下降方向),使函数值在该点附近的范围内下降最快 k+1=xk- ak?f(k) k 0,1,2,L 由于最速下降法是以负梯度方向作为搜索方向,所以 最速下降法又称为梯度法 问题转化为求最佳步长因子的一维搜索问题 f(xk+1)=f(xk-ak? f(xk)) minf(xk-a? f(xk)) mini ca) 2021/2/20
2021/2/20 5 2. 最速下降法 • 目标函数值f(x) →min • 从某点x出发，其搜索方向dk取该点的负梯度方向(最速 下降方向) ，使函数值在该点附近的范围内下降最快 • 由于最速下降法是以负梯度方向作为搜索方向，所以 最速下降法又称为梯度法 • 问题转化为求最佳步长因子的一维搜索问题 ( ) 1 0,1, 2, x x a f x k k k k k + = - ? L ( ) ( ( )) ( ( )) ( ) k k k k k k 1 min min a a f x f x a f x f x a f x a + = - ? - ? j
根据一元函数极值的必要条件和多元复合函数求导公 式,得 j Aa)=-?fLxk ak#if(xk)] f(xk)=0 xk+1=Xk- ak? f(x, x [蜒( Xk+l )f(xk)=0 相邻两点的函数梯度相互垂直 局部最快,整体上并不是最快 图最速下降法的搜索路径 2021/2/20 6
2021/2/20 6 • 根据一元函数极值的必要条件和多元复合函数求导公 式，得 • 相邻两点的函数梯度相互垂直 • 局部最快，整体上并不是最快 ( ) { [ ( )]} ( ) T j ¢ a f x a f x f x = - ? k k k k 蜒 = 0 [ ( )] ( ) T 蜒f x f x k k + 1 = 0 ( ) x x a f x k k k k + 1 = - ? T d d k k + 1 = 0 x1 x2 O 图 最速下降法的搜索路径
例题 1.求目标函数f(x)x12+25x2的极小值 取初始点x0=[2,2丁 初始点处函数值及梯度分别为 104 f(r) 2 沿负梯度方向搜索 40 f(x0) )0 100 0 2021/2/20
2021/2/20 7 例题 1. 求目标函数f(x)=x1 2+25x2 2的极小值 取初始点x 0=[2,2]T 初始点处函数值及梯度分别为 ( ) 0 f x = 104 ( ) 1 0 2 2 4 50 100 x f x x 轾 轾 ? = 犏 犏 犏 犏 臌 臌 沿负梯度方向搜索 ( ) 0 1 0 0 0 0 0 2 4 2 4 2 100 2 100 a x x a f x a a 轾 轾 轾 - = - ? - = 犏 犏 犏 犏 犏 犏- 臌 臌 臌
求最佳步长 f(x)=minf[x-a? f(xo) min{(2-4a0)2+25(2-1000}= miny (a a为一维搜索最佳步长,应满足极值必要条件 ja0)=-8(2-4)-5000(-100)=0 可算出一维搜索最佳步长 626 0.02003072 31252 以及第一次迭代设计点的位置和函数值 1.919877 1000:0,3071785?102 从而完成了最速下降法的第一次迭代 2021/2/20 8
2021/2/20 8 a0为一维搜索最佳步长，应满足极值必要条件 ( ) [ ( )] {( ) ( ) } ( ) 1 0 0 2 2 0 0 min min 2 4 25 2 100 min a a a f x f x a f x a a a j = - ? = - + - = ( ) ( ) ( ) j ¢ a a a 0 = - - - - = 8 2 4 5000 2 100 0 可算出一维搜索最佳步长 0 626 0.02003072 31252 a = = 以及第一次迭代设计点的位置和函数值 0 1 2 0 2 4 1.919877 2 100 0.3071785 10 a x a - 轾 - 轾 = = 犏 犏 犏臌 - 犏犏- ? 臌 从而完成了最速下降法的第一次迭代 求最佳步长
继续下去,经过10次迭代后,可以得到最 优解 f(x")=0 该问题的目标函数fx)的等值线为一族椭圆 迭代点从x走的是一段锯齿路线。 2021/2/20
2021/2/20 9 • 继续下去，经过10次迭代后，可以得到最 优解 • 该问题的目标函数f(x)的等值线为一族椭圆， 迭代点从x 0走的是一段锯齿路线。 0 0 x * 轾 = 犏犏臌 f x( ) 0 * = x 0 x 1 x 2
最速下降算法的程序框图 给定x0,E k=0 dk= f(x) ak=minf(x*+a, dk) x*+l=x+adk k=k+1 是 否 +1-< 结束 2021/2/20
2021/2/20 10 最速下降算法的程序框图 给定x 0 , k=0 d k=f(xk ) ak=minf(xk+akd k ) x k+1=xk+akd k k=k+1 ‖x k+1－x k x*=x ‖＜ k+1 结束 是 否