机械优化设计无约束优化方法PPT课件

1、第四章 无约束优化方法§4-1最速下降法（梯度法）§4-2牛顿类方法§4-3变尺度法§4-4共辘方向法 §4-5鲍威尔方法§4-6其它方法（如坐标辂换法.单纯形法）点击此处输入相 关文本内容点击此处输入相 关文本内容标题添加点击此处输入相关文本内容标题添加点击此处输入相关文本内容第1章所列举的机械优化设计问题,都是在一定的限制条件下追求某一指标为最小,它们都属于约束优化 问题。工程问题大都如此。为什么要研究超束优化问题(1)有些实际问题,其数学模型本身就是一个无约束 优化问题。(2 )通过熟悉它的解法可以为研究约束优化问题打下良好的基

2、础。(3 )约字优化问题的求解可以通过一系列无约束优化 方法来达到。所以无约束优化问题的解法是优化设计方法的基本组成部分 > 也是优化方法的基础。(4 )对于多维无约束问题来说,古典极值理论中令 一阶导数为零但要求二阶可微,且要判断海赛矩 阵为正定才能求得极小点,这种方法有理论意义, 但无实用价值。和一维问题一样,若多元函数F(X) 不可微,亦无法求解。但古典极值理论是无约束优 化方法发展的基础。无约束优化问题是:求维设计变量使目标函数目前已研究出很多种无约束优化方法,它们的主要不同点在于构造搜盍方向上的差别。(1 )间接法一使用导数,如梯度法(阻尼) 牛顿法变尺度法、共辘梯度法等。(2

3、 )直接法不使用导数信息,如坐标轮换法. 鲍威尔法单纯形法等。用直接法寻找极小点时,不必求函数的导数,只要计 算目标函数值。这类方法较适用于解决变量个数较少的 (n<20)问题,一般情况下比间接法效率低。间接法除 要计算目标函数值外,还要计算目标函数的梯度,有的 还要计算其海赛矩阵。搜索方向的构成问题乃是无约束优化方法的关键。4-1梯度法基本思想:函数的负梯度方向是函数值在该点下降最快的方向。将n维问题转化为一系列沿负梯度 方向用_维搜索方法寻优的问题,利用负梯度作为 搜索方向,故称最速下降法或梯度法。搜索方向s取该点的负梯度方向-巧（兀）（最速下降方 向）,使函数值在该点附近的范围内下

4、降最快。为了使目标函数值沿搜索方向Vf (*)能够获得 最大的下降值,其步长因子应取一雍擾索的最佳 步长。即有根据一元函数极值的必要条件和多元复合 函数求导公式 得在最速下降法中,相邻两个迭代点上的函 数梯度相互垂直。而搜 索方向就是负梯度方向, 因此相邻两个搜索方向 互相垂直。这就是说在 迭代点向函数极小点靠 近的过程,走的是曲折 的路线。形成"之字 形的锯齿现象,而且越 接近极小点锯齿越细。图41最速下降法的搜索路径方法特点(1)初始点可任选,每次迭代计算量小,存储量少,程序简短。即使从一个不好的初始点出 发,开始的几步迭代,目标函数值下降很快, 然后慢慢逼近局部极小点。(2 )

5、任意相邻两点的搜索方向是正交的,它的迭代路径为绕道逼近极小点。当迭代点接近极小点时,步长变得很小,越走越慢。例4 - 1求目标函数冬的极小点。 解取初始点#则初始点处函数值及梯度分别为f(x°) = l(M沿负梯度方向进行一维搜索,有«(为_维搜索最佳步长,应满足极值必要条件算出一维搜索最佳步长第一次迭代设计点位置和函数值继续作下去,经io次迭代后,得到最优解je=p> cf /(x)=O这个问题的目标函数的等值线为一簇椭圆，迭代点从I走的是一段锯齿形路线,见图42。将上例中目标函数引入变换Ji=xp y2=5x2则函数f （力变为：必总0参七其等值线由椭圆变成一簇同

6、心圆。仍从兰=R可即岀发进行最速下降法寻优。此时：如二伽4 _2%_旳2003)=沿负梯度方向进行维搜索:y =y°心)io-410羽卩为_维搜索最佳步长,可由极值条件:由 <®e)=c00 =2652= 0.5从而算得一步计算后设计点的位置及其目标函数:yl = 2-40。-_0_10 200。0经变换后,只需一次迭代,就可找到最优解。 这是因为经过尺度变换:Ji =几儿二5.等值线由椭圆变成圆。梯度法的特点 (1)理论明确,程序简单,对初始点要求不严格。 (2)对一般函数而言,梯度法的收敛速度并不快,因为最速下降方向仅仅是指某点的一个同部性质。 (3)梯度法相邻两

7、次搜索方向的正交性,决定了迭代 全过程的搜索路线呈锯齿状,在远离极小点时逼近速度 较快,而在接近极小点时逼近速度较慢。 (4)梯度法的收敛速度与目标函数的性质密切相关。对于等值线(面)为同心圆(球)的目标函数,一次搜索即可达到极小点。4-2牛顿法及其改进基本思想：在/邻域内用一个二次函数0 （X）来近似代替原目 标函数,并愉（X啲极小点作为对目标函数/（X） 求优的下一个迭代点*:经多次迭代，使之逼近目 标函数/的极小点。牛顿法是求函数极值的最古老算法之设严为曲）的极小点这就是多元函数求极值的牛顿法迭代公式。对于二次函数,海赛矩阵躍一个常矩阵,其 中各元素均为常数。因此,无论从任何点出发,只

8、需_步就可找到极小点。例4 - 2求目标函数 心* 的极小点。 解取初始点分虫可经过一次迭代即求得极小点jcO函数极小值/(x)=0从牛顿法迭代公式的推演中可以看到,迭代点 的位置是按照极值条件确定的,其中并未含有沿下 降方向搜寻的概念。因此对于非二次函数,如果采 用上述牛顿迭代公式,有时会使函数值上升。阻尼牛顿法”邛且尼因子,沿牛顿方向进行一维搜索的最佳 步长,由下式求得:阻尼牛顿法程序框图(I)初始点应选在X*附近,有_定难度； (2 )若迭代点的海赛矩阵为奇异,则无法求逆矩阵,不能构造牛顿法方向；(3 )不仅要计算梯度,还要求海赛矩阵及其逆矩阵,计算量和存储量大。此外,对于二阶不可微的F

9、(£也 不适用。虽然阻尼牛顿法有上述缺点但在特定条件下它 具有收敛最快的优点,并为其他的算法提供了思路和 理论依据。梯度法与牛顿法:一般迭代式:梯度法:牛顿法:阻尼牛顿法:4-3变尺度法DFP变尺度法首先有戴维顿(Davidon )与鲍维尔(Powell )于1959年提出,又于1963年由弗莱彻(Fletcher )和鲍维尔加以发展和完善,成为现代公认的较好的算法之一。DFP法是基于牛顿法的思想又作了重要改进。这种算法仅用到梯度,不必计算海赛矩阵及其逆矩阵,但又能使搜索方向逐渐逼近牛顿方向,具有较快的收敛速度。1.基本思想2变量的尺度变换是放大或缩小各个坐标。通过 尺值时，需要进行

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

11、如AW则得到梯度法；如吕=|费0牙则得到阻尼牛顿法；当矩阵牡不断地迭代而能很好地逼近丘/x)r 时,就可以不再需要计算二阶导数。变尺度法的关键在于尺度矩阵肚的产生。对于二次函数:进行尺度变换 xQc目的：减少二次项的偏心在新的坐标系中,函数您0的二次项变为:如G是正定,则总存在矩阵Q ,使得:(2GQ=i用矩阵o右乘等式两边，得：2&用矩阵0左乘等式两边，得：QSGi 所以 Q2Y1上式说明：二次函数矩阵G的逆阵,可以通过尺度变换 矩阵0来求得。牛顿迭代公式:记：Off =力A称为变尺度矩阵搜索方向:迭代公式:在例4-2中2 0G 二如取0 501VT0O求得:5D(=2Alod.wl

12、p=Liuop>ECI )損d=<3 (IOBisg+0障廿鬲奴酬Iff縮幻罢要牡嗨鬲MQ1II首図取比(世星皐粉)世舉取sYfdp世舉愜必妈覆CM2 ) BFGS算法(Broyden-Fletcher-Gold frob- Shanno)DFP算法由于舍入误差和_维搜索不精确,有可能导致构造矩阵的正定性遭到破坏,以至算法不稳 定。BFGS算法对于维数较高问题具有更好的稳走 性。开始例43 :用DFP算法求下列问题的极值:解驾躺冷趣麟造第取初始变尺度矩阵为单位矩阵4。=八则第一次 搜寻方向为沿別方向进行_维搜索,得«、为一维搜索最佳步长,应满足得：r 9",二2

13、 ）再按DFP法构造点0处的搜寻方向/ ,需计算代入校正公式T-0.51-0.51 -0.53一_-4_2L &Q -413d Im再沿加进行一维搜索,得2 + crx2 = x1 =5 10.5 + a5 1”.为一维搜索最佳步长f应满足5,4得 °丨二一 厂二3 ）判断0是否为极值点梯度:海赛矩阵:4可见点满足极值梯度为零向量，海赛矩阵正定。 充要条件,因此为极小点。/3)=-«4-4共辘方向法1共辅方向：设G为mx阶实对称正定矩阵,如果有两个兀维 向量別和刃满足耳则称向量別与加关于矩阵G共辘。当G为单位矩阵时=C假设目标函数兀0在极值点附近的二次近似函数为对二

14、维情况任选取初始点疋沿某个下降方向/作一维搜索,得0因为«(是沿別方向搜索的最佳步长,即在点0处函数f ( X )沿方向別的方向导数为零。考虑到点0处方向导数与梯度之间的关系,故有如果按最速下降法,选择负梯度方向-巧住)为搜索 方向,则将发生锯齿现象O取下一次的迭代搜索方向/直扌旨极小点工*。如果能够选定这样的搜索方向,那么对于二元二次 函数只需顺次进行別.加两次直线搜索就可以求到 极小点兀*,即有那么这样的/方向应该满足什么条件呢？对于前述的二次函数：有当A71工乂方寸,也工0"是代工）极小点,应满足极值必要条件,故有b a *将等式两边同时左乘（r）r得：心心 =c就是

15、使/直指极小点h , di所必须满足的条件。 两个向量/和d】称为G的共辆向量,或称/和圧 对G是共觇方向。2.共辄方向的性质性质1若非零向量系別,小,d2,是对G共辘, 则这加个向量是线性无关的。性质2在兀维空间中互相共辘的非零向量的个数不超过仏性质3从任意初始点出发，顺次沿个G的共辘方 向別"，进行一维搜索,最多经过次迭代就可以找到的二次函数代兀）极小点。关键:新的共辘方向确定在无约束方法中许多算法都是以共觇方向 作为搜索方向 它们具有许多特点。根据构造 共觇方向的原理不同 可以形成不同的共觇方 向法。3.共辘梯度法共辘梯度法是共辘方向法中的一种,该方法中 每一个共辘向量都是依赖

16、于迭代点处的负梯度 而构造出来。从*出发,沿负梯度方向作一维搜索：设与冰共SS的下一个方向於14由冰和点冲的负梯 度的线形组合构成,即：则：解得：上两式相减 并代入为函数的泰勒二次展开式将式因此A =V/Cx"1)22V/(x):两边相乘，并应用共觇条件开始）例题44求下列问题的极值,已知初始点1, 1丫迭代精度解：1）第一次沿负梯度方向搜寻计算初始点处的梯度-4为一维搜索最佳步长,应满足得：久=0.2520.5V/(x') =-1-2IlVCf 202代入目标函数2）第二次迭代:=025由 0(Q=C得 &T从而有：因 |vR收敛。优化方法的演化一般迭代式:梯度法:

17、牛顿法:阻尼牛顿法:变尺度法:梯度法：共觇梯度法:冈(*)冈(严)4-5鲍威尔方法鲍威尔法是以共觇方向为基础的收敛较 快的直接法之一，是一种十分有效的算法。 1964年f鲍维尔提出这种算法f其基本思想 是直接利用迭代点的目标函数值来构造共觇 方向 然后从任一初始点开始”逐次沿共觇 方向作一维搜索求极小点。并在以后的实践 中进行了改进。基本思想:在不用导数的前提下,在迭代中逐次构造G的共辅方向。1共辅方向的生成设於，*+，为从不同 点出发,沿自一芳向 刃进行一维搜索而到 的两个极小点。豔畫蠶黑豔瞿黠和此E点另一方面,对于上述二次函数,其*,工如两点处的梯度可表示为:因而有取匕全y这说明只要沿d彷

18、向分别对函作两次一维搜索, 得到两个极小点卅和,那么这两点的连线所 给出的方向d僦是与亦一起对G共辘的方向。2.基本算法二维情况描述鲍威尔的基本算法:1 ）任选一初始点0, 再选两个线性无关的 向量,如坐*示轴单i立 向量匂=1, 0丁和 吁DIP作为初始 搜索方向。2 ）从x咄发,顺次沿匂 切作一维搜索,得X1时,X点两点连线 得一新方向加用/代替勺形成两个线性无关向量仑2，/ 作为 下一轮迭代的搜索方向。再：从出发,沿/作一 维搜索得点作为下一轮迭代的初始点。方法的基本迭代格式包括共辘方向产生和方向替换两主要步骤。把二维情况的基本算法扩展到维,则鲍威尔基本算法的要点是在每一轮迭代中总有一个

19、始点（第一轮的始点 是任选的初始点）和兀个线性独立的搜索方向。从 始点出发顺次沿个方向作一维搜索得一终点,由 始点和终点决定了一个新的搜索方向。用这个方向替换原来兀个方向中的一个,于是 形成新的搜索方向组。替换的原则是去掉原方向 组的第一个方向而将新方向排在原方向的最后。 此外规定,从这一轮的搜索终点出发沿新的搜索 方向作_维搜索而得到的极小点作为下一轮迭 代的始点。这样就形成算法的循环。上述基本算法仅具有理论意义 因为在迭代中的个搜索方向有时会变成线性相关而不能形成共辘方向。这时组不胁维空间, 可能求不到极小点,所以上述基本算法有待改进。3.改进的算法在鲍威尔基本算法中,每_轮迭代都用连结始

20、点和终点所产生出的搜索方向去替换原向量组中的第一个向量,而不管它的"好坏,这是产生向量组线性相关的原因所在。在改进的算法中首先判断原向量组是否需要 替换。如果需要替换,还要进一步判断原向量组中 哪个向量最坏,然后再用新产生的向量替换这个最 坏的向量,以保证逐次生成共辘方向。为此,要解决两个关键问题： (1)冰“是否较好?是否应该进入新的方向组? 即方向组是否进行更新? (2)如果应该更新方向组,小"不_定替换方向”而是有择地替触某向/ o令在肪欠循环中 人二f仃；)3川：)F厂川二)分别称为一轮迭代的始点.终点和反射点。则在循环中函数下降最多的第加次迭代是相应的方向为:o为

21、了构成共辘性好的方向组,须遵循下列准则:在肪欠循环中,若满足条件：F3<F0则选用新方向冰杠,并在第氐+1迭代中用冰+7替换对应于A 的方向i ：。否则，仍然用原方向组进行第氐+1迭代。这样重复迭代的结果,后面加进去的向量都彼此对G共辘,经兀轮迭代即可得到_个由个共辘方向所组成的方向组。对于二次函数,最多轮就可找到极小点,而对般函数,往往要超过兀轮才能找到极小点（这里他”表示设计空间的维数）。C结束）例4-5用改进的鲍威尔法求目标函数的最优解。已知初始点1,1 J迭代精度<sO3D解：（1）第1轮迭代计算1沿勺方向进行一维搜索_ 一c>得 二 2_以;为起点,沿第二坐标轴方向

22、%进行一维 搜索得&2=°5确定此轮中的最大下降量及其相应方向反射点及其函数值检验Powe 11条件由于满足Powell条件,则淘汰函数值下降量最 大的方向勺,下一轮的基本方向组为仑2 i :。构成新的方向315205沿（方向一维搜索得极小点和极小值此点为下轮迭代初始点。 按点距准则检验终止条件需进行第二轮迭代机算。 (2)第2轮迭代计算此轮基本方向组为勺丿: 分别相当于I人. 起始点为； =I ' O沿02方向进行一维搜索得以为起点沿(方向一维搜索得确定此轮中函数值最大下降量及其相应方向3 =Q08A=ooi£反射点及其函数值检验Powell条件f淘汰函数

23、值下降量最大的方向乞 即勺 > 下一轮的基本方向组应为”：匚。构成新的方向沿I方向进行一维搜索得 宀:冷）=仝检验终止条件(3 )第3轮迭代计算此轮基本方向组为1丿,起始点为J二先后沿/:丿方向,进行一维搜索,得检验终止条件憶占|=Cte 实际上,前两轮迭代的（J;为共辘方向,由于J本例目标函数是二次函数,按共辘方向的二次收敛性,故前两轮的结果就是问题的最优解但每一轮迭代都进行卄1次迭代。§4-6其它方法(如坐标轮换法.单纯形法)前面介绍的许多优化方法,除鲍威尔(Powell) 法外,都需要计算目标函数的导数,而在实际工程的 最优化问题中,目标函数的导数往往很难求出或者根 本无

24、法求出。下面所介绍的方法只需要计算目标函数 值,无需求其导数,因此计算比较简单,其几何概念 也比较清晰,属于直接法的无约束最优化方法。这类 方法适用于不知道目标函数的数学表达式而仅知其具体算法的情况。这也是直接法的一个优点。坐标轮换法坐标轮换法的基本思想:是将一个n维优化问题转化为 依次沿n个坐标方向反复进行一维搜索问题。这种方法的实 质是把n维问题的求优过程转化为对每个变量逐次进行一维 求优的循环过程。每次一维搜索时,只允许n个变量的一次改动,其余(nl)个变量定不变。故坐标轮换法也常称单变 量法或变量交错法。坐标轮换法此法的效能在很大程度上取决于目标函数的性质。X。方法特点(1)计算量少程

25、序简单,不需要求函数导数的直接 探索目标函数最优解的方法；(2 )探索路线较长,问题的维数愈多求解的效率愈低。 当维数n> 10时,则不应采用此法。仅适用于11较少(n <10 )的目标函数求优；(3 )改变初始点重新迭代,可避免出现病态。（开始）步长加速法（Hook-Reeves算法）_步长加速法原理步长加速法也称之为离散步长的Hook-Reeves算法, 是一种不使用导数的直接搜索算法,其算法过程可分成 两个基本阶段:坐标循环试探及模矢加速搜索。见下图, 从初始探点Y。出发,依次沿n个坐标方向用固定步长进 行试探,寻找更好的点年矢加速搜索,就是沿模矢方向X加涉长前进,以得到第k

26、+1次迭代的出发点Y。,这样就完成了一次迭代 然后再从新的Y。出发,进行下一轮坐标循环试探,如此 重复进行,使目标值不断减小。二步长加速法算法设问题为X。为初始点f弓局 弓依 次舟坐标轴的单位方向向量, 初始坐标循环试探的步长为>（），模矢加速搜索的加速步长 因子为a>l （通常取a=2 ） f迭代终止准则为矣£为预妊确定的正数）O（1）（2）窃彳宀字，珈沪字）gp»,集它?清形（3 ）若片十土令4车（2）；否则，转（4 ）否则转（6 ）否则令（6） 孝詰希娜舉!九丘伸闭否则,转（2 ）NuXo开始/(ro)<(x>+i)/(ro)<(x>

27、;+i)从Yo岀发，依次沿&试探.碍丫八直到匕/(*)2/(Yo)X，+】u匕Yo = X +a(X»+iXQ/(ro)<(x>+i)梯度法：共觇梯度法:冈(*)冈(严)鲍威尔（Powell）法共觇法直接法鲍威尔法原理,如何构成共辘方向？ !鲍威尔（Powell）法共觇法直接法鲍威尔（Powell）法共觇法直接法坐标轮换法直接法步长加速法（Hook-Reeves算法）OxOxx2LOx单纯形方法基本思想切彎負换法也是一种不使用导数的求解无 翘束极小化问题的直接搜索方法,与前面几种方 法交舉聖養書纯戋替换法不是利用搜索方向幷 二£庶售代到另一个更优的点，而

28、是从一个单纯 形迭代到另一个更优的单纯形。定义:单纯形M雇空前中的恰好有M+1个顶点（极点）的有界的 凸多面体称之为一个单纯形。根据定义,可知,维空间中的单纯形是线段, 二维空间中的单纯形是三角形,而三维空间中的单纯 形则是四面体。在单纯形替换算法中,从一个单纯形到另一个单 纯形的迭代主要通过反射.扩张、收缩和缩边这4个操 作来实现。下面以二维问题为例来对4种操作进行说明 （参见卞图）O儿（3 ）收缩一一在得到反射点X5之后f如果有(1)反射设除了最劣点X以外的基余顶点的中心为X4，作X关于点X4的对称点X5 ,称X5为X的反射点。求反射点的过程称之为反射。(2 )扩张一一在得到反射点X5之后

29、f如果X5优于原单纯形的最劣 点(即有f表明反射方向(x-x1)是有利方向 反射成功。若逬一步有沿反射方向前进适当的距离到点x“ X6称之为扩桑点；求秆张融过程称之为扩张。扩 张之后,若扩张点X6优于反射点X5 ,则扩张成功,以X6取代X #得 新单纯形X“ X2, X3；否则f扩张失败f舍弃扩张点,以反射X5点 取代X,得新单纯形X5, X2, X3 o表示反射部分成功Z方向（X5X）虽然是有利方向，但X5前 进过远,应收缩到介于X4与X5之间的某个点X“如果出现/闪三心）o表示反射完全失败，应退回到介于X4 与X之间的某个点X&。上述两种从反射点向X】方向后退的过程都称之为收缩。如

30、果收缩点优于原来的最劣点X一称收缩成功,并以收缩点取代原最劣点,构成新单纯形徑7疋2正3或凶兀兀；否则f称之为收缩失败,舍弃收缩点。(4 )缩边若收缩失败,则应压缩当前单纯形的边长:令最优点X3不动,而其余顶点向X3方向压缩,使边长缩短(通常缩 短一半),以产生新单纯形。如下图所示,点X压缩到点X9 ,点X2压缩到点X10 ,得新单纯形X9，X1O，X3,这一过程称之为缩边。二单纯形替换算法设初始点为X。,初始边长力,为坐标轴方向的单位向量中，预定正数&1，&2(2 )比较各项点心的函数值,挑出其中的最优点,记为Xl ；最劣 点,记Xh ；次差点,记为人；1 n(3 )求皮射中心禾口反身克磊X卄=-工Xni=O(4)根据不同情况，分别进行扩张，vv、收缩或缩边,其中收缩因子= X曲Q=Q%造新单纯形；'其中,a>0,通常取吐1 ；n2(5 )如果满足 工/(XJ/(X2Z=1输出孔,为原问题近似极小点；否则，转(2 )。（开（开的出初始单纯各顶点XX/ = O. 1.2.丄）儿人广/（勺1>G*"（-VG）收缩.qv«4 I 个 0(X»m2 xm | ) /«» 4 /