《无约束优化方法》PPT课件.ppt

《《无约束优化方法》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《无约束优化方法》PPT课件.ppt（53页珍藏版）》请在三一办公上搜索。

1、第四章无约束优化方法,第一节 概述,从第一章列举的机械设计问题，大多数实际问题是约束优化问题。,约束优化问题的求解转化为一系列的无约束优化问题实现的。,因此，无约束优化问题的解法是优化设计方法的基本组成部分，也是优化方法的基础。,无约束优化问题的极值条件,解析法,数值法,数学模型复杂时不便求解,可以处理复杂函数及没有数学表达式的优化设计问题,搜索方向问题是无约束优化方法的关键。,各种无约束优化方法的区别：确定搜索方向的方法不同。,无约束优化方法分类,利用目标函数的一阶或二阶导数,利用目标函数值,（最速下降法、共轭梯度法、牛顿法）,（坐标轮换法、鲍威尔等）,第二节 最速下降法,优化设计追求目标函

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)个变量固定不动，只对第一个变量进行一维搜索得到最优点x1（1）。然后，又保持(n-1)个变量不变，再对第二个变量进行一维搜索到x2（1）等等。,图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个顶点（极点）的有界的凸多面体称之为一个单纯形。根据定义，可知，一维空间中的单纯形是线段，二维空间中的单纯形是三角形，而三维空间中的单纯形则是四面体。在单纯形替换算法中，从一个单纯形到另一个单纯形的迭代主要通过反射、扩张、收缩和缩边这4个操作来实现。下面以二维问题为例来对4种操作进行说明（参

9、见下图）。,（1）反射设除了最劣点X1以外的基余顶点的中心为X4，作X1关于点X4的对称点X5，称X5为X1的反射点。求反射点的过程称之为反射。,（2）扩张在得到反射点X5之后，如果X5优于原单纯形的最劣点（即有），表明反射方向（X5X1）是有利方向，反射成功。若进一步有，可沿反射方向前进适当的距离到点X6。X6称之为扩张点，求扩张点的过程称之为扩张。扩张之后，若扩张点X6优于反射点X5，则扩张成功，以X6取代X1，得新单纯形X6,X2,X3；否则，扩张失败，舍弃扩张点，以反射X5点取代X1，得新单纯形X5,X2,X3。,设当前的单纯形的顶点为X1，X2，X3，且有,如果出现。表示反射完全失败

10、，应退回到介于X4与X1之间的某个点X8。,（3）收缩在得到反射点X5之后，如果有,表示反射部分成功，方向（X5X1）虽然是有利方向，但X5前进过远，应收缩到介于X4与X5之间的某个点X7。,上述两种从反射点向X1方向后退的过程都称之为收缩。如果收缩点优于原来的最劣点X1，称收缩成功，并以收缩点取代原最劣点，构成新单纯形X7,X2,X3或X8,X2,X3；否则，称之为收缩失败，舍弃收缩点。,（4）缩边若收缩失败，则应压缩当前单纯形的边长：令最优点X3不动，而其余顶点向X3方向压缩，使边长缩短（通常缩短一半），以产生新单纯形。如下图所示，点X1压缩到点X9，点X2压缩到点X10，得新单纯形X9,X10,X3，这一过程称之为缩边。,二、单纯形替换算法设初始点为X0，初始边长h，ei为坐标轴方向的单位向量，预定正数,（2）计算各顶点Xi的函数值；,（3）比较各顶点Xi的函数值，挑出其中的最优点，记为XL；最劣 点，记XH；次差点，记为XG；,