现代设计理论与方法(优化设计第四章总结)ppt课件.pptx

《现代设计理论与方法(优化设计第四章总结)ppt课件.pptx》由会员分享，可在线阅读，更多相关《现代设计理论与方法(优化设计第四章总结)ppt课件.pptx（27页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、致知力行明德任责Kunming University of Science and TechnologyFaculty of Mechanical and Electrical Engineering第四章第四章 无约束优化方法总结无约束优化方法总结明德任责 致知力行篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统 目前已研究出很多种无约束优化方法，它们的目前已研究出很多种无约束优化方法，它们的主要不同点主要不同点在于在于构造搜索方向构造搜索方向上的差别上的差别。按照按照是否使用目标函数导数是否使用目标函数导数可分为：可分为：（1 1

2、）间接法）间接法要使用导数要使用导数，如梯度法、（阻尼）牛顿法、，如梯度法、（阻尼）牛顿法、变尺度法、共轭梯度法等变尺度法、共轭梯度法等。（2 2）直接法）直接法不使用导数信息不使用导数信息，如坐标轮换法、，如坐标轮换法、鲍威尔法鲍威尔法、单形替换法单形替换法等等。无约束优化无约束优化问题问题求求n n维设计变量维设计变量使目标函数使目标函数 明德任责 致知力行篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统搜索方向的构成问题乃是无约束优化方法的关键。搜索方向的构成问题乃是无约束优化方法的关键。用用直接法寻找极小点时，不必求函数的导数

3、，只要计算目标直接法寻找极小点时，不必求函数的导数，只要计算目标函数值。函数值。这类方法较适用于解决变量个数较少的（这类方法较适用于解决变量个数较少的（n 20n 20）问题）问题，一般情况下一般情况下比间接法效率低比间接法效率低。间接法间接法除要计算目标函数值外，还要除要计算目标函数值外，还要计算目标函数的梯度计算目标函数的梯度，有的还要计算其海赛矩阵。有的还要计算其海赛矩阵。迭迭代代搜搜索索方方法法是是无无约约束束优优化化的的最最常常用用求求解解方方法法，其其通通用用格格式式为：为：明德任责 致知力行篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是

4、一种得分类型的系统 基本思想：函数的负梯度方向是函数值在该点下降最快的方向。将n维问题转化为一系列沿负梯度方向用一维搜索方法寻优的问题，利用负梯度作为搜索方向，故称最速下降法或梯度法。搜索方向s取该点的负梯度方向 (最速下降方向)，使函数值在该点附近的范围内下降最快。一、最速下降法明德任责 致知力行篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统 为为了了使使目目标标函函数数值值沿沿搜搜索索方方向向 能能够够获获得得最最大大的下降值，其步长因子的下降值，其步长因子 应取一维搜索的最佳步长。即有应取一维搜索的最佳步长。即有 根据一元函数

5、根据一元函数极值的必要条件极值的必要条件和和多元复合函数求导公式多元复合函数求导公式，得，得 相邻相邻两个迭代点上的函数两个迭代点上的函数梯度相互垂直梯度相互垂直。特点：以特点：以锯齿状锯齿状向极值点靠近，而且向极值点靠近，而且越接近极小点锯齿越细越接近极小点锯齿越细明德任责 致知力行篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统最速下降法搜索过程演示（以二维为例）最速下降法搜索过程演示（以二维为例）明德任责 致知力行篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统最速下降

6、最速下降方法方法特点特点（1 1）初始点可任选初始点可任选，每次，每次迭代计算量小迭代计算量小，存储量少存储量少，程序简短程序简短。即使从一个不好的初始点出发，开始的几步。即使从一个不好的初始点出发，开始的几步迭代，目标函数值下降很快，然后慢慢逼近局部极小点。迭代，目标函数值下降很快，然后慢慢逼近局部极小点。（2 2）任意相邻两点的搜索方向是正交的，它的迭代路）任意相邻两点的搜索方向是正交的，它的迭代路径为绕道逼近极小点。径为绕道逼近极小点。当迭代点接近极小点时，步长变当迭代点接近极小点时，步长变得很小，越走越慢。得很小，越走越慢。明德任责 致知力行篮球比赛是根据运动队在规定的比赛时间里得分多

7、少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统设 为 的极小点 牛顿法基本思想：在xk邻域内用一个二次函数 来近似代替原目标函数，并将 的极小点作为对目标函数 求优的下一个迭代点 。经多次迭代，使之逼近目标函数 的极小点。牛顿法是求函数极值的最古老算法之一。牛顿型法明德任责 致知力行篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统这就是多元函数求极值的牛顿法迭代公式。对于二次函数，海赛矩阵H是一个常矩阵，其中各元素均为常数。因此，无论从任何点出发，只需一步就可找到极小点。阻尼牛顿法（避免了迭代后函数值上升的现象）阻尼

8、因子，沿牛顿方向进行一维搜索的最佳步长 从牛顿法迭代公式的推演中可以看到，迭代点的位置是按照极值条件确定的，其中并未含有沿下降方向搜寻的概念。因此对于非二次函数，如果采用上述牛顿迭代公式，有时会使函数值上升。明德任责 致知力行篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统 牛顿法搜索过程演示（以二维为例）牛顿法搜索过程演示（以二维为例）明德任责 致知力行篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统阻尼牛顿方法特点阻尼牛顿方法特点 （1 1）初始点应选在初始点应选在X X

9、*附近附近，有一定难度；，有一定难度；（2 2）尽管每次迭代都不会是函数值上升，但尽管每次迭代都不会是函数值上升，但不能保证不能保证每次下降每次下降 ；（3 3）若迭代点的若迭代点的海赛矩阵为奇异海赛矩阵为奇异，则无法求逆矩阵，则无法求逆矩阵，不能构造牛顿法方向不能构造牛顿法方向；（4 4）不仅要计算梯度，还要求海赛矩阵及其逆矩阵，不仅要计算梯度，还要求海赛矩阵及其逆矩阵，计算量和存储量大计算量和存储量大。此外，对于。此外，对于二阶不可微的二阶不可微的F F(X X)也不也不适用适用。虽然阻尼牛顿法有上述缺点，但在虽然阻尼牛顿法有上述缺点，但在特定条件下它特定条件下它具有收敛最快的优点具有收敛

10、最快的优点，并为其他的算法，并为其他的算法提供了思路和理提供了思路和理论依据论依据。明德任责 致知力行篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统 DFP变尺度法首先有戴维顿（Davidon）与1959年提出，又于1963年由弗莱彻（Fletcher）和鲍维尔加以发展和完善，成为现代公认的较好的算法之一。DFP法是基于牛顿法的思想又作了重要改进。这种算法仅用到梯度，不必计算海赛阵及其逆矩阵，但又能使搜索方向逐渐逼近牛顿方向，具有较快的收敛速度。三、变尺度法变量的尺度变换是放大或缩小各个坐标。通过尺度变换可以把函数的偏心程度降到最低

11、限度。明德任责 致知力行篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统 梯度法构造简单，只用到一阶偏导数，计算量小，初始点可任选，且开始几次迭代，目标函数值下降很快；其主要缺点是迭代点接近X*时，即使对二次正定函数收敛也非常慢。牛顿法收敛很快，对于二次函数只需迭代一次便达到最优点，对非二次函数也能较快迭代到最优点，但要计算二阶偏导数矩阵及其逆阵，对维数较高的优化问题，其计算工作和存储量都太大。变尺度法将两种算法的优点综合起来，扬长避短梯度法和牛顿法特性回顾明德任责 致知力行篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，

12、因此，篮球比赛的计时计分系统是一种得分类型的系统v变量的尺度变换是变量的尺度变换是放大或缩小各个坐标放大或缩小各个坐标。通过尺度变。通过尺度变换可以把换可以把函数的偏心程度降低到最低限度函数的偏心程度降低到最低限度。尺度变换。尺度变换技巧能技巧能显著地改进几乎所有极小化方法的收敛性质显著地改进几乎所有极小化方法的收敛性质。牛顿法就可看成是经过尺度变换后的梯度法。经过尺度变换，使函数偏心率减小到零，函数的等值面变为球面(或超球面)，使设计空间中任意点处函数的梯度都通过极小点，用最速下降法只需一次迭代就可达到极小点。对变换前的二次函数，在使用牛顿方法时，由于其牛顿方向直接指向极小点，因此只需一次迭

13、代就能找到极小点。明德任责 致知力行篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统变尺度法搜索过程演示（以二维为例）变尺度法搜索过程演示（以二维为例）明德任责 致知力行篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统四、鲍威尔方法 鲍威尔法是以共轭方向为基础的收敛较快的直接法之鲍威尔法是以共轭方向为基础的收敛较快的直接法之一，是一，是一种十分有效的算法一种十分有效的算法。1964 1964年，鲍维尔提出这种算法，其年，鲍维尔提出这种算法，其基本思想是直接利基本思想是直接利用

14、迭代点的目标函数值来构造共轭方向用迭代点的目标函数值来构造共轭方向，然后从任一初始，然后从任一初始点开始，逐次沿共轭方向作一维搜索求极小点。并在以后点开始，逐次沿共轭方向作一维搜索求极小点。并在以后的实践中进行了改进。的实践中进行了改进。明德任责 致知力行篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统对函数：对函数：基本思想基本思想：在不用导数的前提下，在迭代中逐次构造在不用导数的前提下，在迭代中逐次构造G G的共轭的共轭方向。方向。1.1.共轭方向的生成共轭方向的生成设设x xk k,x xk+1k+1为从不同点出为从不同点出发发

15、，沿同一方向沿同一方向d dj j进行进行一维搜索而到的两个极一维搜索而到的两个极小点。小点。共轭共轭方向的方向的生成生成演示演示明德任责 致知力行篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统基本算法v二维情况描述鲍威尔的基本算法二维情况描述鲍威尔的基本算法:1 1）任任选选一一初初始始点点x x0 0，再再选选两两个个线线性性无无关关的的向向量量，如如 坐坐 标标 轴轴 单单 位位 向向 量量e e1 1=1,0=1,0T T和和e e2 2=0,1=0,1T T作作为为初始搜索方向初始搜索方向。2 2）从从x x0 0出出发发

16、，顺顺次次沿沿e e1 1，e e1 1作一维搜索作一维搜索，得，得 点点，两两点点连连线线得得一新方向一新方向d d1 1明德任责 致知力行篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统沿沿d d2 2作一维搜索得点作一维搜索得点x x2 2 。即是即是二维问题的极小点二维问题的极小点x x*。方法的基本迭代格式包括方法的基本迭代格式包括共轭方向产生共轭方向产生和和方向替换方向替换两主要步骤。两主要步骤。用用 d d1 1代替代替e e1 1形成两个线性无关向量形成两个线性无关向量d d1 1,e e2 2 ，作为下一轮，作为下一

17、轮迭代的搜索方向迭代的搜索方向。再。再 从出发，沿从出发，沿d d1 1作一维搜索得点作一维搜索得点 ，作为下一轮迭代的初始点。，作为下一轮迭代的初始点。3 3）从从 出出发发，顺顺次次沿沿e e2 2,d,d1 1作作一一维维搜搜索索，得得到到点点 ，两两点点连连线线得得一一新新方向方向:明德任责 致知力行篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统 二维情况描述鲍威尔的搜索过程演示二维情况描述鲍威尔的搜索过程演示 明德任责 致知力行篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得

18、分类型的系统 二维改进鲍威尔方法的搜索过程演示二维改进鲍威尔方法的搜索过程演示 和若若d1换换em否则，使用原来的方向组否则，使用原来的方向组e1、e2，以F2、F3最小值点位新的起点映射映射,非搜索非搜索明德任责 致知力行篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统五、单形替换法一、基本思想一、基本思想 单纯形替换法单纯形替换法也是一种不使用导数的求解无也是一种不使用导数的求解无约束极小化问题的约束极小化问题的直接搜索方法直接搜索方法，与前面几种方，与前面几种方法不同的是，单纯形替换法法不同的是，单纯形替换法不是利用搜索方向不是

19、利用搜索方向从从一个点迭代到另一个更优的点，而是一个点迭代到另一个更优的点，而是从一个单纯从一个单纯形形迭代到另一个迭代到另一个更优的单纯形更优的单纯形。该方法该方法只需要计算目标函数值，无需求其导数只需要计算目标函数值，无需求其导数，因此，因此计算比较简单，其几何概念也比较清晰，属于直接法的计算比较简单，其几何概念也比较清晰，属于直接法的无约束最优化方法。这类方法无约束最优化方法。这类方法适用于不知道目标函数的适用于不知道目标函数的数学表达式而仅知其具体算法的情况数学表达式而仅知其具体算法的情况。这也是直接法的。这也是直接法的一个优点。一个优点。明德任责 致知力行篮球比赛是根据运动队在规定的

20、比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统定义定义：单纯形：单纯形 n n维维空间中的恰好有空间中的恰好有n n+1+1个顶点个顶点（极点）的有界的（极点）的有界的凸多面体凸多面体称之为一个单纯形。称之为一个单纯形。根据定义，可知，根据定义，可知，一维空间中的单纯形是线段一维空间中的单纯形是线段，二维空间二维空间中的单纯形是三角形中的单纯形是三角形，而，而三维空间中的单纯形则是四面体三维空间中的单纯形则是四面体。在单纯形替换算法中，从一个单纯形到另一个单纯形的迭在单纯形替换算法中，从一个单纯形到另一个单纯形的迭代主要通过代主要通过反射、扩张、收缩和缩边反射

21、、扩张、收缩和缩边这这4 4个操作来实现。下面个操作来实现。下面以二维问题为例来对以二维问题为例来对4 4种操作进行说明（参见下图）。种操作进行说明（参见下图）。明德任责 致知力行篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统X2X1X3X8X4X5X6X7目标函数：中点：反射点：扩张点：收缩点：进一步收缩：如果：扩张如果：取x2，x3，x6；否则取x2，x3，x5。如果：则取x2，x3，x5。如果：则收缩若：取x2,x3,x7。否则x2,x3,x5。如果：若：取x2,x3,x8，否则弃x8。若 缩边。X9单形替换法过程动画演示明德

22、任责 致知力行篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统方法方法搜索方向搜索方向函数梯度修函数梯度修正因子正因子所用目标函数所用目标函数信息信息梯度法I（单位阵）一阶导数一阶导数(阻尼)牛顿法一、二阶导数一、二阶导数共轭梯度法一阶导数变尺度法一阶导数一阶导数鲍威尔方法零阶方法目标函数值单形替换法最差点和其余点重心连线零阶方法目标函数值 无约束优化方法搜索方向之间的相互联系明德任责 致知力行篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统无约束优化方法间接法总结1 1、梯

23、度法、梯度法 方向方向 负梯度负梯度 用到一阶导数用到一阶导数 适合于精度不高或用于复杂函数寻找一个好的初始点适合于精度不高或用于复杂函数寻找一个好的初始点2 2、牛顿法、牛顿法 用到用到一阶导数和海一阶导数和海赛赛矩阵矩阵，具有二次收敛性，具有二次收敛性 要求要求海赛海赛矩阵非奇异矩阵非奇异，且，且维数不宜太高维数不宜太高3 3、变尺度法、变尺度法 收敛快，效果好，被认为是收敛快，效果好，被认为是目前最有效的无约束优化方目前最有效的无约束优化方法法。适用于。适用于维数较高，具有一阶偏导数的目标函数维数较高，具有一阶偏导数的目标函数 明德任责 致知力行篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统无约束优化方法直接法总结1 1、坐标轮换法、坐标轮换法 计算效率较低计算效率较低 适合维数较低，目标函数无导数或导数较难求得适合维数较低，目标函数无导数或导数较难求得2 2、PowellPowell法法 具有二次收敛性，具有二次收敛性，收敛速度较快收敛速度较快，可靠性高，被认为是可靠性高，被认为是直接法中最有效的方法之一直接法中最有效的方法之一3 3、单纯形法、单纯形法 思路清楚，收敛慢思路清楚，收敛慢本章结束