《现代设计方法ppt课件第4节.ppt》由会员分享，可在线阅读，更多相关《现代设计方法ppt课件第4节.ppt（62页珍藏版）》请在三一办公上搜索。
1、1,本章主要内容 优化设计概述 优化问题的数学分析基础 一维探索优化方法 无约束多维问题的优化方法 约束问题的优化方法 Matlab在优化设计中的应用,2,3,第四节 常用的无约束优化方法,4.1 坐标轮换法 4.2 鲍威尔(Powell)法4.3 梯度法4.4 牛顿法4.5 DFP变尺度法无约束优化方法的评价准则及选用,4,任何一次迭代，都是求使得即其中：表示步长因子(k)表示最优步长因子,5,概述,基本迭代公式:,?,无约束优化问题,内容:讨论几个常用无约束优化方法的基本思想、方法构成、迭代步骤以及终止准则等方面问题。,无约束优化方法,直接法：坐标轮换法、鲍威尔(Powell)法,间接法：
2、梯度法、牛顿法、变尺度法,直接搜索法：只需进行函数值的计算与比较来确定迭代方向和步长间接法：利用函数的一阶或二阶偏导数矩阵来确定迭代方向和步长,6,4.1 坐标轮换法,迭代方向S取为一系列坐标轴方向，通常都用单位坐标矢量ei作为这种迭代的方向矢量，则坐标轮换法所取的迭代方向就依次为:,第一轮:任取一初始点X(0),第二轮:,7,迭代步长的确定,最优步长利用一维优化方法确定沿该方向上具有最小目标函数值的步长，即:minF(X(k)+(k)S(k)=minF(X(k)+(k)S(k)加速步长先选择一个不大的初始步长0，在每次一维搜索中都是先沿正向从0开始作试探计算函数值，若函数值下降，则以倍增的速
3、度加大步长，步长序列为0、20、40、80、直到函数值保持下降的最后一个步长为止。若试探时函数值已增大，则改沿反向，即取-0后再加速步长。,8,终止准则:,9,坐标轮换法的特点,具有程序结构简单，易于掌握等优点。但是计算效率比较低，这一缺点当优化问题的维数较高时更为突出。一般认为，此方法应用于n10的低维优化问题比较适宜收敛速度与等值线的形状有关,10,不同性质目标函数坐标轮换法的求优效能,收敛速度很快,收敛速度很慢,求优失效,等值线为椭圆,长、短轴与x1,x2轴平行,等值线为椭圆,长、短轴与x1,x2轴不平行,11,4.2 鲍威尔（Powell）法,12,4.2.1 鲍威尔(Powell)法
4、的基本思想,鲍威尔法是直接搜索法中一个十分有效的算法。该算法是沿着逐步产生的共轭方向进行搜索的，因此本质上是一种共轭方向法，鲍威尔法的收敛速率较快。以共轭方向作为搜索方向，不只限于鲍威尔法，也用于其他一些较为有效的方法，可以统称为共轭方向法。因此，共轭方向的概念在优化方法研究中占有重要的地位。共轭方向在最优化问题中的应用是基于其具有一个重要性质，即：设 S1、S2、Sn是关于A的n个互相共轭的向量，则对于求正定二次函数 的极小点，从任意初始点出发，依次沿Si i=1，2，n)方向进行一维最优化搜索，至多n步便可以收敛到极小点,13,2.4.2 共轭方向,一、共轭方向的基本概念若有两个n维矢量S
5、1、S2，对nn阶对称正定矩阵A能满足:,称n维空间矢量S1与S2对A共轭共轭矢量所代表的方向称为共轭方向。,正交，可以看作是共轭的特例共轭，可以看作是正交的推广,例:(1),共轭并正交,14,2.5 关于优化方法中搜寻方向的理论基础2.5.2 共轭方向,例:(2),共轭但不正交,正交但不共轭,例:(3),15,设A为nn阶实对称正定矩阵，有一组非零的n维矢量S1、S2、Sq，若满足 ij 则称矢量系Si(i1，2，qn)对于矩阵A共轭,16,一、共轭方向的基本概念,二元二次函数,海赛矩阵正定有极小点,F(X)的等值线是同心椭圆簇几何特性:两条平行的任意方向的切线,其切点的连线必通过椭圆簇的中
6、心。,17,一、共轭方向的基本概念,S1与S2是对A共轭的一对矢量,证明：,梯度,而,即：,结论:两个平行方向的极小点构成的新方向与原方向相互共轭,对于二维正定二次函数只要分别沿两个共轭方向寻优即可找到最优点.,18,与此类似，可以推出对于n维正定二次函数共轭方向的一个十分重要的极为有用的性质：从任意初始点出发，依次沿n个线性无关的与A共轭的方向S1，S2，Sn各进行一维搜索，那么总能在第n步或n步之前就能达到n维正定二次函数的极小点；并且这个性质与所有的n个方向的次序无关。简言之，用共轭方向法对于二次函数从理论上来讲，n步就可达到极小点。因而说共轭方向法具有有限步收敛的特性。通常称具有这种性
7、质的算法为二次收敛算法。,19,二、共轭矢量的几个性质,共轭矢量之所以引起优化研究者的重视，是因为它的某些性质对提高优化方法的收敛速率极为有用。(1)矢量S1与S2正交关系，是矢量S1与S2对A共轭的特殊情形。在n维设计空间里，单位坐标矢量系：e1，e2，en为正交矢量系。(2)若矢量系S1、S2、Sn，对于对称正定矩阵A共轭，则它必为线性独立(线性无关)矢量系。对于n维设计空间而言，线性独立矢量系中的矢量个数不能超过维数n，即共轭矢量系中矢量个数最多等于n(证明略)。(3)关于二次收敛性问题,对于一般的n元二次正定函数F(x)，依次按共轭矢量系(S1，S2，Sn)中各矢量方向进行n次一维搜索
8、，就可达到等值线(椭圆)中心理论极小点。二次收敛性是指一种算法，如果对于二次正定函数，从理论上只要进行有限次一维搜索，就可达到理论极小点，把这种算法称为具有二阶收敛性(二次收敛性)或有限步收敛性。,20,例2.1,解：(1)第一个搜索方向,(2)函数的海赛矩阵 对称正定,21,例2.1,解：(4)任取初始点,沿S1方向一维搜索求得该方向极小点,(5)求与S1相共轭的方向S2,S2=X(2)-X(1)=,核验计算,矢量S1与S2确为对A矩阵共轭。,(6)从X(1)点出发，沿S2方向作一维搜索，得极小点 X*=0 0T,22,4.2.1 鲍威尔基本算法,23,4.2.1 鲍威尔基本算法,任取一初始
9、点 X(0)X0(1)第一环:e1,e2,e3 S1第二环:e2,e3,S1 S2第三环:e3,S1,S2 S3,第一轮,S1,S2,S3两两共轭,结论:两个平行方向的极小点构成的新方向与原方向相互共轭,24,4.2.1 鲍威尔基本算法,第一环:e1,e2,e3 S1第二环:e2,e3,S1 S2第三环:e3,S1,S2 S3,第一轮,S1是e1,e2,e3 的线性组合S2是e2,e3,S1的线性组合S3是e3,S1,S2的线性组合,新一环方向组:e2,e3,S1 线性相关!,降维,25,鲍威尔法的基本思想:对原始共轭方向法进行修正,即在某环已取得的n+1个方向中,选取n 个线性无关,共轭程度
10、尽可能高的方向作为下一环的基本方向组,从而避免出现“退化”现象.鲍威尔法与原始共轭方向法的主要区别是：在构成K+1环基本方向组时，不再总是淘汰前一环(K环)中的第一个方向，而是根据条件式是否得到满足分两种情况来处理。,4.2.1 鲍威尔修正算法,26,4.2.1 鲍威尔修正算法,第K环方向组:,鲍威尔基本算法,第K+1环方向组:,一、Powell 修正算法的搜索方向,Powell 修正算法的基本方向组构成是从下面原则出发的：在某环已取得的n+1个方向中，选取n个线性无关的并且共轭程度尽可能高的方向作为下一环的基本方向组，从而避免出现“退化”现象。,27,4.2.1 鲍威尔修正算法,映射点,一、
11、Powell 修正算法的搜索方向,Powell 判别式,28,4.2.1 鲍威尔修正算法,一、Powell 修正算法的搜索方向,第K环方向组:,(1)第K+1环方向组:,(2)第K+1环初始点:,情况一：Powell 判别式中若至少 有一个不等式成立，则第K+1环的方向组仍用老方向组,初始点:,当F2 F3时,当F2F3时,情况二：Powell 判别式中若两个 不等式均不成立，则第K+1环的方向组,初始点:,29,以二维为例:两条件式至少有一成立且F2F3,30,两条件式均不成立且m=1 两条件式均不成立且m=2,31,4.2.1 鲍威尔修正算法,一、Powell 修正算法的搜索方向,终止准则
12、:,采用了上述产生基本方向组的新方式后，除了第一环以单位坐标矢量系为基本方向组外，以后每轮开始就不必重置单位坐标矢量系，只要一环接一环继续进行即可。随着逐环迭代的继续，各环的基本方向组将渐趋共轭。因此，这个修正了的鲍威尔算法，虽然已不再像基本算法那样具有二次收敛的性质，但修正算法确实克服了退化的不利情形，同时仍能够有效地、越来越快地收敛于无约束最优点x*。,二、修正算法的迭代步骤及流程图,32,解：第一环迭代计算,沿第一坐标方向e1进行一维搜索,沿第二坐标轴方向e2进行一维搜索,构成新方向：,33,沿s1方向一维搜索得极小点与极小值,需进行第二环迭代计算。,第二环迭代计算：首先确定上环中的最大
13、函数下降量及其相应方向,映射点及其函数值,计算点距,34,检验鲍尔条件,鲍威尔条件两式均不成立。第二环取基本方向组和起始点为,沿e2方向作一维搜索得,沿S1方向一维搜索得,构成新生方向,沿S2方向一维搜索得,去掉函数值下降最大的方向,补上新增的方向初始点取新增方向的极小点,35,检查迭代终止条件,需再作第三环迭代计算。,根据具体情况来分析，S1、S2实际上为共轭方向的（见图4.9）。本题又是二次函数，按共轭方向的二次收敛性质，上面的结果就是问题的最优解。可以预料，如果作第三环迭代，则一定各一维搜索的步长为零，必有,故得最优解,36,解:令,正定,用解析法验证,得:,37,?,迭代过程、算法框图
14、和m文件,开始,输入,k1,i1,沿着坐标轴方向计算最优步长,i=n？,ii+1,Powell条件满足?,输出,结束,y,n,n,y,y,n,?,n,y,?,?,?,?,38,鲍威尔法的特点:是到目前为止求解无约束优化问题的最有效的方法。不需求导数,只需计算目标函数值。适用中、小型问题。,39,4.3 梯度法,终止准则:,优点：程序结构简单，每次迭代所需的计算量及储存量也小，而且当迭代点离最优点较远时函数值下降速度很快。缺点：但是这种方法在迭代点到达最优点附近时，进展十分缓慢，而且常常由于一维搜索的步长误差而产生的扰动不可能取得较高的收敛精度。,40,41,例题4.3 用梯度法求目标函数F(x
15、)=+25 的最优解。已知初始点x(0)2 2T，迭代精度取=0.005。解：函数的梯度,第一次迭代：以x(0)为起点沿-g(0)方向作一维搜索,初始点函数梯度值:,第一点函数梯度值:,42,43,解:令,正定,得:,用解析法验证,44,梯度法的特点:,几何概念直观,方法和程序简单,远离极小点时收敛速度快。但越接近极小点收敛速度越慢。,45,4.4 牛顿法,4.4.1 原始牛顿法原始牛顿法的基本思想：在第k次迭代点X(k)邻域内，用一个二次函数(X)去近似代替原目标函数F(X)，然后求出这个二次函数的极小点作为对原目标函数求优的下一个迭代点X(k+1)，通过若干次的重复迭代，使迭代点逐步逼近原
16、目标函数的极小点X*,一元函数f(x)在x(k)点的泰勒展开式：,利用原目标函数f(x)1个点的3个信息:函数值fk、一阶导数值fk、二阶导数值fk构造一个二次函数(x)去近似代替,注意：与一维优化方法的二次插值法的不同,46,一元函数f(x)的例子,47,4.4 牛顿法,4.4.1 原始牛顿法,一元函数f(x)在x(k)点的泰勒展开式：,n元函数F(X)在X(k)点的泰勒展开式：,48,4.4 牛顿法,4.4.1 原始牛顿法,令,牛顿方向:,(定步长),49,4.4 牛顿法,4.4.1 原始牛顿法,牛顿法具有二次收敛性。对于二次正定函数，迭代一次即可到达最优点；对于非二次函数，若函数的二次性
17、态较强或迭代点已进入最优点的较小邻域，则其收敛速度也是很快的。但原始牛顿法还存在一个问题：由于在全部迭代过程中，取步长(k)1，这种定步长有时造成函数值反而有所增大。,50,4.4 牛顿法,4.4.1 原始牛顿法4.4.2 阻尼牛顿法,(1)对目标函数有较严格的要求。除了函数具有连续的一二阶导数以外，为了保证函数的稳定下降，海赛矩阵必须正定；为了能求逆阵又要求海赛矩阵必须非奇异。(2)计算相当复杂，除了求梯度以外还需计算二阶偏导数矩阵和它的逆矩阵，占用机器的贮存量也很大。所以，它在工程优化设计中的应用受到一定的限制。,51,梯度法和牛顿法对比,52,例题4.5 用牛顿法求函数F(x)4(x11
18、)22(x21)2x1x210的最优解。初始点x(0)0 0T，105。解：函数的梯度海赛矩阵及其逆在x(0)点处,53,沿S(0)方向一维搜索求最优步长得代入函数解得：(0)=1故新迭代点为该点的梯度满足终止条件，迭代即可结束,54,牛顿法的特点：,牛顿法具有二次收敛性，对正定二次函数一次迭代即可达到极小点。对目标函数性态较好或当初始点取在极小点附近时收敛速度快。但对目标函数有较高的要求，必须存在一阶、二阶偏导数，H（x(k)）需正定且非奇异。计算复杂，计算量大。,55,4.5 DFP变尺度法,梯度法:,牛顿法:,Davidon于1959年提出:,拟牛顿公式,拟牛顿方向,Ak是根据需要构造的
19、nn阶对称矩阵，它是随着迭代点位置的变化而变化的。若AkE(单位矩阵)，上式为梯度方向；若Ak为目标函数二阶导数矩阵的逆矩阵H(x(k)-1，则为牛顿方向。,尺度矩阵,4.5.1 变尺度法的基本思想,56,变尺度法的基本思想：设法构造一个对称正定阵Ak代替,并在选代计算中，使其逐渐逼近。因此，一旦达到极值点附近，就可望达到牛顿法的收敛速度，同时又避免了矩阵的求逆计算。其选代公式：Ak是根据需要构造的nn阶对称矩阵，它是随着迭代点位置的变化而变化的。,4.5 DFP变尺度法,57,4.5.2 变尺度法构造矩阵的产生,递推方法产生:,校正矩阵,变尺度法采用构造矩阵来代替牛顿法中海赛矩阵的逆阵，其主
20、要目的之一是为了避免计算二阶偏导数和计算它的逆矩阵，力图仅用梯度和其他一些易于获得的信息来确定迭代方向。分析一下海赛矩阵与梯度之间的关系。,58,4.5.2 变尺度法构造矩阵的产生,海赛矩阵与梯度之间的关系,位移矢量,梯度矢量差,拟牛顿条件(拟牛顿方程),P116,DFP公式,59,4.5.3 对DFP法几个问题的说明与讨论,(1)DFP公式总有确切的解。(2)构造矩阵的正定性。(3)DFP法搜索方向的共轭性。(4)关于算法的稳定性。为了提高实际计算中的稳定性，一方面应对一维搜索提出较高的精度要求，另一方面在发生破坏正定性时，将构造矩阵重置为单位矩阵E重新开始，通常采用的简单办法是在n次迭代后重置单位矩阵。,4.5.4 DFP算法的迭代步骤,60,例题 4.6,用DFP变尺度法求目标函数F(x)4(x15)2(x26)2的最优解。已知初始点x(0)8 9T，迭代精度0.01。解：第一次迭代：,式中最优步长(0)应该用一维搜索方法在计算机上求解。为了说明问题，又因为此例目标函数简单，所以用解析法来求：,61,例题 4.6,为求极小，将上式对求导，并令f()0得,第二次迭代：确定x(1)点的拟牛顿方向S(1),按DFP公式计算构造矩阵,将数据代入得,则拟牛顿方向为,62,例题 4.6,沿S(1)方向进行一维搜索求最优点x(2),求一维搜索步长,
