《《无约束优化方法》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《无约束优化方法》PPT课件.ppt（68页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第四章 无约束优化方法第一节 概述从第一章列举的机械设计问题，大多数实际问题是约束优化问题。约束优化问题的求解转化为一系列的无约束优化问题实现的。因此，无约束优化问题的解法是优化设计方法的基本组成部分，也是优化方法的基础。无约束优化问题的极值条件解析法(间接解法)数值法(直接解法)数学模型复杂时不便求解可以处理复杂函数及没有数学表达式的优化设计问题搜索方向问题是无约束优化方法的关键。各种无约束优化方法的区别：确定搜索方向的方法不同。无约束优化方法分类利用目标函数的一阶或二阶导数利用目标函数值（最速下降法、共轭梯度法、牛顿法）（坐标轮换法、鲍威尔法等）第二节 最速下降法优化设计追求目标函数值最小
2、，若搜索方向取该点的负梯度方向，使函数值在该点附近的范围内下降最快。按此规律不断走步，形成以下迭代算法：以负梯度方向为搜索方向，所以称最速下降法或梯度法。搜索方向确定为负梯度方向，还需确定步长因子即求一维搜索的最佳步长，既有由此可知，在最速下降法中，相邻两个迭代点上的函数梯度相互垂直。而搜索方向就是负梯度方向，因此相邻两个搜索方向互相垂直。例4-1 求目标函数的极小点。作业第四章 习题4-3设目标函数为 ，试用最速下降法求其最优解。第三节牛顿型方法在第三章中，我们已经讨论了一维搜索的牛顿方法。得出一维情况下的牛顿迭代公式第三节牛顿型方法对于多元函数，在泰勒展开，得设为函数的极小点，根据极值的必
3、要条件这就是多元函数求极值的牛顿法迭代公式。4.3.2 阻尼牛顿法牛顿法的缺陷是，在确定极值点的过程中，并不含有沿下降方向搜索的概念。因此对于非二次型函数，在迭代过程中，可能出现的现象。为此人们提出了所谓的阻尼牛顿法。作为一个搜索方向，则阻尼牛顿法采用下述迭代公式:是沿牛顿方向进行一维搜索的最佳步长,称为阻尼因子。其中令通过下式求得这样就能保证阻尼牛顿法程序框图阻尼牛顿法程序框图 以上介绍的最速下降法及牛顿法或者阻尼牛顿法，属于经典的数学方法。显然在这些方法中要用到某点函数的一阶梯度，二阶梯度等信息，同时对牛顿法还要用到逆矩阵的计算等。当变量维数较高时，计算工作量相当大，影响计算速度。理论上，
4、牛顿法的收敛速度高于最速下降法。从以上二种经典方法中，人们不断努力，发掘，提出了不同的改进方法。第四节共轭方向及共轭方向法为了克服最速下降法的锯齿现象，提高收敛速度，发展了一类共轭方向法。搜索方向是共轭方向。一、共轭方向的概念共轭方向的概念是在研究二次函数时引出的。首先考虑二维情况1 共轭方向定义定义1：设G为 阶实对称正定矩阵，而 为在n维欧氏空间中的两个非零向量，如果满足式：则称向量 关于实对称正定矩阵G 是共轭的，或简称 与 关于G 共轭如果按最速下降法，选择负梯度方向为搜索方向，会产生锯齿现象。为避免锯齿的发生，取下一次的迭代搜索方向直接指向极小点，如果选定这样的搜索方向，对于二元二次
5、函数只需进行两次直线搜索就可以求到极小点。应满足什么条件？对于二次函数 在 处取得极小点的必要条件等式两边同乘 得是对G的共轭方向。三、共轭方向法1、选定初始点 ，下降方向 和收敛精度，k=0。2、沿 方向进行一维搜索，得3、判断 是否满足，若满足则打印否则转4。4、提供新的共轭方向 ，使 5、置 ，转2。共共轭轭方方向向法法程程序序框框图图第五节 共轭梯度法共轭梯度法是共轭方向法的一种，共轭向量有迭代点的负梯度构造出来，所以称共轭梯度法。从点 出发，沿G某一共轭方向 作一维搜索,到达而在点 、处的梯度分别为：得出共轭方向与梯度之间的关系。此式表明沿方向进行一维搜索，其终点 与始点 的梯度值差
6、与 的共轭方向 正交。图4-9 共轭梯度法的几何说明第六节 坐标轮换法坐标轮换法是每次搜索只允许一个变量变化，其余变量保持不变，即沿坐标轴方向轮流进行搜索的寻优方法。它把多变量的优化问题轮流地转化成单变量的优化问题。因此又称变量轮换法。其基本原理是将一个多维的无约束最优化问题转化为一系列较低维的最优化问题来求解，简单地说，就是先将(n-1)个变量固定不动，只对第一个变量进行一维搜索得到最优点x1（1）。然后，又保持(n-1)个变量不变，再对第二个变量进行一维搜索到x2（1）等等。4.6.1 坐标轮换法的搜索过程及方向向量取法坐标轮换法的搜索过程及方向向量取法下面以二元函数为例 2.搜索方向与步
7、长的确定（1）搜索方向的确定对于第k轮第i次的计算第k轮第I次的迭代方向，它轮流取n维坐标的单位向量。3.搜索步长的确定关于 值通常有以下几种取法（1）加速步长法（2）最优步长法 最优步长法就是利用一维最优搜索方法来完成每一次迭代，即此时可以采用方法或二次插值方法来计算 的值。图4-9 坐标轮换法的程序框图4.坐标轮换法存在的问题图415 坐标轮换法在各种不同情况下的效能（a）搜索有效；（b）搜索低效；（c）搜索无效第七节 鲍威尔法Powell一、共轭方向的生成直接利用函数值来构造共轭方向的一种共轭方向法。基本思想：在不用求导数的前提下，在迭代中逐次构造Hessian 矩阵G的共轭方向。4.7
8、.2 鲍威尔法的基本算法二、基本算法三、改进的算法在鲍维尔基本算法中，每一轮迭代都用连结始点和终点所产生出的搜索方向去替换原来向量组中的第一个向量，而不管它的“好坏”。改进的算法是：首先判断原向量组是否需要替换。如需要替换，在产生新的向量。单纯形法:通过计算单纯形顶点的函数值并加以比较，找到一个较好的点组成新的单纯形。不断地向极小点靠近。属于直接寻优方法类，仅需要目标函数值信息。第八节 单纯形法单纯形法基本原理单纯形是指在n维空间中具有n+1个顶点的多面体。以二元函数为例 设，最好点，最差点，次坏点 点称作点的相对于点的反射点 以上说明，可以通过反射、扩张、收缩、缩边方式得到一个新的单纯型，其
9、中至少有一个顶点的函数值比原单纯形要小。单纯形法的计算步骤单纯形法的计算步骤以二元函数为例 以二元函数 为例第九节变尺度法变尺度法的基本思想：前面讨论的梯度法和牛顿法，它们的迭代公式可以看作下列公式的特例。变尺度法是对牛顿法的修正，它不是计算二阶导数的矩阵和它的逆矩阵，而是设法构造一个对称正定矩阵H来代替Hesse矩阵的逆矩阵。并在迭代过程中，使其逐渐逼近H-1。由于对称矩阵H在迭代过程中是不断修正改变的，它对于一般尺度的梯度起到改变尺度的作用，因此H又称变尺度矩阵。一、尺度矩阵的概念变量的尺度变换是放大或缩小各个坐标。通过尺度变换可以把函数的偏心程度降低到最低限度。对于一般二次函数如果进行尺
10、度变换则在新的坐标系中，函数的二次项变为选择这样变换的目的：降低二次项的偏心程度。若矩阵G是正定的，则总存在矩阵Q使使得函数偏心度变为零。用Q-1 右乘等式两边，得再用Q左乘等式两边，得所以说明二次函数矩阵G的逆矩阵，可以通过尺度变换矩阵Q求得。这样，牛顿法迭代过程中的牛顿方向可写成：三、变尺度法的一般步骤解析法(间接解法)数值法(直接解法)数学模型复杂时不便求解可以处理复杂函数及没有数学表达式的优化设计问题搜索方向问题是无约束优化方法的关键。各种无约束优化方法的区别：确定搜索方向的方法不同。无约束优化方法分类利用目标函数的一阶或二阶导数利用目标函数值（最速下降法、共轭梯度法、牛顿法）（坐标轮换法、鲍威尔法、单纯形法等）总结