第5章-无约束优化方法.ppt

《第5章-无约束优化方法.ppt》由会员分享，可在线阅读，更多相关《第5章-无约束优化方法.ppt（94页珍藏版）》请在金锄头文库上搜索。

1、第5章 无约束优化方法,5-1 最速下降法（梯度法） 5-2 牛顿类方法 5-3 变尺度法 5-4 共轭方向法 5-5 鲍威尔方法 5-6 其它方法（如坐标轮换法、单纯形法）,第1章所列举的机械优化设计问题，都是在一定的限制条件下追求某一指标为最小，它们都属于约束优化问题。工程问题大都如此。 为什么要研究无约束优化问题? （1）有些实际问题，其数学模型本身就是一个无约束优化问题。 （2）通过熟悉它的解法可以为研究约束优化问题打下良好的基础。 （3）约束优化问题的求解可以通过一系列无约束优化方法来达到。所以无约束优化问题的解法是优化设计方法的基本组成部分，也是优化方法的基础。,（4）对于多维无约

2、束问题来说，古典极值理论中令一阶导数为零，但要求二阶可微，且要判断海赛矩阵为正定才能求得极小点，这种方法有理论意义，但无实用价值。和一维问题一样，若多元函数F(X)不可微，亦无法求解。但古典极值理论是无约束优化方法发展的基础。,目前已研究出很多种无约束优化方法，它们的主要不同点在于构造搜索方向上的差别。,（1）间接法要使用导数，如梯度法、（阻尼）牛顿法、变尺度法、共轭梯度法等。 （2）直接法不使用导数信息，如坐标轮换法、鲍威尔法单纯形法等。,无约束优化问题是：,求n维设计变量,使目标函数,搜索方向的构成问题乃是无约束优化方法的关键。,用直接法寻找极小点时，不必求函数的导数，只要计算目标函数值。

3、这类方法较适用于解决变量个数较少的（n 20）问题，一般情况下比间接法效率低。间接法除要计算目标函数值外，还要计算目标函数的梯度，有的还要计算其海赛矩阵。,5-1 梯度法,基本思想：函数的负梯度方向是函数值在该点下降最快的方向。将n维问题转化为一系列沿负梯度方向用一维搜索方法寻优的问题，利用负梯度作为搜索方向，故称最速下降法或梯度法。,搜索方向s取该点的负梯度方向 (最速下降方向) ，使函数值在该点附近的范围内下降最快 。,为了使目标函数值沿搜索方向 能够获得最大的下降值，其步长因子 应取一维搜索的最佳步长。即有,根据一元函数极值的必要条件和多元复合函数求导公式，得,在最速下降法中，相邻两个迭

4、代点上的函数梯度相互垂直。而搜索方向就是负梯度方向，因此相邻两个搜索方向互相垂直。这就是说在迭代点向函数极小点靠近的过程，走的是曲折的路线。形成“之”字形的锯齿现象，而且越接近极小点锯齿越细。,图5-2 最速下降法的搜索路径,方法特点 （1）初始点可任选，每次迭代计算量小，存储量少，程序简短。即使从一个不好的初始点出发，开始的几步迭代，目标函数值下降很快，然后慢慢逼近局部极小点。 （2）任意相邻两点的搜索方向是正交的，它的迭代路径为绕道逼近极小点。当迭代点接近极小点时，步长变得很小，越走越慢。,sk,沿负梯度方向进行一维搜索，有,为一维搜索最佳步长，应满足极值必要条件,例5-1 求目标函数 的

5、极小点。 解 取初始点 则初始点处函数值及梯度分别为,算出一维搜索最佳步长,第一次迭代设计点位置和函数值,继续作下去，经10次迭代后，得到最优解,这个问题的目标函数的等值线为一簇椭圆,迭代点从 走的是一段锯齿形路线，见图5-3。,将上例中目标函数 引入变换,其等值线由椭圆变成一簇同心圆。,仍从 即 出发进行最速下降法寻优。此时：,沿负梯度方向进行一维搜索：,则函数f(X)变为：,y1=x1, y2=5x2,由,从而算得一步计算后设计点的位置及其目标函数：,经变换后，只需一次迭代，就可找到最优解。,这是因为经过尺度变换：,等值线由椭圆变成圆。,梯度法的特点,（1）理论明确，程序简单，对初始点要求

6、不严格。 （2）对一般函数而言，梯度法的收敛速度并不快，因为最速下降方向仅仅是指某点的一个局部性质。 （3）梯度法相邻两次搜索方向的正交性，决定了迭代全过程的搜索路线呈锯齿状，在远离极小点时逼近速度较快，而在接近极小点时逼近速度较慢。 （4）梯度法的收敛速度与目标函数的性质密切相关。对于等值线(面)为同心圆（球）的目标函数，一次搜索即可达到极小点。,5-2 牛顿法及其改进,设 为 的极小点,这就是多元函数求极值的牛顿法迭代公式。,对于二次函数 ，海赛矩阵H是一个常矩阵，其中各元素均为常数。因此，无论从任何点出发，只需一步就可找到极小点。,例5-2 求目标函数 的极小点。 解 取初始点,从牛顿法

7、迭代公式的推演中可以看到，迭代点的位置是按照极值条件确定的，其中并未含有沿下降方向搜寻的概念。因此对于非二次函数，如果采用上述牛顿迭代公式，有时会使函数值上升 。,阻尼牛顿法,阻尼因子 ，沿牛顿方向进行一维搜索的最佳步长，由下式求得：,经过一次迭代即求得极小点,函数极小值,阻尼牛顿法程序框图,方法特点 （1） 初始点应选在X*附近，有一定难度； （2） 尽管每次迭代都不会是函数值上升，但不能保证每次下降 ； （3） 若迭代点的海赛矩阵为奇异，则无法求逆矩阵，不能构造牛顿法方向； （4） 不仅要计算梯度，还要求海赛矩阵及其逆矩阵，计算量和存储量大。此外，对于二阶不可微的F(X)也不适用。 虽然阻

8、尼牛顿法有上述缺点，但在特定条件下它具有收敛最快的优点，并为其他的算法提供了思路和理论依据。,一般迭代式：,梯度法：,牛顿法：,阻尼牛顿法：,梯度法与牛顿法：,5-3 变尺度法,DFP变尺度法首先有戴维顿（Davidon）与1959年提出，又于1963年由弗莱彻（Fletcher）和鲍维尔加以发展和完善，成为现代公认的较好的算法之一。 DFP法是基于牛顿法的思想又作了重要改进。这种算法仅用到梯度，不必计算海赛阵及其逆矩阵，但又能使搜索方向逐渐逼近牛顿方向，具有较快的收敛速度。,基本思想 变量的尺度变换是放大或缩小各个坐标。通过尺 度变换可以把函数的偏心程度降到最低限度。,例如在用最速下降法求

9、的极小,值时 ,需要进行10次迭代才能达到极小点,如作变换,y1=x1, y2=5x2,消除了函数的偏心，用最速下降法只需一次迭代即可求得极小点。,梯度法构造简单，只用到一阶偏导数，计算量小，初始点可任选，且开始几次迭代，目标函数值下降很快；其主要缺点是迭代点接近X*时，即使对二次正定函数收敛也非常慢。 牛顿法收敛很快，对于二次函数只需迭代一次便达到最优点，对非二次函数也能较快迭代到最优点，但要计算二阶偏导数矩阵及其逆阵，对维数较高的优化问题，其计算工作和存储量都太大。,能不能将两种算法的优点综合起来，扬长避短？,Ak 是需要构造nn的一个对称方阵 ，,如Ak=I, 则得到梯度法 ；,变尺度法

10、的关键在于尺度矩阵Ak的产生 。,对于二次函数:,进行尺度变换,在新的坐标系中，函数f(x)的二次项变为：,目的：减少二次项的偏心,如G是正定，则总存在矩阵Q，使得：,用矩阵Q-1右乘等式两边，得：,用矩阵Q左乘等式两边，得：,所以,上式说明：二次函数矩阵G的逆阵，可以通过尺度变换矩阵Q来求得。,牛顿迭代公式：,记：,搜索方向：,迭代公式：,A 称为变尺度矩阵,在例5-2中,如取,求得：,构造尺度矩阵Ak,从初始矩阵A0=I(单位矩阵)开始，通过对公式,因此，一旦达到最优点附近，就可望达到牛顿法的收敛速度。,1）DFP法（Davidon-Fletcher-Powell),式中,2）BFGS算法

11、(Broyden-Fletcher-Gold frob-Shanno ),DFP算法由于舍入误差和一维搜索不精确，有可能导致构造矩阵的正定性遭到破坏，以至算法不稳定。BFGS算法对于维数较高问题具有更好的稳定性。,例5-3： 用DFP算法求下列问题的极值：,解： 1）取初始点 ，为了按DFP法构造第一次搜寻方向d0，需计算初始点处的梯度,取初始变尺度矩阵为单位矩阵A0=I，则第一次搜寻方向为,沿d0方向进行一维搜索，得,为一维搜索最佳步长，应满足,得:,2）再按DFP法构造点x1处的搜寻方向d1，需计算,代入校正公式,=,=,第二次搜寻方向为,再沿d1进行一维搜索，得,为一维搜索最佳步长，应满

12、足,3）判断x2是否为极值点,梯度:,海赛矩阵 :,梯度为零向量,海赛矩阵正定。可见点满足极值充要条件，因此为极小点。,5-4 共轭方向法,1.共轭方向： 设G为nn阶实对称正定矩阵，如果有两个n维向量d0和d1满足 ，则称向量d0与d1 关于矩阵G共轭。,当G为单位矩阵时，,假设目标函数f(x) 在极值点附近的二次近似函数为,对二维情况,任选取初始点x0沿某个下降方向d0作一维搜索，得x1,因为 是沿d0方向搜索的最佳步长，即在点x1处函数f（x）沿方向d0的方向导数为零。考虑到点x1处方向导数与梯度之间的关系，故有,如果按最速下降法，选择负梯度方向 为搜索方向，则将发生锯齿现象 。,取下一

13、次的迭代搜索方向d1直指极小点x*。,如果能够选定这样的搜索方向，那么对于二元二次函数只需顺次进行d0、d1两次直线搜索就可以求到极小点x* ，即有,那么这样的d1方向应该满足什么条件呢 ?,对于前述的二次函数:,当 时，,x*是f(x)极小点，应满足极值必要条件，故有,将等式两边同时左乘 得：,有,就是使d1直指极小点x* ， d1所必须满足的条件 。,两个向量d0和d1称为G的共轭向量，或称d0和d1对G是共轭方向。,2.共轭方向的性质,性质1 若非零向量系d0,d1,d2,dm-1是对G共轭，则这m个向量是线性无关的。,性质2 在n维空间中互相共轭的非零向量的个数不超过n。,性质3 从任

14、意初始点出发，顺次沿n个G的共轭方向d0,d1, d2,进行一维搜索，最多经过n次迭代就可以找到的二次函数f(x)极小点。,关键：新的共轭方向确定,在无约束方法中许多算法都是以共轭方向作为搜索方向，它们具有许多特点。根据构造共轭方向的原理不同，可以形成不同的共轭方向法。,3.共轭梯度法,共轭梯度法是共轭方向法中的一种，该方法中每一个共轭向量都是依赖于迭代点处的负梯度而构造出来。 从xk出发，沿负梯度方向作一维搜索:,设与dk共轭的下一个方向dk+1由dk和点xk+1的负梯度的线形组合构成，即：,共轭条件：,则：,解得：,令,为函数的泰勒二次展开式,则,上两式相减，并代入,将式,与式,两边相乘，

15、并应用共轭条件,得：,因此,，已知初始点1,1T,例题 5-4 求下列问题的极值,解： 1）第一次沿负梯度方向搜寻 计算初始点处的梯度,为一维搜索最佳步长，应满足,迭代精度 。,得:,2）第二次迭代：,代入目标函数,得,因,收敛。,由,从而有：,5-5 鲍威尔方法,鲍威尔法是以共轭方向为基础的收敛较快的直接法之一，是一种十分有效的算法。 1964年，鲍维尔提出这种算法，其基本思想是直接利用迭代点的目标函数值来构造共轭方向，然后从任一初始点开始，逐次沿共轭方向作一维搜索求极小点。并在以后的实践中进行了改进。,对函数：,基本思想：在不用导数的前提下，在迭代中逐次构造G的共轭方向。,1.共轭方向的生

16、成,设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,