机械优化设计--第四章(第6次课)

机械优化设计2016年9月上海海事大学SHANGHAIMARITIMEUNIVERSITY何军良14:301上海海事大学ShanghaiMaritimeUniversity19092009200419121958机械优化设计中的几个问题优化设计概述优化设计的数学基础2目录CONTENTS一维搜索方法无约束优化方法线性规划约束优化方法14:30第四章无约束优化方法概述01最速下降法牛顿型方法共轭方向与共轭方向法020304坐标轮换法05共轭梯度法变尺度法鲍威尔方法060708单形替换法0914:30314:30变尺度法也称拟牛顿法，它是基于牛顿法的思想而又作了重大改进的一类方法。我们所介绍的变尺度法是由Davidon于1959年提出又经Fletcher和Powell加以发展和完善的一种变尺度法，故称为DFP变尺度法。4.7变尺度法1()kkkkXXfX)()]([121kkkkkXfXfXX能否克服各自的缺点，综合发挥其优点？2)阻尼牛顿法1)梯度法*简单，开始时目标函数值下降较快，但越来越慢。*目标函数值在最优点附近时收敛快，但要用到二阶导数和矩阵求逆。（1）问题提出414:304.7变尺度法（2）基本思想变量的尺度变换是放大或缩小各个坐标。通过尺度变换可以把函数的偏心程度降到最低限度。这种算法仅用到梯度，不必计算海赛阵及其逆矩阵，但又能使搜索方向逐渐逼近牛顿方向，具有较快的收敛速度。尺度变换技巧能显著地改进几乎所有极小化方法的收敛性质。例如在用最速下降法求极小值时,需要进行10次迭代才能达到极小点。221212(,)25f(1)()()1kkkkkxxaGg(1)()()kkkkxxag梯度法:牛顿法:(1)()()kkkkkxxaAg514:304.7变尺度法（2）基本思想xxQ进行尺度变换在新的坐标系中，函数f(x)的二次项变为：1122xGxxGxTTTQQ目的：减少二次项的偏心如G是正定，则总存在矩阵Q，使得：GITQQ对于二次函数:1()2TTfxxGxbxc614:304.7变尺度法（2）基本思想用矩阵Q-1右乘等式两边，得：用矩阵Q左乘等式两边，得：1GTQQGITQQ所以1GTQQ上式说明：二次函数矩阵G的逆阵，可以通过尺度变换矩阵来求得。TAQQ714:30(3)变尺度法的搜索方向:S(k)=-Akgk，称为拟牛顿方向。(1)Ak为构造的nn阶对称矩阵，它随迭代点的位置变化而变化，对梯度起到改变尺度的作用，又称为变尺度矩阵。若Ak=I，上式为梯度法的迭代公式若Ak=Hk-1，上式为阻尼牛顿法的迭代公式(1)()()kkkkkxxaAg（3）迭代公式4.7变尺度法(2)当矩阵Ak不断地迭代而能很好地逼近时，就可以不再需要计算二阶导数。21[()]kfx变尺度法的关键在于尺度矩阵Ak的产生。814:30拟牛顿方向S(k)=-Akgk必须具有下降性、收敛性和计算的简便性。下降性—要求变尺度矩阵为对阵正定矩阵；收敛性—要求变尺度矩阵逐渐逼近Hk-1，满足拟牛顿条件；简便性—希望变尺度矩阵有如下递推形式：•Ak+1=Ak+△Ak（4）变尺度矩阵的产生4.7变尺度法914:30下降性：要求S(k)与-gk之间的夹角小于90o，即：-[S(k)]Tgk0将拟牛顿方向带入上式，得：-[S(k)]Tgk=[Akgk]Tgk=[gk]TAkgk0所以只要Ak为对阵正定矩阵，S(k)就是下降方向。（4）变尺度矩阵的产生4.7变尺度法1014:30变尺度矩阵是随迭代过程的推进而逐次改变的，因而它是一种矩阵序列选取初始矩阵A0，并以梯度方向快速收敛，通常取单位矩阵E作为初始矩阵，即A0=E。而后的矩阵均是在前一构造矩阵的基础上校正得到，令推广到一般的k+1次构造矩阵{Ak}，k=1，2，……A1=A0+△A0Ak+1=Ak+△Ak矩阵序列的基本迭代式△Ak称为校正矩阵（4）变尺度矩阵的产生4.7变尺度法简便性：1114:30构造矩阵Ak+1应该满足一个重要条件—拟牛顿条件变尺度法采用构造矩阵来代替牛顿法中海赛矩阵的逆阵，主要目的之一就是为了避免计算二阶偏导数和逆矩阵，力图仅用梯度和其他一些易于获得的信息来确定迭代方向，因此，拟牛顿条件是关于海赛矩阵和梯度之间的关系。（5）拟牛顿条件4.7变尺度法1214:30设F(x)为一般形式n阶的目标函数，并具有连续的一、二阶偏导。在点x(k)处的二次泰勒近似展开xHxxgxFxFkTTkk21)()()(该近似二次函数的梯度为：xHgxFkk)(式中，若令，则有)(kxxx)1(kxx)()()1(1kkkkkxxHgg)(11)()1(kkkkkggHxx（5）拟牛顿条件4.7变尺度法1314:30上式中，x(k+1)–x(k)称之为位移矢量，并简化书写:(1)()kkkxx而gk+1-gk是前后迭代点的梯度矢量差，简化书写：kkkggy1由以上三式得：1kkkHy海赛矩阵与梯度间的关系式（5）拟牛顿条件4.7变尺度法1414:30按照变尺度法产生构造矩阵的递推思想，期望能够借助前一次迭代的某些结果来计算下一个构造矩阵，因此可以根据上式，用第k+1次构造矩阵Ak+1近似代替Hk-1，则kkkyA1上式即产生构造矩阵Ak+1应满足的一个重要条件，通常称为拟牛顿条件或拟牛顿方程（5）拟牛顿条件4.7变尺度法1514:30（6）变尺度矩阵的构造4.7变尺度法拟牛顿条件可写成kkkkAAy或(1)kkkkkAyAyDFP算法中的校正矩阵△Ak取为下列形式：(2)TTkkkkkkkAuuvv待定系数保证△Ak对称kkkyA11614:30（6）变尺度矩阵的构造4.7变尺度法将(2)代入(1):TTkkkkkkkkkkkuuyvvyAy两边对比得:,TkkkkkuuyTkkkkkkvvyAy取,kkkkkuvAy1kTkky1kTkkkyAy则：TTkkkkkkkTTkkkkkAyyAAyyAy回代到(2)得:DFP变尺度法的迭代式为：11kkkkkTTkkkkkkkkTTkkkkkXXAfXAyyAAAyyAy1714:30由上式可以看出，构造矩阵Ak+1的确定取决于第k次迭代中的下列信息：上次的构造矩阵：Ak迭代点的位移矢量：迭代点的梯度增量：)()1(kkkxxkkkggy1因此，不必作二阶导数矩阵及其求逆的计算（6）变尺度矩阵的构造4.7变尺度法1814:30DFP算法的收敛速度介于梯度法和牛顿法之间。DFP法具有二次收敛性(搜索方向的共轭性)。对于二次函数F(x)，DFP法所构成的搜索方向序列S(0),S(1),S(2),…为一组关于海赛矩阵H共轭的矢量，即DFP法属于共轭方向法，具有二次收敛性。在任何情况下，这种方法对于二次目标函数都将在n步内搜索到目标函数的最优点，而且最后的构造矩阵An必等于海赛矩阵H。（7）DFP变尺度算法的特点4.7变尺度法1914:31（7）DFP变尺度算法的特点4.7变尺度法关于算法的稳定性，数值计算稳定性较差。1.算法的稳定性是指算法的每次迭代都能使目标函数值单调下降。2.构造矩阵正定性从理论上肯定了DFP法的稳定性，但实际上，由于每次迭代的一维搜索只能具有一定的精确度，且存在机器运算的舍入误差，构造矩阵的正定性仍然有可能遭到破坏；3.为了提高实际计算中的稳定性，一方面应对一维搜索提出较高的精度要求，另一方面，当发生破坏正定性时，将构造矩阵重置为单位矩阵E重新开始，通常采用的简单办法是在n次迭代后重置单位矩阵2014:311.任取初始点x(0)给出迭代精度ε.计算初始点精度及其模。若转步骤⑺，否则进行下一步2.置k←0，取Ak←E3.计算迭代方向，沿S(k)方向做一维搜索求优化步长a(k)，使)()0(0xFg0g0gkkkgAS)()(min)()()()()()(kkkkkSxFSxF确定下一个迭代点)()()()1(kkkkSxx（8）DFP变尺度算法的计算步骤4.7变尺度法2114:314.计算x(k+1)的梯度gk+1及其模，若则转步骤⑺，否则转下一步1kg1kg5.计算位移矢量和梯度矢量)()1(kkkxxkkkggy1kky按DFP公式计算构造矩阵kkTkTkTkkkkTkTkkkkyAyAyyAyAA16.置k←k+1。若kn(n为优化问题的维数)返回步骤⑶，否则返回步骤⑵7.输出最优解（x*，F*），终止计算（8）DFP变尺度算法的计算步骤4.7变尺度法2214:31DFP算法流程图,n,x)0(输入：）（计算：）（）（00)0(xFgIA0k)()()()1()()()()()()()()(minkkkkkkkkkkkSxxSxFgAS)()1()1(kkxFgk=n？)1()1()1()()1()()()()1()()1(kkkkkTkTkTTkkkkgASNMAAyAyyANyMggyxx)1()0(kxx入口出口*)(*]*)1(xFFxxk?)1(kg+-+-2314:31解：1）取初始点，为了按DFP法构造第一次搜寻方向d0，需计算初始点处的梯度221212112(,)242fxxxxxxx0[11]Tx0120212244()422xxxxfxx取初始变尺度矩阵为单位矩阵A0=I，则第一次搜寻方向为0001044()0122dAxf例:用DFP算法求下列问题的极值：24（9）DFP算例4.7变尺度法14:31010000014141212xxd一维搜索最佳步长应满足1002000()min()min(40203)ffxxd得:00.25120.5x2）再按DFP法构造点x1处的搜寻方向d1，需计算1121212241()422xxxxfxx沿d0方向进行一维搜索，得（9）DFP算例4.7变尺度法2514:31010143224ggg0102110.510.5xxx代入校正公式000000000000[][][][]TTTTxxAggAAxggAg1310.5340.543310.53444=（9）DFP算例4.7变尺度法2614:31100AAA21191010.5912112550010.50.251216194152550100=第二次搜寻方向为1118665dAg再沿d1进行一维搜索，得12111182560.55xxd（9）DFP算例4.7变尺度法2714:31为一维搜索最佳步长，应满足12112111811()min()min(4)52ffxxd154242x,得3）判断x2是否为极值点梯度:2122212240()420xxxxfxx海赛矩阵:2222()24fx（9）DFP算例4.7变尺度法梯度为零向量,海赛矩阵正定。