车辆优化设计理论与实践PPT课件

车辆优化 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 理论与实践江苏大学汽车与交通工程学院*《车辆优化设计理论与实践》教学课件可编辑第3章无约束优化方法 3.1概述 3.2坐标轮换法 3.3鲍威尔方法 3.4最速下降法 3.5牛顿型方法 3.6共轭梯度法 3.7变尺度法 3.8无约束优化方法的选用*可编辑可编辑3.1概述 当机械优化设计的很多问题，都是在一定的限制条件下追求某一指标为最小，所以它们都属于约束优化问题。但是，也有些实际问题，其数学模型本身就是一个无约束优化问题，或者除了在非常接近最终极小点的情况下，都可以按无约束问题来处理。 另外研究无约束优化问题的另一个原因是，通过熟悉它的解法可以为研究约束优化问题打下良好的基础。除此以外，约束优化问题的求解可以通过一系列无约束优化方法来达到。所以无约束优化问题的解法是优化设计方法的基本组成部分，也是优化方法的基础。*可编辑可编辑3.1概述 按下述公式不断进行，形成迭代的下降算法。 各种无约束优化方法的区别就在于确定其搜索方向的方法不同。所以，搜索方向的构成问题乃是无约束优化方法的关键。 根据构成搜索方向所使用的信息性质的不同，无约束优化方法可以分为两类。一类是只利用目标函数值的无约束优化方法，如坐标轮换法，鲍威尔（Powell）法等。另一类是利用目标函数的一阶或二阶导数的无约束优化方法，如最速下降法、共轭梯度法、牛顿法及变尺度法等。*可编辑可编辑3.1概述 对于无约束优化问题的求解，可以直接应用第2章讲述的极值条件来确定极值点位置。 除了一些特殊情况外，一般说来非线性方程组的求解与求无约束极值一样也是一个困难问题，甚至前者比后者更困难。一般用数值计算方法直接求解无约束极值问题。 数值计算方法最常用的是搜索方法，其基本思想是从给定的初始点出发，沿某一搜索方向进行搜索，确定最佳步长使函数值沿方向下降最大。*可编辑可编辑3.2坐标轮换法3.2.1坐标轮换法的算法原理 1．基本思想将一个n维问题转化为一系列的一维优化问题来求解，是一个降维的思想，具体来说，就是沿着坐标方向轮流搜索，每次n－1个变量固定，只对一个变量作一维搜索，首先沿第一个坐标轴方向进行一维搜索，求出该方向上目标函数最小的点或函数值有所下降的点，再以为起点，沿第二坐标轴方向进行一维搜索，找到点，依次进行至，得到迭代点，到此完成一轮迭代。*可编辑可编辑3.2坐标轮换法 图3-1坐标轮换法的迭代过程*可编辑可编辑3.2坐标轮换法 2．步长的确定步长的选择可有下面三种方法。1）随即选择法随机选择步长，只要保证函数值下降。2）最优步长法利用一维搜索来完成该方向上的最优步长，该方法的每一步均可最大限度地减小目标函数值，故可期望收敛得更快些，但程序稍微复杂。3）加速步长法这方法是开始选一个不大的初始步长，在每一次搜索中，都是以开始，随后在函数值下降的情况下以，，……倍增的速度加大步长，直至函数值不再下降，取其前步长为最终步长，这种办法较简单，程序易编制。*可编辑可编辑3.2坐标轮换法例3-1求min， 初始点为 解：从出发，沿方向搜索，得点： 由得*可编辑可编辑3.2坐标轮换法 得： 从出发，沿方向搜索，求得 由得*可编辑可编辑3.2坐标轮换法 将，进行第二轮迭代，按此法迭代下去，经7步（14次）迭代，可得到点，目标函数值为0.002，此问题的最优解应为，*可编辑可编辑3.2坐标轮换法3．迭代步骤 ①取初始点，判别收敛精度，维数n。 ②求单变量极值问题的最优解，以求出。min ③判别是否满足，若，则转④；若i＜n，则令，转到②。 ④检验是否满足精度要求若满足判别准则，则迭代停止，即所求；否则转②。*可编辑可编辑3.2坐标轮换法4．坐标轮换法讨论 坐标轮换法具有程序简单，易于掌握的优点，但它的计算效率较低，因此它虽然步步在登高，但相当于沿两个垂直方向在爬山，路途迂回曲折，收敛很慢，因此它适用于维数较低（一般＜10）的目标函数求优。 另外对于如图3-2所示的有“脊线”的目标函数等值线的情形，如果迭代点出现在脊线上点时，沿两个坐标轴方向均不能使函数值下降，而只有在一定范围内的方向才能使函数值下降，这就出现了病态而导致迭代失效。*可编辑可编辑3.2坐标轮换法3.2.2算法的MATLAB实现 在MATLAB中编程实现的坐标轮换法函数为：minZB。 功用：用坐标轮换法求解函数的极值。 调用格式：[x,minf]=minZB(f,x0,delta,gama,sita,var,eps)其中，f:目标函数; x0:初始点； delta:初始步长； gama:加速系数； sita:收缩系数； var：自变量向量； eps:精度；*可编辑可编辑3.2坐标轮换法 3.2.3算法举例例3-2用坐标轮换法求下列函数的极小值。*可编辑可编辑3.3鲍威尔法3.3.1鲍威尔法的基本原理 鲍威尔法是直接利用函数值来构造共轭方向的一种共轭方向法。其基本思想是在不用导数的前提下，在迭代中逐次构造共轭方向。鲍威尔的基本算法是：在每一轮迭代中总有一个始点（第一轮的始点是任选的初始点）和个线性独立的搜索方向。 从始点出发顺次沿个方向作一维搜索得一终点，由始点和终点决定了一个新的搜索方向。用这个方向替换原来个方向中的一个，于是形成新的搜索方向组。替换的原则是去掉原方向组的第一个方向而将新方向排在原方向的最后。 此外规定，从这一轮的搜索终点出发沿新的搜索方向作一维搜索而得到的极小点，作为下一轮迭代的始点。这样就形成算法的循环。因为这种方法在迭代中逐次生成共轭方向，而共轭方向是较好的搜索方向，所以鲍威尔法又称作方向加速法。*可编辑可编辑3.3鲍威尔法 鲍威尔法的寻优过程如图所示。*可编辑可编辑3.3鲍威尔法例3-3用Powell法求解。 解：由 得 由*可编辑可编辑3.3鲍威尔法 得 得*可编辑可编辑3.3鲍威尔法 第一轮迭代结束。以作为新的起始点，作为新的起始方向进行下一轮迭代。 由 得 由得*可编辑可编辑3.3鲍威尔法 由 得 本例中*可编辑可编辑3.3鲍威尔法 把二维情况的基本算法扩展到维，则鲍威尔基本算法的要点是：在每一轮迭代中总有一个始点（第一轮的始点是任选的初始点）和个线性独立的搜索方向。从始点出发顺次沿个方向作一维搜索得一终点，由始点和终点决定了一个新的搜索方向。用这个方向替换原来个方向中的一个，于是形成新的搜索方向组。替换的原则是去掉原方向组的第一个方向而将新方向排在原方向的最后。 在鲍威尔基本算法中，每一轮迭代都用连结始点和终点所产生出得搜索方向去替换原向量组中得第一个向量，而不管它的“好坏”，这是产生向量组线性相关的原因所在。因此在改进的算法中首先判断原向量组是否需要替换。如果需要替换，还要进一步判断原向量组中哪个向量最坏，然后再用新产生的向量替换这个最坏的向量，以保证逐次生成共轭方向。*可编辑可编辑*可编辑可编辑*可编辑可编辑3.3鲍威尔法3.3.2算法的MATLAB实现 在MATLAB中编程实现的Powell法函数为：minPowell。 功用：用Powell法求解函数的极值。 调用格式：[x,minf]=minPowell(f,x0,P,var,eps) 其中，f:目标函数; x0:初始点； P:线性无关的初始向量组； var：自变量向量； eps:精度； x:目标函数最小值时的自变量值； minf：目标函数的最小值。*可编辑可编辑3.3鲍威尔法3.3.3算法举例 例3-5用坐标轮换法求下列函数的极小值。*可编辑可编辑3.4最速下降法3.4.1最速下降法的算法原理 如前所述，函数的梯度方向是函数上升最快的方向，也就是说，函数的负梯度方向是函数下降最快的方向。因此，将搜索方向取该点的负梯度方向（最速下降方向），就能使函数值在该点附近的范围内下降最快。按此规律不断走步，就形成了最速下降法迭代公式：*可编辑可编辑3.4最速下降法3.4.1最速下降法的算法原理 由于最速下降法是以负梯度方向作为搜索方向，所以最速下降法又称梯度法。为了使目标函数值沿搜索方向能获得最大的下降值，其步长因子应取一维搜索的最佳步长。 在最速下降法中，相邻两个迭代点上的函数梯度相互垂直。而搜索方向就是负梯度方向，因此相邻两个搜索方向互相垂直。这就是说在最速下降法中，迭代点向函数极小点靠近的过程，走的是曲折的路线。这一次的搜索方向与前一次的搜索方向互相垂直，形成“之”字形的锯齿现象。从直观上可以看到，在远离极小点的位置，每次迭代可使函数值有较多的下降。*可编辑可编辑3.4最速下降法最速下降法的搜索过程*可编辑可编辑3.4最速下降法例3-6用最速下降法求目标函数的极小点。 解：取初始点 则初始点处函数值及梯度分别为*可编辑可编辑3.4最速下降法 沿负梯度方向进行一维搜索，有 为一维搜索最佳步长 第一次迭代设计点位置和函数值*可编辑可编辑3.4最速下降法 从而完成了最速下降法的第一次迭代。继续作下去，经10次迭代后，得到最优解*可编辑可编辑3.4最速下降法3.4.2算法的MATLAB实现 在MATLAB中编程实现的最速下降法函数为：minZSXJ。 功用：用最速下降法法求解函数的极值。 调用格式：[x,minf]=minZSXJ(f,x0,var,eps) 其中，f:目标函数; x0:初始点； var：自变量向量； eps:精度； x:目标函数最小值时的自变量值； minf：目标函数的最小值。*可编辑可编辑3.4最速下降法3.4.3算法举例 例3-7用最速下降法求下列函数的极小值。*可编辑可编辑3.5牛顿型方法3.5.1牛顿法的算法原理 牛顿方法和最速下降法一样，也是求解极值问题古老的算法之一。 在第2章中我们已讨论过一维搜索的牛顿方法。对于一元函数，假定已给出极小点的一个较好的近似点，则在处将函数进行泰勒展开到二次项，得二次函数。按极值条件得的极小点，用它作为的第一个近似点。然后再在处进行泰勒展开，并求得第二个近似点。如此迭代下去，得到一维情况下的牛顿迭代公式*可编辑可编辑3.5牛顿型方法3.5.1牛顿法的算法原理 对于多元函数 多元函数求极值的牛顿法迭代公式*可编辑可编辑3.5牛顿型方法例3-8用牛顿法求的极小值。 解：取初始点，则初始点处的函数梯度、海赛矩阵及其逆阵分别是*可编辑可编辑3.5牛顿型方法 代入牛顿法迭代公式，得 从而经过一次迭代即求得极小点及函数极小值。*可编辑可编辑3.5牛顿型方法 3.5.1牛顿法的算法原理 对于多元函数 多元函数求极值的牛顿法迭代公式*可编辑可编辑3.5牛顿型方法3.5.2算法的MATLAB实现 在MATLAB中编程实现的修正牛顿法函数为：minXNT。 功用：用最速下降法法求解函数的极值。 调用格式：[x,minf]=minXNT(f,x0,var,eps) 其中，f:目标函数; x0:初始点； var：自变量向量； eps:精度； x:目标函数最小值时的自变量值； minf：目标函数的最小值。*可编辑可编辑3.5牛顿型方法3.5.3算法举例 例3-8用修正牛顿法求函数的极小值。*可编辑可编辑3.6共轭梯度法 3.6.1共轭梯度法的算法原理 共轭梯度法是共轭方向法中的一种，因为在该方法中每一个共轭向量都是依赖于迭代点处的负梯度而构造出来的，所以称作共轭梯度法。*可编辑可编辑3.6共轭梯度法 3.6.1共轭梯度法的算法原理 为了利用梯度求共轭方向，我们首先来研究共轭方向与梯度之间的关系。 考虑二次函数 从点出发，沿G的某一共轭方向作一维搜索，到达点，即*可编辑可编辑3.6共轭梯度法 有： 而在点处的梯度、分别为*可编辑可编辑3.6共轭梯度法 若和对G是共轭的，则有 即得 这就是共轭方向与梯度之间的关系。此式 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 明沿方向进行一维搜索，其终点与始点的梯度之差与的共轭方向正交。共轭梯度法就是利用这个性质做到不必计算矩阵就能求得共轭方向的。*可编辑可编辑3.6共轭梯度法 共轭梯度法的几何说明*可编辑可编辑 共轭梯度法的计算过程如下： 1）设初始点，第一个搜索方向取点的负梯度。即 沿进行一维搜索，，并算出点处的梯度。是以为切线和某等值曲线的切点。根据梯度和该点等值面的切面相垂直的性质，因此和正交，从而和正交，即和组成平面正交系。*可编辑可编辑3.6共轭梯度法 2）在、所构成的平面正交系中求的共轭方向，作为下一步的搜索方向。*可编辑可编辑3.6共轭梯度法 沿方向进行一维搜索，得，并算出该点梯度，有 即 根据共轭方向与梯度的关系式可知：构成一个正交系。*可编辑可编辑3.6共轭梯度法 3）在所构成的正交系中，求与及均共轭的方向。 根据共轭方向与梯度的关系，可求出：*可编辑可编辑3.6共轭梯度法 如此继续下去可求得共轭方向的递推公式为 沿着这些共轭方向一直搜索下去，直到最后迭代点处梯度的模小于给定允许值为止。若目标函数为非二次函数，经次搜索还未达到最优点时，则以最后得到的点作为初始点，重新计算共轭方向，一直到满足精度要求为止。*可编辑可编辑3.6共轭梯度法例3-9用共轭梯度法求二次函数 的极小点及极小值。 解：取初始点 则 取*可编辑可编辑3.6共轭梯度法 沿方向进行一维搜索，得 其中的为最佳步长 求得：*可编辑可编辑3.6共轭梯度法 为建立第二个共轭方向，需计算点处的梯度及系数值，得 从而求得第二个共轭方向*可编辑可编辑3.6共轭梯度法 再沿进行一维搜索，得 其中的为最佳步长， 求得 则*可编辑可编辑3.6共轭梯度法 计算点处的梯度 说明点满足极值必要条件，再根据点的海赛矩阵 是正定的，可知满足极值充分必要条件。故为极小点，即 而函数极小值为*可编辑可编辑3.6共轭梯度法3.6.2算法的MATLAB实现 在MATLAB中编程实现的共轭梯度法函数为：minGETD。 功用：用共轭梯度法求解函数的极值。 调用格式：[x,minf]=minGETD(f,x0,var,eps) 其中，f:目标函数; x0:初始点； var：自变量向量； eps:精度； x:目标函数最小值时的自变量值； minf：目标函数的最小值。*可编辑可编辑3.6共轭梯度法3.6.3算法举例 例3-10用共轭梯度法求函数的最小值*可编辑可编辑3.7变尺度法3.7.1变尺度法的算法原理 1．变尺度法的基本概念 对于一般二次函数 如果进行尺度变换 则在新的坐标系中，函数的二次项变为 选择这样变换的目的，是为了减低二次项的偏心程度。若矩阵是正定的，则总存在矩阵使 （单位矩阵）*可编辑可编辑3.7变尺度法3.7.1变尺度法的算法原理 1．变尺度法的基本概念 所以 这说明二次函数矩阵的逆阵，可以通过尺度变换矩阵来求得。这样，牛顿法迭代过程中得牛顿方向便可写成 牛顿迭代公式变为 *可编辑可编辑3.7变尺度法 比较牛顿法迭代公式和梯度法迭代公式 可以看出，差别在于牛顿法中多了部分。实际上是在空间内测量距离大小的一种度量，称作尺度矩阵*可编辑可编辑3.7变尺度法 既然牛顿法迭代公式可用尺度变换矩阵表示出来，即 它和梯度法迭代公式只差一个尺度矩阵，那么牛顿法就可看成是经过尺度变换后的梯度法。经过尺度变换，使函数偏心率减小到零，函数的等值面变为球面（或超球面），使设计空间中任意点处函数的梯度都通过极小点，用最速下降法只需一次迭代就可达到极小点。*可编辑可编辑3.7变尺度法 为了避免在迭代公式中计算海赛矩阵的逆阵，可用在迭代中逐步建立的变尺度矩阵 来替换，即构造一个矩阵序列来逼近海赛逆矩阵序列。每迭代一次，尺度就改变一次，这正是“变尺度”的含义。这样，上式变为 其中作一维搜索而得到的最佳步长。*可编辑可编辑3.7变尺度法 这个迭代公式代表面很广，例如当（单位矩阵）时，它就变成最速下降法。以上就是变尺度法的基本思想。 为了使变尺度矩阵确实与近似，并具有容易计算的特点，必须对附加某些条件。1）为保证迭代公式具有下降性质，要求中得每一个矩阵都是对称正定的。2）要求之间的迭代具有简单的形式。*可编辑可编辑3.7变尺度法 为最简单的形式，其中为校正矩阵。上式称作校正公式。 3）要求必须满足拟牛顿条件。*可编辑可编辑3.7变尺度法*可编辑可编辑3.7变尺度法 对于校正矩阵，可由具体的公式来计算，不同的公式对应不同的变尺度法，在下面进行讨论。但不论哪种变尺度法，必须满足拟牛顿条件，即： 或 满足上式的有无穷多个，因此上述变尺度法（属于拟牛顿法）构成一族算法。*可编辑可编辑3.7变尺度法 3．DEP算法和BFGS算法DEP算法中的尺度矩阵取下列形式：*可编辑可编辑3.7变尺度法 DEP算法由舍入误差和一维搜索不精确，有可能导致奇异，而使数值稳定性方面不够理想。BFGS算法的校正公式为*可编辑可编辑3.7变尺度法例3-11用DEP算法求下列函数的极值解。 解：1）取初始点， 计算初始点处的梯度*可编辑可编辑3.7变尺度法 并取初始变尺度矩阵为单位矩阵，则第一次搜寻方向为 沿方向进行一维搜索*可编辑可编辑3.7变尺度法 其中为一维搜索最佳步长 得 2）再按DEP法构造点处的搜寻方向，需计算*可编辑可编辑3.7变尺度法 代入校正公式*可编辑可编辑3.7变尺度法 则第二次搜寻方向为 再沿方向进行一维搜索，得*可编辑可编辑3.7变尺度法 其中为一维搜索最佳步长，应满足 得： 3）为了判断点是否为极值点，需计算点处的梯度及海赛矩阵*可编辑可编辑3.7变尺度法 梯度为零向量，海赛矩阵正定。可见点满足极值充要条件，因此为极小点。此函数的极值解为*可编辑可编辑3.7变尺度法3.7.2算法的MATLAB实现 在MATLAB中编程实现的变尺度法函数为：minDFP。 功用：用变尺度法求解函数的极值。 调用格式：[x,minf]=minDFP(f,x0,var,eps) 其中，f:目标函数; x0:初始点； var：自变量向量； eps:精度； x:目标函数最小值时的自变量值； minf：目标函数的最小值。*可编辑可编辑3.8无约束优化方法的选用3.8.1算法的评价准则 1.可靠性 所谓可靠性是指算法在合理精度要求下，在一定的计算时间和一定的迭代次数内，求解最优化问题的计算成功率，能解出的问题越多，则算法的可靠性越好。所以有的文献也称它为通用性。 往往一种算法在一定计算时间，一定迭代次数，一定精度范围内不能求出最优解，而延长计算时间，增加迭代次数或降低精度要求则可能收敛，因此，可以根据情况，规定当产生下列情况之一时为计算失败，这些情况是： ①在一定计算时间内不能求出最优解； ②在给定最大迭代次数内不能求出最优解； ③解的精度达不到要求； ④在非最优点停机。*可编辑可编辑3.8无约束优化方法的选用3.8.1算法的评价准则 2.有效性 有效性指某种算法解题的效率。常有衡量标准：其一是在同一题目、同一精度要求和同一初始点的情况下所用计算机的机时数；其二是在同样条件下的函数求值次数，包括目标函数的求值和导数求值的总次数。 3.准备工作的难易程度 这条是考虑使用者准备工作的难易程度，如求函数的导数和编写计算程序的难易程度等。显然准备工作越简易越好。至于一个低效而易于准备的程序同一个高效却难于准备的程序，究竟哪一个好，这要在人力和拥有计算机存储量之间权衡才能确定。*可编辑可编辑3.8无约束优化方法的选用3.8.1算法的评价准则 4.收敛性 每种算法必须具有收敛性，否则，该算法在理论上就不能成立，当然也就根本不能用于解题。 比较不同算法时，常用的一种收敛性判据是它们有效地进行二次函数优化的能力。因为在最优点附近，可用二次型很好地近似取代一般函数，不能很好地完成二次函数最优化算法，当搜索接近于最优点时，也不太可能很好地完成求一般非线性函数极值点的搜索。*可编辑可编辑3.8无约束优化方法的选用3.8.2无约束优化方法的特点及应用范围 通常认为牛顿法在收敛条件下，其迭代次数少于变尺度法，变尺度法的迭代次数又少于共轨梯度法，而共轨梯度法的迭代次数又少于共轨方向法及Powell法，而后者的迭代次数又少于单纯变形或最速下降法、坐标轮换法。但是从计算程序的复杂程度来看，恰好与这一次序相反，因此，实际应用中，应选用哪种方法。如何将几种方法结合起来，扬长避短是很重要的。*可编辑可编辑3.8无约束优化方法的选用 坐标轮换法 不需求导数，程序编制简单，存储量少，但计算效率低，可靠性也差，当目标函数的等值线具有脊线性态时，可能失败。适用于n<10的小型优化问题，当函数等值线为圆或长短轴都平行于坐标轴的椭圆时此法很有效。*可编辑可编辑3.8无约束优化方法的选用 Powell法 具有二次收敛性，收敛速度较快，可靠性也较好，具有直接法的共同优点，一般认为存储量少，程序编制相对复杂一些。适用于中小型优化问题，对于多维问题收敛速度较慢。*可编辑可编辑3.8无约束优化方法的选用 最速下降法 属间接法，要计算一阶导数，方法简单，可靠性较好，能稳定地使函数值下降。对初始点要求不高，存储量少，缺点是初始几步收敛快，后面收敛缓慢，愈靠近极值点愈慢。适用于精度要求不高或用于复杂函数寻找一个好的初始点。*可编辑可编辑3.8无约束优化方法的选用 牛顿法 当初始点选得合适时是目前收敛速度最快的算法。但当初始点选得不当时，会影响收敛导致失败。需计算一、二阶偏导数及Hessain矩阵的逆阵，准备工作量大，程序复杂，存储量多，故当函数变量较多和因次较高时不宜采用此法。*可编辑可编辑3.8无约束优化方法的选用 修正牛顿法 即使初始点选择不当，此法亦会成功，其他特点与牛顿法相同。 共轭梯度法 是共轭方向法之一，属间接法。需计算函数一阶偏导数，程序编制容易。准备工作量比牛顿法小，收敛速度较快。计算机存储量比牛顿法和DFP法少得多，但有效性不如DFP法，适用于维数较高且易于求一阶偏导数的目标函数。*可编辑可编辑3.8无约束优化方法的选用 变尺度法 是共轭方向法之一，属间接法。具有二次收敛性，收敛速度快，对初始点要求不高，因此目前认为它是最有效的无约束优化方法之一，适用于维数较高的问题，甚至可用到n>100的优化问题。*可编辑