无约束优化方法(1).ppt

第三章 无约束问题的最优化方法,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*) 。,二. 意义：,为约束优化方法的研究提供了策略思想、概念基础和基本方法； 为约束优化问题的间接解法提供了有效而方便的方法； 对于某些工程问题，进行分析后，便于提供解决的有效方法； 约束优化问题的求解往往可以通过一系列无约束优化方法实现； 无约束优化问题的解法是优化设计方法的基本组成部分。,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)点出发，沿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) 各种无约束优化方法的区别在于确定其搜索方向的S(k)的方法不同。所以，搜索方向的构成问题是无约束优化问题的关键。,五. 无约束优化方法的关键问题：,3.1 引言,六. 无约束优化方法的分类：,3.1 引言,无约束优化方法的分类依据就是根据(k)和S(k)的确定方法而定的。若根据构成搜索方向所使用的信息性质的不同，可以分为两类。 1、间接法 又称解析法，是利用目标函数导数的无约束优化方法，如最速下降法、共轭梯度法、牛顿法及变尺度法等。 2、直接法 只利用目标函数值的无约束优化方法，如坐标轮换法、鲍威尔法及单形替换法等。,3.2 一维搜索方法,一. 一维搜索：,定义: 在第K次迭代时，从已知点 X(k)出发，沿给定方向求最优步长因子(k)，使 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)的极小点，设其为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)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 =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 的矩形建筑物，若边长能符合以下条件，则最美观：,欧几里德几何称这种边长分割为黄金分割。,序列消去法中，为提高效率，减少计算量和存储量，希望,黄金分割法的算法框图,解：在搜索区间内取两试点并且计算它们函数值,比较两试点函数值，缩短搜索区间，由于 ，消去右区间，令：,例3-2 用黄金分割法求单变量函数 的极小点。初始搜索区间 ，迭代精度,判断迭代终止条件：,不满足迭代终止条件。再取两试点并且比较它们的函数值，继续缩短 搜索区间。搜索区间经过6次缩短（中间迭代过程略）后，区间长度为：,可以终止迭代，得到近似极小点和最优解,3.2 一维搜索方法,五. 二次插值法（抛物线法）：,1. 基本原理：,步骤：,3.2 一维搜索方法,2. 步骤 (续)：,3. 结果分析：,问题：若不满足精度，如何缩小区间，再拟合（分四种情况分析） ？, 令：,单谷搜索区间缩短情况,入口,xp*x2?,f2*fP*?,f2fP*?,x3 x2 f3 f2 x2 xp* f2 fP*,x1 x2 f1 f2 x2 xp* f2 fP*,出口,Y,Y,Y,N,N,N,a,b,c,d,二次插值法区间缩短流程图,3.2 一维搜索方法,与黄金分割法相比，二次插值法充分利用函数值的信息；收敛快；调用函数次数少。,4.方法评价:,5.迭代终止条件:,当满足如下两个条件，可终止迭代：,如果 和 两点的距离很小，即：,如果 和 充分接近，即：,二次插值法的算法框图,解：1）确定初始插值结点与函数值,2）计算插值函数极小点,例3-3 用二次插值法求一维函数 的最优解。初始单谷搜索区间 ，迭代精度,由于判别式成立，表明 落在单谷搜索区间之内,3）缩短单谷搜索区间,由于 和 ，则舍弃左边的区间 ，构成缩短后的新搜 索区间 。即：,4）检验迭代终止条件,满足迭代终止条件，输出最优解,六. 切线法：,一维搜索函数 ，假定已给出较好的近似点 ，连续可微的函数在极小点附近与一个二次函数很接近，所以可以在 附近用一个二次函数 来逼近函数 ：,以二次函数 的极小点作为 极小点的一个新近似点 ，根据极值必要条件：,3.2 一维搜索方法,解： 1) 求函数的一阶、二阶导函数：,例3-4 给定函数 ，初始值为 ，控制误差 ，试用切线法求其极小点。,2) 求,3) 求,4) 迭代值如下：,切线法流程图,N,Y,开始,结束,k=k+1,给定 k=0,. 收敛速度快； . 需要计算函数的一阶和二阶导数，增加迭代工作量； . 要求初始点选得比较好，离极小点不远，否则有可能使极小化序列发散或收敛到非极小点。,切线法优缺点:,3.2 一维搜索方法,3.2 一维搜索方法,取具有极小点的单峰函数的探索区间a,b的坐标中点 作为计算点，计算目标函数在该点处的导数为 ，并利用函数在极小点处的导数为零而在其左侧为负、右侧为正的原理，来判断极小点所在的那一半探索区间，以消掉另一半区间。这样逐次迭代下去，总能将探索区间收敛到一个局部极小点附近，求得极小点的近似解。 收敛速度虽然较慢，但缩短率也达到0.5，特别是每次迭代计算量较少，可靠性较好，所以仍然是一个受欢迎的方法。,七. 平分法：,3.2 一维搜索方法,平分法的迭代计算步骤:,给定 计算 ，若 ，则停止迭代并取 否则进行下一步。 计算 ，若 或 ，则停止迭代并取 若 则取 为缩短后的搜索区间 转第二步 若 则取 为缩短后的搜索区间 转第二步,当 求解困难时:,可直接计算 并比较两者大小，用序列消去法原理消去掉近一半的区域，再重新迭代，直到将探索区间缩短至精度要求为止。,例3-5 试用平分法求 的极小点和极小值，设,解： 1) 取,2) 计算,3) 缩短搜索区间为 取,4) 计算,5) 所以函数的极小点为 ,极小值为:,3.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,格点法区间搜索原理,格点法流程图,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 一维搜索方法,九. 间接法与直接法的异同点：,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次迭代，直至收敛到最优点x*。,3.3 坐标轮换法、共轭方向法和Poweel法,一. 坐标轮换法：,3. 方法评价：,方法简单，容易实现。 当维数增加时，效率明显下降。 收敛慢，以振荡方式逼近最优点。,受目标函数的性态影响很大。 如图 a) 所示，二次就收敛到极值点； 如图 b) 所示，多次迭代后逼近极值点； 如图 c) 所示，目标函数等值线出现山脊（或称陡谷），在脊线的尖点A处没有一个坐标方向可以使函数值下降，只有在锐角所包含的范围搜索才可以达到函数值下降的目的，故坐标轮换法对此类函数会失效。,3.3 坐标轮换法、共轭方向法和Poweel法,i=n,坐标轮换法的流程图,开始,给定：x0, ,k=1,i=1, x0k=x0,xik=x0k-1,沿ei方向一维搜索求i xik=xi-1k+ ikei x=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. 共轭方向的由来：,2. 共轭方向的定义：,共轭方向概念是在研究具有正定矩阵G的二次函数,的极小化问题时形成的。其基本思想是在不用导数的前提下，在迭代中逐次构造G的共轭方向。,3.3 坐标轮换法、共轭方向法和Poweel法,3. 共轭方向法的二次收敛性：,正定的二元二次函数的等值线为一组椭圆，任选初始点x0，沿某个下降方向S0作一维搜索，得x1,此时， x1点的梯度必然与方向S0垂直，即有：,S0与某一等值线相切于x1点。下一次的迭代，若选择负梯度方向为搜索方向，将产生锯齿现象。为避免锯齿的产生，我们取迭代方向S0直指极小点x*，如图所示。 若选定这样的方向，则对于二元二次函数只需进行S0 和S1两次搜索就可以求得极小点x*，即,3.3 坐标轮换法、共轭方向法和Poweel法,3. 共轭方向法的二次收敛性（续）：,由于 ，当 时 ，由 是 的极小点，应满足极值必要条件，故 即：,等式两端同乘以 ,得 ，故两个向量 ， 是G的共轭向量。,因此，若要使第二个迭代点成为正定二元二次函数的极小点，只要使两次一维搜索的方向 ， 关于函数的二阶导数矩阵G共轭就可以了。 对于正定二次n维函数，从任意的初始点出发，沿着这n个共轭方向进行一维搜索，就可以得到目标函数的极小点。因此，对于二次函数来说，经过n步搜索就可以达到函数的极小点。 对于非二次n维函数，可以用二阶泰勒级数将函数在极小点附近展开，省略去高于二次的项后可以得到函数的二次近似，同样按照二次函数构成共轭方向。,3.3 坐标轮换法、共轭方向法和Poweel法,4. 二维函数的共轭方向：,二维函数 ，任意给定某个方向 ，按这个方向上的两条平行线进行一维搜索求得的极小点为 和 ，它们应该是方向为 的两条平行线与目标函数等值线的切点。,连接两个切点 和 构成向量：,可以证明，如果二维函数的海塞矩阵H 是正定的，则S1向量与向量S2满足条件：,具有这种性质的方向为关于正定矩阵H的共轭方向。,3.3 坐标轮换法、共轭方向法和Poweel法,所以有：,4. 二维函数的共轭方向（续）：,证明：,设二维函数在极值点X*附近的二次泰勒展开式为：,由此得函数的一阶导数：,由于S1为等值线的切线，故方向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. 多维二次函数共轭方向的构建：,如果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 ) 的 n-1 个方向和共轭方向 S(1)，构筑共轭方向 S(2) 搜索 n+1次得极值点 xn+1(2) 。其中，为保证搜索方向的线性无关，去除了 Sm(2) 方向 。,在第 k 轮迭代中，为避免产生线性相关或近似线性相关，需要去除前一轮中的某个方向 Sm(k)。去除的原则请自学。,3.3 坐标轮换法、共轭方向法和Poweel法,共轭方向法的程序框图,9. 共轭方向法的缺陷：,共轭方向法的迭代过程可能会产生不理想的情况，在以后某环的迭代中可能出现基本方向组为线性相关向量系。以后的搜索将在维数下降后的设计空间中进行，无法收敛到n维设计空间中目标函数的极小点。,以三维问题为例，设从初始点 出发，沿着坐标轴方向 ，进行第一环搜索，在各个方向获得极小点为：,由该环搜索的初始点 与终点 产生的新生方向：,3.3 坐标轮换法、共轭方向法和Poweel法,9. 共轭方向法的缺陷（续）：,如果其中第三维优化步长 等于或非常接近0，即表示沿着则坐标轴方向 的搜索没有前进或前进很少，则共轭方向：,表明向量 与向量 是线性相关的。,第2环搜索的基本方向组 中， 是 与 线性相关或接近线性相关，即向量 在 和 组成的平面内。以后的搜索将在维数下降（不包含方向 ）的平面中进行，无法收敛到 空间中目标函数 的极小点 。,3.3 坐标轮换法、共轭方向法和Poweel法,三. Poweel法：,1. 基本步骤：,1.给定初始点 ，选取由n个线性无关的向量 组成的初始方向组，置 。,2.从 出发，顺次沿 作一维搜索得 。接着以 为起点，沿方向： 移动一个 的距离，得到：,分别称为一轮迭代的始点、终点和反射点。它们所对应的函数值分别为：,同时计算各中间点处的函数值，并记为：,3.3 坐标轮换法、共轭方向法和Poweel法,3.3 坐标轮换法、共轭方向法和Poweel法,1. 基本步骤（续）：,计算n个函数值之差：,3.为了构造第k1环基本方向组，采用如下判别式：,按以下两种情况处理：,其中最大者记作：,鲍威尔判别式,a.上式中至少一个不等式成立，则第k+1环的基本方向仍用老方向组. ,k+1的环初始点取:,1. 基本步骤（续2）：,b.两式均不成立，则淘汰函数值下降最大的方向，并用第k环的新生方向补入k+1环基本方向组的最后，即k+1环的方向组为：,k+1环的初始点取 ， 是第k环沿 方向搜索的极小点。,3.3 坐标轮换法、共轭方向法和Poweel法,鲍威尔法的流程图,一. 梯度法（最速下降法）：,1.基本思想：,2.负梯度方向为最速下降方向的证明：,目标函数负梯度向量方向代表最速下降方向，因此选择负梯度向量方向为搜索方向，期望很快找到最优点。,S,由方向导数概念可得：,设：,取最小值1时，S为梯度的负方向。,3.4 梯度法和共轭梯度法,4.迭代格式：,3.搜索方向：,a.任意给定一个初始步长，使其满足：,根据一元函数的极值必要条件和多元复合函数的求导公式，得：,或,负梯度方向 或单位负梯度向量,5.最佳步长 的选取：,b.沿负梯度方向作一维搜索，求最佳步长，对目标函数求极小，以得到最佳步长：,即：,3.4 梯度法和共轭梯度法,最速下降法向极小点的逼近路径是锯齿形路线，越接近极小点，锯齿越细，前进速度越慢。 这是因为，梯度是函数的局部性质，从局部上看，在该点附近函数的下降最快，但从总体上看则走了许多弯路，因此函数值的下降并不快。,5.最佳步长 的选取（续）：,此式表明，相邻的两个迭代点的梯度是彼此正交的。也即在梯度的迭代过程中，相邻的搜索方向相互垂直。,6.搜索路径：,3.4 梯度法和共轭梯度法,（1）任选初始迭代点x(0)，选收敛精度。 （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. 方法评价：,迭代过程简单，对初始点的选择，要求不高。 梯度方向目标函数值下降迅速只是个局部性质，从整体来看，不一定是收敛最快的方向。 以二维二次函数为例，相邻两次的搜索方向是正交的，所以搜索路径是曲折的锯齿形的；对于高维的非线性函数，接近极值点处，容易陷入稳定的锯齿形搜索路径。,例4-1 二维无约束目标函数 试用梯度法求其极小值，初始点 ，精度,解： 1）计算目标函数在初始点的梯度、梯度的模和单位负梯度方向,2）计算最佳搜索步长,3）计算第一次迭代更新值和目标函数值,4）当迭代7次时，满足终止条件，得到最有值,3.4 梯度法和共轭梯度法,二. 共轭梯度法（旋转梯度法）：,1. 基本思想：,2. 共轭方向：,对梯度法作一个修正，将搜索方向由负梯度方向旋转一个角度，使相邻的两次搜索方向由正交变为共轭，成为二次收敛。,3. 共轭系数：,推导过程请自学。,(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+1 f(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）计算目标函数在初始点的梯度、梯度的模和单位负梯度方向,2）计算新迭代点的梯度和搜索方向的修正量，进行第2次搜索,可见，共轭梯度法具有两次收敛性，对于二维函数只要经过两次迭代就可以达到极值点。,3.5 牛顿法和变尺度法,一. 牛顿法（二阶梯度法）：,1. 基本思想：,将 f(x) 在 x(k) 点作台劳展开，取二次函数式(x) 作为近似函数,以(x) 的极小值点作为 f(x) 的近似极小值点。,说明：,f(x) 若是正定二次函数，一般迭代一次即可；若是严重非线性函数，则可能不收敛，或收敛到鞍点。,2. 修正牛顿法（阻尼牛顿法）：,一. 牛顿法（二阶梯度法）：,可通过如下极小化过程求得：,避免了迭代后函数上升的现象，保持了牛顿法二次收敛的特性，对初始点的选取并没有苛刻的要求。,阻尼牛顿法的计算步骤：,1）给定初始点 ，收敛精度 ，置,3.5 牛顿法和变尺度法,3.5 牛顿法和变尺度法,3. 方法评价：,使用牛顿法时，若目标函数是严重非线性函数，则是否收敛将与初始点有很大关系；而使用修正牛顿法，能保证每次迭代目标函数值下降，从而放宽了对初始点的要求。 若初始点选得合适，牛顿法的收敛速度相当快。 牛顿法求逆矩阵的工作量大，计算量与存储量均随 n2上升。,3）求 ，其中 为沿 进行一维搜索的最佳步长,4）检查收敛精度。若 ，则 ，否则，令 ，返回2）继续进行搜索。,2）计算：,阻尼牛顿法流程图,3.5 牛顿法和变尺度法,变尺度法也称拟牛顿法，它是基于牛顿法的思想而又作了重大改进的一类方法。,梯度法只需计算函数的一阶偏导数，计算量小，当迭代点远离最优点时，函数值下降很快，但当迭代点接近最优点时收敛速度极慢。,DFP变尺度法是由Davidon于1959年提出的一种变尺度法； BFGS变尺度法是由Broydon等提出的改进算法，提高了算法的稳定性。,牛顿法不仅需要计算一阶偏导数，而且要计算二阶偏导数及其逆阵，计算量很大，但牛顿法具有二次收敛性，当迭代点接近最优点时，收敛速度很快。,若迭代过程先用梯度法，后用牛顿法并避开牛顿法的海赛矩阵的逆矩阵的烦琐计算，则可以得到一种较好的优化方法，这就是“变尺度法”产生的构想。,一. 变尺度法:,3.5 牛顿法和变尺度法,二. DFP 变尺度法:,1. 变尺度的定义：,每确定一次搜索方向，调整一次模（尺度）的大小，称为变尺度。,2. 基本思想：,发扬梯度法和牛顿法各自的优点，避免两者各自的缺点，将两者结合起来，形成变尺度法。,3.5 牛顿法和变尺度法,3. 变尺度矩阵的构造：,原则： 使目标函数值有下降性，则变尺度矩阵应为实对称矩阵（请证明）； 使算法有二次收敛性，则 S(k) (k=1,2,)应关于 H(k) 是共轭的；,构造变尺度矩阵的递推公式：,4. 修正矩阵:,3.5 牛顿法和变尺度法,步骤：,1、选定初始点和收敛精度； 2、计算初始点处的梯度，选取初始对称正定矩阵A0，置k=0； 3、计算搜索方向Sk= - Akgk ； 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) 的计算较复杂，存储量较大。 算法稳定性较差，由于计算机有舍入误差，容易使 H (k) 的正定性破坏，趋于奇异。,3.5 牛顿法和变尺度法,DFP变尺度法流程图,例4-3 二维无约束目标函数 试用DFP算法求其极小值。,解： 1）取初始点 ，为了按DFP法构造第一次搜索方向 ，需要计算初始点处的梯度：,并取初始变尺度矩阵为单位矩阵A0=I，则第一次搜索方向为：,沿 方向进行一维搜索，得：,其中， 为一维搜索最佳步长，应满足：,2）再按DFP法构造 点处的搜索方向 ，需要计算：,得：,代入DFP校正公式，得：,得：,则第二次搜索方向为：,其中， 为一维搜索最佳步长，应满足：,沿d1进行一维搜索：,3)为了判断x2点是否为极值点，需计算x2点处的梯度及其海赛矩阵：,梯度为零向量，海赛矩阵为正定矩阵，可见x2点满足极值充分必要条件，因此x2为极小点。函数的极值解为：,DFP算法由于舍入误差和一维搜索的不精确，有可能导致Ak奇异，而使数值稳定性方面不够理想。所以1970年提出更稳定的算法，称为BFGS算法，其校正公式为：,因为变尺度法的有效性促使其不断发展，所以出现过许多变尺度法的算法，1970年黄（huang）从共轭条件出发对变尺度法做了统一处