无约束优化方法.ppt

第四章 无约束优化方法,第一节 概述,第1章所列举的机械优化设计问题，都是在一定的限制条件下追求某一指标为最小，它们都属于约束优化问题。,约束优化问题的求解转化为一系列的无约束优化问题实现的。,因此，无约束优化问题的解法是优化设计方法的基本组成部分，也是优化方法的基础。,为什么要研究无约束优化问题?（1）有些实际问题，其数学模型本身就是一个无约束优化问题。（2）通过熟悉它的解法可以为研究约束优化问题打下良好的基础。（3）约束优化问题的求解可以通过一系列无约束优化方法来达到。所以无约束优化问题的解法是优化设计方法的基本组成部分，也是优化方法的基础。,（4）对于多维无约束问题来说，古典极值理论中令一阶导数为零，但要求二阶可微，且要判断海赛矩阵为正定才能求得极小点，这种方法有理论意义，但无实用价值。和一维问题一样，若多元函数f(x)不可微，亦无法求解。但古典极值理论是无约束优化方法发展的基础。,目前已研究出很多种无约束优化方法，它们的主要不同点在于构造搜索方向上的差别。,无约束优化问题是：,求n维设计变量,使目标函数,解析法,数值法,数学模型复杂时不便求解,可以处理复杂函数及没有数学表达式的优化设计问题,搜索方向问题是无约束优化方法的关键。,各种无约束优化方法的区别：确定搜索方向的方法不同。,无约束优化方法分类,利用目标函数的一阶或二阶导数,利用目标函数值,（最速下降法、共轭梯度法、牛顿法）,（坐标轮换法、鲍威尔等）,搜索方向的构成问题乃是无约束优化方法的关键。,用直接法寻找极小点时，不必求函数的导数，只要计算目标函数值。这类方法较适用于解决变量个数较少的（n 20）问题，一般情况下比间接法效率低。间接法除要计算目标函数值外，还要计算目标函数的梯度，有的还要计算其海赛矩阵。,第二节 最速下降法,优化设计追求目标函数值最小，若搜索方向取该点的负梯度方向，使函数值在该点附近的范围内下降最快。,按此规律不断走步，形成以下迭代算法：,以负梯度方向为搜索方向，所以称最速下降法或梯度法。,搜索方向确定为负梯度方向，还需确定步长因子,即求一维搜索的最佳步长，既有,由此可知，在最速下降法中，相邻两个迭代点上的函数梯度相互垂直。而搜索方向就是负梯度方向，因此相邻两个搜索方向互相垂直。,在最速下降法中，相邻两个迭代点上的函数梯度相互垂直。而搜索方向就是负梯度方向，因此相邻两个搜索方向互相垂直。这就是说在迭代点向函数极小点靠近的过程，走的是曲折的路线。形成“之”字形的锯齿现象，而且越接近极小点锯齿越细。,图4-2 最速下降法的搜索路径,方法特点（1）初始点可任选，每次迭代计算量小，存储量少，程序简短。即使从一个不好的初始点出发，开始的几步迭代，目标函数值下降很快，然后慢慢逼近局部极小点。（2）任意相邻两点的搜索方向是正交的，它的迭代路径为绕道逼近极小点。当迭代点接近极小点时，步长变得很小，越走越慢。,沿负梯度方向进行一维搜索，有,为一维搜索最佳步长，应满足极值必要条件,例41 求目标函数 的极小点。解 取初始点则初始点处函数值及梯度分别为,算出一维搜索最佳步长,第一次迭代设计点位置和函数值,继续作下去，经10次迭代后，得到最优解,这个问题的目标函数的等值线为一簇椭圆,迭代点从 走的是一段锯齿形路线，见图4-3。,将上例中目标函数 引入变换,其等值线由椭圆变成一簇同心圆。,仍从 即 出发进行最速下降法寻优。此时：,沿负梯度方向进行一维搜索：,则函数f(X)变为：,y1=x1,y2=5x2,由,从而算得一步计算后设计点的位置及其目标函数：,经变换后，只需一次迭代，就可找到最优解。,这是因为经过尺度变换：,等值线由椭圆变成圆。,梯度法的特点,（1）理论明确，程序简单，对初始点要求不严格。（2）对一般函数而言，梯度法的收敛速度并不快，因为最速下降方向仅仅是指某点的一个局部性质。（3）梯度法相邻两次搜索方向的正交性，决定了迭代全过程的搜索路线呈锯齿状，在远离极小点时逼近速度较快，而在接近极小点时逼近速度较慢。（4）梯度法的收敛速度与目标函数的性质密切相关。对于等值线(面)为同心圆（球）的目标函数，一次搜索即可达到极小点。,第三节 牛顿型方法,在第三章中，我们已经讨论了一维搜索的牛顿方法。,得出一维情况下的牛顿迭代公式,对于多元函数，在,泰勒展开，得,这是多元函数求极值的牛顿法迭代公式。,对于二次函数，海赛矩阵H是一个常矩阵，其中各元素均为常数。因此，无论从任何点出发，只需一步就可找到极小点。,例42 求目标函数 的极小点。解 取初始点,从牛顿法迭代公式的推演中可以看到，迭代点的位置是按照极值条件确定的，其中并未含有沿下降方向搜寻的概念。因此对于非二次函数，如果采用上述牛顿迭代公式，有时会使函数值上升。,阻尼牛顿法,阻尼因子，沿牛顿方向进行一维搜索的最佳步长，由下式求得：,经过一次迭代即求得极小点,函数极小值,阻尼牛顿法程序框图,方法特点（1）初始点应选在X*附近，有一定难度；（2）尽管每次迭代都不会是函数值上升，但不能保证每次下降；（3）若迭代点的海赛矩阵为奇异，则无法求逆矩阵，不能构造牛顿法方向；（4）不仅要计算梯度，还要求海赛矩阵及其逆矩阵，计算量和存储量大。此外，对于二阶不可微的F(X)也不适用。虽然阻尼牛顿法有上述缺点，但在特定条件下它具有收敛最快的优点，并为其他的算法提供了思路和理论依据。,一般迭代式：,梯度法：,牛顿法：,阻尼牛顿法：,梯度法与牛顿法：,第四节 共轭方向及共轭方向法,为了克服最速下降法的锯齿现象，提高收敛速度，发展了一类共轭方向法。搜索方向是共轭方向。,一、共轭方向的概念,共轭方向的概念是在研究二次函数,时引出的。,首先考虑二维情况,如果按最速下降法，选择负梯度方向为搜索方向，会产生锯齿现象。,为避免锯齿的发生，取下一次的迭代搜索方向直接指向极小点，如果选定这样的搜索方向，对于二元二次函数只需进行两次直线搜索就可以求到极小点。,应满足什么条件？,对于二次函数 在 处取得极小点的必要条件,等式两边同乘 得,是对G的共轭方向。,就是使d1直指极小点x*，d1所必须满足的条件。,两个向量d0和d1称为G的共轭向量，或称d0和d1对G是共轭方向。,二.共轭方向的性质,性质1 若非零向量系d0,d1,d2,dm-1是对G共轭，则这m个向量是线性无关的。,性质2 在n维空间中互相共轭的非零向量的个数不超过n。,性质3 从任意初始点出发，顺次沿n个G的共轭方向d0,d1,d2,进行一维搜索，最多经过n次迭代就可以找到的二次函数f(x)极小点。,三、共轭方向法,1、选定初始点，下降方向 和收敛精度，k=0。,2、沿 方向进行一维搜索，得,3、判断 是否满足，若满足则打印,否则转4。,4、提供新的共轭方向，使,5、置，转2。,第五节 共轭梯度法,共轭梯度法是共轭方向法的一种，共轭向量有迭代点的负梯度构造出来，所以称共轭梯度法。,从点 出发，沿G某一共轭方向 作一维搜索,到达,而在点、处的梯度分别为：,3.共轭梯度法,共轭梯度法是共轭方向法中的一种，该方法中每一个共轭向量都是依赖于迭代点处的负梯度而构造出来。从xk出发，沿负梯度方向作一维搜索:,设与dk共轭的下一个方向dk+1由dk和点xk+1的负梯度的线形组合构成，即：,共轭条件：,则：,解得：,令,为函数的泰勒二次展开式,则,上两式相减，并代入,将式,与式,两边相乘，并应用共轭条件,得：,因此,，已知初始点1,1T,例题 4-4 求下列问题的极值,解：1）第一次沿负梯度方向搜寻计算初始点处的梯度,为一维搜索最佳步长，应满足,迭代精度。,得:,2）第二次迭代：,代入目标函数,得,因,收敛。,由,从而有：,图4-9 共轭梯度法的几何说明,第六节 变尺度法(DFP法),变尺度法的基本思想：,前面讨论的梯度法和牛顿法，它们的迭代公式可以看作下列公式的特例。,变尺度法是对牛顿法的修正，它不是计算二阶导数的矩阵和它的逆矩阵，而是设法构造一个对称正定矩阵H来代替Hesse矩阵的逆矩阵。并在迭代过程中，使其逐渐逼近H-1。,由于对称矩阵H在迭代过程中是不断修正改变的，它对于一般尺度的梯度起到改变尺度的作用，因此H又称变尺度矩阵。,DFP变尺度法首先有戴维顿（Davidon）与1959年提出，又于1963年由弗莱彻（Fletcher）和鲍维尔加以发展和完善，成为现代公认的较好的算法之一。DFP法是基于牛顿法的思想又作了重要改进。这种算法仅用到梯度，不必计算海赛阵及其逆矩阵，但又能使搜索方向逐渐逼近牛顿方向，具有较快的收敛速度。,基本思想 变量的尺度变换是放大或缩小各个坐标。通过尺度变换可以把函数的偏心程度降到最低限度。,例如在用最速下降法求 的极小,值时,需要进行10次迭代才能达到极小点,如作变换,y1=x1,y2=5x2,消除了函数的偏心，用最速下降法只需一次迭代即可求得极小点。,梯度法构造简单，只用到一阶偏导数，计算量小，初始点可任选，且开始几次迭代，目标函数值下降很快；其主要缺点是迭代点接近X*时，即使对二次正定函数收敛也非常慢。牛顿法收敛很快，对于二次函数只需迭代一次便达到最优点，对非二次函数也能较快迭代到最优点，但要计算二阶偏导数矩阵及其逆阵，对维数较高的优化问题，其计算工作和存储量都太大。,能不能将两种算法的优点综合起来，扬长避短？,Ak 是需要构造nn的一个对称方阵，,如Ak=I,则得到梯度法；,变尺度法的关键在于尺度矩阵Ak的产生。,对于二次函数:,进行尺度变换,在新的坐标系中，函数f(x)的二次项变为：,目的：减少二次项的偏心,如G是正定，则总存在矩阵Q，使得：,用矩阵Q-1右乘等式两边，得：,用矩阵Q左乘等式两边，得：,所以,上式说明：二次函数矩阵G的逆阵，可以通过尺度变换矩阵Q来求得。,牛顿迭代公式：,记：,搜索方向：,迭代公式：,A 称为变尺度矩阵,在例42中,如取,求得：,三、变尺度法的一般步骤,DFP算法,DFP算法,DFP算法,例题 4-5,第七节 坐标轮换法,坐标轮换法是每次搜索只允许一个变量变化，其余变量保持不变，即沿坐标方向轮流进行搜索的寻优方法。,它把多变量的优化问题轮流地转化成单变量的优化问题。,因此又称变量轮换法。,其基本原理是将一个多维的无约束最优化问题转化为一系列较低维的最优化问题来求解，简单地说，就是先将(n-1)个变量固定不动，只对第一个变量进行一维搜索得到最优点x1（1）。然后，又保持(n-1)个变量不变，再对第二个变量进行一维搜索到x2（1）等等。,图412 坐标轮换法原理图,2.搜索方向与步长的确定,对于第k轮第i次的计算,第k轮第I次的迭代方向，它轮流取n维坐标的单位向量。,3.搜索步长的确定,关于 值通常有以下几种取法（1）加速步长法（2）最优步长法 最优步长法就是利用一维最优搜索方法来完成每一次迭代，此时可以采用0.618方法或二次插值方法来计算。,图413 加速步长法的搜索路线,图414 最优步长法的搜索路线,4.坐标轮换法存在的问题,图415 坐标轮换法在各种不同情况下的效能（a）搜索有效；（b）搜索低效；（c）搜索无效,第八节 Powell法（方向加速法）,Powell法是利用共轭方向可以加速收敛的性质所形成的一种搜索算法。,一、共轭方向的生成,二、基本算法,三、改进的算法,在鲍维尔基本算法中，每一轮迭代都用连结始点和终点所产生出的搜索方向去替换原来向量组中的第一个向量，而不管它的“好坏”。,改进的算法是：首先判断原向量组是否需要替换。如需要替换，在产生新的向量。,第八节 Powell法（方向加速法）,鲍威尔法是以共轭方向为基础的收敛较快的直接法之一，是一种十分有效的算法。1964年，鲍维尔提出这种算法，其基本思想是直接利用迭代点的目标函数值来构造共轭方向，然后从任一初始点开始，逐次沿共轭方向作一维搜索求极小点。并在以后的实践中进行了改进。,对函数：,基本思想：在不用导数的前提下，在迭代中逐次构造G的共轭方向。,1.共轭方向的生成,设xk,xk+1为从不同点出发，沿同一方向dj进行一维搜索而到的两个极小点。,梯度和等值面相垂直的性质,dj和 xk,xk+1两点处的梯度gk,gk+1之间存在关系:,另一方面，对于上述二次函数，其xk,xk+1两点处的梯度可表示为:,因而有,取,这说明只要沿dj方向分别对函作两次一维搜索，得到两个极小点xk和xk+1，那么这两点的连线所给出的方向dk就是与dj一起对G共轭的方向。,2.基本算法,二维情况描述鲍威尔的基本算法:,1）任选一初始点x0，再选两个线性无关的向量，如坐标轴单位向量e1=1,0T和e2=0,1T作为初始搜索方向。,2）从x0出发，顺次沿e1，e1作一维搜索，得 点，两点连线得一新方向d1,沿d2作一维搜索得点x2。,即是二维问题的极小点x*。,方法的基本迭代格式包括共轭方向产生和方向替换两主要步骤。,用 d1代替e1形成两个线性无关向量d1,e2，作为下一轮迭代的搜索方向。再 从出发，沿d1作一维搜索得点，作为下一轮迭代的初始点。,3）从出发，顺次沿e2,d1 作一维搜索，得到点，两点连线得一新方向:,把二维情况的基本算法扩展到n维，则鲍威尔基本算法的要点是：在每一轮迭代中总有一个始点（第一轮的始点是任选的初始点）和n个线性独立的搜索方向。从始点出发顺次沿n个方向作一维搜索得一终点，由始点和终点决定了一个新的搜索方向。用这个方向替换原来n个方向中的一个，于是形成新的搜索方向组。替换的原则是去掉原方向组的第一个方向而将新方向排在原方向的最后。此外规定，从这一轮的搜索终点出发沿新的搜索方向作一维搜索而得到的极小点，作为下一轮迭代的始点。这样就形成算法的循环。,3）若目标函数为正定二次函数，n轮结束后即可到达最优点。,2）每轮迭代产生一个新方向取代原来的第一方向，n轮迭代后可产生n个彼此共轭的方向；,1）开始采用坐标轴方向；,Powell基本算法,上述基本算法仅具有理论意义。,因为在迭代中的n个搜索方向有时会变成线性相关而不能形成共轭方向。这时组不成n维空间，可能求不到极小点，所以上述基本算法有待改进。,3.改进的算法,在鲍威尔基本算法中，每一轮迭代都用连结始点和终点所产生出的搜索方向去替换原向量组中的第一个向量，而不管它的“好坏”，这是产生向量组线性相关的原因所在。,在改进的算法中首先判断原向量组是否需要替换。如果需要替换，还要进一步判断原向量组中哪个向量最坏，然后再用新产生的向量替换这个最坏的向量，以保证逐次生成共轭方向。,为此，要解决两个关键问题：（1）dk1是否较好？是否应该进入新的方向组？即方向组是否进行更新？,（2）如果应该更新方向组，dk1不一定替换方向，而是有选择地替换某一方向。,令在k次循环中,分别称为一轮迭代的始点、终点和反射点。,则在循环中函数下降最多的第m次迭代是,记：,相应的方向为。,为了构成共轭性好的方向组，须遵循下列准则：,在k次循环中，若满足条件：,和,则选用新方向dk，并在第k+1迭代中用dk替换对应于 的方向。否则，仍然用原方向组进行第k+1迭代。,因此,这样重复迭代的结果，后面加进去的向量都彼此对G共轭，经n轮迭代即可得到一个由n个共轭方向所组成的方向组。对于二次函次，最多n次就可找到极小点，而对一般函数，往往要超过n次才能找到极小点（这里“n”表示设计空间的维数）。,例4-5 用改进的鲍威尔法求目标函数,解：（1）第1轮迭代计算,，,沿e1方向进行一维搜索,得,以 为起点，沿第二坐标轴方向 e2 进行一维搜索,得,确定此轮中的最大下降量及其相应方向,反射点及其函数值,检验Powell条件,由于满足Powell条件，则淘汰函数值下降量最大的方向e1，下一轮的基本方向组为e2，。,构成新的方向,沿 方向一维搜索得极小点和极小值,，,此点为下轮迭代初始点。,按点距准则检验终止条件,需进行第二轮迭代机算。,（2）第2轮迭代计算,此轮基本方向组为e2，分别相当于，起始点为。,沿e2方向进行一维搜索得,以 为起点沿 方向一维搜索得,确定此轮中函数值最大下降量及其相应方向,反射点及其函数值,检验Powell条件，淘汰函数值下降量最大的方向e2，下一轮的基本方向组应为，。,构成新的方向,沿 方向进行一维搜索得,检验终止条件,（3）第3轮迭代计算,此轮基本方向组为，起始点为，先后沿，方向，进行一维搜索，得,，,故最优解,检验终止条件,实际上，前两轮迭代的，为共轭方向，由于本例目标函数是二次函数，按共轭方向的二次收敛性，故前两轮的结果就是问题的最优解，但每一轮迭代都需要进行n+1次迭代。,第九节 单纯形方法,基本思想 单纯形替换法也是一种不使用导数的求解无约束极小化问题的直接搜索方法，与前面几种方法不同的是，单纯形替换法不是利用搜索方向从一个点迭代到另一个更优的点，而是从一个单纯形迭代到另一个更优的单纯形。,定义：单纯形 n维空间中的恰好有n+1个顶点（极点）的有界的凸多面体称之为一个单纯形。根据定义，可知，一维空间中的单纯形是线段，二维空间中的单纯形是三角形，而三维空间中的单纯形则是四面体。在单纯形替换算法中，从一个单纯形到另一个单纯形的迭代主要通过反射、扩张、收缩和缩边这4个操作来实现。下面以二维问题为例来对4种操作进行说明（参见下图）。,（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，且有,如果出现。表示反射完全失败，应退回到介于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的函数值，挑出其中的最优点，记为XL；最劣点，记XH；次差点，记为Xw；（3）求反射中心,其中，a0，通常取a=1；,输出XL，为原问题近似极小点；否则，转（2）。,（5）如果满足,表1 无约束优化方法搜索方向之间的相互联系间接法,（海赛矩阵的逆阵）,无约束优化方法间接法总结,1、梯度法 方向 负梯度 用到一阶导数 适合于精度不高或用于复杂函数寻找一个好的初始点2、牛顿法 用到一阶导数和海色矩阵，具有二次收敛性 要求海色矩阵奇异，且维数不宜太高3、共轭梯度法 用到一阶导数，具有二次收敛性4、变尺度法(DFP法)收敛快，效果好，被认为是目前最有效的无约束优化方法。适用于维数较高，具有一阶偏导数的目标函数,1、坐标轮换法 计算效率较低 适合维数较低，目标函数无导数或导数较难求得2、Powell法 具有二次收敛性，收敛速度较快，可靠性高，被认为是直接法中最有效的方法之一3、单纯形法 思路清楚，收敛慢,无约束优化方法直接法总结,第四章 无约束优化作业,