机械优化设计--第四章(第6次课).pptx
- 文档编号:18955185
- 上传时间:2024-09-13
- 格式:PPTX
- 页数:94
- 大小:2.91MB
机械优化设计--第四章(第6次课).pptx
《机械优化设计--第四章(第6次课).pptx》由会员分享,可在线阅读,更多相关《机械优化设计--第四章(第6次课).pptx(94页珍藏版)》请在冰点文库上搜索。
机械优化设计20162016年年99月月上上海海海海事事大大学学SHANGHAIMARITIMEUNIVERSITYSHANGHAIMARITIMEUNIVERSITY何军良何军良03:
241上海海事大学上海海事大学ShanghaiMaritimeUniversity19092009200419121958机械优化设计中的几个问题优化设计概述优化设计的数学基础2目录CONTENTS一维搜索方法无约束优化方法线性规划约束优化方法03:
24第四章无约束优化方法概述01最速下降法牛顿型方法共轭方向与共轭方向法020304坐标轮换法05共轭梯度法变尺度法鲍威尔方法060708单形替换法0903:
24303:
24变尺度法也称拟牛顿法,它是基于牛顿法的思想而又作了重大改进的一类方法。
我们所介绍的变尺度法是由Davidon于1959年提出又经Fletcher和Powell加以发展和完善的一种变尺度法,故称为DFP变尺度法。
4.7变尺度法能否克服各自的缺点,综合发挥其优点?
2)阻尼牛顿法1)梯度法*简单,开始时目标函数值下降较快,但越来越慢。
*目标函数值在最优点附近时收敛快,但要用到二阶导数和矩阵求逆。
(1)问题提出403:
244.7变尺度法
(2)基本思想n变量的尺度变换是放大或缩小各个坐标。
通过尺度变换可以把函数的偏心程度降到最低限度。
n这种算法仅用到梯度,不必计算海赛阵及其逆矩阵,但又能使搜索方向逐渐逼近牛顿方向,具有较快的收敛速度。
n尺度变换技巧能显著地改进几乎所有极小化方法的收敛性质。
例如在用最速下降法求极小值时,需要进行10次迭代才能达到极小点。
梯度法:
牛顿法:
503:
244.7变尺度法
(2)基本思想进行尺度变换在新的坐标系中,函数f(x)的二次项变为:
目的:
减少二次项的偏心如G是正定,则总存在矩阵Q,使得:
对于二次函数:
603:
244.7变尺度法
(2)基本思想用矩阵Q-1右乘等式两边,得:
用矩阵Q左乘等式两边,得:
所以上式说明:
二次函数矩阵G的逆阵,可以通过尺度变换矩阵来求得。
703:
24(3)变尺度法的搜索方向:
S(k)=-Akgk,称为拟牛顿方向。
(1)Ak为构造的nn阶对称矩阵,它随迭代点的位置变化而变化,对梯度起到改变尺度的作用,又称为变尺度矩阵。
n若Ak=I,上式为梯度法的迭代公式n若Ak=Hk-1,上式为阻尼牛顿法的迭代公式(3)迭代公式4.7变尺度法
(2)当矩阵Ak不断地迭代而能很好地逼近时,就可以不再需要计算二阶导数。
变尺度法的关键在于尺度矩阵Ak的产生。
803:
24拟牛顿方向S(k)=-Akgk必须具有下降性、收敛性和计算的简便性。
n下降性要求变尺度矩阵为对阵正定矩阵;n收敛性要求变尺度矩阵逐渐逼近Hk-1,满足拟牛顿条件;n简便性希望变尺度矩阵有如下递推形式:
Ak+1=Ak+Ak(4)变尺度矩阵的产生4.7变尺度法903:
24下降性:
要求S(k)与-gk之间的夹角小于90o,即:
-S(k)Tgk0将拟牛顿方向带入上式,得:
-S(k)Tgk=AkgkTgk=gkTAkgk0所以只要Ak为对阵正定矩阵,S(k)就是下降方向。
(4)变尺度矩阵的产生4.7变尺度法1003:
24变尺度矩阵是随迭代过程的推进而逐次改变的,因而它是一种矩阵序列选取初始矩阵A0,并以梯度方向快速收敛,通常取单位矩阵E作为初始矩阵,即A0=E。
而后的矩阵均是在前一构造矩阵的基础上校正得到,令推广到一般的k+1次构造矩阵Ak,k=1,2,A1=A0+A0Ak+1=Ak+Ak矩阵序列的矩阵序列的基本迭代式基本迭代式Ak称为校正矩阵(4)变尺度矩阵的产生4.7变尺度法简便性:
1103:
24n构造矩阵Ak+1应该满足一个重要条件拟牛顿条件n变尺度法采用构造矩阵来代替牛顿法中海赛矩阵的逆阵,主要目的之一就是为了避免计算二阶偏导数和逆矩阵,力图仅用梯度和其他一些易于获得的信息来确定迭代方向,因此,拟牛顿条件是关于海赛矩阵和梯度之间的关系。
(5)拟牛顿条件4.7变尺度法1203:
24设F(x)为一般形式n阶的目标函数,并具有连续的一、二阶偏导。
在点x(k)处的二次泰勒近似展开该近似二次函数的梯度为:
式中,若令,则有(5)拟牛顿条件4.7变尺度法1303:
24上式中,x(k+1)x(k)称之为位移矢量,并简化书写:
而gk+1-gk是前后迭代点的梯度矢量差,简化书写:
由以上三式得:
海赛矩阵与梯度间的关系式(5)拟牛顿条件4.7变尺度法1403:
24按照变尺度法产生构造矩阵的递推思想,期望能够借助前一次迭代的某些结果来计算下一个构造矩阵,因此可以根据上式,用第k+1次构造矩阵Ak+1近似代替Hk-1,则上式即产生构造矩阵Ak+1应满足的一个重要条件,通常称为拟牛顿条件或拟牛顿方程(5)拟牛顿条件4.7变尺度法1503:
24(6)变尺度矩阵的构造4.7变尺度法拟牛顿条件可写成或DFP算法中的校正矩阵Ak取为下列形式:
待定系数保证Ak对称1603:
24(6)变尺度矩阵的构造4.7变尺度法将
(2)代入
(1):
两边对比得:
取则:
回代到
(2)得:
DFP变尺度法的迭代式为:
1703:
24由上式可以看出,构造矩阵Ak+1的确定取决于第k次迭代中的下列信息:
上次的构造矩阵:
Ak迭代点的位移矢量:
迭代点的梯度增量:
因此,不必作二阶导数矩阵及其求逆的计算(6)变尺度矩阵的构造4.7变尺度法1803:
24nDFP算法的收敛速度介于梯度法和牛顿法之间。
nDFP法具有二次收敛性(搜索方向的共轭性)。
对于二次函数F(x),DFP法所构成的搜索方向序列S(0),S
(1),S
(2),为一组关于海赛矩阵H共轭的矢量,即DFP法属于共轭方向法,具有二次收敛性。
在任何情况下,这种方法对于二次目标函数都将在n步内搜索到目标函数的最优点,而且最后的构造矩阵An必等于海赛矩阵H。
(7)DFP变尺度算法的特点4.7变尺度法1903:
24(7)DFP变尺度算法的特点4.7变尺度法n关于算法的稳定性,数值计算稳定性较差。
1.算法的稳定性是指算法的每次迭代都能使目标函数值单调下降。
2.构造矩阵正定性从理论上肯定了DFP法的稳定性,但实际上,由于每次迭代的一维搜索只能具有一定的精确度,且存在机器运算的舍入误差,构造矩阵的正定性仍然有可能遭到破坏;3.为了提高实际计算中的稳定性,一方面应对一维搜索提出较高的精度要求,另一方面,当发生破坏正定性时,将构造矩阵重置为单位矩阵E重新开始,通常采用的简单办法是在n次迭代后重置单位矩阵2003:
241.任取初始点x(0)给出迭代精度.计算初始点精度及其模。
若转步骤,否则进行下一步2.置k0,取AkE3.计算迭代方向,沿S(k)方向做一维搜索求优化步长a(k),使确定下一个迭代点(8)DFP变尺度算法的计算步骤4.7变尺度法2103:
244.计算x(k+1)的梯度gk+1及其模,若则转步骤,否则转下一步5.计算位移矢量和梯度矢量按DFP公式计算构造矩阵6.置kk+1。
若kn(n为优化问题的维数)返回步骤,否则返回步骤7.输出最优解(x*,F*),终止计算(8)DFP变尺度算法的计算步骤4.7变尺度法2203:
24DFP算法流程图k=n?
入口入口出口出口+-+-2303:
24解:
1)取初始点,为了按DFP法构造第一次搜寻方向d0,需计算初始点处的梯度取初始变尺度矩阵为单位矩阵A0=I,则第一次搜寻方向为例:
用DFP算法求下列问题的极值:
24(9)DFP算例4.7变尺度法03:
24一维搜索最佳步长应满足得:
2)再按DFP法构造点x1处的搜寻方向d1,需计算沿d0方向进行一维搜索,得(9)DFP算例4.7变尺度法2503:
24代入校正公式=(9)DFP算例4.7变尺度法2603:
24=第二次搜寻方向为再沿d1进行一维搜索,得(9)DFP算例4.7变尺度法2703:
24为一维搜索最佳步长,应满足,得3)判断x2是否为极值点梯度:
海赛矩阵:
(9)DFP算例4.7变尺度法梯度为零向量,海赛矩阵正定。
可见满足极值充要条件,因此为极小点。
2803:
24例:
用DFP变尺度法求目标函数的最优解。
已知初始点,迭代精度=0.01解:
第一次迭代:
(9)DFP算例4.7变尺度法2903:
24式中最优步长应用一维搜索方法在计算机上求解。
为了说明问题,又因为此例目标函数简单,所以用解析法来求:
为求极小,将上式对求导,并令f()=0得:
于是:
(9)DFP算例4.7变尺度法3003:
24第二次迭代:
确定x
(1)点的拟牛顿方向S
(1)按DFP公式计算构造矩阵(9)DFP算例4.7变尺度法3103:
24将数据代入得则拟牛顿方向为沿S
(1)方向进行一维搜索求最优点x
(2)求一维搜索步长(9)DFP算例4.7变尺度法3203:
24则:
迭代即可结束,输出优化解(9)DFP算例4.7变尺度法3303:
24讨论:
该题的理论最优点是。
按DFP搜索方向为共轭的性质,本题为二元二次函数在两次迭代后即达到最优点,本题计算结果稍有误差,这是由于一维搜索的不精确性产生的。
若在已知A1的基础上,再用DFP公式递推下一次的构造矩阵,可计算得而计算目标函数海赛矩阵的逆阵有(9)DFP算例4.7变尺度法3403:
24DFP算法由于舍入误差和一维搜索的不精确,有可能导致Ak奇异,而使数值稳定性方面不够理想。
所以1970年,Broyden、Fletcher、Goldstein、Shanno等人提出一种更稳定的算法,称为BFGS算法。
其校正公式为:
(9)BFGS变尺度法4.7变尺度法3503:
2436
(1)概述4.8鲍威尔方法基本思想:
基于坐标轮换法,不用求导数,在迭代中逐次产生共轭搜索方向。
收敛效果:
对于正定(有极小值)二次函数,经过n轮迭代后求得极小点;对于非二次函数,一般也具有较高的收敛速度。
Powell法是求解无约束优化问题的最好方法。
将其与惩罚函数法结合,可以处理有约束优化问题。
03:
24为两个极小点根据梯度与等值面之间关系可知
(2)共轭方向的生成4.8鲍威尔方法3703:
24对于二次函数,两点处的梯度可表示为代入到公式:
(2)共轭方向的生成4.8鲍威尔方法3803:
24结论:
从不同的点出发沿某一方向分别对函数作两次一维搜索,得到两个极小点,那么这两个极小点的连线方向与该方向对G共轭
(2)共轭方向的生成4.8鲍威尔方法3903:
24(3)基本算法4.8鲍威尔方法鲍威尔基本算法的搜索过程(二维)1)任选一初始点x0,再选两个线性无关的向量,如坐标轴单位向量e1=1,0T和e2=0,1T作为初始搜索方向。
x1x2x0oe1e2d1d2x*14003:
24(3)基本算法4.8鲍威尔方法鲍威尔基本算法的搜索过程(二维)2)从x0出发,顺次沿e1,e2作一维搜索,得点,两点连线得一新方向d1x1x2x0oe1e2d1d2x*14103:
24(3)基本算法4.8鲍威尔方法鲍威尔基本算法的搜索过程(二维)用d1代替e1形成两个线性无关向量d1,e2,作为下一轮迭代的搜索方向。
再从出发,沿d1作一维搜索得点,作为下一轮迭代的初始点。
3)从出发,e2,d1作一维搜索,得到点,两点连线得一新方向:
x1x2x0ooe1e2d1d2x*1从沿d2作一维搜索得点x2。
即是二维问题的极小点x*。
4203:
24(3)基本算法4.8鲍威尔方法鲍威尔基本算法的搜索过程(二维)方法的基本迭代格式包括共轭方向产生和方向替换两主要步骤。
4303:
24(3)基本算法4.8鲍威尔方法鲍威尔基本算法的搜索过程(三维)441.第一轮基本方向组取单位坐标矢量系e1、e2、e3、en,沿这些方向依次作一维搜索,然后将始末两点相连作为新生方向。
2.再沿新生方向作一维搜索,完成第一轮的迭代。
以后每轮的基本方向组是将上轮的第一个方向淘汰,上轮的新生方向补入本轮的最后而构成:
d2k,d3k,dnk,dk03:
24(4)基本算法示例4.8鲍威尔方法4503:
24(4)基本算法示例4.8鲍威尔方法4603:
24(4)基本算法示例4.8鲍威尔方法4703:
24(4)基本算法示例4.8鲍威尔方法4803:
24(4)基本算法示例4.8鲍威尔方法4903:
24(4)基本算法示例4.8鲍威尔方法5003:
24(4)基本算法示例4.8鲍威尔方法5103:
24(4)基本算法示例4.8鲍威尔方法5203:
24(4)基本算法示例4.8鲍威尔方法5303:
24(4)基本算法示例4.8鲍威尔方法5403:
24可能在某一轮迭代中出现基本方向组为线性相关的矢量系的情况。
如第k轮中,产生新的方向:
dk=xnk-x0k=1kd1k+2kd2k+nkdnk式中,d1k、d2k、dnk为第k轮基本方向组矢量,1k、2k、nk为各方向的最优步长。
若在第k轮的优化搜索过程中出现1k=0,则方向dk表示为d2k、d3k、dnk的线性组合,以后的各次搜索将在降维的空间进行,无法得到n维空间的函数极小值,计算将失败。
(5)基本算法缺陷4.8鲍威尔方法5503:
24鲍威尔基本算法的退化x1x2x31=02e23e3S1如图所示为一个三维优化问题的示例,设第一轮中1=0,则新生方向与e2、e3共面,随后的各环方向组中,各矢量必在该平面内,使搜索局限于二维空间,不能得到最优解。
e2e3S1(5)基本算法缺陷4.8鲍威尔方法5603:
24(5)基本算法缺陷4.8鲍威尔方法5703:
24(5)基本算法缺陷4.8鲍威尔方法5803:
24(5)基本算法缺陷4.8鲍威尔方法5903:
24(5)基本算法缺陷4.8鲍威尔方法6003:
24(5)基本算法缺陷4.8鲍威尔方法6103:
24(5)基本算法缺陷4.8鲍威尔方法6203:
24(5)基本算法缺陷4.8鲍威尔方法6303:
24(5)基本算法缺陷4.8鲍威尔方法6403:
24(5)基本算法缺陷4.8鲍威尔方法6503:
24(5)基本算法缺陷4.8鲍威尔方法6603:
2467(6)修正算法4.8鲍威尔方法*根据Powell条件判定是否需换方向;如需换向,则换掉函数值下降量最大的方向。
选取n个线性无关且尽可能共轭的方向作为下一轮搜索的方向组。
做法:
形成新的搜索方向组时,不是固定的去掉前一次搜索方向组中的第一个方向,而是首先根据Powell条件,判断原方向组是否需要替换,若需要,则进一步判断原方向组中哪个方向最坏,并以前一轮新生成的搜索方向替换本轮中的这个最坏方向。
03:
2468(6)修正算法4.8鲍威尔方法方向组的构造在第k轮的搜索中,x0k为初始点,搜索方向为d1k、d2k、dnk,产生的新方向为dk,此方向的极小点为xk。
沿dk方向移动得到点xn+1k=2xnk-x0k,称之为x0k对xnk的反射点。
计算x0k、x1k、xnk、xk、xn+1k各点的函数值,记作:
F0=F(x0k)F2=F(xnk)F3=F(xn+1k)=F(xm-1k)-F(xmk)是第k轮方向组中,依次沿各方向搜索函数下降值03:
24鲍威尔算法的方向淘汰(F3)(F2)(F0)反射点反射点函数最大下降量函数最大下降量m始点始点终点终点(6)修正算法4.8鲍威尔方法6903:
24为了构造第k+1轮基本方向组,采用如下判别式:
按照以下两种情况处理:
1)上式中至少一个不等式不成立,则第k+1轮的基本方向仍用老方向组d1k、d2k、dnk。
k+1轮的初始点取x0k+1=xnkF2F0,不满足判别条件,因而下轮迭代应继续使用原来的搜索方向e1,e2因为F20,通常取a=1;
(1)令;输出XL,为原问题近似极小点;否则,转
(2)。
(扩张时=2)构造新单纯形;(4)根据不同情况,分别进行扩张,收缩或缩边,其中收缩因子(5)如果满足
(2)计算步骤4.9单型替换法8703:
24例例试用单型替换求的极小值.解解:
选,并取和这三点不在一条直线上,用它们作为初始单纯形的顶点(如图所示)(3)算例4.9单型替换法8803:
24然后计算各顶点的函数值:
可知为最差点,为最好点。
以表示和的重心,则反射点(3)算例4.9单型替换法8903:
24由于,故需扩张。
取,则因为,故以代替,由,和构成新单纯形,然后进行下一个循环。
该问题的最优解为。
经32次循环,可把目标函数减小到。
(3)算例4.9单型替换法9003:
244.10无约束优化方法总结
(1)无约束优化问题的评价准则为了比较各种优化方法的特性,必须建立合理的评价准则。
无约束优化方法评价准则主要包括以下几个方面:
1、可靠性。
即在合理的精度要求下,在一定允许时间内能解出各种不同类型问题的成功率。
能够解出的问题越多,则算法的可靠性越好。
2、有效性。
即算法的解题效率。
它有两个衡量标准。
其一是对同一题目,在相同精度和初始条件下,比较机时多少。
其二是在相同精度下,计算同一题目所需要的函数的计算次数。
3、简便性。
一方面指实现该算法的准备工作量的大小。
另一方面指算法占用存储单元的数量。
9103:
244.10无约束优化方法总结
(2)无约束优化方法的评价结论可靠性:
牛顿法较差,因为它对目标函数要求太高,解题成功率较低。
有效性:
坐标变换法和梯度法的计算效率较低,因为它们从理论上不具有二次收敛性。
简便性:
牛顿法和变尺度法的程序编制较复杂,牛顿法还占用较多的存储单元。
在选用无约束优化方法时,一方面要考虑优化方法的特点,另一方面要考虑目标函数的情况。
1、一般而言,对于维数较低或者很难求得导数的目标函数,使用坐标轮换法或鲍威尔法较合适。
2、对于二次性较强的目标函数,使用牛顿法效果好。
3、对于一阶偏导数易求的目标函数,使用梯度法可使程序编制简单,但精度不宜过高。
4、综合而言,鲍威尔法和变尺度法(DFP)具有较好的性能。
9203:
244.10无约束优化方法总结(3)无约束优化方法的联系搜索方向函数梯度修正因子所用目标函数信息梯度法I(单位阵)一阶导数牛顿法二阶导数共轭梯度法一阶导数变尺度法一阶导数方法鲍威尔法函数值零阶方法单形替换法零阶方法函数值最差点和最好点与次好点中点的连线9303:
24作业1.试用Newton法求的极小点,初始点取为。
2.用DFP算法求,取3.试用鲍威尔修正算法求目标函数的最优解。
已知初始点,迭代精度=0.0014.用共轭梯度法求,其中,选初始点。
94
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 机械 优化 设计 第四