无约束优化方法.ppt

《无约束优化方法.ppt》由会员分享，可在线阅读，更多相关《无约束优化方法.ppt（101页珍藏版）》请在三一办公上搜索。

1、第三章无约束问题的最优化方法,3.1 引言 3.2 一维搜索方法 3.3 坐标轮换法、共轭方向法和Poweel法 3.4 梯度法和共轭梯度法 3.5 牛顿法和变尺度法 3.6 单形替换法 3.7 无约束优化设计方法小结,3.1 引言,一.目的：,求一组 n 维设计变量 X=x1,x2,x n T,使目标函数达到 min.f(x)XRn即求目标函数的最优解：最优点 x*和最优值 f(x*)。,二.意义：,为约束优化方法的研究提供了策略思想、概念基础和基本方法；为约束优化问题的间接解法提供了有效而方便的方法；对于某些工程问题，进行分析后，便于提供解决的有效方法；约束优化问题的求解往往可以通过一系列

2、无约束优化方法实现；无约束优化问题的解法是优化设计方法的基本组成部分。,3.1 引言,三.内容：,一维搜索：求最优步长因子(k),多维（变量）优化：确定搜索方向 S(k),黄金分割 切线法 平分法插值法 格点法,坐标轮换法 最速下降法共轭方向法 鲍威尔法梯度法 共轭梯度法牛顿法 单形替换法变尺度法,3.1 引言,四.无约束优化方法计算步骤：,1、选择一个初始点x(0)，这一点越靠近极小点x*越好。2、若已经取得某设计点x(k)，并且该点不是近似极小点，则在x(k)点根据函数f(x)的性质，选择一个方向S(k)，并且沿此方向搜索函数值是下降的，称下降方向。3、当搜索方向S(k)确定后，由x(k)

3、点出发，沿S(k)方向进行搜索，定出步长因子(k)，得到新的设计点：x(k+1)=x(k)+(k)S(k)，并满足f(x(k+1)f(x(k)4、若x(k+1)满足迭代计算终止条件，x(k+1)点作为x*；否则从该点出发，返回第二步继续搜索迭代。,开始,给定x和S的初始值,计算使 f（x+S）极小,x x+S,满足收敛条件？,结束,形成新的S,无约束优化算法粗框图,无约束优化数值计算方法采用的是搜索方法，其基本思想是从给定的初始点出发，沿某一个搜索方向进行不断的搜索，确定最佳步长使函数值沿搜索方向下降最大，其迭代公式为 x(k+1)=x(k)+(k)S(k)各种无约束优化方法的区别在于确定其搜

4、索方向的S(k)的方法不同。所以，搜索方向的构成问题是无约束优化问题的关键。,五.无约束优化方法的关键问题：,3.1 引言,六.无约束优化方法的分类：,3.1 引言,无约束优化方法的分类依据就是根据(k)和S(k)的确定方法而定的。若根据构成搜索方向所使用的信息性质的不同，可以分为两类。1、间接法 又称解析法，是利用目标函数导数的无约束优化方法，如最速下降法、共轭梯度法、牛顿法及变尺度法等。2、直接法 只利用目标函数值的无约束优化方法，如坐标轮换法、鲍威尔法及单形替换法等。,3.2 一维搜索方法,一.一维搜索：,定义:在第K次迭代时，从已知点 X(k)出发，沿给定方向求最优步长因子(k)，使

5、f(X(k)+S(k)达到最小值的过程，称为一维搜索。,方法：,1.解析法：,f(x(k+1)=min.f(x(k)+S(k)=f(x(k)+(k)S(k),步骤:f(X(k)+S(k)沿S(k)方向x(k)台劳展开；取二次近似：,对求导，令其为零。,2.数值迭代法：,直接法应用序列消去原理：分数法、黄金分割法近似法利用多项式函数逼近（曲线拟合）原理：二次插值法、三次插值法,求得最优步长因子：,3.2 一维搜索方法,二.迭代法求解一维搜索问题的基本思想：,先选定一个初始点x0，从x0出发沿某一选定方向p0求f(x)的极小点，设其为x1；然后再从x1出发沿某一选定方向p1求f(x)的极小点，设其

6、为x2；如此下去，从xk出发沿某一选定方向pk求的极小点xk+1，直到求得的xk满足要求为止。求得的值是逐渐下降的：称pk为第k次的搜索方向，因此，在过xk的pk方向上，任意一点可以表示为x=xk+t*pk，目标函数值为f(xk+t*pk)，目标函数实际上成了一元函数。所以沿pk方向求f(x)的极小点，就是求一元函数f(xk+t*pk)的极小问题，表示为：,总结：将优化问题转化为一系列的一维搜索问题,3.2 一维搜索方法,沿方向S的一维搜索,3.2 一维搜索方法,单峰区间解析概念：,在区间 1，3 内，函数只有一个峰值，则此区间为单峰区间。单峰区间内，一定存在一点*，当任意一点2*时，f(2)

7、f(*)，,说明：单峰区间内，函数可以有不可微点，也可以是不连续函数；,三.搜索区间的确定：,f(x),0,1,3,0,f(x),3,1,f(),3,2,*,1,0,当2*时，仍有f(2)f(*)，则*是最优点，也即为最优步长因子(k)。,2,确定的搜索区间必定是一个含有最优点*的单峰区间。,3.2 一维搜索方法,2。单峰区间几何概念：,指函数在区间内只有一个极小点。在极小点左边的函数值应是严格下降，在极小点右边的函数值应是严格上升，即单峰区间内的函数值具有的特征是：“高低高”。,进退法确定的单峰区间,三.搜索区间的确定：,3.2 一维搜索方法,3.定步长搜索法:,4.加速步长搜索法：,f 2

8、=f(1+t0),1,f1,解：计算试点,例3-1 用进退法求单变量函数 的搜索区间。初始点，步长,比较两试点函数值，由于 作前进搜索,比较两试点函数值，由于 作前进搜索,比较两试点函数值，由于 作前进搜索,此时，三个试点 函数值已经出现“高低高”特征，得搜索区间为,3.2 一维搜索方法,四.黄金分割法(0.618)：,1.序列消去原理：,f(),3(1),12,*,1(1),0,3(2),11,21 22,1(2),1(3),3(3),3.2 一维搜索方法,黄金分割法消去示例：,3.2 一维搜索方法,2.黄金分割与0.618：,b,d,古希腊建筑师认为：边长为 b，d 的矩形建筑物，若边长能

9、符合以下条件，则最美观：,欧几里德几何称这种边长分割为黄金分割。,序列消去法中，为提高效率，减少计算量和存储量，希望,黄金分割法的算法框图,解：在搜索区间内取两试点并且计算它们函数值,比较两试点函数值，缩短搜索区间，由于，消去右区间，令：,例3-2 用黄金分割法求单变量函数 的极小点。初始搜索区间，迭代精度,判断迭代终止条件：,不满足迭代终止条件。再取两试点并且比较它们的函数值，继续缩短搜索区间。搜索区间经过6次缩短（中间迭代过程略）后，区间长度为：,可以终止迭代，得到近似极小点和最优解,3.2 一维搜索方法,五.二次插值法（抛物线法）：,1.基本原理：,步骤：,3.2 一维搜索方法,2.步骤

10、(续)：,3.结果分析：,问题：若不满足精度，如何缩小区间，再拟合（分四种情况分析）？,令：,单谷搜索区间缩短情况,入口,xp*x2?,f2*fP*?,f2fP*?,x3 x2 f3 f2x2 xp*f2 fP*,x1 x2 f1 f2x2 xp*f2 fP*,出口,Y,Y,Y,N,N,N,a,b,c,d,二次插值法区间缩短流程图,3.2 一维搜索方法,与黄金分割法相比，二次插值法充分利用函数值的信息；收敛快；调用函数次数少。,4.方法评价:,5.迭代终止条件:,当满足如下两个条件，可终止迭代：,如果 和 两点的距离很小，即：,如果 和 充分接近，即：,二次插值法的算法框图,解：1）确定初始插

11、值结点与函数值,2）计算插值函数极小点,例3-3 用二次插值法求一维函数 的最优解。初始单谷搜索区间，迭代精度,由于判别式成立，表明 落在单谷搜索区间之内,3）缩短单谷搜索区间,由于 和，则舍弃左边的区间，构成缩短后的新搜索区间。即：,4）检验迭代终止条件,满足迭代终止条件，输出最优解,六.切线法：,一维搜索函数，假定已给出较好的近似点，连续可微的函数在极小点附近与一个二次函数很接近，所以可以在 附近用一个二次函数 来逼近函数：,以二次函数 的极小点作为 极小点的一个新近似点，根据极值必要条件：,3.2 一维搜索方法,解：1)求函数的一阶、二阶导函数：,例3-4 给定函数，初始值为，控制误差，

12、试用切线法求其极小点。,2)求,3)求,4)迭代值如下：,切线法流程图,N,Y,开始,结束,k=k+1,给定k=0,.收敛速度快；.需要计算函数的一阶和二阶导数，增加迭代工作量；.要求初始点选得比较好，离极小点不远，否则有可能使极小化序列发散或收敛到非极小点。,切线法优缺点:,3.2 一维搜索方法,3.2 一维搜索方法,取具有极小点的单峰函数的探索区间a,b的坐标中点 作为计算点，计算目标函数在该点处的导数为，并利用函数在极小点处的导数为零而在其左侧为负、右侧为正的原理，来判断极小点所在的那一半探索区间，以消掉另一半区间。这样逐次迭代下去，总能将探索区间收敛到一个局部极小点附近，求得极小点的近

13、似解。收敛速度虽然较慢，但缩短率也达到0.5，特别是每次迭代计算量较少，可靠性较好，所以仍然是一个受欢迎的方法。,七.平分法：,3.2 一维搜索方法,平分法的迭代计算步骤:,给定计算，若，则停止迭代并取 否则进行下一步。计算，若 或，则停止迭代并取 若 则取 为缩短后的搜索区间 转第二步 若 则取 为缩短后的搜索区间 转第二步,当 求解困难时:,可直接计算 并比较两者大小，用序列消去法原理消去掉近一半的区域，再重新迭代，直到将探索区间缩短至精度要求为止。,例3-5 试用平分法求 的极小点和极小值，设,解：1)取,2)计算,3)缩短搜索区间为 取,4)计算,5)所以函数的极小点为,极小值为:,3

14、.2 一维搜索方法,设一维函数为f(x)，搜索区间为a,b，一维收敛精度为。在区间a,b的内部取n个等分点：x1,x2,xn。区间被分为n+1等分，各分点坐标为对应各点的函数值为y1,y2,yn+2。比较其大小，取最小者ym=minyk,k=1,2,n2，则在区间xm-1,xm+1内必包含极小点，取xm-1,xm+1为缩短后新区间，若新区间满足收敛条件:x m+1-xm+1，则最优解为x*=xm，y*=ym 若不能满足精度要求，把当前区间作为初始搜索区间，重复上述步骤直至满足精度为止。,八.格点法：,新区间,y1,ym-1,ym,ym+1,Yn2,x1,a,xm-1,xm,xm+1,Xn2,b

15、,格点法区间搜索原理,格点法流程图,Y,N,开始,p=y,m=k,yp,给定,m=0,k=1，p=足够大的数,k=n,k=k+1,|b-a|,N,Y,Y,N,相同点：都是利用区间消去法原理将初始搜索区间不断缩短，从而 求得极小点的数值近似解。不同点：试验点位置的确定方法不同。直接法中试验点的位置是由某种给定的规律确定的，并未考虑函数值的分布。黄金分割法是按照等比例0.618缩短率确定的，仅仅利用了试验点函数值进行大小的比较；间接法中，试验点的位置是按函数值近似分布的极小点确定的，利用了函数值本身或其导数信息。当函数具有较好的解析性质时，间接方法比直接方法效果更好。,3.2 一维搜索方法,九.间

16、接法与直接法的异同点：,3.2 一维搜索方法,1.掌握进退法确定单谷搜索区间；2.掌握黄金分割法的原理和程序设计；3.掌握二次插值法的原理和程序设计；4.掌握切线法的原理和流程；5.了解平分法和格点法。,十.学习要求：,试用二次插值法求 的近似极小点和极小值，已知,十一.习题：,一.坐标轮换法：,1.基本思想：,2.搜索方向与步长：,每次以一个变量坐标轴作为搜索方向，将n维的优化问题转化为一维搜索问题。例，第k轮迭代的第i次搜索，是固定除xi外的n-1个变量，沿xi变量坐标轴作一维搜索，求得极值点 xi(k)n次搜索后获得极值点序列x1(k),x2(k,xn(k)，若未收敛，则开始第k+1次迭

17、代，直至收敛到最优点x*。,3.3 坐标轮换法、共轭方向法和Poweel法,一.坐标轮换法：,3.方法评价：,方法简单，容易实现。当维数增加时，效率明显下降。收敛慢，以振荡方式逼近最优点。,受目标函数的性态影响很大。如图 a)所示，二次就收敛到极值点；如图 b)所示，多次迭代后逼近极值点；如图 c)所示，目标函数等值线出现山脊（或称陡谷），在脊线的尖点A处没有一个坐标方向可以使函数值下降，只有在锐角所包含的范围搜索才可以达到函数值下降的目的，故坐标轮换法对此类函数会失效。,3.3 坐标轮换法、共轭方向法和Poweel法,i=n,坐标轮换法的流程图,开始,给定：x0,k=1,i=1,x0k=x0

18、,xik=x0k-1,沿ei方向一维搜索求ixik=xi-1k+ikeix=xk f=f(x),|xnk-x0k|,x*=x f*=f(x*),结束,i=i+1,x0k+1=xnk,k=k+1,N,Y,N,Y,此问题可用一维优化方法求解，这里用微分学求解：,解：1.作第一轮迭代计算,得：,1)沿e1方向进行一维搜索,例4-1 用坐标轮换法求目标函数 的无约束最优解，给定初始点，精度要求,其中 为第一轮的起始点。取：,按最优步长原则确定,2)以 为新起点，沿e2方向一维搜索：,按最优步长原则确定,得：,3)按迭代终止条件检验,2.作第二轮迭代计算，如此共进行9轮得到结果,二.共轭方向法：,1.共

19、轭方向的由来：,2.共轭方向的定义：,共轭方向概念是在研究具有正定矩阵G的二次函数,的极小化问题时形成的。其基本思想是在不用导数的前提下，在迭代中逐次构造G的共轭方向。,3.3 坐标轮换法、共轭方向法和Poweel法,3.共轭方向法的二次收敛性：,正定的二元二次函数的等值线为一组椭圆，任选初始点x0，沿某个下降方向S0作一维搜索，得x1,此时，x1点的梯度必然与方向S0垂直，即有：,S0与某一等值线相切于x1点。下一次的迭代，若选择负梯度方向为搜索方向，将产生锯齿现象。为避免锯齿的产生，我们取迭代方向S0直指极小点x*，如图所示。若选定这样的方向，则对于二元二次函数只需进行S0 和S1两次搜索

20、就可以求得极小点x*，即,3.3 坐标轮换法、共轭方向法和Poweel法,3.共轭方向法的二次收敛性（续）：,由于，当 时，由 是 的极小点，应满足极值必要条件，故 即：,等式两端同乘以,得，故两个向量，是G的共轭向量。,因此，若要使第二个迭代点成为正定二元二次函数的极小点，只要使两次一维搜索的方向，关于函数的二阶导数矩阵G共轭就可以了。对于正定二次n维函数，从任意的初始点出发，沿着这n个共轭方向进行一维搜索，就可以得到目标函数的极小点。因此，对于二次函数来说，经过n步搜索就可以达到函数的极小点。对于非二次n维函数，可以用二阶泰勒级数将函数在极小点附近展开，省略去高于二次的项后可以得到函数的二

21、次近似，同样按照二次函数构成共轭方向。,3.3 坐标轮换法、共轭方向法和Poweel法,4.二维函数的共轭方向：,二维函数，任意给定某个方向，按这个方向上的两条平行线进行一维搜索求得的极小点为 和，它们应该是方向为 的两条平行线与目标函数等值线的切点。,连接两个切点 和 构成向量：,可以证明，如果二维函数的海塞矩阵H是正定的，则S1向量与向量S2满足条件：,具有这种性质的方向为关于正定矩阵H的共轭方向。,3.3 坐标轮换法、共轭方向法和Poweel法,所以有：,4.二维函数的共轭方向（续）：,证明：,设二维函数在极值点X*附近的二次泰勒展开式为：,由此得函数的一阶导数：,由于S1为等值线的切线

22、，故方向S1应垂直于X(1),X(2)的梯度方向：,3.3 坐标轮换法、共轭方向法和Poweel法,所以有：,4.二维函数的共轭方向（续2）：,两式相减得：,由，上式可简化为：,3.3 坐标轮换法、共轭方向法和Poweel法,5.二维函数共轭方向法的迭代过程：,1.令循环次数k1，取初始点，初始搜索方向为坐标方向,4.取下次循环的初始点，替换掉原来的第一方向，构成新的搜索方向：,5.k=k+1，转步骤2。,2.从 出发，依次沿 和 进行一维搜索，分别得到相应的极小点 和。,3.构建新方向，沿 方向进行搜索，得到第k次的极小点,3.3 坐标轮换法、共轭方向法和Poweel法,6.多维二次函数共轭

23、方向的构建：,如果n维函数的海赛矩阵是正定的，一组非零向量 满足：,则向量系：是关于海赛矩阵H共轭，即他们是n个互为共轭的方向。,3.3 坐标轮换法、共轭方向法和Poweel法,8.方法评价：,计算步骤复杂;是二次收敛方法，收敛快。对非正定函数，也很有效;是比较稳定的方法。,7.说明：,若是正定二次函数，n 轮迭代后收敛于最优点 x*。若是非正定二次函数，则迭代次数增加。,若是 n 维问题，步骤相同。搜索方向：第一轮迭代，沿初始方向组 Si(1)(i=1,2,n)的 n 个方向和共轭方向 S(1)，搜索 n+1 次得极值点 xn+1(1)；第二轮迭代，沿方向组 Si(2)(i=1,2,n；im

24、)的 n-1 个方向和共轭方向 S(1)，构筑共轭方向 S(2)搜索 n+1次得极值点 xn+1(2)。其中，为保证搜索方向的线性无关，去除了 Sm(2)方向。,在第 k 轮迭代中，为避免产生线性相关或近似线性相关，需要去除前一轮中的某个方向 Sm(k)。去除的原则请自学。,3.3 坐标轮换法、共轭方向法和Poweel法,共轭方向法的程序框图,9.共轭方向法的缺陷：,共轭方向法的迭代过程可能会产生不理想的情况，在以后某环的迭代中可能出现基本方向组为线性相关向量系。以后的搜索将在维数下降后的设计空间中进行，无法收敛到n维设计空间中目标函数的极小点。,以三维问题为例，设从初始点 出发，沿着坐标轴方

25、向，进行第一环搜索，在各个方向获得极小点为：,由该环搜索的初始点 与终点 产生的新生方向：,3.3 坐标轮换法、共轭方向法和Poweel法,9.共轭方向法的缺陷（续）：,如果其中第三维优化步长 等于或非常接近0，即表示沿着则坐标轴方向 的搜索没有前进或前进很少，则共轭方向：,表明向量 与向量 是线性相关的。,第2环搜索的基本方向组 中，是 与 线性相关或接近线性相关，即向量 在 和 组成的平面内。以后的搜索将在维数下降（不包含方向）的平面中进行，无法收敛到 空间中目标函数 的极小点。,3.3 坐标轮换法、共轭方向法和Poweel法,三.Poweel法：,1.基本步骤：,1.给定初始点，选取由n

26、个线性无关的向量 组成的初始方向组，置。,2.从 出发，顺次沿 作一维搜索得。接着以 为起点，沿方向：移动一个 的距离，得到：,分别称为一轮迭代的始点、终点和反射点。它们所对应的函数值分别为：,同时计算各中间点处的函数值，并记为：,3.3 坐标轮换法、共轭方向法和Poweel法,3.3 坐标轮换法、共轭方向法和Poweel法,1.基本步骤（续）：,计算n个函数值之差：,3.为了构造第k1环基本方向组，采用如下判别式：,按以下两种情况处理：,其中最大者记作：,鲍威尔判别式,a.上式中至少一个不等式成立，则第k+1环的基本方向仍用老方向组.,k+1的环初始点取:,1.基本步骤（续2）：,b.两式均

27、不成立，则淘汰函数值下降最大的方向，并用第k环的新生方向补入k+1环基本方向组的最后，即k+1环的方向组为：,k+1环的初始点取，是第k环沿 方向搜索的极小点。,3.3 坐标轮换法、共轭方向法和Poweel法,鲍威尔法的流程图,一.梯度法（最速下降法）：,1.基本思想：,2.负梯度方向为最速下降方向的证明：,目标函数负梯度向量方向代表最速下降方向，因此选择负梯度向量方向为搜索方向，期望很快找到最优点。,S,由方向导数概念可得：,设：,取最小值1时，S为梯度的负方向。,3.4 梯度法和共轭梯度法,4.迭代格式：,3.搜索方向：,a.任意给定一个初始步长，使其满足：,根据一元函数的极值必要条件和多

28、元复合函数的求导公式，得：,或,负梯度方向 或单位负梯度向量,5.最佳步长 的选取：,b.沿负梯度方向作一维搜索，求最佳步长，对目标函数求极小，以得到最佳步长：,即：,3.4 梯度法和共轭梯度法,最速下降法向极小点的逼近路径是锯齿形路线，越接近极小点，锯齿越细，前进速度越慢。这是因为，梯度是函数的局部性质，从局部上看，在该点附近函数的下降最快，但从总体上看则走了许多弯路，因此函数值的下降并不快。,5.最佳步长 的选取（续）：,此式表明，相邻的两个迭代点的梯度是彼此正交的。也即在梯度的迭代过程中，相邻的搜索方向相互垂直。,6.搜索路径：,3.4 梯度法和共轭梯度法,（1）任选初始迭代点x(0)，

29、选收敛精度。（2）确定x(k)点的梯度(开始k=0)。（3）判断是否满足终止条件，若满足输出最优解，结束计算。否则转下步。（4）从x(k)点出发，沿 方向作一维搜索求最优步长(k)。得下一迭代点。令k=k+1 返回步骤（2）。,7.迭代终止条件：,采用梯度准则：,8.迭代步骤：,3.4 梯度法和共轭梯度法,梯度法流程图,N,Y,开始,给定：x(0)，,k=0,x*=x(k)f*=f(x(k),结束,x(k)=x(0),k=k+1,3.4 梯度法和共轭梯度法,9.方法评价：,迭代过程简单，对初始点的选择，要求不高。梯度方向目标函数值下降迅速只是个局部性质，从整体来看，不一定是收敛最快的方向。以二

30、维二次函数为例，相邻两次的搜索方向是正交的，所以搜索路径是曲折的锯齿形的；对于高维的非线性函数，接近极值点处，容易陷入稳定的锯齿形搜索路径。,例4-1 二维无约束目标函数 试用梯度法求其极小值，初始点，精度,解：1）计算目标函数在初始点的梯度、梯度的模和单位负梯度方向,2）计算最佳搜索步长,3）计算第一次迭代更新值和目标函数值,4）当迭代7次时，满足终止条件，得到最有值,3.4 梯度法和共轭梯度法,二.共轭梯度法（旋转梯度法）：,1.基本思想：,2.共轭方向：,对梯度法作一个修正，将搜索方向由负梯度方向旋转一个角度，使相邻的两次搜索方向由正交变为共轭，成为二次收敛。,3.共轭系数：,推导过程请

31、自学。,(k)S(k),步骤：,5.方法评价：,迭代程序简单，容易实现，存储量较小。开始采用梯度方向，目标函数值下降快，后又为旋转梯度方向，具有二次收敛速度，收敛快。,3.4 梯度法和共轭梯度法,开始,k=0，计算：-f(x0),|f(xk+1)|？,结束,求(k)，x(k+1)=x(k)+(k)S(k),计算：f(xk+1),x*=xk+1f(x*)=f(xk+1),Y,N,给定：x(0)，,k n？,x0=xk+1,Y,N,Sk+1=-f(xk+1)+kSk,K=K+1,共轭梯度法流程图,例4-2 二维无约束目标函数 试用共轭梯度法求其极小值，初始点，精度,解：1）计算目标函数在初始点的梯

32、度、梯度的模和单位负梯度方向,2）计算新迭代点的梯度和搜索方向的修正量，进行第2次搜索,可见，共轭梯度法具有两次收敛性，对于二维函数只要经过两次迭代就可以达到极值点。,3.5 牛顿法和变尺度法,一.牛顿法（二阶梯度法）：,1.基本思想：,将 f(x)在 x(k)点作台劳展开，取二次函数式(x)作为近似函数,以(x)的极小值点作为 f(x)的近似极小值点。,说明：,f(x)若是正定二次函数，一般迭代一次即可；若是严重非线性函数，则可能不收敛，或收敛到鞍点。,2.修正牛顿法（阻尼牛顿法）：,一.牛顿法（二阶梯度法）：,可通过如下极小化过程求得：,避免了迭代后函数上升的现象，保持了牛顿法二次收敛的特

33、性，对初始点的选取并没有苛刻的要求。,阻尼牛顿法的计算步骤：,1）给定初始点，收敛精度，置,3.5 牛顿法和变尺度法,3.5 牛顿法和变尺度法,3.方法评价：,使用牛顿法时，若目标函数是严重非线性函数，则是否收敛将与初始点有很大关系；而使用修正牛顿法，能保证每次迭代目标函数值下降，从而放宽了对初始点的要求。若初始点选得合适，牛顿法的收敛速度相当快。牛顿法求逆矩阵的工作量大，计算量与存储量均随 n2上升。,3）求，其中 为沿 进行一维搜索的最佳步长,4）检查收敛精度。若，则，否则，令，返回2）继续进行搜索。,2）计算：,阻尼牛顿法流程图,3.5 牛顿法和变尺度法,变尺度法也称拟牛顿法，它是基于牛

34、顿法的思想而又作了重大改进的一类方法。,梯度法只需计算函数的一阶偏导数，计算量小，当迭代点远离最优点时，函数值下降很快，但当迭代点接近最优点时收敛速度极慢。,DFP变尺度法是由Davidon于1959年提出的一种变尺度法；BFGS变尺度法是由Broydon等提出的改进算法，提高了算法的稳定性。,牛顿法不仅需要计算一阶偏导数，而且要计算二阶偏导数及其逆阵，计算量很大，但牛顿法具有二次收敛性，当迭代点接近最优点时，收敛速度很快。,若迭代过程先用梯度法，后用牛顿法并避开牛顿法的海赛矩阵的逆矩阵的烦琐计算，则可以得到一种较好的优化方法，这就是“变尺度法”产生的构想。,一.变尺度法:,3.5 牛顿法和变

35、尺度法,二.DFP 变尺度法:,1.变尺度的定义：,每确定一次搜索方向，调整一次模（尺度）的大小，称为变尺度。,2.基本思想：,发扬梯度法和牛顿法各自的优点，避免两者各自的缺点，将两者结合起来，形成变尺度法。,3.5 牛顿法和变尺度法,3.变尺度矩阵的构造：,原则：使目标函数值有下降性，则变尺度矩阵应为实对称矩阵（请证明）；使算法有二次收敛性，则 S(k)(k=1,2,)应关于 H(k)是共轭的；,构造变尺度矩阵的递推公式：,4.修正矩阵:,3.5 牛顿法和变尺度法,步骤：,1、选定初始点和收敛精度；2、计算初始点处的梯度，选取初始对称正定矩阵A0，置k=0；3、计算搜索方向Sk=-Akgk；

36、4、沿Sk方向一维搜索，计算gk+1、sk=xk+1-xk、yk=gk+1-gk。5、判断是否满足终止准则，若满足输出最优解，否则转6。6、当迭代n次还未找到极小点，重置Ak为单位矩阵，并以当前点为初始点返回2，否则转7。7、计算Ak+1=Ak+Ak，置k=k+1返回3。,6.方法评价：,DFP变尺度法以逐次逼近的方法实现 H-1 的计算，当目标函数的一阶导数易求时，以一阶代替二阶导数的计算是有效的方法。算法的第一步是梯度法，最速下降；接近 x*时，又采用二次收敛的共轭方向，总的收敛速度较快。H(k)近似代表 x(k)点的二阶导数，当其为零时，可判断 x(k)为鞍点。H(k)的计算较复杂，存储

37、量较大。算法稳定性较差，由于计算机有舍入误差，容易使 H(k)的正定性破坏，趋于奇异。,3.5 牛顿法和变尺度法,DFP变尺度法流程图,例4-3 二维无约束目标函数 试用DFP算法求其极小值。,解：1）取初始点，为了按DFP法构造第一次搜索方向，需要计算初始点处的梯度：,并取初始变尺度矩阵为单位矩阵A0=I，则第一次搜索方向为：,沿 方向进行一维搜索，得：,其中，为一维搜索最佳步长，应满足：,2）再按DFP法构造 点处的搜索方向，需要计算：,得：,代入DFP校正公式，得：,得：,则第二次搜索方向为：,其中，为一维搜索最佳步长，应满足：,沿d1进行一维搜索：,3)为了判断x2点是否为极值点，需计

38、算x2点处的梯度及其海赛矩阵：,梯度为零向量，海赛矩阵为正定矩阵，可见x2点满足极值充分必要条件，因此x2为极小点。函数的极值解为：,DFP算法由于舍入误差和一维搜索的不精确，有可能导致Ak奇异，而使数值稳定性方面不够理想。所以1970年提出更稳定的算法，称为BFGS算法，其校正公式为：,因为变尺度法的有效性促使其不断发展，所以出现过许多变尺度法的算法，1970年黄（huang）从共轭条件出发对变尺度法做了统一处理，写出了统一公式：,一.BFGS变尺度法:,可以看出，当取，就是DFP法的公式。当取，就是BFGS法的公式,3.5 牛顿法和变尺度法,3.6 单形替换法,一.单形替换法基本思想:,单

39、纯形：在一定的空间中的最简单的图形，如三角形，四面体等。,先算出n维空间n+1个点处的函数值，然后将它们进行比较，从它们之间大小关系可判断函数变化的大致越势，作为寻求搜索方向的参考。,反射、扩张、收缩,缩边,单形替换法流程图,例4-4 二维无约束目标函数 试用单形替换法求其极小值。,解：选为顶点做初始单纯形，计算各顶点函数值：,可见最好点xL=x0,最差点xH=x1，次差点xG=x2。求x0，x2的重心x3：,求反射点x4及其函数值 f4：,由于 f4 f0,故需要扩张，取 得扩张点x5：,由于 f5 f4,故以x5代替x4，由x0 x2x5构成新单纯形，进行下一循环，经过32次循环，可将目标

40、函数值降到110-6,接近极小值。f*=f(x*)=f(5,6)=0.,单纯形法一般用于维数小于10的情况。,3.7 无约束优化设计方法小结,1.可靠性。即在合理的精度要求下，在一定允许的时间内能解出各种不同类型问题的成功率。能够解出的问题越多，则算法的可靠性越好；2.有效性。即算法的解题效率。它有两个衡量标准。其一是对同一题目，在相同精度和初始条件下，比较机时多少。其二是在相同精度下，计算同一题目所需要的函数的计算次数；3.简便性。一方面指实现该算法的准备工作量的大小。另一方面指算法占用存储单元的数量。,一.评价准则:,3.7 无约束优化设计方法小结,二.适用范围:,可靠性：牛顿法较差，因为

41、它对目标函数要求太高，解题成功率较低。有效性：坐标变换法和梯度法的计算效率较低，因为它们从理论上不具有二次收敛性。简便性：牛顿法和变尺度法的程序编制较复杂，牛顿法还占用较多的存储单元。,3.7 无约束优化设计方法小结,三.优化方法的选择:,在选用无约束优化方法时，一方面要考虑优化方法的特点，另一方面要考虑目标函数的情况。,1、一般而言，对于维数较低或者很难求得导数的目标函数，使用坐标轮换法或鲍威尔法较合适。2、对于二次性较强的目标函数，使用牛顿法效果好。3、对于一阶偏导数易求的目标函数，使用梯度法可使程序编制简单，但精度不宜过高。4、综合而言，鲍威尔法和DFP法具有较好的性能。,3.7 无约束优化设计方法小结,Poweel法 共轭梯度法 牛顿法 变尺度(DFP)法迭代次数搜索次数搜索方向收敛速度存储量适用维数稳定性,2 2 1 2 6 2 1 2共轭方向,零阶算法 一阶算法 二阶算法 超线性 较慢 二次收敛 收敛最快 二次收敛 小 中 最大 较大,存储量随n2 随n，t n20 n200300 好 中 差 中下,四.各算法对比:,学习要求,1、掌握最速下降法，2、掌握共轭方向概念；3、掌握共轭梯度法原理和程序设计；4、掌握牛顿法原理及流程设计；5、了解鲍威尔方法，坐标轮换法，DFP变尺度法和单形替换法。,