【文档说明】机械优化设计_第四章无约束优化方法.pptx，共(61)页，1.180 MB，由精品优选上传

转载请保留链接：https://www.ichengzhen.cn/view-259984.html

以下为本文档部分文字说明：

机械优化设计第四章无约束优化方法一、概述二、最速下降法（梯度法）三、牛顿型方法（牛顿法和阻尼牛顿法）四、共轭方向和共轭方向法五、共轭梯度法六、变尺度法七、坐标轮换法机械优化设计实际中的工程问题大都是在一定限制条件下追求某一指标为最小，属于约束优化问题。为什么要研究

无约束优化问题？1）有些实际问题，其数学模型本身就是一个无约束问题；2）通过熟悉它的解法可以为研究约束优化问题打下良好的基础；3）约束优化问题的求解可用通过一系列无约束优化方法来达到。所以无约束优化问题的解法是优化设计方法的基本组成部分，也是优化方法的基础。

机械优化设计1、无约束优化问题n求维设计变量使目标函数12,,TnXxxx=()minfX→X，而对没有任何限制条件。2、求解方法（1）利用极值条件来确定极值点的位置。（2）数值计算方法——搜索方法基本思想

：从给定的初始点出发，沿某一搜索方向0x0d进行搜索，确定最佳步长0使函数值沿0d下降最大。依此方式不断进行，形成迭代的下降算法：1kkkkXXd+=+(0,1,2)k=一、概述机械优化设计3、算法框图机械优化设计4、无约束优化

方法的分类根据确定其搜索方向方法不同，可分为：kd（2）利用目标函数的一阶或二阶导数的无约束优化方法（或称间接法）如：最速下降法（梯度法）、共轭梯度法、牛顿法及变尺度法；间接法除了要计算目标函数值外，还要计算目标函数的梯度，有的还要计算其海赛矩阵；（1）只利用目标函数值的无约束优化

方法（或称直接法，即不使用导数信息），如：坐标轮换法、单形替换法及鲍威（Powell）法。直接法不必求函数导数，只计算目标函数值。适用于求解变量个数较少（小于20）的问题，一般情况下效率较低。搜索方向的构成问题是无约束优化方法的关键。机械优化设计二、最速下降法（梯度法）1、基本思想函数的负梯

度方向是函数值在该点下降最快的方向。将n维问题转化为一系列沿负梯度方向用一维搜索方法寻优的问题，即利用负梯度作为搜索方向，故称为最速下降法或梯度法。()dfX=−()1kkkkXXfX+=−(0,1,2)k=搜索方向取该点的负梯度方向即，使函数

值在该点附近的范围内下降最快。机械优化设计2、最速下降法的原理（1）使，按此规律不断走步，形成迭代算法：()dfX=−()1kkkkXXfX+=−(0,1,2)k=（2）其步长因子取一维搜索的最佳步长，

即k根据一元函数极值的必要条件和多元复合函数求导公式，得()()()0TkkKkfXfXfX=−−=()10Tkkdd+=()()10Tkkfxfx+=或()()()()1minminkkkkkkkfxfx

afxfxafx+=−=−=机械优化设计由此可知，在最速下降法中，相邻两个迭代点上的函数梯度相互垂直。而搜索方向就是负梯度方向，因此相邻两个搜索方向互相垂直。这就是说在迭代点向函数极小点靠近的过程，走的

是曲折的路线，形成“之”字形的锯齿现象，而且越接近极小点锯齿越细。最速下降法的搜索路径函数梯度为局部性质，因此并非“最快”。机械优化设计梯度法的迭代历程机械优化设计方法特点1）初始点可任选，每次迭代计算量小，存储量少，程序简短。即使从一个不好的初始点

出发，开始的几步迭代，目标函数值下降很快，然后慢慢逼近局部极小点；2）任意相邻两点的搜索方向是正交的，它的迭代路径为绕道逼近极小点。当迭代点接近极小点时，步长变得很小，越走越慢。机械优化设计最速下降法的程序框图

机械优化设计例：求目标函数()221225fXxx=+的极小点解法1：取初始点02,2TX=，则初始点处的函数值及梯度分别为：()()01021042450100fXxfXx===()0100000242421002100XXfX−

=−=−=−0为一维搜索最佳步长，应满足极值必要条件()()()10022minmin(24)25(2100)minfXfXfX=−=−+−=()0008

(24)5000(2100)0=−−−−=06260.0200307231252==机械优化设计则第一次迭代设计点位置和函数值0120241.91987721000.307178510X−−==−−

()13.686164fX=经过10次迭代后，得到最优解：0,0TX=()0fX=该问题的目标函数的等值线为一族椭圆，迭代点走的是一段锯齿形路线。机械优化设计解法2：引入变化11225yxyx

==，则目标函数()12,fxx变为()221212,yyyy=+()0104Y=()010224220YyYy==()0100000242410201020YYY−=−=−=−026

0.552==010240102000Y−==−()10Y=0,0TX=()0fX=，经过坐标（尺度）变化后，只需要经过一次迭代，就可找到最优解：机械优化设计不同等值线的迭代过程机械优化设计讨论()12212121

22201,250502xfxxxxxxx=+=()1221212122201,022yyyyyyyy=+=可以看出二者的对角形矩阵不同，前者的等值线为一族椭圆，后者的

等值线为一族同心圆，这说明对角形矩阵是表示度量的矩阵或者是表示尺度的矩阵，最速下降法的收敛速度和变量的尺度有很大关系。机械优化设计3、最速下降法收敛速度的估计式2121kkmXXXXM+−−−M()fx的海赛矩阵最大特征值上界——的海赛矩阵最小特征值下界()fx——m212262

4150625kkkXXXXXX+−−−=−2122102kkYYYY+−−−=机械优化设计梯度法的特点：（1）理论明确，程序简单，对初始点要求不严格；（2）对一般函数而言，梯度法的收敛速度并不快，因为最速下降法仅仅是

指某点的一个局部性质；（3）梯度法相邻两次搜索方向的正交性决定了迭代全过程的搜索路径呈锯齿形，在远离极小点时逼近速度较快，而在接近极小点时逼近速度较慢；（4）梯度法的收敛速度与目标函数的性质密切相关。对于等值线（面）为同心圆（球）的目标函数，一次搜索即可达到极小点。机械优化设计三、牛顿型方法基

本思想：在领域内用一个二次函数来近似代替原目标函数，并将的极小值作为目标函数求优的下一个迭代点。经多次迭代，使之逼近目标函数的极小点。kx)(x)(x)(xf)(xf1+kx),2,1,0()()('''1=−=+kxfxfxxkkkk机械优

化设计对于多元函数()fX，设kX为()fX极小点X的第一个近似点，()fX泰勒展开，保留到二次项，得:设1kX+为()X的极小点，它作为()fX极小点X的下一个近似点，根据极值必要条件：()10kX+=即()()

()210kkkkfXfXXX++−=()()112(0,1,2)kkkkXXfXfXk−+=−=()2kfX——海赛矩阵1、牛顿法对于二次函数，海赛矩阵是常矩阵，故从任何点出发，只需一步可找

到极小点。---多元函数求极值的牛顿法迭代公式。()()fxx()()()()()()212TTkkkkkkfxfxxxxxfxxx=+−+−−机械优化设计例:()221212,25fxxxx=+用牛顿法求的极小值解：取初始点02,2TX=，则()01022450100Xx

fXx==()2020050fX=()1201021050fX−=()()110200102402121000050XXfXfX−

=−=−=代入牛顿法迭代公式可得:从而经过一次迭代即求得极小点和函数极小值。机械优化设计2、阻尼牛顿法把()()12kkkdfXfX−=−看作一个搜索方向，称其为牛顿方向

，则阻尼牛顿法的迭代公式为：()()112(0,1,2)kkkkkkkkXXdXfXfXk−+=+=−=k——阻尼因子，即沿牛顿方向进行一维搜索的最佳步长，可通过如下极小化过程求得：()()()1minkkkkkkfXfXdfXd+=+=+（1）阻尼牛顿法的

迭代公式在牛顿法中，迭代点的位置是按照极值条件确定，并未含有沿下降方向搜寻的概念，因此采用牛顿迭代公式，对于非二次函数，有时会使函数值上升。机械优化设计（2）阻尼牛顿法的计算步骤1）给定初始点，收敛精度，置0X0k2）计算()()()122kk

kfXfXfX−、、()()12kkkdfXfX−=−3）求1kkkkXXd+=+4）检查收敛精度。若1kkXX+−，则，停机；1kXX+=否则置1kk+返回到2），继续进行搜索。机械优化设计（3）阻尼牛顿法的程序框图机械优化设

计方法特点：1）初始点应选在极小点附近，有一定难度；2）尽管每次迭代都不会是函数上升，但不能保证每次都下降；3）若迭代点的海赛矩阵为奇异，则无法求逆矩阵，不能构造牛顿法方向；4）不仅要计算梯度，还要求海赛矩阵及其逆矩阵，计算量和存储量大。此外对于

二阶不可微函数也不适用。虽然阻尼牛顿法有上述缺点，但在特定条件下它具有收敛最快的优点，可为其他算法提供思路和理论依据。机械优化设计梯度法与牛顿法的比较一般迭代式：梯度法：牛顿法：阻尼牛顿法：()1kkkkX

XfX+=−(0,1,2)k=()()112(0,1,2)kkkkkkkkXXdXfXfXk−+=+=−=1kkkkXXd+=+(0,1,2)k=机械优化设计四、共轭方向和共

轭方向法（一）共轭方向的概念设G为nxn阶实对称正定矩阵，如果有两个n维向量和满足，则称向量与关于矩阵G共轭，或称他们是G的共轭方向。当G为单位矩阵时，()010TdGd=0d1d0d1d0)(10=ddT共轭方向的概念是在研究二次函数()12TTfXXGXbXc=++G当为对称正定矩阵时引出

的使搜索方向直指极小点。为了克服最速下降法的锯齿现象，提高收敛速度，发展了一类共轭方向法。搜索方向是共轭方向。即将相邻两次搜索方向由正交变为共轭。机械优化设计首先考虑二维情况，如果按最速下降法，选择负梯度方向为搜索方向，会产生锯齿现象。为避免锯齿的发生，取下一次的迭代搜索方向直接

指向极小点，如果选定这样的搜索方向，对于二元二次函数只需进行两次直线搜索就可以求到极小点。1000xxad=+*111xxad=+()1100Txffxdd==如果能选定这样的方向，则只需两步搜索得到极小点，即机械优化设计结论：()010T

dGd=两个向量0d1d，对G是共轭向量。1d应满足什么条件？对于二次函数在处取得极小点的必要条件()fx*x()**0fxGxb=+=()()*111111fxGxadbGxbaGd=++=++()1110fxaGd=+=等式两边同左乘得：()0Td0d1d和称为对

G的共轭方向。()12TTfXXGXbXc=++01*1时，当xx机械优化设计（三）共轭方向法1、共轭方向法的步骤（1）选定初始点0X，下降方向0d和收敛精度，置0k（2）沿kd方向进行一维

搜索，得1kkkkXXd+=+（3）判断()1kfX+是否满足，若满足则打印，1kX+停机，否则转4）。（4）提供新的共轭方向1kd+，使()10,0,1,2,,TjkdGdjk+==（5）置1kk+，转2）。机械优化设计2

、共轭方向法程序框图机械优化设计3、格拉姆—斯密特向量系共轭化法（共轭方向的确定）1、选定线性无关向量系，如n个坐标轴的单位向量；011,,nvvv−00dv=2、取，令，根据共轭条件得10110dvd=+()()()01001100TTdGd

dGvd=+=()()011000TTdGvdGd=−()()0110100TTdGvdvddGd=−()()1110TjkkkjkTjjjdGvdvddGd+++==−()()11,TjkkrTjjdGddGd++=−3、递推

可得：机械优化设计五、共轭梯度法1、共轭梯度法是共轭方向法中的一种，该方法中每一个共轭向量都是依赖与迭代点处的负梯度而构造出来。对于二次函数()12TTfXXGXbXc=++1kkkkxxad+=+1kkkkxxad+−=kkgGxb=+从点出发，沿G某一共轭方向作一维搜索

,到达kxkd1kx+11kkgGxb++=+而在点、处的梯度分别为：kx1kx+机械优化设计()()10Tjkkdgg+−=1kkgg+、kX1kX+——点处的梯度jd若和kd对G是共轭方向，则：()11kkkkkkggGxxaGd

++−=−=()0TjkdGd=其中：机械优化设计得出共轭方向与梯度之间的关系。此式表明沿方向kd进行一维搜索，其终点与始点的梯度值差1kx+kx1kkgg+−与的共轭方向正交。kdjd结论：机械优化设计2、共轭梯度法计算原理

kX)2,1,0(1=+=+kdxxkkkk从出发，沿负梯度方向作一维搜索：)(kkxfd−=设与共轭的下一个方向是由和点的负梯度的线性组合构成，即：kd1+kdkd1+kxkkkkdxfd+−=++)(11共轭条件（与梯度的关系）：

0))()(()(11=−++kkTkxfxfd将式（1）代入（2）得：（1）（2）0))()()()((11=−+−++kkkkkxfxfdxf机械优化设计22111)()()()]([)()]([

kkkTkkTkkxfxfxfxfxfxf==+++kkkkdxfd+−=++)(11221)()(kkkxfxf=+因此可得共轭方向的递推公式：)2,1,0(1=+=+kdxxkkkkkkkkdxfd+−

=++)(11机械优化设计3、共轭梯度法计算过程（1）设初始点0X、00dg=−、1000XXd=+计算1g（2）求的共轭方向0d2110120,gdgdg=−+2111XXd=+计算2g（3）求与和均共轭的方向0d1d2221221gdgdg=−+（4）再沿方向进行一维搜索，如此继续下去

，2d可求得共轭方向的递推公式为：21112(0,1,2,,1)kkkkkgdgdkng+++=−+=−机械优化设计4、共轭梯度法程序框图机械优化设计六、变尺度法1、问题的提出能否克服各自的缺点，综合发挥其优点？2）阻尼牛顿法1）梯度法*简单，开始时目标函数值下降较快，但越

来越慢。*目标函数值在最优点附近时收敛快，但要用到二阶导数和矩阵求逆。()()112(0,1,2)kkkkkkkkXXdXfXfXk−+=+=−=()1kkkkXXfX+=−机械优化设计2、变尺度法的基本思想

对于一般函数，当用牛顿法寻求极小点时，()fX其牛顿迭代公式为：11(0,1,2,)kkkkkXXGgk+−=−=其中：()kkgfX()2kkGfX为了避免迭代公式中计算海赛矩阵的逆阵，用对称正定矩阵近似的逆，每迭代一次，尺度就改变一次。而的产生从给定开始逐步修整

得到。()Hk()2kfX()Hk()1H机械优化设计3、尺度矩阵的概念对于一般二次函数()12TTfXXGXbXc=++如进行尺度变化XQX1122TTTXGXXQGQX→若矩阵是正定的，则总存在矩阵

使可得GQTQGQI=1TQQG−=牛顿迭代法公式变为：()1kkTkkXXQQfX+=−THQQ=牛顿法可以看成经过尺度变化后的梯度法----尺度矩阵变量的尺度变换是放大或缩小各个坐标。通过尺度变换可以把函数的偏心程度降低到最低限度。机械优化设计12)]([−kxf)(1kkkkkx

fHxx−=+nnkH是需要构造的一个对称方阵，kHIHk=如果，则得到梯度法；12)]([−=kkxfH如果，则得到阻尼牛顿法；当矩阵不断地迭代而能很好地逼近时，就可以不再需要计算二阶导数。变尺度法的关键在于尺度矩阵的产生。机械优化设计（2）变尺度矩阵应满足的

条件1）为了保证迭代公式具有下降性质，要求kH中的每一个矩阵都是对称正定的；2）要求之间的迭代具有简单的形式：kH3）要求必须满足拟牛顿条件。kH()111kkkkkHggXX+++−=−11,kk

kkkkSXXygg++−−令1kkkHyS+=拟牛顿条件kkkEHH+=+1即通过修正矩阵的不断修正，使其在迭代中不断逼近。kE)(1kxG−机械优化设计4、变尺度法的一般步骤（1）选定初始点和收敛精度；0X

（2）计算，选取初始对称正定矩阵，()00gfX=0H置；0k（3）计算搜索方向；kkkdHg=−（4）沿方向进行一维搜索，计算kd1kkkkXXd+=+()111,,kkkkkkkkgfXSXXygg++++==−=−（5）

判断是否满足迭代终止准则，若满足则，1kXX+=停机，否则6）；（6）当迭代次后还没有找到极小点时,重置为单位矩阵nkH并以当前设计点位初始点；01kXX+（7）计算矩阵1kkkHHE+=+，置1kk+，返回到3。机械优化设计5、变尺度

法计算程序框图机械优化设计5、DFP算法DFP算法的计算步骤和变尺度法的一半步骤相同，只是具体计算校正矩阵时按公式：1(0,1,2)TTkkkkkkkkTTkkkkkssHyyHHHksyyHy+=+−=例：用

DFP算法求()221212112,242fxxxxxxx=+−−的极值解。（求解过程详见教材）DFP算法是由戴维顿（Davidon）于1953年提出，又于1963年由弗莱彻(Fletcher)和鲍威尔加以发展，称为现代公认较好的算法之一。机械优化设计七、坐标轮换法

坐标轮换法是在每次搜索只允许一个变量变化，其余变量保持不变，即沿坐标方向轮流进行搜索的寻优方法。它把多变量的优化问题轮流地转化成单变量（其余变量视为常量）的优化问题，因此又称这种方法为变量轮换法。轮换过程中不需要目标函数的导数，只需要目标函数信息值。属于直接法的无约束最优化方法。此类

方法适用于不知道目标函数的数学表达式而仅知其目标函数值信息的情况。这也是直接法的一个优点。机械优化设计1、坐标轮换法的寻优过程（1）从初始点出发，沿第一个坐标方向搜索，即00x011de=，得按照一维搜索方法确定00001011xxd=+最佳步长因子满足

01()0001minfxd+（2）从出发，沿01x022de=方向搜索得00002122xxd=+其中：步长因子满足：02()0012minfxd+02x为一轮终点。()0k（3）检验始终点的距离是否满足精度要求。满

足结束；不满足，开始新一轮。1002xx机械优化设计结论：对于个变量的函数，若在第轮沿第个坐标nki方向进行搜索，其迭代公式为：kid1(0,1,2,1,2,)kkkkiiiixxdkin−=+==其中搜索方向取坐标方向，即()1,,kiidein==

若0kknxx−则knxx，否则10kknxx+进行下一轮搜索，一直到满足精度应要求为止。机械优化设计2、程序框图机械优化设计3、坐标轮换法的特点（1）收敛效果与目标函数等值线的形状有很大关系。（2）搜索只能轮流沿着坐标方向搜

索，要经过多次曲折迂回的路径才能达到极小点，在极值点附近收敛速度很慢。机械优化设计八、鲍威尔（Powell）方法(方向加速法)自学概述：Powell法是以共轭方向为基础的收敛较快的直接法之一，是一种十分有效的算法。1964年，Powell提出这种算法，其基本思想是直接利用迭代点的目标函

数值来构造共轭方向，然后，从任一初始点开始，逐次沿共轭方向作一维搜索求极小点。并在以后的实践中进行了改进。机械优化设计对于二次函数()12TTfXXGXbXc=++基本思想：在不用导数的前提下，在迭代中逐次构造G的共轭方向。1、共轭方向的生成➢设为从不同点出

发，沿同一方向进行一维搜索而得到的两个极小点。1,+kkxxjd机械优化设计➢由梯度和等值面垂直的性质，和两点处的梯度之间存在关系：jd1,+kkxxbGxgbGxgkkkk+=+=++11,0)()()()(11=−=−++kkTjkkTjxxGdggd0)(

,0)(1==+kTjkTjgdgd1,+kkgg1,+kkxx另一方面，对于上述二次函数，其两点处的梯度可表示为：将两式相减可得：取方向kkkxxd−=+1结论：这说明要沿方向分别对函数作两次一维搜索，得到

两个极小点，那么这两点的连线所给出的方向就是与一起对G共轭的方向。jd1,+kkxxkdjd机械优化设计机械优化设计2、基本算法（以二维情况为例）1）任选一初始点x0，再选两个线性无关的向量如坐标轴的单

位向量e1=[1,0]T和e1=[0,1]T本作为初始搜索方向；2）从x0出发，顺次沿e1，e2作一维搜索，得到点，两点连线得一新方向0201,xx1d0021xxd−=机械优化设计用d1代替e1形成两个线性无关向量d1，e2，作

为下一轮迭代的搜索方向。再从出发，沿d1作一维搜索得点，作为下一轮迭代的初始点。3）从出发，顺次沿e2，d1作一维搜索，得到点，两点连线得一新方向10122xxd−=02x10x10x1211,xx2d沿作一维搜索得点x基本迭代格式包括共轭方向产生和方向替换两个主要步骤。机械优化设计把二维情况的

基本算法扩展到n维，Powell的算法要点：➢在每一轮迭代中总有一个起始点（第一轮的起始点是任选）和n个线性独立的搜索方向。从起始点出发顺次沿n个方向作一维搜索得一终点，由始点和终点决定了一个新的搜索方向。➢用这个方向替换原来n个方向中的一个，于是形成新的搜索方向组

。替换的原则是去掉原方向组的第一个方向而将新方向排在原方向的最后。此外规定，从这一轮的搜索终点出发沿新的搜索方向作一维搜索而得到的极小点，作为下一轮迭代的始点。这样就形成算法的循环。➢由于这种方法在迭代中生成共轭方向，而共轭方向是较好的搜索方向，故powell法又称为方向加速法。机

械优化设计三、改进的算法在鲍维尔基本算法中，每一轮迭代都用连结始点和终点所产生出的搜索方向去替换原来向量组中的第一个向量，而不管它的“好坏”。这是产生向量组线性相关的原因所在。改进的算法是：首先判断原向量组是否需要替换。如需要替换，还需进一步判断原向量组中哪个向量最坏，然后再用新产生的向量替

换这个最坏的向量，以保证逐次生成共轭方向。上述算法仅具有理论意义，这是因为在迭代的n个搜索方向有时会变成线性相关而不能形成共轭方向。这时组不成n维空间，可能求不到极小点，故上述算法有待改进。机械优化设计