机械优化设计-第四章

机械优化设计2016年9月上

海

海

事

大

学SHANGHAIMARITIMEUNIVERSITY何军良2023/4/181第一页，共九十五页。上海海事大学ShanghaiMaritimeUniversity

1909

2009

2004

1912

19587机械优化设计中的几个问题1优化设计概述2优化设计的数学基础2目录CONTENTS3一维搜索方法4无约束优化方法5线性规划6约束优化方法2023/4/18第二页，共九十五页。第四章无约束优化方法

概述01

最速下降法牛顿型方法

共轭方向与共轭方向法020304坐标轮换法05

共轭梯度法

变尺度法

鲍威尔方法060708

单形替换法092023/4/183第三页，共九十五页。变尺度法也称拟牛顿法，它是基于牛顿法的思想而又作了重大改进的一类方法。我们所介绍的变尺度法是由Davidon

于1959年提出又经Fletcher

和Powell

加以发展和完善的一种变尺度法，故称为DFP变尺度法。4.7变尺度法能否克服各自的缺点，综合发挥其优点？2)阻尼牛顿法1)梯度法*简单，开始时目标函数值下降较快，但越来越慢。*目标函数值在最优点附近时收敛快，但要用到二阶导数和矩阵求逆。（1）

问题提出4第四页，共九十五页。4.7变尺度法（2）

基本思想变量的尺度变换是放大或缩小各个坐标。通过尺度变换可以把函数的偏心程度降到最低限度。这种算法仅用到梯度，不必计算海赛阵及其逆矩阵，但又能使搜索方向逐渐逼近牛顿方向，具有较快的收敛速度。尺度变换技巧能显著地改进几乎所有极小化方法的收敛性质。例如在用最速下降法求极小值时,需要进行10次迭代才能达到极小点。梯度法:牛顿法:5第五页，共九十五页。4.7变尺度法（2）

基本思想进行尺度变换在新的坐标系中，函数f(x)的二次项变为：目的：减少二次项的偏心如G是正定，则总存在矩阵Q，使得：对于二次函数:6第六页，共九十五页。4.7变尺度法（2）

基本思想

用矩阵Q-1右乘等式两边，得：用矩阵Q左乘等式两边，得：所以上式说明：二次函数矩阵G的逆阵，可以通过尺度变换矩阵

来求得。7第七页，共九十五页。(3)变尺度法的搜索方向:S(k)

=

-Ak

gk

，称为拟牛顿方向。

(1)Ak为构造的nn

阶对称矩阵，它随迭代点的位置变化而变化，对梯度起到改变尺度的作用，又称为变尺度矩阵。若Ak=I，上式为梯度法的迭代公式若Ak=Hk-1

，上式为阻尼牛顿法的迭代公式（3）

迭代公式4.7变尺度法(2)当矩阵Ak

不断地迭代而能很好地逼近时，就可以不再需要计算二阶导数。变尺度法的关键在于尺度矩阵Ak的产生。8第八页，共九十五页。拟牛顿方向S(k)

=

-Ak

gk

必须具有下降性、收敛性和计算的简便性。下降性—要求变尺度矩阵为对阵正定矩阵；收敛性—要求变尺度矩阵逐渐逼近Hk-1，满足拟牛顿条件；简便性—希望变尺度矩阵有如下递推形式：Ak+1

=Ak+△Ak（4）

变尺度矩阵的产生4.7变尺度法9第九页，共九十五页。下降性：要求S(k)与-gk之间的夹角小于90o，即：-[S(k)]Tgk>0将拟牛顿方向带入上式，得：-[S(k)]Tgk=[Akgk]Tgk=[gk]TAkgk>0所以只要Ak为对阵正定矩阵，S(k)

就是下降方向。（4）

变尺度矩阵的产生4.7变尺度法10第十页，共九十五页。变尺度矩阵是随迭代过程的推进而逐次改变的，因而它是一种矩阵序列选取初始矩阵A0，并以梯度方向快速收敛，通常取单位矩阵E作为初始矩阵，即A0=E。而后的矩阵均是在前一构造矩阵的基础上校正得到，令推广到一般的k+1次构造矩阵{Ak}，k=1，2，……A1=A0+△A0Ak+1=Ak+△Ak矩阵序列的基本迭代式△Ak称为校正矩阵（4）

变尺度矩阵的产生4.7变尺度法简便性：11第十一页，共九十五页。构造矩阵Ak+1应该满足一个重要条件—拟牛顿条件变尺度法采用构造矩阵来代替牛顿法中海赛矩阵的逆阵，主要目的之一就是为了避免计算二阶偏导数和逆矩阵，力图仅用梯度和其他一些易于获得的信息来确定迭代方向，因此，拟牛顿条件是关于海赛矩阵和梯度之间的关系。（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第十四页，共九十五页。按照变尺度法产生构造矩阵的递推思想，期望能够借助前一次迭代的某些结果来计算下一个构造矩阵，因此可以根据上式，用第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的确定取决于第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.7变尺度法19第十九页，共九十五页。（7）DFP变尺度算法的特点4.7变尺度法关于算法的稳定性，数值计算稳定性较差。算法的稳定性是指算法的每次迭代都能使目标函数值单调下降。构造矩阵正定性从理论上肯定了DFP法的稳定性，但实际上，由于每次迭代的一维搜索只能具有一定的精确度，且存在机器运算的舍入误差，构造矩阵的正定性仍然有可能遭到破坏；为了提高实际计算中的稳定性，一方面应对一维搜索提出较高的精度要求，另一方面，当发生破坏正定性时，将构造矩阵重置为单位矩阵E重新开始，通常采用的简单办法是在n

次迭代后重置单位矩阵20第二十页，共九十五页。任取初始点x(0)

给出迭代精度ε.计算初始点精度及其模。若转步骤⑺，否则进行下一步置k←0，取Ak←E计算迭代方向，沿S(k)

方向做一维搜索求优化步长a(k)

，使确定下一个迭代点（8）DFP变尺度算法的计算步骤4.7变尺度法21第二十一页，共九十五页。计算x(k+1)

的梯度gk+1及其模，若则转步骤⑺，否则转下一步计算位移矢量和梯度矢量按DFP公式计算构造矩阵置k←k+1。若k<n(n为优化问题的维数)返回步骤⑶，否则返回步骤⑵输出最优解（x*，F*），终止计算（8）DFP变尺度算法的计算步骤4.7变尺度法22第二十二页，共九十五页。DFP算法流程图k=n？入口出口+-+-23第二十三页，共九十五页。解：1）取初始点，为了按DFP法构造第一次搜寻方向d0，需计算初始点处的梯度取初始变尺度矩阵为单位矩阵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变尺度法梯度为零向量,海赛矩阵正定。可见满足极值充要条件，因此为极小点。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)求一维搜索步长（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等人提出一种更稳定的算法，称为BFGS算法。其校正公式为：（9）BFGS变尺度法4.7变尺度法35第三十五页，共九十五页。36（1）

概述4.8

鲍威尔方法基本思想：基于坐标轮换法，不用求导数，在迭代中逐次产生共轭搜索方向。收敛效果：对于正定（有极小值）二次函数，经过n轮迭代后求得极小点；对于非二次函数，一般也具有较高的收敛速度。Powell法是求解无约束优化问题的最好方法。将其与惩罚函数法结合，可以处理有约束优化问题。第三十六页，共九十五页。为两个极小点根据梯度与等值面之间关系可知（2）

共轭方向的生成4.8

鲍威尔方法37第三十七页，共九十五页。对于二次函数，两点处的梯度可表示为代入到公式：（2）

共轭方向的生成4.8

鲍威尔方法38第三十八页，共九十五页。结论：从不同的点出发沿某一方向分别对函数作两次一维搜索，得到两个极小点，那么这两个极小点的连线方向与该方向对G共轭（2）

共轭方向的生成4.8

鲍威尔方法39第三十九页，共九十五页。（3）

基本算法4.8

鲍威尔方法鲍威尔基本算法的搜索过程（二维）1）任选一初始点x0，再选两个线性无关的向量，如坐标轴单位向量e1=[1,0]T和e2=[0,1]T作为初始搜索方向。x1x2x0oe1e2d1d2x*140第四十页，共九十五页。（3）

基本算法4.8

鲍威尔方法鲍威尔基本算法的搜索过程（二维）2）从x0出发，顺次沿e1，e2作一维搜索，得点，两点连线得一新方向d1x1x2x0oe1e2d1d2x*141第四十一页，共九十五页。（3）

基本算法4.8

鲍威尔方法鲍威尔基本算法的搜索过程（二维）用d1代替e1形成两个线性无关向量d1,e2

，作为下一轮迭代的搜索方向。再从出发，沿d1作一维搜索得点，作为下一轮迭代的初始点。3）从出发，→

e2,→

d1

作一维搜索，得到点，两点连线得一新方向:x1x2x0oe1e2d1d2x*1从沿d2作一维搜索得点x2

。即是二维问题的极小点x*

。42第四十二页，共九十五页。（3）

基本算法4.8

鲍威尔方法鲍威尔基本算法的搜索过程（二维）方法的基本迭代格式包括共轭方向产生和方向替换两主要步骤。43第四十三页，共九十五页。（3）

基本算法4.8

鲍威尔方法鲍威尔基本算法的搜索过程（三维）44第一轮基本方向组取单位坐标矢量系e1、e2、

e3

、…、en，沿这些方向依次作一维搜索，然后将始末两点相连作为新生方向。再沿新生方向作一维搜索，完成第一轮的迭代。以后每轮的基本方向组是将上轮的第一个方向淘汰，上轮的新生方向补入本轮的最后而构成：d2k

,

d3k,……dnk

,

dk第四十四页，共九十五页。（4）

基本算法示例4.8

鲍威尔方法45第四十五页，共九十五页。（4）

基本算法示例4.8

鲍威尔方法46第四十六页，共九十五页。（4）

基本算法示例4.8

鲍威尔方法47第四十七页，共九十五页。（4）

基本算法示例4.8

鲍威尔方法48第四十八页，共九十五页。（4）

基本算法示例4.8

鲍威尔方法49第四十九页，共九十五页。（4）

基本算法示例4.8

鲍威尔方法50第五十页，共九十五页。（4）

基本算法示例4.8

鲍威尔方法51第五十一页，共九十五页。（4）

基本算法示例4.8

鲍威尔方法52第五十二页，共九十五页。（4）

基本算法示例4.8

鲍威尔方法53第五十三页，共九十五页。（4）

基本算法示例4.8

鲍威尔方法54第五十四页，共九十五页。

可能在某一轮迭代中出现基本方向组为线性相关的矢量系的情况。如第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

鲍威尔方法55第五十五页，共九十五页。鲍威尔基本算法的退化x1x2x31=02e23e3S1如图所示为一个三维优化问题的示例，设第一轮中1=0

，则新生方向与e2、e3共面，随后的各环方向组中，各矢量必在该平面内，使搜索局限于二维空间，不能得到最优解。e2e3S1（5）

基本算法缺陷4.8

鲍威尔方法56第五十六页，共九十五页。（5）

基本算法缺陷4.8

鲍威尔方法57第五十七页，共九十五页。（5）

基本算法缺陷4.8

鲍威尔方法58第五十八页，共九十五页。（5）

基本算法缺陷4.8

鲍威尔方法59第五十九页，共九十五页。（5）

基本算法缺陷4.8

鲍威尔方法60第六十页，共九十五页。（5）

基本算法缺陷4.8

鲍威尔方法61第六十一页，共九十五页。（5）

基本算法缺陷4.8

鲍威尔方法62第六十二页，共九十五页。（5）

基本算法缺陷4.8

鲍威尔方法63第六十三页，共九十五页。（5）

基本算法缺陷4.8

鲍威尔方法64第六十四页，共九十五页。（5）

基本算法缺陷4.8

鲍威尔方法65第六十五页，共九十五页。（5）

基本算法缺陷4.8

鲍威尔方法66第六十六页，共九十五页。67（6）

修正算法4.8

鲍威尔方法*①根据Powell条件判定是否需换方向；②如需换向，则换掉函数值下降量最大的方向。选取n个线性无关且尽可能共轭的方向作为下一轮搜索的方向组。做法：形成新的搜索方向组时，不是固定的去掉前一次搜索方向组中的第一个方向，而是首先根据Powell条件，判断原方向组是否需要替换，若需要，则进一步判断原方向组中哪个方向最坏，并以前一轮新生成的搜索方向替换本轮中的这个最坏方向。第六十七页，共九十五页。68（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轮方向组中，依次沿各方向搜索函数下降值第六十八页，共九十五页。鲍威尔算法的方向淘汰(F3)(F2)(F0)反射点函数最大下降量△m始点终点（6）

修正算法4.8

鲍威尔方法69第六十九页，共九十五页。为了构造第k+1轮基本方向组，采用如下判别式：

按照以下两种情况处理：

1)上式中至少一个不等式不成立，则第k+1轮的基本方向仍用老方向组d1k、d2k、

•••、

dnk。k+1轮的初始点取

x0k+1=xnkF2<F3

x0k+1=xn+1kF2F3

（6）

修正算法4.8

鲍威尔方法70第七十页，共九十五页。2）两式均成立，则淘汰函数值下降最大的方向，并用第k轮的新生方向补入k+1轮基本方向组的最后，即k+1轮的方向组为d1k、d2k

、….、dm-1k、dm+1k、•••、dnk、

dk

。k+1轮的初始点取:

x0k+1=xk,xk是第k轮沿dk方向搜索的极小点。（6）

修正算法4.8

鲍威尔方法(F3)(F2)(F0)反射点函数下降量△始点终点dk方向极小点71第七十一页，共九十五页。Powell算法的步骤如下：⑴任选初始迭代点，选定迭代精度ε，取初始基本方向组为单位坐标矢量系其中，i=1，2……n

然后令k=1（轮数）开始迭代⑵沿诸方向依次进行n次一维搜索，确定各步长（7）

修正算法步骤4.8

鲍威尔方法72第七十二页，共九十五页。得到点阵i=1，2……n构成新生方向沿方向进行一维搜索求得优化步长(3)计算各迭代点的函数值，找出相邻点函数值差最大者（1≤m≤n）及与之相对应的两个点和，并以表示两点的连线方向。（7）

修正算法步骤4.8

鲍威尔方法73第七十三页，共九十五页。（4）反射点函数值（5）判断是否满足迭代终止条件。则可结束迭代，最优解为停止计算。否则，继续进行下步。（7）

修正算法步骤4.8

鲍威尔方法74第七十四页，共九十五页。检验鲍威尔判别条件是否成立若至少其中之一不成立转下步，否则转步骤⑺⑹确定k+1轮的基本方向组和起始点（即取老方向组）当F2＜F3当F2≥F3令k←k+1，返回步骤⑵（7）

修正算法步骤4.8

鲍威尔方法75第七十五页，共九十五页。⑺确定k+1轮的方向组和起始点令k←k+1，返回步骤⑵（7）

修正算法步骤4.8

鲍威尔方法76第七十六页，共九十五页。77例用鲍威尔法求函数的极小值解：

选取初始点,初始搜索方向初始点处的函数值第一轮迭代：1）沿方向进行一维搜索，得：其中为一维搜索最佳步长，应满足得：所以，（8）

算例4.8

鲍威尔方法第七十七页，共九十五页。782）再沿方向进行一维搜索，得：其中为一维搜索最佳步长，应满足：得：所以，取沿搜索的函数值增量的最大者终点的反射点和函数值为：（8）

算例4.8

鲍威尔方法第七十八页，共九十五页。793）Powell条件判断：F3>F0，不满足判别条件，因而下轮迭代应继续使用原来的搜索方向e1,e2因为F2<F3，所以取为下轮迭代起始点。第二轮迭代：1）沿方向进行一维搜索，得：其中为一维搜索最佳步长，应满足得：所以，（8）

算例4.8

鲍威尔方法第七十九页，共九十五页。802）再沿方向进行一维搜索，得：其中为一维搜索最佳步长，应满足：得：所以，取沿搜索的函数值增量的最大者终点的反射点和函数值为：（8）

算例4.8

鲍威尔方法第八十页，共九十五页。813）Powell条件判断：满足用新方向替换

，下轮搜索方向为

下轮起始点为从出发，沿搜索的极小点：其中为一维搜索最佳步长，应满足得：已足够接近极值点[2.52.5]T。（8）

算例4.8

鲍威尔方法第八十一页，共九十五页。82单形替换法是利用对简单几何图形各顶点的目标函数值作相互比较，在连续改变几何图形的过程中，逐步以目标函数值较小的顶点取代目标函数值最大的顶点，从而进行求优的一种方法，属于直接法之一。（1）

基本原理4.9

单型替换法现以求二元函数的极小点为例，说明单形替换法形成原理.设二元函数在平面上取不在同一条直线上的三个点,和，并以它们为顶点构成一单纯形——三角形。算出各顶点的函数值，，，比较其大小，现假定比较后有这说明点最差，点最好，点次差。为了寻找极小点，一般来说应向最差点的反对称方向进行搜索．第八十二页，共九十五页。83（1）

基本原理4.9

单型替换法以记为的中点（如图所示），在的延长线上取点，使

称为是关于的反射点。算出的函数值，可能出现以下几种情形：．第八十三页，共九十五页。

(1)

这说明搜索方向正确，可进一步扩大效果，继续沿

向前搜索，也就是向前扩张。这时取

其中为扩张因子，一般取。

如果，说明扩张有利，就可以点代替点构成新的单纯形。

如果，说明扩张不利，舍去点，仍以点

代替构成新的单纯形

。．（1）

基本原理4.9

单型替换法84第八十四页，共九十五页。(2)

这说明搜索方向正确，但无须扩张，以代替构成新的单纯形。(3)

这表示点走得太远，应缩回一些。若以表示压缩因子，则有

常取为0.5。以代替

构成新的单纯形（1）

基本原理4.9

单型替换法85第八十五页，共九十五页。(4)这时应压缩更多一些，将新点压缩至之间，令（1）

基本原理4.9

单型替换法86如果则以代替构成新的单纯形否则认为方向上的所有点的函数值都大于，不能沿此方向搜索。这时，可以以为中心进行缩边，使顶点和向移近一半距离，得新单纯形.以此单纯形为基础再进行寻优。第八十六页，共九十五页。（2）比较各顶点Xi的函数值，挑出其中的最优点，记为XL；最劣点，记XH；次差点，记为Xw；（3）求反射中心其中，a>0，通常取a=1；

（1）令；输出XL，为原问题近似极小点；否则，转（2）。(扩张时α=2)构造新单纯形；（4）根据不同情况，分别进行扩张，收缩或缩边，其中收缩因子（5）如果满足（2）

计算步骤4.9

单型替换法87第八十七页，共九十五页。

例

试用单型替换求的极小值.

解:

选,并取和．

这三点不在一条直线上，用它们作为初始单纯形的顶点

（如图所示）．．（3）

算例4.9

单型替换法88第八十八页，共九十五页。然后计算各顶点的函数值：可知

为最差点，为最好点。以表示和的重心，则反射点（3）

算例4.9

单型替换法89第八十九页，共九十五页。由于，故需扩张。取，则因为，故以代替，由，和构成新单纯形，然后进行下一个循环。该问题的最优解为。经32次循环，可把目标函数减小到。（3）

算例4.9