第4章无约束优化方法.ppt

机械优化设计,第四章无约束优化方法,4.1,概述,4.2,最速下降法,4.3,牛顿型方法,4.4,共轭方向及共轭方向法,4.5,共轭梯度法,4.6,变尺度法,4.7,坐标轮换法,4.8,鲍威尔方法,4.9,单型替换法,第四章无约束优化方法,第一节概述,，,数值解法：是利用已有的信息，通过计算点一步一步地直接移动，逐步逼近最后达到最优点。,1）选择迭代方向即探索方向；2）在确定的方向上选择适当步长迈步进行探索,第四章无约束优化方法,第一节概述,，,无约束优化方法可以分成两类：一类是利用目标函数的一阶或二阶导数的无约束优化方法（如最速下降法、共轭梯度法、牛顿法及变尺度法）；另一类只利用目标函数的无约束优化方法（如坐标轮换法、单形替换法及鲍威尔法等）。,第四章无约束优化方法,第二节最速下降法,，,定义：最速下降法就是采用使目标函数值下降得最快的负梯度方向作为探索方向，来求目标函数的极小值的方法，又称为梯度法。,最速下降法的迭代公式,第四章无约束优化方法,第二节最速下降法,，,最速下降法的迭代步骤：,第四章无约束优化方法,第二节最速下降法,，,第四章无约束优化方法,第二节最速下降法,，,最速下降法的特点：1）对初始搜索点无严格要求；2）收敛速度不快；3）相邻两次迭代搜索方向互相垂直，在远离极值点处收敛快，在靠近极值点处收敛慢；4）收敛速度与目标函数值的性质有关，对等值线是同心圆的目标函数来说，经过一次迭代就可以达到极值点。,第四章无约束优化方法,第三节牛顿型法,，,牛顿型法的基本思想：利用二次曲线来逐点近似原目标函数，以二次曲线的极小点来近似原目标函数的极小点并逐渐逼近该点。,基本牛顿法的迭代公式：,第四章无约束优化方法,第三节牛顿型法,，,基本牛顿法的迭代公式：,第四章无约束优化方法,第三节牛顿型法,，,基本牛顿法的迭代公式：,阻尼牛顿法的迭代公式：,第四章无约束优化方法,第三节牛顿型法,，,阻尼牛顿法的迭代步骤：,第四章无约束优化方法,第三节牛顿型法,，,阻尼牛顿法的迭代公式：,第四章无约束优化方法,第四节共轭方向及共轭方向法,，,在下一次迭代时，选择搜索方d1指向极小点x*，,共轭方向,以二元函数为例：我们任意选择一个初始点x0点，沿着某个下降方向d0作一维搜索,第四章无约束优化方法,第四节共轭方向及共轭方向法,，,共轭方向,正交,第四章无约束优化方法,第四节共轭方向及共轭方向法,，,共轭方向的性质,第四章无约束优化方法,第四节共轭方向及共轭方向法,，,共轭方向法的步骤,第四章无约束优化方法,第四节共轭方向及共轭方向法,，,共轭方向的形成格拉姆-斯密特向量系共轭化的方法,n个线性无关的向量系vi（i=0,1，n-1）,一组独立向量dr（r=0,1，n-1）,第四章无约束优化方法,第四节共轭方向及共轭方向法,，,第四章无约束优化方法,第五节共轭梯度法,，,共轭梯度法：先沿最速下降方向(负梯度方向)探索第一步，然后沿与该负梯度方向相共轭的方向进行探索。,第四章无约束优化方法,第五节共轭梯度法,，,共轭方向与梯度之间的关系：,它表示沿着方向dk做一维搜索，它的终点xk+1与始点xk的梯度之差与dk的共轭方向dj正交。,第四章无约束优化方法,第五节共轭梯度法,，,共轭梯度法递推公式：,第四章无约束优化方法,第五节共轭梯度法,，,共轭梯度法步骤：,第四章无约束优化方法,第五节共轭梯度法,，,共轭梯度法步骤：,第四章无约束优化方法,第五节共轭梯度法,，,共轭梯度法,设法构造出一个对称正定矩阵来代替，并在迭代过程中使逐渐逼近,那么就简化了牛顿法的计算，并且保持了牛顿法收敛快的优点。,第四章无约束优化方法,第六节变尺度法（拟牛顿法）,，,变尺度法的基本思想：,第四章无约束优化方法,第六节变尺度法（拟牛顿法）,，,尺度矩阵,G正定,目的：目标函数的偏心率减小到零。,第四章无约束优化方法,第六节变尺度法（拟牛顿法）,，,变尺度矩阵的建立：,变尺度法的迭代公式：,搜索方向：,尺度矩阵应具备的条件：,1）为正定对称矩阵；2）具有简单的迭代形式:3）满足拟牛顿条件：令则,第四章无约束优化方法,第六节变尺度法（拟牛顿法）,，,变尺度法的一般步骤：,第四章无约束优化方法,第六节变尺度法（拟牛顿法）,，,变尺度法的流程图：,第四章无约束优化方法,第六节变尺度法（拟牛顿法）,，,DFP算法：,DFP算法的校正公式,第四章无约束优化方法,第六节变尺度法（拟牛顿法）,，,DFP算法：,第四章无约束优化方法,第七节坐标轮换法,，,基本思想：每次仅对多元函数的一个变量沿其坐标轴进行一维探索，其余各变量均固定不动，并依次轮换进行一维探索的坐标轴，完成第一轮探索后再重新进行第二轮探索，直到找到目标函数在全域上的最小点为止。目的：将一个多维的无约束最优化问题，转化为一系列的一维问题来求解。,第四章无约束优化方法,第七节坐标轮换法,，,二维问题,第四章无约束优化方法,第七节坐标轮换法,，,第k轮迭代公式：,第四章无约束优化方法,第七节坐标轮换法,，,步长的几种取法：,随机选择方法加速步长法最优步长法（一维搜索方法，如：黄金分割法、二次插值法，来确定最优步长）,第四章无约束优化方法,第七节坐标轮换法,，,加速步长法：,第四章无约束优化方法,第七节坐标轮换法,，,坐标轮换法的流程图,第四章无约束优化方法,第七节坐标轮换法,，,坐标轮换法的特点：,计算简单、概念清楚、易于掌握；但搜索路线较长（需要经过多次曲折迂回的路径才能达到极值点），计算率较低，特别是当维数很高时很费时，所以坐标轮换法只能用于低维（n10）的优化问题求解。此外，坐标轮换法的效率在很大程度上取决于目标函数的性态，也就是等值线的形态与坐标轴的关系。,第四章无约束优化方法,第八节鲍威尔法,，,鲍威尔法的基本思想：直接利用迭代点的目标函数值来构造共轭方向，然后再从任一初始点出发，逐次的共轭方向作一维搜索求极值点。,第四章无约束优化方法,第八节鲍威尔法,，,共轭方向的生成：,结论：从不同的两点出发，沿同一方向进行两次一维搜索，所得两个极小点的连线方向便是原方向共轭的另一方向。,第四章无约束优化方法,第八节鲍威尔法,，,共轭方向的生成：,二维情况：任意点出发沿着x1轴方向和AB方向搜索，即可得到极小点。,第四章无约束优化方法,第八节鲍威尔法,，,基本POWELL法（二维）：,第四章无约束优化方法,第八节鲍威尔法,基本POWELL法（n维）：,1）从初始点出发，首先沿着n个坐标轴方向进行一维搜索，得到一个终点；2）由初始点和终点连线形成一个新方向，该方向排在原方向组的最后，去掉原方向组的的第一个方向，形成新的方向组；3）从上一轮的搜索终点出发沿新的搜索方向作一维搜索而得到的极小点，作为下一轮迭代的始点。4）从新的始点出发，沿着新的方向组做一维搜索。如此反复进行n轮搜索后，可找到n个共轭方向，若目标函数是正定二次型函数，则经过n轮后就可以找到极小点。,第四章无约束优化方法,第八节鲍威尔法,改进POWELL法：,获得新方向构成新方向组时,不是轮换地去掉原来的方向,而是经判别后,在n+1个方向中留下最接近共轭的n个方向。,1）给定初始点，选取初始方向组，它由n个线性无关的向量组成置k=02）从出发顺次沿作一维搜索得接着以为起点，沿方向移动一个距离得到并分别求出,改进POWELL算法的步骤:,一轮迭代的始点,一轮迭代的终点,一轮迭代的反射点,同时计算各中间点函数值,计算n个函数值之差,并找出其中最大的一个,（3）根据是否满足判别条件,来确