机械优化设计--第四章(第5次课).pptx

机械优化设计--第四章(第5次课).pptx

《机械优化设计--第四章(第5次课).pptx》由会员分享，可在线阅读，更多相关《机械优化设计--第四章(第5次课).pptx（81页珍藏版）》请在冰点文库上搜索。

,何军良,20:

29,1,2,目录,CONTENTS,20:

29,第四章无约束优化方法,概述,01,最速下降法,牛顿型方法,共轭方向与共轭方向法,02,03,04,共轭梯度法,05,变尺度法,坐标轮换法,鲍威尔方法,06,07,08,单形替换法,09,20:

29,3,4,4.1概述,工程问题大都为有约束优化问题。

为什么要研究无约束优化问题?

有些实际问题，其数学模型本身就是一个无约束优化问题。

通过熟悉它的解法可以为研究约束优化问题打下良好的基础。

约束优化问题的求解可以通过一系列无约束优化方法来达到。

所以无约束优化问题的解法是优化设计方法的基本组成部分，也是优化方法的基础。

20:

29,5,4.1概述,无约束优化问题是：

求n维设计变量,使目标函数,无约束优化问题极值存在的必要条件：

20:

29,6,4.1概述,目前已研究出很多种无约束优化方法，它们的主要不同点在于构造搜索方向上的差别。

（1）间接法要使用导数，如梯度法、（阻尼）牛顿法、变尺度法、共轭梯度法等。

（2）直接法不使用导数信息，如坐标轮换法、鲍威尔法、单形替换法等。

用直接法寻找极小点时，不必求函数的导数，只要计算目标函数值。

这类方法较适用于解决变量个数较少的（n20）问题，一般情况下比间接法效率低。

间接法除要计算目标函数值外，还要计算目标函数的梯度，有的还要计算其海赛矩阵。

搜索方向的构成问题乃是无约束优化方法的关键。

其搜索方向直接取定或由计算目标函数值所得的信息来确定。

20:

29,7,4.1概述,7,7,选择初始迭代点x0。

从迭代点xk出发进行搜索，确定使目标函数值下降的搜索方向dk。

确定适当的步长因子k，求xk+1=xk+kdk，使f（xk+1）f（xk）。

选择适当的终止准则，若xk+1满足终止准则，则终止迭代计算，并输出局部最优点x*xk+1；否则，令kk+1，返回步骤

（2）继续进行优化搜索。

无约束优化方法求解的四个步骤:

20:

29,8,4.2最速下降法,

（1）基本思想,搜索方向d取该点的负梯度方向（最速下降方向），使函数值在该点附近的范围内下降最快。

终止判别条件,20:

29,9,4.2最速下降法,

（2）计算方法,为了使目标函数值沿搜索方向能够获得最大的下降值，其步长因子应取一维搜索的最佳步长。

即有,步长因子求解方法：

解析法：

根据极值点必要条件。

黄金分割法牛顿法抛物线法,20:

29,10,4.2最速下降法,

（2）计算方法,根据一元函数极值的必要条件及复合函数求导公式得,20:

29,11,4.2最速下降法,（3）现象,最速下降法的搜索路径,在最速下降法中，相邻两个迭代点上的函数梯度相互垂直。

搜索方向就是负梯度方向，因此相邻两个搜索方向互相垂直。

形成“之”字形的锯齿现象，而且越接近极小点锯齿越细。

20:

29,12,4.2最速下降法,在远离极小点位置，每次迭代可使函数值有较多的下降。

在接近极小点位置，每次迭代行进的距离缩短，收敛速度减慢。

最速下降性”只是迭代点邻域的局部性质。

从全局看，并非最速下降方向。

（3）现象,20:

29,13,4.2最速下降法,（4）计算步骤,1）给定初始迭代点x0，精度，维数n；,2）令k0；,3）计算xk的梯度；,4）以xk点为出发点，求方向上的最优步长k，有；,终止判别？

若满足条件，输出最优解，xk+1x*,f*f（x*）。

否则，令kk+1，转步骤3）。

20:

29,14,4.2最速下降法,（4）计算步骤,20:

29,15,4.2最速下降法,（5）举例,沿负梯度方向进行一维搜索，有,例：

求目标函数的极小点。

取初始点,解：

初始点处梯度：

20:

29,16,4.2最速下降法,（5）举例,为一维搜索最佳步长，应满足极值必要条件,20:

29,17,4.2最速下降法,（5）举例,第一次迭代设计点位置和函数值,因此，迭代终止：

20:

29,18,4.2最速下降法,（5）举例,20:

29,19,4.2最速下降法,（5）举例,例：

用最速下降法求,极小点，精度,解：

1）取初始点。

初始梯度,2）沿负梯度方向一维搜索,3）求最优步长,初始点处函数值,20:

29,20,4.2最速下降法,（5）举例,4）计算新的迭代点位置和函数值,5）迭代终止条件判断,继续迭代。

取初始点为X1，继续重复1-5步，直到满足精度要求。

迭代10次的结果是：

20:

29,21,4.2最速下降法,（5）举例,这个问题的目标函数的等值线为一簇椭圆,迭代点从X0走的是一段锯齿形路线，见图。

20:

29,22,4.2最速下降法,（5）举例,其等值线由椭圆变成一簇同心圆。

则函数f（X）变为：

y1=x1,y2=5x2,将上例中目标函数引入变换,仍从,即出发进行最速下降法寻优。

此时：

20:

29,23,4.2最速下降法,（5）举例,0为一维搜索最佳步长，可由极值条件：

从而算得一步计算后设计点的位置及其目标函数：

由,沿负梯度方向进行一维搜索：

20:

29,24,4.2最速下降法,（5）举例,经变换后，只需一次迭代，就可找到最优解。

这是因为经过尺度变换：

等值线由椭圆变成圆。

20:

29,25,4.2最速下降法,（5）举例,例：

用最速下降法求下面无约束优化问题：

20:

29,26,4.2最速下降法,（5）举例,20:

29,27,4.2最速下降法,（5）举例,20:

29,28,4.2最速下降法,（5）举例,20:

29,29,4.2最速下降法,（6）收敛性分析,最速下降法的收敛速度和变量的尺度关系很大。

在适当条件下，收敛速度的估计公式：

式中m表示f（x）的海塞矩阵的最大特征值上界，M表示f（x）的海塞矩阵的最小特征值的下界,对于等值线为椭圆的二次型函数,其海塞矩阵为,特征值为2，50,因此,收敛性较慢,20:

29,30,4.2最速下降法,（7）最速下降法的典型特征,由于一维搜索是求,的极小。

故应满足：

即,因此，在梯度法中，相邻两次搜索方向（即相邻两次迭代点的梯度方向）是正交的。

20:

29,31,4.2最速下降法,（7）最速下降法的典型特征,理论明确，程序简单，对初始点要求不严格。

对一般函数而言，梯度法的收敛速度并不快，因为最速下降方向仅仅是指某点的一个局部性质。

梯度法相邻两次搜索方向的正交性，决定了迭代全过程的搜索路线呈锯齿状，在远离极小点时逼近速度较快，而在接近极小点时逼近速度较慢。

梯度法的收敛速度与目标函数的性质密切相关。

对于等值线（面）为同心圆（球）的目标函数，一次搜索即可达到极小点。

20:

29,32,4.3牛顿型方法,

（1）基本思想,在xk邻域内用一个二次函数来近似代替原目标函数，并将的极小点作为对目标函数求优的下一个迭代点。

经多次迭代，使之逼近目标函数的极小点。

牛顿法是求函数极值的最古老算法之一。

20:

29,33,4.3牛顿型方法,

（2）迭代公式,原函数:

近似二次函数:

求的极小点，要求其梯度等于零。

20:

29,34,4.3牛顿型方法,

（2）迭代公式,（牛顿方向）,2）步长因子：

令,由此，,这就是多元函数求极值的牛顿法迭代公式。

对于二次函数，海赛G是一个常矩阵，其中各元素均为常数。

因此，无论从任何点出发，只需一步就可找到极小点。

20:

29,35,4.3牛顿型方法,（3）举例,例：

求目标函数的极小点。

解：

取初始点,经过一次迭代即求得极小点,20:

29,36,4.3牛顿型方法,（4）阻尼牛顿法,对于正定二次函数，牛顿法可以直达极小点。

对于非二次函数，基本牛顿法的步长因子恒为1，有时会导致迭代发散而失效，如果采用上述牛顿迭代公式，有时会使函数值上升。

问题提出,20:

29,37,4.3牛顿型方法,（4）阻尼牛顿法,比如，对于如下问题：

当,新迭代点,当,新迭代点,问题提出,20:

29,38,4.3牛顿型方法,（4）阻尼牛顿法,迭代公式,阻尼因子，沿牛顿方向进行一维搜索的最佳步长，由下式求得：

20:

29,39,4.3牛顿型方法,（4）阻尼牛顿法,迭代步骤,1）给定初始点x0，收敛精度，置k=0；2）计算3）求,其中k是沿dk一维搜索最优步长；,4）检查收敛精度。

若时停止，否则k=k+1，返回第二步。

20:

29,40,4.3牛顿型方法,（4）阻尼牛顿法,算法特点,1）不能保证每次迭代都使函数值下降。

举例说明：

用阻尼牛顿法求函数的最优解。

初始点,函数的梯度,20:

29,41,4.3牛顿型方法,（4）阻尼牛顿法,算法特点,牛顿方向,结果说明迭代后的新点仍为原点，无法继续迭代。

原因是海赛矩阵不定，导致失败。

20:

29,42,4.3牛顿型方法,（4）阻尼牛顿法,算法特点,2）初始点应选在x*附近，有一定难度；3）尽管每次迭代都不会是函数值上升，但不能保证每次下降4）收敛速度较牛顿法慢，但对初始点无特殊要求，实用性更好5）要求海赛矩阵正定（保证有极小值）和非奇异（保证有逆矩阵）。

这使得该法对复杂多变量目标函数的优化问题无实用价值；6）不仅要计算梯度，还要求海赛矩阵及其逆矩阵，计算量和存储量大。

虽然阻尼牛顿法有上述缺点，但在特定条件下它具有收敛最快的优点，并为其他的算法提供了思路和理论依据。

20:

29,43,4.3牛顿型方法,（5）牛顿型法与梯度法对比,一般迭代式：

梯度法：

牛顿法：

阻尼牛顿法：

20:

29,44,

（1）共轭方向的概念,4.4共轭方向与共轭方向法,设G为nn阶实对称正定矩阵，如果有两个n维向量d0和d1满足，则称向量d0和d1关于矩阵G共轭。

如果G=I（单位矩阵），就有，d0和d1方向正交，即与单位矩阵共轭的方向是正交方向，所以正交方向是共轭方向的一个特例。

但两者不能混淆。

共轭但不正交,正交但不共轭,对于,共轭正交,20:

29,45,

（1）共轭方向的概念,4.4共轭方向与共轭方向法,假设目标函数f（x）在极值点附近的二次近似函数为,对二维情况,任选取初始点x0沿某个下降方向d0作一维搜索，得x1,20:

29,46,

（1）共轭方向的概念,4.4共轭方向与共轭方向法,如果按最速下降法，选择负梯度方向为搜索方向，则将发生锯齿现象。

取下一次的迭代搜索方向d1直指极小点x*。

因为0是沿d0方向搜索的最佳步长，即在点x1处函数f（x）沿方向d0的方向导数为零。

考虑到点x1处方向导数与梯度之间的关系，故有,20:

29,47,

（1）共轭方向的概念,4.4共轭方向与共轭方向法,如果能够选定这样的搜索方向，那么对于二元二次函数只需顺次进行d0、d1两次直线搜索就可以求到极小点x*，即有,那么这样的d1方向应该满足什么条件呢?

对于前述的二次函数:

有,20:

29,48,

（1）共轭方向的概念,4.4共轭方向与共轭方向法,当时，,x*是f（x）极小点，应满足极值必要条件，故有,将等式两边同时左乘,同时得：

20:

29,49,

（1）共轭方向的概念,4.4共轭方向与共轭方向法,就是使d1直指极小点x*，d1所必须满足的条件。

两个向量d0、d1和称为G的共轭向量，或称d0和d1对G是共轭方向。

20:

29,50,

（1）共轭方向的概念,4.4共轭方向与共轭方向法,则称d0,d1,dm-1是对G共轭,定义：

若设G为n*n对称正定矩阵，若n维空间中有m个非零向量系d0,d1,dm-1是满足,当G=I（单位矩阵）时，d0,d1,dm-1正交。

共轭概念是正交概念的推广，正交是共轭的特例。

20:

29,51,

（2）共轭方向的性质,4.4共轭方向与共轭方向法,性质1若非零向量系d0,d1,dm-1是对G共轭，则这m个向量是线性无关的。

性质2在n维空间中互相共轭的非零向量的个数不超过n。

性质3从任意初始点出发，顺次沿m个G的共轭方向d0,d1,dm-1进行一维搜索，最多经过m次迭代就可以找到的二次函数f（x）极小点。

20:

29,52,（3）共轭方向法,4.4共轭方向与共轭方向法,20:

29,53,（3）共轭方向法,4.4共轭方向与共轭方向法,在无约束方法中许多算法都是以共轭方向作为搜索方向，它们具有许多特点。

根据构造共轭方向的原理不同，可以形成不同的共轭方向法。

格拉姆-斯密特矢量系共轭化方法共轭梯度法鲍威尔（Powell）法,20:

29,54,（4）格拉姆-斯密特矢量系共轭化方法,4.4共轭方向与共轭方向法,选定n个线性无关的矢量系v0,v1,vn-1，首先取,令,其中10是待定系数，可根据d1与d0的共轭条件来确定，即,从而求得与d0的共轭的d1,20:

29,55,（4）格拉姆-斯密特矢量系共轭化方法,4.4共轭方向与共轭方向法,设已求得共轭的矢量d0,d1,dk，现求dk+1,令,为使dk+1与dj（j=0,1,k）共轭，应有,由此解得,Why?

20:

29,56,（4）格拉姆-斯密特矢量系共轭化方法,4.4共轭方向与共轭方向法,由于,可推导出,由于d0,d1,dk共轭，所以,即,20:

29,57,（4）格拉姆-斯密特矢量系共轭化方法,4.4共轭方向与共轭方向法,例：

求,的一组共轭矢量系d0,d1,d2,解：

（1）选定三个单位矢量e0、e1、e2作为一组线性无关矢量系,

（2）取d0=e0，求d1,20:

29,58,（4）格拉姆-斯密特矢量系共轭化方法,4.4共轭方向与共轭方向法,

（2）求d2,（3）判断是否满足共轭的定义,20:

29,59,（4）格拉姆-斯密特矢量系共轭化方法,4.4共轭方向与共轭方向法,对于非二次函数，可在极小点附近用二次函数来近似。

上式中的海塞矩阵相当于二次函数中的矩阵G，但x*未知，当迭代点x0充分靠近x*时，可用G（x0）构造共轭矢量系。

20:

29,60,

（1）概述,4.5坐标轮换法,许多优化方法都需要计算目标函数的导数，而在实际工程的最优化问题中，目标函数的导数往往很难求出或者根本无法求出。

坐标轮换法只需要计算目标函数值，无需求其导数，因此计算比较简单，其几何概念也比较清晰，属于直接法的无约束最优化方法。

这类方法适用于不知道目标函数的数学表达式而仅知其具体算法的情况。

这也是直接法的一个优点。

20:

29,61,

（2）基本思想,4.5坐标轮换法,又称为单变量法，它是把一个多维无约束优化问题转化为依次沿各坐标方向的一维优化问题。

对n维空间中每个坐标依次搜索完一遍，称为完成一个搜索“轮”，然后，将前一轮得到的最优点，作为下一轮搜索的起始点。

这样，不断循环，直到满足收敛条件为止。

20:

29,62,

（2）基本思想,4.5坐标轮换法,以二维问题为例进行说明,设有二维目标函数f（X），其等值线如图所示，计算方法如下：

1.选择初始迭代点，搜索精度.,2.以为起点，并沿坐标轴方向搜索，采用一维优化方法确定最优步长，并计算。

3.再以为起点，并沿坐标轴方向搜索，采用一维优化方法确定最优步长，计算。

4.到此完成一轮搜索，进行终止条件判别:

?

若条件满足，则输出最优解。

否则，进行下步。

5.，转步骤

（2），进行下一轮的迭代运算。

20:

29,63,例用坐标轮换法求的极小值.,解,1）取初始点，沿方向一维搜索，得:

其中为一维搜索最佳步长，应满足,得：

沿方向一维搜索，得:

其中为一维搜索最佳步长，应满足,得：

计算误差,4.5坐标轮换法,（3）算例,20:

29,64,2）第二次迭代搜索,沿方向一维搜索，得:

其中为一维搜索最佳步长，应满足,得：

沿方向一维搜索，得:

其中为一维搜索最佳步长，应满足,得：

计算误差,4.5坐标轮换法,20:

29,65,3）第三次迭代搜索,沿方向一维搜索，得:

其中为一维搜索最佳步长，应满足,得：

沿方向一维搜索，得:

其中为一维搜索最佳步长，应满足,得：

计算误差,同理，继续迭代，共24次，可得到,4.5坐标轮换法,20:

29,例:

用坐标轮换法求下列目标函数的无约束最优解。

给定初始点，精度要求=0.1,解：

做第一轮迭代计算,沿e1方向进行一维搜索,式中，为第一轮的起始点，取,4.5坐标轮换法,20:

29,66,按最优步长原则确定最优步长1，即极小化,此问题可由某种一维优化方法求出1:

以为新起点，沿e2方向一维搜索,以最优步长原则确定2，即为极小化,4.5坐标轮换法,20:

29,67,对于第一轮按终止条件检验,计算5轮后，有,故近似优化解为,4.5坐标轮换法,20:

29,68,69,1.给定初始点,迭代精度,维数n,搜索方向（i=1n）；,2.置k0；,3.置i1；,4.置；,5.从点出发,沿方向进行关于的一维搜索,求出最优步长,使,6.判别i=n?

若满足条件则进行步骤7;否则置i+1i,返回步骤5；,7.检验是否满足终止迭代条件?

若满足则输出最优解;否则置（i=1n）,XnkX0,k+1k,返回步骤3。

4.5坐标轮换法,（4）计算步骤,20:

29,70,（4）算法步骤,20:

29,方法简单，容易实现。

当维数增加时，效率明显下降，只适于N10的小型优化问题。

收敛慢，以振荡方式逼近最优点。

受目标函数的性态影响很大。

当函数的等值线族为长、短轴分别与坐标轴平行的椭圆时，如图a）所示，二次就收敛到极值点；但当函数的等值线族仍为椭圆，仅仅只是长短轴倾斜时，如图b）所示，多次迭代后逼近极值点；如图c）所示，目标函数等值线出现山脊（或称陡谷），若搜索到A点，再沿两个坐标轴以t0步长测试，目标函数值均上升，计算机判断A点为最优点。

事实上发生错误。

4.5坐标轮换法,（5）方法评价,71,20:

29,共轭梯度法是共轭方向法的一种，因为该方法中每一个共轭向量都是依赖于迭代点处的负梯度而构造出来的，所以称作共轭梯度法。

以梯度法相邻两次迭代的负梯度方向呈线性无关且互为正交这点为基础而构造出的一种具有二次收敛的算法。

每轮搜索方向为一组共轭方向,但第一方向为负梯度方向。

4.6共轭梯度法,

（1）概述,72,20:

29,共轭梯度法的搜索方向是在采用梯度法基础上的共轭方向，目标函数F（x）在迭代点X（k+1）处的负梯度为-F（X（k+1），该方向与前一搜索方向S（k）互为正交，在此基础上构造一种具有较高收敛速度的搜索方向。

4.6共轭梯度法,

（2）搜索方向,73,20:

29,4.6共轭梯度法,

（2）搜索方向,74,第二方向：

第一方向：

*d1可表示为两个负梯度方向的线性组合。

可以推导出一般搜索方向dk+1需要满足如下条件

（1）

（2）以dk与-f（X（k+1）为基底的子空间中，矢量相共轭，即满足：

其中：

20:

29,75,，,以后新方向均按下述迭代公式产生：

因而，,因为,（G是二次函数的Hessian矩阵）,故有,二次函数,其梯度为,4.6共轭梯度法,（3）推导过程,20:

29,（4）计算f（Xk+1），若|f（Xk+1）|，则终止迭代，取X*=Xk+1；否则进行下一步;,

（1）选初始点X0和收敛精度；,

（2）令k=0，计算d0=-f（X0）;,（3）沿dk方向进行一维搜索求k，得Xk+1=Xk+kdk;,（5）检查搜索次数，若k=n，则令X0=Xk+1，转

（2），否则，进行下一步;,（6）构造新的共轭方向：

dk+1=-f（Xk+1）+kdk，令k=k+1，转（3）;,重置负梯度方向,4.6共轭梯度法,（4）算法步骤,76,20:

29,77,k=n,重置负梯度方向,是,停止,4.6共轭梯度法,（4）算法步骤,20:

29,共轭梯度法属于解析法，其算法需求一阶导数，所用公式及算法简单，所需存储量少。

该方法以正定二次函数的共轭方向理论为基础，对二次型函数可以经过有限步达到极小点，所以具有二次收敛性。

但是对于非二次型函数，以及在实际计算中由于计算机舍入误差的影响，虽然经过n次迭代，仍不能达到极小点，则通常以重置负梯度方向开始，搜索直至达到预定精度，其收敛速度也是较快的。

4.6共轭梯度法,（4）算法特点,78,20:

29,79,例：

用共轭梯度法求二次函数的极小点和极小值。

精度,解：

1）取初始点,初始点模，取,2）沿d0方向一维搜索,3）求最优步长,则初始梯度,4.6共轭梯度法,（5）算例,20:

29,80,4）计算新的迭代点的梯度及模,6）计算迭代点的系数和新的共轭方向,5）迭代终止条件判断,继续进行迭代计算。

4.6共轭梯度法,20:

29,81,4.6共轭梯度法,7）再沿d1进行一维搜索，得,8）求最优步长,9）计算X2的梯度和海赛矩阵,G正定,迭代2次的结果：

20:

29,