第五章无约束优化的间接搜索法.ppt
《第五章无约束优化的间接搜索法.ppt》由会员分享,可在线阅读,更多相关《第五章无约束优化的间接搜索法.ppt(40页珍藏版)》请在三一文库上搜索。
1、机械优化设计,太原科技大学 张学良,第五章 无约束优化的间接搜索法,间搜索法是指搜索方向S(k)的构建利用目标函数的一阶或二阶导数信息的无约束优化方法,如梯度法、牛顿法、共轭梯度法、变尺度法。,X (k+1)=X (k) + (k) S(k) (k =0 , 1 , 2 , ),基本思想,5.1 梯度法(最速下降法、负梯度法),利用负梯度方向作为迭代计算的搜索方向,即 S(k) = f (X(k) ) 或 S(k) = f (X(k) )/| f (X(k) ) |,迭代计算公式,X (k+1)=X (k) + (k) f (X(k) ) 或 X (k+1)=X (k) + (k) f (X(
2、k) ),举例: 用梯度法求目标函数 f (X) = x12 + 4x22 的无约束最优解。初始点X1(0)= 0 0 T , X2(0)= 2 2 T。,基本思想和基本算法,5.2 牛顿法,在点X(k)的邻域内,用一个二次函数(X) 来近似代替原目标函数,并以 (X ) 的极小点作为原目标函数的极小点的近似值,若不满足收敛精度要求,则将该近似极小点作为下一次迭代的初始点。如此反复迭代,直到所求的近似极小点满足收敛精度要求为止。,f (X) f (X (k) + T f (X (k) (X - X (k) + 0.5 (X - X (k) T 2 f (X (k) (X - X (k)= (X
3、), (X)的极小点应满足: (X)=0 即 f (X (k)+ 2 f (X (k) (X - X (k) =0,2 f (X (k) (X - X (k) = - f (X (k),当 2 f (X (k) 正定且有逆阵时,上式两边同时左乘 2 f (X (k) -1, 得,X = X (k) - 2 f (X (k) -1 f (X (k),牛顿法的迭代公式为 X (k+1) = X (k) - 2 f (X (k) -1 f (X (k),X (k+1)=X (k) + (k) S(k),牛顿方向:S(k) = - 2 f (X (k) -1 f (X (k) 迭代步长:(k) =1,
4、修正牛顿法(又称阻尼牛顿法)的迭代公式为 X (k+1) = X (k) - (k) 2 f (X (k) -1 f (X (k) 阻尼因子: (k),计算步骤及算法框图,1) 任选初始点 X (0) ,给定收敛精度0, k=0;,2) 计算X (k)点的梯度f (X (k)及其模;,3) 检验终止条件: | f (X (k) | ? 若满足,则输出最优解:X * = X (k), f * = f (X *) ,并终止迭代计算 ; 否则,继续下一步迭代计算;,4)计算X (k)点的海赛矩阵2 f (X (k)及其逆矩阵2 f (X (k) -1,5)沿牛顿方向S(k) = - 2 f (X (
5、k) -1 f (X (k) 进行一维搜索,求最佳步长(k);,6)令X (k+1)=X (k) + (k) S(k) ,并令k k+1,转2),重复上述迭代计算过程。,举例: 用牛顿法求目标函数 f (X) = x12 + 4x22 的无约束最优解。初始点X1(0)= 0 0 T , X2(0)= 2 2 T。,解: f (X) = 2x1 8x2 T,X1(1)= X1(0) - 2f (X1(0)-1 f (X1(0) ),X2(1)= X2(0) - 2f (X2(0)-1 f (X2(0) ),可见,X2(1)= X1(0) = 0 0 T 就是目标函数的理论极小点,仅仅迭代了一次,
6、与初始点的选择无关。,由于一般函数在极小点附近呈现出较强的二次性,所以牛顿法在极小点附近收敛速度较快。但无论是牛顿法还是修正牛顿法在每次迭代计算时都要计算目标函数的海赛,矩阵及其逆阵,因此计算工作量很大,特别是矩阵求逆,当维数高时工作量更大,且当海赛矩阵为奇异阵时,其逆阵不存在,无法使用牛顿法,所以在实际使用中受到一定限制。另外,从计算机存储方面考虑,牛顿法所需要的存储量是很大的。,若能设法构造一个矩阵来逼近海赛矩阵的逆阵而避免计算海赛矩阵及其逆阵,这样的方法统称为拟牛顿法。如只用梯度信息但比梯度法快的共轭梯度法,以及针对牛顿法提出的变尺度法等。,基本思想,5.3 共轭梯度法,共轭梯度法属于共
7、轭方向法中的一种方法。它是利用目标函数在迭代点X(k)的梯度来构造共轭搜索方向的,具有二次收敛性。,共轭梯度法搜索的第一步沿负梯度方向,以后各步沿与上次搜索方向相共轭的方向进行搜索。共轭梯度法的关键是如何在迭代过程中不断生成共轭搜索方向,共轭梯度法共轭搜索方向的生成,考虑二次函数 f (X) = 0.5 XT H X + BT X + C,从 X(k) 出发,沿H的某一共轭方向S(k)作一维搜索得到 X(k+1),即 X(k+1) X(k) = (k) S(k) (1),将f (X)在 X(k) 和 X(k+1)两点处的梯度表示并记作,g(k) = f (X(k) ) = H X(k) + B
8、 (2) g(k+1) = f (X(k+1) ) = H X(k+1) + B (3),(3)-(2)得,g(k+1) g(k) = H ( X(k+1) X(k) )= (k) H S(k) (4),(4)式两边同时左乘S(j) T,有 S(j) Tg(k+1) g(k) = (k) S(j) TH S(k) = 0,若S(j)和S(k)关于H共轭,则有,S(j) T H S(k) = 0,即 S(j) T g(k+1) g(k) = 0 (5),式(5)就是共轭方向与梯度之间的关系。它表明沿方向S(k) 进行一维搜索,其终点X(k+1)与始点X(k)梯度之差(g(k+1)g(k)与 S(
9、k) 的共轭,方向S(j)与正交。共轭梯度法就是利用这个性质做到不必计算矩阵H就能求得共轭方向的。,1)设初始点X(0) ,第一个搜索方向S(0)取X(0)点的负梯度方向 -g(0)。即 S(0) = -g(0) 沿S(0)进行一维搜索,得 X(1) = X(0) + (0) S(0),并计算X(1)点的梯度 g(1) 。,那么, g(1)与S(0) 有什么关系呢?,X(0),g(1),-g(0),X(1),二者正交,即 g(1)TS(0)=0 或 S(0)Tg(1) =0,因此,S(0)与g(1)构成平面正交系。,2)在S(0)与g(1)构成的平面正交系中求S(0)的共轭方向S(1),以此作
10、为下一步迭代计算的搜索方向。取S(1)为S(0)与g(1)的线性组合,即 S(1) = -g(1) + (0)S(0) 其中,(0)为待定常数,可以利用共轭方向与梯度之间的关系求得。,由 S(1) T g(1) g(0) = 0 有 -g(1) + (0)S(0) T g(1) g(0) = 0,展开,得 - g(1)Tg(1) +g(1)Tg(0)+(0)S(0)Tg(1) - (0)S(0)Tg(0) = 0,所以 - g(1)Tg(1) - (0)S(0)Tg(0) = 0,所以 (0) = - g(1)Tg(1) / S(0)Tg(0) = g(1)Tg(1) / g(0)Tg(0)
11、= |g(1)|2 / |g(0)|2,S(1) = -g(1) + |g(1)|2 / |g(0)|2 S(0),沿S(1)进行一维搜索,得 X(2) = X(1) + (1) S(1),并计算X(2)点的梯度 g(2) ,则有,S(1)Tg(2) =0,故有 -g(1) + (0)S(0) T g(2) = 0 (6),因为S(0)和S(1)共轭,所以有 S(0) T g(2) g(1) = 0,因为 S(0) T g(1) = 0 所以 S(0) T g(2) = 0,即 g(2) 与g(0)正交。 所以 S(0) T g(2) = 0,由式(6)得 g(1) T g(2) = 0,可见
12、, g(0)、g(1) 、g(2)构成一个空间正交系。,3)在g(0)、g(1)、g(2)构成的空间正交系中求与S(0)及S(1)均共轭的方向S(2),以此作为下一步迭代计算的搜索方向。仍取S(2)为g(0)、g(1)、g(2) 的线性组合,即 S(2) = -g(2) + (1) g(1) + (0) g(0) 其中, (1) 、 (0) 为待定常数,可以利用共轭方向与梯度之间的关系求得。,S(2) T g(1) g(0) = 0 S(2) T g(2) g(1) = 0,即 -g(2) + (1) g(1) + (0) g(0) T g(1) g(0) = 0 -g(2) + (1) g(
13、1) + (0) g(0) T g(2) g(1) = 0,所以 (1)g(1)Tg(1) - (0) g(0)T g(0) = 0 -g(2)T g(2) - (1)g(1)Tg(1) = 0,令 (1) = - (1),得 (1) = - (1) = g(2)T g(2)/ g(1)Tg(1) = |g(2)|2 / |g(1)|2,(0) = (1) g(1)T g(1)/ g(0)Tg(0) = - (1) (0),因此 S(2) = -g(2) + (1) g(1) + (0) g(0) = -g(2) - (1) g(1) - (1) (0) g(0) = -g(2) + (1)
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第五 无约束 优化 间接 搜索
链接地址:https://www.31doc.com/p-2582849.html