《无约束优化方法ppt课件》由会员分享，可在线阅读，更多相关《无约束优化方法ppt课件（53页珍藏版）》请在金锄头文库上搜索。
1、第四章无约束优化方法第一节概述从第一章列举的机械设计问题，大多数实践问题是约束优化问题。约束优化问题的求解转化为一系列的无约束优化问题实现的。因此，无约束优化问题的解法是优化设计方法的根本组成部分，也是优化方法的根底。无约束优化问题的极值条件解析法数值法数学模型复杂时不便求解可以处置复杂函数及没有数学表达式的优化设计问题搜索方向问题是无约束优化方法的关键。各种无约束优化方法的区别：确定搜索方向的方法不同。无约束优化方法分类利用目的函数的一阶或二阶导数利用目的函数值最速下降法、共轭梯度法、牛顿法坐标轮换法、鲍威尔等第二节最速下降法优化设计追求目的函数值最小，假设搜索方向取该点的负梯度方向，使函数
2、值在该点附近的范围内下降最快。按此规律不断走步，构成以下迭代算法：以负梯度方向为搜索方向，所以称最速下降法或梯度法。搜索方向确定为负梯度方向，还需确定步长因子即求一维搜索的最正确步长，既有由此可知，在最速下降法中，相邻两个迭代点上的函数梯度相互垂直。而搜索方向就是负梯度方向，因此相邻两个搜索方向相互垂直。例4-1求目的函数的极小点。第三节牛顿型方法在第三章中，我们曾经讨论了一维搜索的牛顿方法。得出一维情况下的牛顿迭代公式对于多元函数，在泰勒展开，得设为函数的极小点，根据极值的必要条件这是多元函数求极值的牛顿法迭代公式。例4-2用牛顿法求的极小值。对牛顿法进展改良，提出“阻尼牛顿法第四节共轭方向
3、及共轭方向法为了抑制最速下降法的锯齿景象，提高收敛速度，开展了一类共轭方向法。搜索方向是共轭方向。一、共轭方向的概念共轭方向的概念是在研讨二次函数时引出的。首先思索二维情况假设按最速下降法，选择负梯度方向为搜索方向，会产生锯齿景象。为防止锯齿的发生，取下一次的迭代搜索方向直接指向极小点，假设选定这样的搜索方向，对于二元二次函数只需进展两次直线搜索就可以求到极小点。应满足什么条件？对于二次函数在处获得极小点的必要条件等式两边同乘得是对G的共轭方向。三、共轭方向法1、选定初始点，下降方向和收敛精度，k=0。2、沿方向进展一维搜索，得3、判别能否满足，假设满足那么打印否那么转4。4、提供新的共轭方向
4、，使5、置，转2。第五节共轭梯度法共轭梯度法是共轭方向法的一种，共轭向量有迭代点的负梯度构造出来，所以称共轭梯度法。从点出发，沿G某一共轭方向作一维搜索,到达而在点、处的梯度分别为：得出共轭方向与梯度之间的关系。此式阐明沿方向进展一维搜索，其终点与始点的梯度值差与的共轭方向正交。图4-9共轭梯度法的几何阐明第六节变尺度法变尺度法的根本思想：前面讨论的梯度法和牛顿法，它们的迭代公式可以看作以下公式的特例。变尺度法是对牛顿法的修正，它不是计算二阶导数的矩阵和它的逆矩阵，而是设法构造一个对称正定矩阵H来替代Hesse矩阵的逆矩阵。并在迭代过程中，使其逐渐逼近H-1。由于对称矩阵H在迭代过程中是不断修
5、正改动的，它对于一般尺度的梯度起到改动尺度的作用，因此H又称变尺度矩阵。一、尺度矩阵的概念变量的尺度变换是放大或减少各个坐标。经过尺度变换可以把函数的偏心程度降低到最低限制。对于普通二次函数假设进展尺度变换那么在新的坐标系中，函数的二次项变为选择这样变换的目的：降低二次项的偏心程度。假设矩阵G是正定的，那么总存在矩阵Q使使得函数偏心度变为零。用Q-1右乘等式两边，得再用Q左乘等式两边，得所以阐明二次函数矩阵G的逆矩阵，可以经过尺度变换矩阵Q求得。这样，牛顿法迭代过程中的牛顿方向可写成：三、变尺度法的普通步骤第七节坐标轮换法坐标轮换法是每次搜索只允许一个变量变化，其他变量坚持不变，即沿坐标方向轮
6、番进展搜索的寻优方法。它把多变量的优化问题轮番地转化成单变量的优化问题。因此又称变量轮换法。其根本原理是将一个多维的无约束最优化问题转化为一系列较低维的最优化问题来求解，简单地说，就是先将(n-1)个变量固定不动，只对第一个变量进展一维搜索得到最优点x11。然后，又坚持(n-1)个变量不变，再对第二个变量进展一维搜索到x21等等。图412 坐标轮换法原理图动画演示2. 搜索方向与步长确实定1搜索方向确实定对于第k轮第i次的计算第k轮第I次的迭代方向，它轮番取n维坐标的单位向量。3.搜索步长确实定关于 值通常有以下几种取法1加速步长法2最优步长法 最优步长法就是利用一维最优搜索方法来完成每一次迭
7、代，即此时可以采用0.618方法或二次插值方法来计算 的值。图413加速步长法的搜索道路图414 最优步长法的搜索道路4 . 坐标轮换法存在的问题图415 坐标轮换法在各种不同情况下的效能a搜索有效；b搜索低效；c搜索无效第八节 Powell法方向加速法 Powell法是利用共轭方向可以加速收敛的性质所构成的一种搜索算法。一、共轭方向的生成二、根本算法三、改良的算法在鲍维尔根本算法中，每一轮迭代都用连结始点和终点所产生出的搜索方向去交换原来向量组中的第一个向量，而不论它的“好坏。改良的算法是：首先判别原向量组能否需求交换。如需求交换，在产生新的向量。改良算法的详细步骤：第九节第九节 单形交换法
8、单形交换法一、根本思想一、根本思想 单纯形交形交换法也是一种不运用法也是一种不运用导数的求解无数的求解无约束极小化束极小化问题的直接搜索方法，与前面几种方的直接搜索方法，与前面几种方法不同的是，法不同的是，单纯形交形交换法不是利用搜索方向从法不是利用搜索方向从一个点迭代到另一个更一个点迭代到另一个更优的点，而是从一个的点，而是从一个单纯形迭代到另一个更形迭代到另一个更优的的单纯形。形。定定义：单纯形形 n维空空间中的恰好有中的恰好有n+1个个顶点极点的有界点极点的有界的凸多面体称之的凸多面体称之为一个一个单纯形。形。 根据定根据定义，可知，一，可知，一维空空间中的中的单纯形是形是线段，段，二二
9、维空空间中的中的单纯形是三角形，而三形是三角形，而三维空空间中的中的单纯形那么是四面体。形那么是四面体。 在在单纯形交形交换算法中，从一个算法中，从一个单纯形到另一个形到另一个单纯形的迭代主要形的迭代主要经过反射、反射、扩张、收、收缩和和缩边这4个个操作来操作来实现。下面以二。下面以二维问题为例来例来对4种操作种操作进展展阐明参明参见以下以下图。1 1反射反射设除了最劣点除了最劣点X1X1以外的基余以外的基余顶点的中心点的中心为X4X4，作作X1X1关于点关于点X4X4的的对称点称点X5X5，称，称X5X5为X1X1的反射点。求反射点的的反射点。求反射点的过程称之程称之为反射。反射。2 2扩张
10、在得到反射点在得到反射点X5X5之后，假之后，假设X5X5优于原于原单纯形的最劣形的最劣点即有点即有 ，阐明反射方向明反射方向X5X1X5X1是有利方是有利方向，反射向，反射胜利。假利。假设进一步有一步有 ，可沿反射方向前，可沿反射方向前进适当的适当的间隔到点隔到点X6X6。X6X6称之称之为扩张点，求点，求扩张点的点的过程称之程称之为扩张。扩张之后，假之后，假设扩张点点X6X6优于反射点于反射点X5X5，那么，那么扩张胜利，利，以以X6X6取代取代X1X1，得新，得新单纯形形X6,X2,X3X6,X2,X3；否那么，；否那么，扩张失失败，舍弃，舍弃扩张点，以反射点，以反射X5X5点取代点取代
11、X1X1，得新，得新单纯形形X5,X2,X3X5,X2,X3。设当前的当前的单纯形的形的顶点点为X1X1，X2X2，X3X3，且有，且有假设出现假设出现 。表示反射完全失败，应退回到介于。表示反射完全失败，应退回到介于X4X4与与X1X1之间的某个点之间的某个点X8X8。3 3收收缩在得到反射点在得到反射点X5X5之后，假之后，假设有有表示反射部分表示反射部分胜利，方向利，方向X5X1X5X1虽然是有利方向，但然是有利方向，但X5X5前前进过远，应收收缩到介于到介于X4X4与与X5X5之之间的某个点的某个点X7X7。 上述两种从反射点向上述两种从反射点向X1方向后退的方向后退的过程都称之程都称
12、之为收收缩。假假设收收缩点点优于原来的最劣点于原来的最劣点X1，称收，称收缩胜利，并以收利，并以收缩点取代原最劣点，构成新点取代原最劣点，构成新单纯形形X7,X2,X3或或X8,X2,X3；否那么，称之否那么，称之为收收缩失失败，舍弃收，舍弃收缩点。点。4缩边假假设收收缩失失败，那么，那么应紧缩当前当前单纯形的形的边长：令最令最优点点X3不不动，而其他，而其他顶点向点向X3方向方向紧缩，使，使边长缩短通短通常常缩短一半，以短一半，以产生新生新单纯形。如以下形。如以下图所示，点所示，点X1紧缩到到点点X9，点，点X2紧缩到点到点X10，得新，得新单纯形形X9,X10,X3，这一一过程称之程称之为缩边。二、单纯形交换算法二、单纯形交换算法设初始点为设初始点为X0X0，初始边长，初始边长h h，eiei为坐标轴方向的单位向量为坐标轴方向的单位向量 ，预定正数，预定正数1 1令令；2计算各算各顶点点Xi的函数的函数值；3比比较各各顶点点Xi的函数的函数值，挑出其中的最，挑出其中的最优点，点，记为XL；最劣；最劣 点，点，记XH；次差点，；次差点，记为XG；
