机械优化设计-无约束优化方法培训课件

机械优化设计-无约束优化方法培训课件17:551机械优化设计-无约束优化方法培训课件23:101上海海事大学ShanghaiMaritimeUniversity

1909

2009

2004

1912

19587机械优化设计中的几个问题1优化设计概述2优化设计的数学基础2目录CONTENTS3一维搜索方法4无约束优化方法5线性规划6约束优化方法17:55上海海事大学19092009200第四章无约束优化方法

概述01

最速下降法

牛顿型方法

共轭方向与共轭方向法020304共轭梯度法05

变尺度法

坐标轮换法

鲍威尔方法060708

单形替换法0917:553第四章无约束优化方法概述01最速下降法44.1概述工程问题大都为有约束优化问题。为什么要研究无约束优化问题?有些实际问题，其数学模型本身就是一个无约束优化问题。通过熟悉它的解法可以为研究约束优化问题打下良好的基础。约束优化问题的求解可以通过一系列无约束优化方法来达到。所以无约束优化问题的解法是优化设计方法的基本组成部分，也是优化方法的基础。17:5544.1概述工程问题大都为有约束优化问题。为什么要研究无54.1概述无约束优化问题是：求n

维设计变量使目标函数无约束优化问题极值存在的必要条件：17:5554.1概述无约束优化问题是：求n维设计变量使目标函数64.1概述

目前已研究出很多种无约束优化方法，它们的主要不同点在于构造搜索方向上的差别。（1）间接法——要使用导数，如梯度法、（阻尼）牛顿法、变尺度法、共轭梯度法等。（2）直接法——不使用导数信息，如坐标轮换法、鲍威尔法、单形替换法等。

用直接法寻找极小点时，不必求函数的导数，只要计算目标函数值。这类方法较适用于解决变量个数较少的(n≤20)问题，一般情况下比间接法效率低。间接法除要计算目标函数值外，还要计算目标函数的梯度，有的还要计算其海赛矩阵。搜索方向的构成问题乃是无约束优化方法的关键。其搜索方向直接取定或由计算目标函数值所得的信息来确定。17:5564.1概述目前已研究出很多种无约束优化方法，它74.1概述77选择初始迭代点x0。从迭代点xk出发进行搜索，确定使目标函数值下降的搜索方向dk。确定适当的步长因子αk，求xk+1

=xk+αkdk，使f(xk+1)<f(xk)。选择适当的终止准则，若xk+1满足终止准则，则终止迭代计算，并输出局部最优点x*←xk+1

；否则，令k←k+1，返回步骤(2)继续进行优化搜索。无约束优化方法求解的四个步骤:17:5574.1概述77选择初始迭代点x0。无约束优化方法求解的84.2最速下降法（1）

基本思想搜索方向d取该点的负梯度方向(最速下降方向)，使函数值在该点附近的范围内下降最快。终止判别条件17:5584.2最速下降法（1）基本思想搜索方向d取该点的负梯94.2最速下降法（2）

计算方法为了使目标函数值沿搜索方向能够获得最大的下降值，其步长因子应取一维搜索的最佳步长。即有步长因子求解方法：解析法：根据极值点必要条件。黄金分割法牛顿法抛物线法17:5594.2最速下降法（2）计算方法为了使目标函数值沿搜索104.2最速下降法（2）

计算方法根据一元函数极值的必要条件及复合函数求导公式得17:55104.2最速下降法（2）计算方法根据一元函数极值的必114.2最速下降法（3）

现象最速下降法的搜索路径在最速下降法中，相邻两个迭代点上的函数梯度相互垂直。搜索方向就是负梯度方向，因此相邻两个搜索方向互相垂直。形成“之”字形的锯齿现象，而且越接近极小点锯齿越细。17:55114.2最速下降法（3）现象最速下降法的搜索路径在最124.2最速下降法在远离极小点位置，每次迭代可使函数值有较多的下降。在接近极小点位置，每次迭代行进的距离缩短，收敛速度减慢。最速下降性”只是迭代点邻域的局部性质。从全局看，并非最速下降方向。（3）

现象17:55124.2最速下降法在远离极小点位置，每次迭代可使函数值134.2最速下降法（4）

计算步骤1)给定初始迭代点x0，精度ε，维数n；2)令k←0；3)计算xk的梯度；4)以xk点为出发点，求方向上的最优步长αk，有；终止判别

？若满足条件，输出最优解，

xk+1→x*,f*←f

(x*)。否则，令k←

k+1，转步骤3)。17:55134.2最速下降法（4）计算步骤1)给定初始迭144.2最速下降法（4）

计算步骤αα17:55144.2最速下降法（4）计算步骤αα23:10154.2最速下降法（5）

举例沿负梯度方向进行一维搜索，有例：

求目标函数的极小点。取初始点解：初始点处梯度：17:55154.2最速下降法（5）举例沿负梯度方向进行一维搜索164.2最速下降法（5）

举例为一维搜索最佳步长，应满足极值必要条件17:55164.2最速下降法（5）举例为一维搜索最佳步长，应满174.2最速下降法（5）

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

举例17:55184.2最速下降法（5）举例23:10194.2最速下降法（5）

举例例：用最速下降法求极小点，精度解：1）取初始点。初始梯度2）沿负梯度方向一维搜索3）求最优步长初始点处函数值17:55194.2最速下降法（5）举例例：用最速下降法求204.2最速下降法（5）

举例4)计算新的迭代点位置和函数值5）迭代终止条件判断继续迭代。取初始点为X1，继续重复1-5步，直到满足精度要求。迭代10次的结果是：17:55204.2最速下降法（5）举例4)计算新的迭代点位214.2最速下降法（5）

举例

这个问题的目标函数的等值线为一簇椭圆,迭代点从X0

走的是一段锯齿形路线，见图

。17:55214.2最速下降法（5）举例这个问题的224.2最速下降法（5）

举例其等值线由椭圆变成一簇同心圆。则函数f(X)变为：y1=x1,y2=5x2将上例中目标函数引入变换

仍从,即出发进行最速下降法寻优。此时：17:55224.2最速下降法（5）举例其等值线由椭圆变成一簇同234.2最速下降法（5）

举例

β0为一维搜索最佳步长，可由极值条件：从而算得一步计算后设计点的位置及其目标函数：由沿负梯度方向进行一维搜索：17:55234.2最速下降法（5）举例β0为一维搜索最佳步244.2最速下降法（5）

举例经变换后，只需一次迭代，就可找到最优解。这是因为经过尺度变换：等值线由椭圆变成圆。17:55244.2最速下降法（5）举例经变换后，只需一次迭代，254.2最速下降法（5）

举例例：用最速下降法求下面无约束优化问题：17:55254.2最速下降法（5）举例例：用最速下降法求下面264.2最速下降法（5）

举例17:55264.2最速下降法（5）举例23:10274.2最速下降法（5）

举例17:55274.2最速下降法（5）举例23:10284.2最速下降法（5）

举例17:55284.2最速下降法（5）举例23:10294.2最速下降法（6）

收敛性分析最速下降法的收敛速度和变量的尺度关系很大。在适当条件下，收敛速度的估计公式：式中m表示f(x)的海塞矩阵的最大特征值上界，M表示f(x)的海塞矩阵的最小特征值的下界对于等值线为椭圆的二次型函数其海塞矩阵为特征值为2，50因此收敛性较慢17:55294.2最速下降法（6）收敛性分析最速下降法的收敛速304.2最速下降法（7）

最速下降法的典型特征由于一维搜索是求的极小。故应满足：即因此，在梯度法中，相邻两次搜索方向（即相邻两次迭代点的梯度方向）是正交的。17:55304.2最速下降法（7）最速下降法的典型特征由于一维314.2最速下降法（7）

最速下降法的典型特征理论明确，程序简单，对初始点要求不严格。对一般函数而言，梯度法的收敛速度并不快，因为最速下降方向仅仅是指某点的一个局部性质。梯度法相邻两次搜索方向的正交性，决定了迭代全过程的搜索路线呈锯齿状，在远离极小点时逼近速度较快，而在接近极小点时逼近速度较慢。梯度法的收敛速度与目标函数的性质密切相关。对于等值线(面)为同心圆(球)的目标函数，一次搜索即可达到极小点。17:55314.2最速下降法（7）最速下降法的典型特征理论明确324.3牛顿型方法（1）

基本思想在xk邻域内用一个二次函数来近似代替原目标函数，并将

的极小点作为对目标函数求优的下一个迭代点。

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

牛顿法是求函数极值的最古老算法之一。17:55324.3牛顿型方法（1）基本思想在xk邻域内用一个二334.3牛顿型方法（2）

迭代公式原函数:近似二次函数:求的极小点，要求其梯度等于零。17:55334.3牛顿型方法（2）迭代公式原函数:近似二次函数344.3牛顿型方法（2）

迭代公式（牛顿方向）1）迭代方向：*2）步长因子：令由此，这就是多元函数求极值的牛顿法迭代公式。对于二次函数，海赛G是一个常矩阵，其中各元素均为常数。因此，无论从任何点出发，只需一步就可找到极小点。17:55344.3牛顿型方法（2）迭代公式（牛顿方向）1）迭代354.3牛顿型方法（3）

举例例：求目标函数

的极小点。解：取初始点经过一次迭代即求得极小点17:55354.3牛顿型方法（3）举例例：求目标函数364.3牛顿型方法（4）

阻尼牛顿法对于正定二次函数，牛顿法可以直达极小点。对于非二次函数，基本牛顿法的步长因子恒为1，有时会导致迭代发散而失效，如果采用上述牛顿迭代公式，有时会使函数值上升。问题提出17:55364.3牛顿型方法（4）阻尼牛顿法对于正定二次函数，374.3牛顿型方法（4）

阻尼牛顿法比如，对于如下问题：①当新迭代点②当新迭代点问题提出17:55374.3牛顿型方法（4）阻尼牛顿法比如，对于如下问题384.3牛顿型方法（4）

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

阻尼牛顿法迭代步骤1）给定初始点x0，收敛精度ε，置k=0；2）计算3）求其中αk是沿dk一维搜索最优步长；4）检查收敛精度ε。若时停止，否则k=k+1，返回第二步。17:55394.3牛顿型方法（4）阻尼牛顿法迭代步骤1）给定初404.3牛顿型方法（4）

阻尼牛顿法算法特点1）

不能保证每次迭代都使函数值下降。举例说明：用阻尼牛顿法求函数的最优解。初始点函数的梯度17:55404.3牛顿型方法（4）阻尼牛顿法算法特点1）不414.3牛顿型方法（4）

阻尼牛顿法算法特点牛顿方向结果说明迭代后的新点仍为原点，无法继续迭代。原因是海赛矩阵不定，导致失败。17:55414.3牛顿型方法（4）阻尼牛顿法算法特点牛顿方向结424.3牛顿型方法（4）

阻尼牛顿法算法特点2）初始点应选在x*附近，有一定难度；3）尽管每次迭代都不会是函数值上升，但不能保证每次下降4）收敛速度较牛顿法慢，但对初始点无特殊要求，实用性更好5）要求海赛矩阵正定（保证有极小值）和非奇异（保证有逆矩阵）。这使得该法对复杂多变量目标函数的优化问题无实用价值；

6）

不仅要计算梯度，还要求海赛矩阵及其逆矩阵，计算量和存储量大。虽然阻尼牛顿法有上述缺点，但在特定条件下它具有收敛最快的优点，并为其他的算法提供了思路和理论依据。17:55424.3牛顿型方法（4）阻尼牛顿法算法特点2）初始点434.3牛顿型方法（5）

牛顿型法与梯度法对比一般迭代式：梯度法：牛顿法：阻尼牛顿法：17:55434.3牛顿型方法（5）牛顿型法与梯度法对比一般迭代44（1）

共轭方向的概念4.4共轭方向与共轭方向法设G为n×n阶实对称正定矩阵，如果有两个n维向量d0和d1满足

，则称向量d0和d1关于矩阵G共轭。如果G=I（单位矩阵），就有，d0和d1方向正交，即与单位矩阵共轭的方向是正交方向，所以正交方向是共轭方向的一个特例。但两者不能混淆。共轭但不正交正交但不共轭对于共轭正交17:5544（1）共轭方向的概念4.4共轭方向与共轭方向法设G45（1）

共轭方向的概念4.4共轭方向与共轭方向法假设目标函数f(x)

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

共轭方向的概念4.4共轭方向与共轭方向法α0d0x0x1x*11α1d1d1如果按最速下降法，选择负梯度方向

为搜索方向，则将发生锯齿现象。

取下一次的迭代搜索方向d1直指极小点x*。因为α0是沿d0方向搜索的最佳步长，即在点x1处函数f(x)沿方向d0的方向导数为零。考虑到点x1处方向导数与梯度之间的关系，故有17:5546（1）共轭方向的概念4.4共轭方向与共轭方向法α047（1）

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

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

共轭方向的概念4.4共轭方向与共轭方向法

就是使d1直指极小点x*，d1所必须满足的条件。两个向量d0、d1和称为G的共轭向量，或称d0和d1对G是共轭方向。17:5549（1）共轭方向的概念4.4共轭方向与共轭方向法就50（1）

共轭方向的概念4.4共轭方向与共轭方向法

则称d0,d1,……,dm-1是对G共轭定义：若设G为n*n对称正定矩阵，若n维空间中有m个非零向量系d0,d1,……,dm-1是满足

当G=I（单位矩阵）时，d0,d1,……,dm-1正交。

共轭概念是正交概念的推广，正交是共轭的特例。17:5550（1）共轭方向的概念4.4共轭方向与共轭方向法则51（2）

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

在n维空间中互相共轭的非零向量的个数不超过n。性质3从任意初始点出发，顺次沿m个G的共轭方向d0,d1,……,dm-1进行一维搜索，最多经过m次迭代就可以找到的二次函数f(x)极小点。17:5551（2）共轭方向的性质4.4共轭方向与共轭方向法性质52（3）

共轭方向法4.4共轭方向与共轭方向法17:5552（3）共轭方向法4.4共轭方向与共轭方向法23:153（3）

共轭方向法4.4共轭方向与共轭方向法在无约束方法中许多算法都是以共轭方向作为搜索方向，它们具有许多特点。根据构造共轭方向的原理不同，可以形成不同的共轭方向法。格拉姆-斯密特矢量系共轭化方法共轭梯度法鲍威尔（Powell）法……17:5553（3）共轭方向法4.4共轭方向与共轭方向法在无约束54（4）

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

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

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

格拉姆-斯密特矢量系共轭化方法4.4共轭方向与共轭方向法例：求的一组共轭矢量系d0,d1,

d2解：（1）选定三个单位矢量e0、e1、e2作为一组线性无关矢量系（2）取d0=e0，求d117:5557（4）格拉姆-斯密特矢量系共轭化方法4.4共轭方向58（4）

格拉姆-斯密特矢量系共轭化方法4.4共轭方向与共轭方向法（2）求d2（3）判断是否满足共轭的定义17:5558（4）格拉姆-斯密特矢量系共轭化方法4.4共轭方向59（4）

格拉姆-斯密特矢量系共轭化方法4.4共轭方向与共轭方向法对于非二次函数，可在极小点附近用二次函数来近似。上式中的海塞矩阵相当于二次函数中的矩阵G，但x*未知，当迭代点x0充分靠近x*时，可用G(x0)构造共轭矢量系。17:5559（4）格拉姆-斯密特矢量系共轭化方法4.4共轭方向60（1）

概述4.5坐标轮换法许多优化方法都需要计算目标函数的导数，而在实际工程的最优化问题中，目标函数的导数往往很难求出或者根本无法求出。坐标轮换法只需要计算目标函数值，无需求其导数，因此计算比较简单，其几何概念也比较清晰，属于直接法的无约束最优化方法。这类方法适用于不知道目标函数的数学表达式而仅知其具体算法的情况。这也是直接法的一个优点。17:5560（1）概述4.5坐标轮换法许多优化方法都需要计算目61（2）

基本思想4.5坐标轮换法又称为单变量法，它是把一个多维无约束优化问题转化为依次沿各坐标方向的一维优化问题。对n维空间中每个坐标依次搜索完一遍，称为完成一个搜索“轮”，然后，将前一轮得到的最优点，作为下一轮搜索的起始点。这样，不断循环，直到满足收敛条件为止。17:5561（2）基本思想4.5坐标轮换法又称为单变量法，它是62（2）

基本思想4.5坐标轮换法以二维问题为例进行说明设有二维目标函数f(X)，其等值线如图所示，计算方法如下：1.选择初始迭代点，搜索精度.2.以

为起点，并沿坐标轴

方向搜索，采用一维优化方法确定最优步长，并计算。3.再以

为起点，并沿坐标轴方向搜索，采用一维优化方法确定最优步长，计算。4.到此完成一轮搜索，进行终止条件判别:?若条件满足，则输出最优解。否则，进行下步。5.，转步骤(2)，进行下一轮的迭代运算。17:5562（2）基本思想4.5坐标轮换法以二维问题为例进行说63例

用坐标轮换法求的极小值.解

1）取初始点，沿方向一维搜索，得:其中为一维搜索最佳步长，应满足得：沿方向一维搜索，得:其中为一维搜索最佳步长，应满足得：计算误差4.5坐标轮换法（3）

算例17:5563例用坐标轮换法求642）第二次迭代搜索沿方向一维搜索，得:其中为一维搜索最佳步长，应满足得：沿方向一维搜索，得:其中为一维搜索最佳步长，应满足得：

计算误差

4.5坐标轮换法17:55642）第二次迭代搜索沿方向一维搜索，得:其中653）第三次迭代搜索沿方向一维搜索，得:其中为一维搜索最佳步长，应满足得：沿方向一维搜索，得:其中为一维搜索最佳步长，应满足得：计算误差同理，继续迭代，共24次，可得到4.5坐标轮换法17:55653）第三次迭代搜索沿方向一维搜索，得:其中例:用坐标轮换法求下列目标函数的无约束最优解。

给定初始点，精度要求ε=0.1解：做第一轮迭代计算沿e1方向进行一维搜索式中，

为第一轮的起始点，取4.5坐标轮换法17:5566例:用坐标轮换法求下列目标函数的无约束最优解。解：做第一轮迭按最优步长原则确定最优步长α1，即极小化此问题可由某种一维优化方法求出α1:

以为新起点，沿e2方向一维搜索以最优步长原则确定α2，即为极小化4.5坐标轮换法17:5567按最优步长原则确定最优步长α1，即极小化此问题可由某种一维优对于第一轮按终止条件检验计算5轮后，有故近似优化解为4.5坐标轮换法17:5568对于第一轮按终止条件检验计算5轮后，有故近似优化解为4.5691.给定初始点,迭代精度,维数n,搜索方向(i=1～n)；2.置k←0；3.置i←1；4.置；5.从点出发,沿方向进行关于的一维搜索,求出最优步长,使6.判别i=n?若满足条件则进行步骤7;否则置i+1→i,返回步骤5；7.检验是否满足终止迭代条件?若满足则输出最优解;否则置

→(i=1～n),Xnk→X0,k+1→k,返回步骤3。4.5坐标轮换法（4）

计算步骤17:55691.给定初始点,迭代精度70（4）

算法步骤17:5570（4）算法步骤23:10

方法简单，容易实现。

当维数增加时，效率明显下降，只适于N<10的小型优化问题。收敛慢，以振荡方式逼近最优点。受目标函数的性态影响很大。当函数的等值线族为长、短轴分别与坐标轴平行的椭圆时，如图a)所示，二次就收敛到极值点；但当函数的等值线族仍为椭圆，仅仅只是长短轴倾斜时，如图b)所示，多次迭代后逼近极值点；如图c)所示，目标函数等值线出现山脊（或称陡谷），若搜索到A点，再沿两个坐标轴以±t0步长测试，目标函数值均上升，计算机判断A点为最优点。事实上发生错误。4.5坐标轮换法（5）

方法评价7117:55方法简单，容易实现。受目标函数的性态影响很大。4.5共轭梯度法是共轭方向法的一种，因为该方法中每一个共轭向量都是依赖于迭代点处的负梯度而构造出来的，所以称作共轭梯度法。以梯度法相邻两次迭代的负梯度方向呈线性无关且互为正交这点为基础而构造出的一种具有二次收敛的算法。每轮搜索方向为一组共轭方向,但第一方向为负梯度方向。4.6共轭梯度法（1）

概述7217:55共轭梯度法是共轭方向法的一种，因为该方法中每一个共轭向量都共轭梯度法的搜索方向是在采用梯度法基础上的共轭方向，目标函数F(x)

在迭代点X(k+1)处的负梯度为-F(X(k+1))，该方向与前一搜索方向S(k)互为正交，在此基础上构造一种具有较高收敛速度的搜索方向。4.6共轭梯度法（2）

搜索方向7317:55共轭梯度法的搜索方向是在采用梯度法基础上的共轭方向，目标函数4.6共轭梯度法（2）

搜索方向74第二方向：第一方向：*d1可表示为两个负梯度方向的线性组合。可以推导出一般搜索方向d