第四章无约束优化方法.pptx

《第四章无约束优化方法.pptx》由会员分享，可在线阅读，更多相关《第四章无约束优化方法.pptx（52页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第1页/共52页第二节最速下降法优化设计追求目标函数值最小，若搜索方向取该点的负梯度方向，使函数值在该点附近的范围内下降最快。按此规律不断走步，形成以下迭代算法：以负梯度方向为搜索方向，所以称最速下降法或梯度法。搜索方向确定为负梯度方向，还需确定步长因子即求一维搜索的最佳步长，既有第2页/共52页由此可知，在最速下降法中，相邻两个迭代点上的函数梯度相互垂直。而搜索方向就是负梯度方向，因此相邻两个搜索方向互相垂直。第3页/共52页第4页/共52页例4-1求目标函数的极小点。第5页/共52页第6页/共52页第三节牛顿型方法在第三章中，我们已经讨论了一维搜索的牛顿方法。得出一维情况下的牛顿迭代公式对

2、于多元函数，在泰勒展开，得设为函数的极小点，根据极值的必要条件第7页/共52页这是多元函数求极值的牛顿法迭代公式。例4-2用牛顿法求的极小值。对牛顿法进行改进，提出“阻尼牛顿法”第8页/共52页第9页/共52页第四节共轭方向及共轭方向法为了克服最速下降法的锯齿现象，提高收敛速度，发展了一类共轭方向法。搜索方向是共轭方向。一、共轭方向的概念共轭方向的概念是在研究二次函数时引出的。首先考虑二维情况第10页/共52页如果按最速下降法，选择负梯度方向为搜索方向，会产生锯齿现象。为避免锯齿的发生，取下一次的迭代搜索方向直接指向极小点，如果选定这样的搜索方向，对于二元二次函数只需进行两次直线搜索就可以求到

3、极小点。第11页/共52页应满足什么条件？对于二次函数在处取得极小点的必要条件等式两边同乘得是对G的共轭方向。第12页/共52页三、共轭方向法1、选定初始点，下降方向和收敛精度，k=0。2、沿方向进行一维搜索，得3、判断是否满足，若满足则打印否则转4。4、提供新的共轭方向，使5、置，转2。第13页/共52页第14页/共52页第五节共轭梯度法共轭梯度法是共轭方向法的一种，共轭向量有迭代点的负梯度构造出来，所以称共轭梯度法。从点出发，沿G某一共轭方向作一维搜索,到达而在点、处的梯度分别为：第15页/共52页得出共轭方向与梯度之间的关系。此式表明沿方向进行一维搜索，其终点与始点的梯度值差与的共轭方向

4、正交。第16页/共52页图4-9共轭梯度法的几何说明第17页/共52页第18页/共52页第19页/共52页第20页/共52页第21页/共52页第22页/共52页第六节变尺度法变尺度法的基本思想：前面讨论的梯度法和牛顿法，它们的迭代公式可以看作下列公式的特例。变尺度法是对牛顿法的修正，它不是计算二阶导数的矩阵和它的逆矩阵，而是设法构造一个对称正定矩阵H来代替Hesse矩阵的逆矩阵。并在迭代过程中，使其逐渐逼近H-1。由于对称矩阵H在迭代过程中是不断修正改变的，它对于一般尺度的梯度起到改变尺度的作用，因此H又称变尺度矩阵。第23页/共52页一、尺度矩阵的概念变量的尺度变换是放大或缩小各个坐标。通过

5、尺度变换可以把函数的偏心程度降低到最低限度。对于一般二次函数如果进行尺度变换第24页/共52页则在新的坐标系中，函数的二次项变为选择这样变换的目的：降低二次项的偏心程度。若矩阵G是正定的，则总存在矩阵Q使使得函数偏心度变为零。用Q-1右乘等式两边，得再用Q左乘等式两边，得所以第25页/共52页说明二次函数矩阵G的逆矩阵，可以通过尺度变换矩阵Q求得。这样，牛顿法迭代过程中的牛顿方向可写成：三、变尺度法的一般步骤第26页/共52页第27页/共52页第七节坐标轮换法坐标轮换法是每次搜索只允许一个变量变化，其余变量保持不变，即沿坐标方向轮流进行搜索的寻优方法。它把多变量的优化问题轮流地转化成单变量的优

6、化问题。因此又称变量轮换法。其基本原理是将一个多维的无约束最优化问题转化为一系列较低维的最优化问题来求解，简单地说，就是先将(n-1)个变量固定不动，只对第一个变量进行一维搜索得到最优点x1（1）。然后，又保持(n-1)个变量不变，再对第二个变量进行一维搜索到x2（1）等等。第28页/共52页第29页/共52页图412 坐标轮换法原理图（动画演示）第30页/共52页2.搜索方向与步长的确定（1）搜索方向的确定对于第k轮第i次的计算第k轮第I次的迭代方向，它轮流取n维坐标的单位向量。第31页/共52页3.搜索步长的确定关于 值通常有以下几种取法（1）加速步长法（2）最优步长法 最优步长法就是利用

7、一维最优搜索方法来完成每一次迭代，即此时可以采用0.618方法或二次插值方法来计算 的值。第32页/共52页图413加速步长法的搜索路线第33页/共52页图414 最优步长法的搜索路线第34页/共52页4.坐标轮换法存在的问题图415 坐标轮换法在各种不同情况下的效能（a）搜索有效；（b）搜索低效；（c）搜索无效第35页/共52页第八节 Powell法（方向加速法）Powell法是利用共轭方向可以加速收敛的性质所形成的一种搜索算法。一、共轭方向的生成第36页/共52页第37页/共52页二、基本算法第38页/共52页三、改进的算法在鲍维尔基本算法中，每一轮迭代都用连结始点和终点所产生出的搜索方向

8、去替换原来向量组中的第一个向量，而不管它的“好坏”。改进的算法是：首先判断原向量组是否需要替换。如需要替换，在产生新的向量。改进算法的具体步骤：第39页/共52页第40页/共52页第41页/共52页第42页/共52页第九节 单形替换法一、基本思想 单纯形替换法也是一种不使用导数的求解无约束极小化问题的直接搜索方法，与前面几种方法不同的是，单纯形替换法不是利用搜索方向从一个点迭代到另一个更优的点，而是从一个单纯形迭代到另一个更优的单纯形。第43页/共52页定义：单纯形 n维空间中的恰好有n+1个顶点（极点）的有界的凸多面体称之为一个单纯形。根据定义，可知，一维空间中的单纯形是线段，二维空间中的单

9、纯形是三角形，而三维空间中的单纯形则是四面体。在单纯形替换算法中，从一个单纯形到另一个单纯形的迭代主要通过反射、扩张、收缩和缩边这4个操作来实现。下面以二维问题为例来对4种操作进行说明（参见下图）。第44页/共52页（1 1）反射设除了最劣点X X1 1以外的基余顶点的中心为X X4 4，作X X1 1关于点X X4 4的对称点X X5 5，称X X5 5为X X1 1的反射点。求反射点的过程称之为反射。（2 2）扩张在得到反射点X X5 5之后，如果X X5 5优于原单纯形的最劣点（即有 ），表明反射方向（X X5 5XX1 1）是有利方向，反射成功。若进一步有 ，可沿反射方向前进适当的距离

10、到点X X6 6。X X6 6称之为扩张点，求扩张点的过程称之为扩张。扩张之后，若扩张点X X6 6优于反射点X X5 5，则扩张成功，以X X6 6取代X X1 1，得新单纯形XX6 6,X,X2 2,X,X3 3；否则，扩张失败，舍弃扩张点，以反射X X5 5点取代X X1 1，得新单纯形XX5 5,X,X2 2,X,X3 3。设当前的单纯形的顶点为X X1 1，X X2 2，X X3 3，且有第45页/共52页如果出现 。表示反射完全失败，应退回到介于X X4 4与X X1 1之间的某个点X X8 8。（3 3）收缩在得到反射点X X5 5之后，如果有表示反射部分成功，方向（X X5 5

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