机械优化设计之无约束优化方法培训课件.ppt

《机械优化设计之无约束优化方法培训课件.ppt》由会员分享，可在线阅读，更多相关《机械优化设计之无约束优化方法培训课件.ppt（94页珍藏版）》请在金锄头文库上搜索。

1、2019/9/7,1,何军良,2019/9/7,2,目 录,CONTENTS,2019/9/7,3,第四章 无约束优化方法,概述,01,最速下降法,牛顿型方法,共轭方向与共轭方向法,02,03,04,坐标轮换法,05,共轭梯度法,变尺度法,鲍威尔方法,06,07,08,单形替换法,09,4,变尺度法也称拟牛顿法，它是基于牛顿法的思想而又作了重大改进的一类方法。我们所介绍的变尺度法是由 Davidon 于1959年提出又经 Fletcher 和 Powell 加以发展和完善的一种变尺度法，故称为DFP变尺度法。,4.7 变尺度法,能否克服各自的缺点，综合发挥其优点？,2) 阻尼牛顿法,1) 梯度

2、法,* 简单，开始时目标函数值下降较快，但越来越慢。,* 目标函数值在最优点附近时收敛快，但要用到二阶导数和矩阵求逆。,（1） 问题提出,5,4.7 变尺度法,（2） 基本思想,变量的尺度变换是放大或缩小各个坐标。通过尺度变换可以把函数的偏心程度降到最低限度。 这种算法仅用到梯度，不必计算海赛阵及其逆矩阵，但又能使搜索方向逐渐逼近牛顿方向，具有较快的收敛速度。 尺度变换技巧能显著地改进几乎所有极小化方法的收敛性质。,例如在用最速下降法求 极小值时 ,需要进行10次迭代才能达到极小点。,梯度法:,牛顿法:,6,4.7 变尺度法,（2） 基本思想,进行尺度变换,在新的坐标系中，函数f(x)的二次项

3、变为：,目的：减少二次项的偏心,如G是正定，则总存在矩阵Q，使得：,对于二次函数:,7,4.7 变尺度法,（2） 基本思想,用矩阵Q-1右乘等式两边，得：,用矩阵Q左乘等式两边，得：,所以,上式说明：二次函数矩阵G的逆阵，可以通过尺度变换矩阵 来求得。,(3) 变尺度法的搜索方向 :S(k) = - Ak gk ，称为拟牛顿方向。,(1) Ak为构造的 n n 阶对称矩阵，它随迭代点的位置变化而变化，对梯度起到改变尺度的作用，又称为变尺度矩阵。,若Ak =I，上式为梯度法的迭代公式 若Ak = Hk-1 ，上式为阻尼牛顿法的迭代公式,（3） 迭代公式,4.7 变尺度法,(2) 当矩阵Ak 不断

4、地迭代而能很好地逼近 时，就可以不再需要计算二阶导数。,变尺度法的关键在于尺度矩阵Ak的产生 。,8,9,拟牛顿方向 S(k) = - Ak gk 必须具有下降性、收敛性和计算的简便性。,下降性要求变尺度矩阵为对阵正定矩阵；,收敛性要求变尺度矩阵逐渐逼近Hk-1，满足拟牛顿条件； 简便性希望变尺度矩阵有如下递推形式：,Ak+1 = Ak +Ak,（4） 变尺度矩阵的产生,4.7 变尺度法,下降性：要求S(k)与-gk之间的夹角小于90o，即：,-S(k)T gk0,将拟牛顿方向带入上式，得：,-S(k)T gk = Ak gkTgk = gkTAk gk 0,所以只要 Ak 为对阵正定矩阵，S

5、(k) 就是下降方向。,（4） 变尺度矩阵的产生,4.7 变尺度法,10,变尺度矩阵是随迭代过程的推进而逐次改变的，因而它是一种矩阵序列,选取初始矩阵A0，并以梯度方向快速收敛，通常取单位矩阵E 作为初始矩阵，即A0=E。而后的矩阵均是在前一构造矩阵的基础上校正得到，令,推广到一般的k+1次构造矩阵, Ak ，k=1，2，,A1=A0+A0,Ak+1=Ak+Ak,矩阵序列的 基本迭代式, Ak 称为校正矩阵,（4） 变尺度矩阵的产生,4.7 变尺度法,简便性：,11,构造矩阵Ak+1应该满足一个重要条件拟牛顿条件,变尺度法采用构造矩阵来代替牛顿法中海赛矩阵的逆阵，主要目的之一就是为了避免计算二

6、阶偏导数和逆矩阵，力图仅用梯度和其他一些易于获得的信息来确定迭代方向，因此，拟牛顿条件是关于海赛矩阵和梯度之间的关系。,（5） 拟牛顿条件,4.7 变尺度法,12,设F(x) 为一般形式 n 阶的目标函数，并具有连续的一、二阶偏导。在点 x(k) 处的二次泰勒近似展开,该近似二次函数的梯度为：,式中 ，若令 ，则有,（5） 拟牛顿条件,4.7 变尺度法,13,上式中，x(k+1) x(k) 称之为位移矢量，并简化书写:,而gk+1 - gk 是前后迭代点的梯度矢量差，简化书写：,由以上三式得 ：,海赛矩阵与 梯度间的关系式,（5） 拟牛顿条件,4.7 变尺度法,14,按照变尺度法产生构造矩阵的

7、递推思想，期望能够借助前一次迭代的某些结果来计算下一个构造矩阵，因此可以根据上式，用第 k+1 次构造矩阵 Ak+1 近似代替 Hk-1 ，则,上式即产生构造矩阵 Ak+1 应满足的一个重要条件，通常称为拟牛顿条件或拟牛顿方程,（5） 拟牛顿条件,4.7 变尺度法,15,（6） 变尺度矩阵的构造,4.7 变尺度法,拟牛顿条件 可写成,或,DFP算法中的校正矩阵 Ak取为下列形式：,待定系数,保证 Ak对称,16,（6） 变尺度矩阵的构造,4.7 变尺度法,将(2)代入(1):,两边对比得:,取,则：,回代到(2)得:,DFP变尺度法的迭代式为 ：,17,由上式可以看出，构造矩阵Ak+1的确定取

8、决于第 k 次迭代中的下列信息：,上次的构造矩阵：Ak 迭代点的位移矢量： 迭代点的梯度增量：,因此，不必作二阶导数矩阵及其求逆的计算,（6） 变尺度矩阵的构造,4.7 变尺度法,18,DFP算法的收敛速度介于梯度法和牛顿法之间。,DFP法具有二次收敛性 (搜索方向的共轭性)。,对于二次函数 F(x)，DFP法所构成的搜索方向序列S(0), S(1) , S(2) ,为一组关于海赛矩阵H共轭的矢量，即DFP法属于共轭方向法，具有二次收敛性。在任何情况下，这种方法对于二次目标函数都将在n步内搜索到目标函数的最优点，而且最后的构造矩阵 An 必等于海赛矩阵H。,（7） DFP变尺度算法的特点,4.

9、7 变尺度法,19,（7） DFP变尺度算法的特点,4.7 变尺度法,关于算法的稳定性，数值计算稳定性较差。,算法的稳定性是指算法的每次迭代都能使目标函数值单调下降。 构造矩阵正定性从理论上肯定了DFP法的稳定性，但实际上，由于每次迭代的一维搜索只能具有一定的精确度，且存在机器运算的舍入误差，构造矩阵的正定性仍然有可能遭到破坏； 为了提高实际计算中的稳定性，一方面应对一维搜索提出较高的精度要求，另一方面，当发生破坏正定性时，将构造矩阵重置为单位矩阵E重新开始，通常采用的简单办法是在 n 次迭代后重置单位矩阵,20,任取初始点 x(0) 给出迭代精度.计算初始点精度 及其模 。若 转步骤，否则进

10、行下一步,置k0，取 AkE,计算迭代方向 ，沿S(k) 方向做一维搜索求优化步长 a(k) ，使,确定下一个迭代点,（8） DFP变尺度算法的计算步骤,4.7 变尺度法,21,计算x(k+1) 的梯度gk+1及其模 ，若 则转步骤，否则转下一步,计算位移矢量 和梯度矢量,按DFP公式计算构造矩阵,置kk+1。若kn (n为优化问题的维数) 返回步骤，否则返回步骤,输出最优解（x*，F*），终止计算,（8） DFP变尺度算法的计算步骤,4.7 变尺度法,22,23,DFP算法流程图,k=n？,入口,出口,+,-,+,-,解： 1）取初始点 ，为了按DFP法构造第一次搜寻方向d0，需计算初始点处

11、的梯度,取初始变尺度矩阵为单位矩阵A0=I，则第一次搜寻方向为,例: 用DFP算法求下列问题的极值：,24,（9） DFP算例,4.7 变尺度法,一维搜索最佳步长应满足,得:,2）再按DFP法构造点x1处的搜寻方向d1，需计算,沿d0方向进行一维搜索，得,（9） DFP算例,4.7 变尺度法,25,代入校正公式,=,（9） DFP算例,4.7 变尺度法,26,=,第二次搜寻方向为,再沿d1进行一维搜索，得,（9） DFP算例,4.7 变尺度法,27,为一维搜索最佳步长，应满足,得,3）判断x2是否为极值点,梯度:,海赛矩阵 :,（9） DFP算例,4.7 变尺度法,梯度为零向量,海赛矩阵正定。

12、可见满足极值充要条件，因此为极小点。,28,例: 用DFP变尺度法求目标函数,的最优解。已知初始点 ，迭代精度=0.01,解：第一次迭代：,（9） DFP算例,4.7 变尺度法,29,式中最优步长应用一维搜索方法在计算机上求解。为了说明问题，又因为此例目标函数简单，所以用解析法来求：,为求极小，将上式对求导，并令f()=0,得：,于是：,（9） DFP算例,4.7 变尺度法,30,第二次迭代：,确定x(1)点的拟牛顿方向S(1),按DFP公式计算构造矩阵,（9） DFP算例,4.7 变尺度法,31,将数据代入得,则拟牛顿方向为,沿 S(1) 方向进行一维搜索求最优点x(2),求一维搜索步长,（

13、9） DFP算例,4.7 变尺度法,32,则：,迭代即可结束，输出优化解,（9） DFP算例,4.7 变尺度法,33,讨论：, 该题的理论最优点是 。按DFP搜索方向为共轭的性质，本题为二元二次函数在两次迭代后即达到最优点，本题计算结果稍有误差，这是由于一维搜索的不精确性产生的。, 若在已知A1的基础上，再用DFP公式递推下一次的构造矩阵，可计算得,而计算目标函数海赛矩阵的逆阵有,（9） DFP算例,4.7 变尺度法,34,DFP算法由于舍入误差和一维搜索的不精确，有可能导致Ak奇异，而使数值稳定性方面不够理想。所以1970年，Broyden、Fletcher、Goldstein、Shanno

14、等人提出一种更稳定的算法，称为BFGS算法。其校正公式为：,（9） BFGS变尺度法,4.7 变尺度法,35,36,（1） 概述,4.8 鲍威尔方法,基本思想：基于坐标轮换法，不用求导数，在迭代中逐次产生共轭搜索方向。,收敛效果：对于正定（有极小值）二次函数，经过n轮迭代后求得极小点；对于非二次函数，一般也具有较高的收敛速度。,Powell法是求解无约束优化问题的最好方法。将其与惩罚函数法结合，可以处理有约束优化问题。,37,为两个极小点,根据梯度与等值面之间关系可知,（2） 共轭方向的生成,4.8 鲍威尔方法,38,对于二次函数， 两点处的梯度可表示为,代入到公式：,（2） 共轭方向的生成,

15、4.8 鲍威尔方法,39,结论：从不同的点出发沿某一方向分别对函数作两次一维搜索，得到两个极小点，那么这两个极小点的连线方向与该方向对G共轭,（2） 共轭方向的生成,4.8 鲍威尔方法,40,（3） 基本算法,4.8 鲍威尔方法,鲍威尔基本算法的搜索过程（二维）,1）任选一初始点x0，再选两个线性无关的向量，如坐标轴单位向量e1=1,0T和e2=0,1T作为初始搜索方向。,41,（3） 基本算法,4.8 鲍威尔方法,鲍威尔基本算法的搜索过程（二维）,2）从x0出发，顺次沿e1， e2作一维搜索，得 点，两点连线得一新方向d1,42,（3） 基本算法,4.8 鲍威尔方法,鲍威尔基本算法的搜索过程（二维）,用 d1代替e1形成两个线性无关向量d1 ,e2 ，作为下一轮迭代的搜索方向。再从 出发，沿d1作一维搜索得点 ，作为下一轮迭代的初始点。,3）从 出发， e2, d1 作一维搜索，得到点 ，两