第4章无约束优化方法(白版)1.ppt
《第4章无约束优化方法(白版)1.ppt》由会员分享,可在线阅读,更多相关《第4章无约束优化方法(白版)1.ppt(94页珍藏版)》请在三一文库上搜索。
1、第四章 无约束优化方法,4-1 最速下降法(梯度法) 4-2 牛顿类方法 4-3 变尺度法 4-4 共轭方向法 4-5 鲍威尔方法 4-6 其它方法(如坐标轮换法、单纯形法),第1章所列举的机械优化设计问题,都是在一定的限制条件下追求某一指标为最小,它们都属于约束优化问题。工程问题大都如此。 为什么要研究无约束优化问题? (1)有些实际问题,其数学模型本身就是一个无约束优化问题。 (2)通过熟悉它的解法可以为研究约束优化问题打下良好的基础。 (3)约束优化问题的求解可以通过一系列无约束优化方法来达到。所以无约束优化问题的解法是优化设计方法的基本组成部分,也是优化方法的基础。,(4)对于多维无约
2、束问题来说,古典极值理论中令一阶导数为零,但要求二阶可微,且要判断海赛矩阵为正定才能求得极小点,这种方法有理论意义,但无实用价值。和一维问题一样,若多元函数F(X)不可微,亦无法求解。但古典极值理论是无约束优化方法发展的基础。,目前已研究出很多种无约束优化方法,它们的主要不同点在于构造搜索方向上的差别。,(1)间接法要使用导数,如梯度法、(阻尼)牛顿法、变尺度法、共轭梯度法等。 (2)直接法不使用导数信息,如坐标轮换法、鲍威尔法单纯形法等。,无约束优化问题是:,求n维设计变量,使目标函数,搜索方向的构成问题乃是无约束优化方法的关键。,用直接法寻找极小点时,不必求函数的导数,只要计算目标函数值。
3、这类方法较适用于解决变量个数较少的(n 20)问题,一般情况下比间接法效率低。间接法除要计算目标函数值外,还要计算目标函数的梯度,有的还要计算其海赛矩阵。,4-1 梯度法,基本思想:函数的负梯度方向是函数值在该点下降最快的方向。将n维问题转化为一系列沿负梯度方向用一维搜索方法寻优的问题,利用负梯度作为搜索方向,故称最速下降法或梯度法。,搜索方向s取该点的负梯度方向 (最速下降方向) ,使函数值在该点附近的范围内下降最快 。,为了使目标函数值沿搜索方向 能够获得最大的下降值,其步长因子 应取一维搜索的最佳步长。即有,根据一元函数极值的必要条件和多元复合函数求导公式,得,在最速下降法中,相邻两个迭
4、代点上的函数梯度相互垂直。而搜索方向就是负梯度方向,因此相邻两个搜索方向互相垂直。这就是说在迭代点向函数极小点靠近的过程,走的是曲折的路线。形成“之”字形的锯齿现象,而且越接近极小点锯齿越细。,图4-2 最速下降法的搜索路径,方法特点 (1)初始点可任选,每次迭代计算量小,存储量少,程序简短。即使从一个不好的初始点出发,开始的几步迭代,目标函数值下降很快,然后慢慢逼近局部极小点。 (2)任意相邻两点的搜索方向是正交的,它的迭代路径为绕道逼近极小点。当迭代点接近极小点时,步长变得很小,越走越慢。,沿负梯度方向进行一维搜索,有,为一维搜索最佳步长,应满足极值必要条件,例41 求目标函数 的极小点。
5、 解 取初始点 则初始点处函数值及梯度分别为,算出一维搜索最佳步长,第一次迭代设计点位置和函数值,继续作下去,经10次迭代后,得到最优解,这个问题的目标函数的等值线为一簇椭圆,迭代点从 走的是一段锯齿形路线,见下图。,将上例中目标函数 引入变换,其等值线由椭圆变成一簇同心圆。,仍从 即 出发进行最速下降法寻优。此时:,沿负梯度方向进行一维搜索:,则函数f(X)变为:,y1=x1, y2=5x2,由,从而算得一步计算后设计点的位置及其目标函数:,经变换后,只需一次迭代,就可找到最优解。,这是因为经过尺度变换:,等值线由椭圆变成圆。,梯度法的特点,(1)理论明确,程序简单,对初始点要求不严格。 (
6、2)对一般函数而言,梯度法的收敛速度并不快,因为最速下降方向仅仅是指某点的一个局部性质。 (3)梯度法相邻两次搜索方向的正交性,决定了迭代全过程的搜索路线呈锯齿状,在远离极小点时逼近速度较快,而在接近极小点时逼近速度较慢。 (4)梯度法的收敛速度与目标函数的性质密切相关。对于等值线(面)为同心圆(球)的目标函数,一次搜索即可达到极小点。,4-2 牛顿法及其改进,设 为 的极小点,这就是多元函数求极值的牛顿法迭代公式。,对于二次函数 ,海赛矩阵H是一个常矩阵,其中各元素均为常数。因此,无论从任何点出发,只需一步就可找到极小点。,例42 求目标函数 的极小点。 解 取初始点,从牛顿法迭代公式的推演
7、中可以看到,迭代点的位置是按照极值条件确定的,其中并未含有沿下降方向搜寻的概念。因此对于非二次函数,如果采用上述牛顿迭代公式,有时会使函数值上升 。,阻尼牛顿法,阻尼因子 ,沿牛顿方向进行一维搜索的最佳步长,由下式求得:,经过一次迭代即求得极小点,函数极小值,阻尼牛顿法程序框图,方法特点 (1) 初始点应选在X*附近,有一定难度; (2) 尽管每次迭代都不会是函数值上升,但不能保证每次下降 ; (3) 若迭代点的海赛矩阵为奇异,则无法求逆矩阵,不能构造牛顿法方向; (4) 不仅要计算梯度,还要求海赛矩阵及其逆矩阵,计算量和存储量大。此外,对于二阶不可微的F(X)也不适用。 虽然阻尼牛顿法有上述
8、缺点,但在特定条件下它具有收敛最快的优点,并为其他的算法提供了思路和理论依据。,一般迭代式:,梯度法:,牛顿法:,阻尼牛顿法:,梯度法与牛顿法:,4-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 称为变尺度矩阵,在例42中,如取,求得:,构造尺度矩阵Ak,从初始矩阵A0=I(单位矩阵)开始,通过对公式,因此,一旦达到最优点附近,就可望达到牛顿法的收敛速度。,1)DFP法(Davidon-Fletcher-Powell),式中,2)BFGS算法(Broyden
11、-Fletcher-Gold frob-Shanno ),DFP算法由于舍入误差和一维搜索不精确,有可能导致构造矩阵的正定性遭到破坏,以至算法不稳定。BFGS算法对于维数较高问题具有更好的稳定性。,例4-3: 用DFP算法求下列问题的极值:,解: 1)取初始点 ,为了按DFP法构造第一次搜寻方向d0,需计算初始点处的梯度,取初始变尺度矩阵为单位矩阵A0=I,则第一次搜寻方向为,沿d0方向进行一维搜索,得,为一维搜索最佳步长,应满足,得:,2)再按DFP法构造点x1处的搜寻方向d1,需计算,代入校正公式,=,=,第二次搜寻方向为,再沿d1进行一维搜索,得,为一维搜索最佳步长,应满足,3)判断x2
12、是否为极值点,梯度:,海赛矩阵 :,梯度为零向量,海赛矩阵正定。可见点满足极值充要条件,因此为极小点。,4-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的负梯度的线形组合构成,即:,共轭条件:,则:,解得:,令,为函数的泰勒二次展开式,则,上两式相减,并代入,将式,与式,两边相乘,并应用共轭条件,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 无约束 优化 方法 白版
链接地址:https://www.31doc.com/p-3430025.html