无约束优化方法讲稿.ppt

机械优化设计关于无约束优化方法第一页，讲稿共四十二页哦4.1 概述，数值解法：数值解法：是利用是利用已有已有的信息，通过计算点一步一步的信息，通过计算点一步一步地直接移动，地直接移动，逐步逼近逐步逼近最后达到最优点。最后达到最优点。1 1）选择迭代方向即探索方向；）选择迭代方向即探索方向；2 2）在确定的方向上选择适当步长迈步进行）在确定的方向上选择适当步长迈步进行探索探索 第二页，讲稿共四十二页哦，无约束优化方法可以分成两类：无约束优化方法可以分成两类：无约束优化方法可以分成两类：无约束优化方法可以分成两类：一类是利用目标函数的一类是利用目标函数的一阶或二阶导数一阶或二阶导数的无约束优化方的无约束优化方法（如最速下降法、共轭梯度法、牛顿法及变尺度法）；法（如最速下降法、共轭梯度法、牛顿法及变尺度法）；另一类另一类只利用目标函数只利用目标函数的无约束优化方法（如坐标轮换的无约束优化方法（如坐标轮换法、单形替换法及鲍威尔法等）。法、单形替换法及鲍威尔法等）。4.1 概述第三页，讲稿共四十二页哦，定义：定义：最速下降法就是采用使目标函数值下降得最最速下降法就是采用使目标函数值下降得最快的快的负梯度方向负梯度方向作为探索方向，来求目标函数的极作为探索方向，来求目标函数的极小值的方法，又称为小值的方法，又称为梯度法梯度法。最速下降最速下降法的迭代法的迭代公式公式4.2 梯度法（最速下降法最速下降法）第四页，讲稿共四十二页哦，最速下降法的迭代步骤：最速下降法的迭代步骤：4.2 梯度法（最速下降法最速下降法）第五页，讲稿共四十二页哦，4.2 梯度法（最速下降法最速下降法）第六页，讲稿共四十二页哦，梯度法的特点：梯度法的特点：1 1）对）对初始搜索点初始搜索点无严格要求；无严格要求；2 2）收敛）收敛速度不快速度不快；3 3）相邻两次相邻两次迭代搜索迭代搜索方向方向互相互相垂直垂直，在远离极值，在远离极值点处收敛快，在靠近极值点处收敛慢；点处收敛快，在靠近极值点处收敛慢；4 4）收敛速度与）收敛速度与目标函数值的性质目标函数值的性质有关，对等值线是有关，对等值线是同心圆同心圆的目标函数来说，经过的目标函数来说，经过一次迭代一次迭代就可以达到极就可以达到极值点。值点。4.2 梯度法（最速下降法最速下降法）第七页，讲稿共四十二页哦4.3牛顿型法，牛顿型法的基本思想：牛顿型法的基本思想：利用利用二次曲线二次曲线来逐点来逐点近似原目标函数近似原目标函数，以，以二次曲二次曲线的极小点线的极小点来来近似原目标函数的极小点近似原目标函数的极小点并逐渐逼近该点。并逐渐逼近该点。基本牛顿法的迭代公式：基本牛顿法的迭代公式：第八页，讲稿共四十二页哦，基本牛顿法的迭代公式：基本牛顿法的迭代公式：4.3牛顿型法第九页，讲稿共四十二页哦，基本牛顿法的迭代公式：基本牛顿法的迭代公式：阻尼牛顿法的迭代公式：阻尼牛顿法的迭代公式：4.3牛顿型法第十页，讲稿共四十二页哦，阻尼牛顿法的迭代步骤：阻尼牛顿法的迭代步骤：阻尼牛顿法的迭代步骤：阻尼牛顿法的迭代步骤：4.3牛顿型法第十一页，讲稿共四十二页哦，阻尼牛顿法的迭代公式：阻尼牛顿法的迭代公式：4.3牛顿型法第十二页，讲稿共四十二页哦 设法构造出一个设法构造出一个对称正定矩阵对称正定矩阵 来代替来代替 ，并在迭代过程中使并在迭代过程中使 逐渐逼近逐渐逼近 ,那么就简化那么就简化了牛顿法的计算，并且保持了牛顿法收敛快的优点。了牛顿法的计算，并且保持了牛顿法收敛快的优点。4.4变尺度法（拟牛顿法），变尺度法的基本思想：变尺度法的基本思想：牛顿方向：牛顿方向：牛顿方向：牛顿方向：变尺度法的变尺度法的迭代公式：迭代公式：尺度矩阵尺度矩阵第十三页，讲稿共四十二页哦，尺尺度度矩矩阵阵G G 正定正定牛顿迭代公式：牛顿迭代公式：目的：目标函数的偏心率减小到零。4.4变尺度法（拟牛顿法）第十四页，讲稿共四十二页哦，变尺度矩阵的建立：变尺度矩阵的建立：变尺度矩阵的建立：变尺度矩阵的建立：变尺度法的迭代公式：变尺度法的迭代公式：搜索方向：搜索方向：尺度矩阵应具备的条件：尺度矩阵应具备的条件：1 1）为正定对称矩阵；）为正定对称矩阵；2 2）具有简单的迭代形式）具有简单的迭代形式:3 3）满足拟牛顿条件：）满足拟牛顿条件：令令 则则4.4变尺度法（拟牛顿法）第十五页，讲稿共四十二页哦，变尺度法的一般步骤：变尺度法的一般步骤：变尺度法的一般步骤：变尺度法的一般步骤：4.4变尺度法（拟牛顿法）第十六页，讲稿共四十二页哦，变尺度法的流程图：变尺度法的流程图：变尺度法的流程图：变尺度法的流程图：4.4变尺度法第十七页，讲稿共四十二页哦，DFPDFP算法：算法：算法：算法：DFPDFP算法的校正公式算法的校正公式4.4变尺度法（拟牛顿法）第十八页，讲稿共四十二页哦，DFPDFPDFPDFP算法：算法：4.4变尺度法（拟牛顿法）第十九页，讲稿共四十二页哦4.5 共轭方向及共轭方向法，在下一次迭代时，选择搜索方在下一次迭代时，选择搜索方d d1 1指向极小点指向极小点x*x*，共轭方向共轭方向以以二元函数二元函数为例：为例：我们任意选择一个我们任意选择一个初始点初始点x x0 0点，点，沿着沿着某个下降方向某个下降方向d d0 0作一维搜索作一维搜索 第二十页，讲稿共四十二页哦，共轭方向共轭方向正交正交4.5 共轭方向及共轭方向法第二十一页，讲稿共四十二页哦，共轭方向的性质共轭方向的性质4.5 共轭方向及共轭方向法第二十二页，讲稿共四十二页哦，共轭方向法的步骤共轭方向法的步骤4.5 共轭方向及共轭方向法第二十三页，讲稿共四十二页哦，共轭方向的形成共轭方向的形成 格拉姆格拉姆格拉姆格拉姆-斯密特向量系共轭化的方法斯密特向量系共轭化的方法斯密特向量系共轭化的方法斯密特向量系共轭化的方法 n n个线性无关的向量系个线性无关的向量系vi vi（i=0,1i=0,1，n-1 n-1）一组独立向量一组独立向量d dr r（r=0,1r=0,1，n-1n-1）4.5 共轭方向及共轭方向法第二十四页，讲稿共四十二页哦，4.5 共轭方向及共轭方向法第二十五页，讲稿共四十二页哦，共轭梯度法：共轭梯度法：先沿先沿最速下降方向最速下降方向(负梯度方向负梯度方向)探索第一步，然后沿与该负探索第一步，然后沿与该负梯度方向相梯度方向相共轭的方向共轭的方向进行探索。进行探索。4.5 共轭梯度法第二十六页，讲稿共四十二页哦，共轭方向与梯度之间的关系：共轭方向与梯度之间的关系：共轭方向与梯度之间的关系：共轭方向与梯度之间的关系：它表示沿着方向它表示沿着方向d dk k做一维搜索，做一维搜索，它的终点它的终点x xk+1k+1与始点与始点x xk k的梯度之差的梯度之差与与d dk k的共轭方向的共轭方向d dj j正交。正交。4.5 共轭梯度法第二十七页，讲稿共四十二页哦，共轭梯度法递推公式：共轭梯度法递推公式：共轭梯度法递推公式：共轭梯度法递推公式：4.5 共轭梯度法第二十八页，讲稿共四十二页哦，共轭梯度法步骤：共轭梯度法步骤：共轭梯度法步骤：共轭梯度法步骤：4.5 共轭梯度法第二十九页，讲稿共四十二页哦，共轭梯度法步骤：共轭梯度法步骤：共轭梯度法步骤：共轭梯度法步骤：4.5 共轭梯度法第三十页，讲稿共四十二页哦，共轭梯度法共轭梯度法共轭梯度法共轭梯度法4.5 共轭梯度法第三十一页，讲稿共四十二页哦4.6 鲍威尔法，鲍威尔法的基本思想鲍威尔法的基本思想：直接利用迭代点的直接利用迭代点的目标函数值目标函数值来来构造共轭方向构造共轭方向，然，然后再从任一初始点出发，后再从任一初始点出发，逐次的共轭方向逐次的共轭方向作一维搜索求极作一维搜索求极值点。值点。第三十二页，讲稿共四十二页哦，共轭方向的生成：共轭方向的生成：结论：结论：从从不同的两不同的两点点出发，沿出发，沿同一方同一方向向进行两次一维搜进行两次一维搜索，所得索，所得两个极小两个极小点的连线方向点的连线方向便是便是原原方向共轭方向共轭的另一方的另一方向。向。第八节 鲍威尔法第三十三页，讲稿共四十二页哦，共轭方向的生成：共轭方向的生成：二维情况：二维情况：任意点出发沿着任意点出发沿着x1x1轴轴方向方向和和ABAB方向搜索，即可得方向搜索，即可得到极小点。到极小点。第八节 鲍威尔法第三十四页，讲稿共四十二页哦，基本基本POWELLPOWELL法（二维）：法（二维）：第八节 鲍威尔法第三十五页，讲稿共四十二页哦基本基本POWELLPOWELL法（法（n n维）：维）：1 1）从初）从初始点始点出发，首先沿着出发，首先沿着n n个坐标轴方向个坐标轴方向进行一维搜索，得到一个进行一维搜索，得到一个终点；终点；2 2）由初）由初始点和终点连线始点和终点连线形成一个形成一个新方向新方向，该方向排在原方向组的最，该方向排在原方向组的最后，去掉原方向组的的第一个方向，形成新的方向组；后，去掉原方向组的的第一个方向，形成新的方向组；3 3）从上一轮的搜索）从上一轮的搜索终点终点出发沿出发沿新的搜索方向新的搜索方向作一维搜索而得到的极小作一维搜索而得到的极小点，作为点，作为下一轮下一轮迭代的迭代的始点始点。4 4）从）从新的始点新的始点出发，沿着出发，沿着新的方向组新的方向组做一维搜索。做一维搜索。如此反复进行如此反复进行n n轮轮搜索后，可找到搜索后，可找到n n个共轭方向个共轭方向，若目标函数是，若目标函数是正定正定二次二次型函数，则经过型函数，则经过n n轮后就可以找到极小点。轮后就可以找到极小点。第八节 鲍威尔法第三十六页，讲稿共四十二页哦改进改进POWELLPOWELL法：法：获得新方向构成新方向组时获得新方向构成新方向组时,不是轮换地去掉原来的方不是轮换地去掉原来的方向向,而是而是经判别经判别后后,在在n+1n+1个方向中留下个方向中留下最接近共轭最接近共轭的的n n个个方向。方向。第八节 鲍威尔法第三十七页，讲稿共四十二页哦1）给定初始点 ，选取初始方向组，它由n个线性无关的向量组成 置k=02）从 出发顺次沿 作一维搜索得 接着以 为起点，沿方向 移动一个距离 得到 并分别求出 改进改进POWELLPOWELL算法的步骤算法的步骤:一轮迭代的始点一轮迭代的终点一轮迭代的反射点第三十八页，讲稿共四十二页哦同时计算各中间点函数值计算n个函数值之差并找出其中最大的一个（3）根据是否满足判别条件来确定是否对原方向组进行替换。因此有第三十九页，讲稿共四十二页哦，不满足判别条件，下轮迭代仍用原方向组，并以中函数值小者作为下一轮迭代的始点。满足判别条件，则下轮迭代的方向组为下一轮迭代的初始值为沿方向进行一维搜索的极小值点（4）判断是否满足收敛准则，满足 为极小值点，否则，应进行下一轮迭代。第四十页，讲稿共四十二页哦，第四十一页，讲稿共四十二页哦感谢大家观看第四十二页，讲稿共四十二页哦