常用的无约束优化方法.ppt

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

1、第四章 常用的无约束优化 方法,王桂从,无约束优化问题的数学模型,求上述问题最优解(x*,F*)的方法称为无约束优化方法,无约束优化方法理论研究开展的比较早，构成的优化方法已很多，也比较成熟。使用无约束优化方法，不仅可以直接求无约束优化设计问题的最优解，而且通过对无约束优化方法的研究给约束优化方法建立明确的概念及提供良好的基础，某些优化设计方法就是先把优化设计问题转化为无约束问题后，再直接用无约束优化方法求解。,无约束优化问题的求解方法,解析法(间接法)：用函数的一阶、二阶导数进行求解的算法,直接搜索法(直接法)：只利用函数值求最优解的解法,解析法的收敛速率较高，直接法的可靠性较高。,无约束优

2、化方法的基本过程,从选定的某初始点x(k)出发，沿着以一定规律产生的搜索方向S(k)，取适当的步长a(k)，逐次搜寻函数值下降的新迭代点x(k+1)，使之逐步逼近最优点x*。初始点x(k)、搜索方向S(k)、迭代步长a(k)称为优化方法算法的三要素。其中以搜索方向S(k)更为突出和重要，它从根本上决定着一个算法的成败、收敛速率的快慢等所以，一个算法的搜索方向成为该优化方法的基本标志，分析、确定搜索方向S(k)是研究优化方法的最根本的任务之一,4.1 坐标轮换法,坐标轮换法由Desopo于1959年提出；坐标轮换法是每次搜索只允许一个变量变化，其余变量保持不变，即沿坐标方向轮流进行搜索的寻优方法

3、；坐标轮换法把多变量的优化问题轮流地转化成了单变量的优化问题。属于直接搜索法。即只需要目标函数的数值信息而不需要目标函数的导数；,4.1 坐标轮换法-基本原理,既可以用于无约束优化问题的求解，又可以经过适当的处理用于约束优化问题；基本特征：将迭代方向 S 取为一系列按序号排列的坐标轴方向，通常都用单位矢量 ei 作为迭代的方向矢量。对于n 维优化问题，当 n 个坐标轴方向依次取过一次后，称为完成了一轮迭代。基本原理：将一个 n 维的无约束最优化问题转化为一系列沿坐标轴方向的一维搜索问题来求解。在每一次迭代中，只改变 n 个变量中的一个，其余变量固定不动，因此常称为单变量法或变量交错法或降维法,

4、4.1 坐标轮换法-迭代步长的确定,在沿坐标轴方向的搜索中，利用一维优化方法来确定沿该方向上具有最小目标函数值的步长，即：,先选择一个不大的初始步长 a0，在每次一维搜索中都是先沿正向从 a 到 a0，开始做试探计算函数值，若函数值下降，则以倍增的速度加大步长，步长序列为a0,2a0,4a0 直到函数值保持下降的最后一个步长为止。,(1)最优步长,(2)加速步长,在无约束优化问题求解中采用最优步长方法是方便的。,4.1 坐标轮换法-迭代过程,第一轮迭代：,(2)以 x1(1)为新起点，沿第二坐标轴的方向e2=0 1T作一维搜索，确定步长2(1)，得第一轮的第二个迭代点：x2(1)=x1(1)+

5、1(1)e2,(1)任取一初始点x(0)作为初始点x0(1)，先沿第一坐标轴的方向e1=1 0T 作一维搜索，用一维优化方法确定最优步长1(1)，得第一轮的第一个迭代点：x1(1)=x0(1)+1(1)e1,4.1 坐标轮换法-迭代过程,x0(2)x2(1)x1(2)=x0(2)+1(2)e1x2(2)=x1(2)+2(2)e2,第二轮迭代：,依次类推,可进行第三轮、第四轮迭代,注意：右上角括号内的数字表示轮数，右下角数字表示该轮中的第几个迭代点号,4.1 坐标轮换法-终止准则,采用点距准则,注意：若采用点距准则或函数值准则，其中采用的点应该是一轮迭代的始点和终点，而不是某搜索方向的前后迭代点

6、。,4.1 坐标轮换法-计算步骤,任选初始点,作为第一轮的起点，置n个坐标轴方向矢量为单位坐标矢量：,按照下面迭代公式进行迭代计算,k为迭代轮数的序号，取 k=1，2，；i为该轮中一维搜索的序号，取 i=1，2，n步长一般通过一维优化方法求出其最优步长,按下式判断是否终止迭代,如满足，迭代终止，并输出最优解,最优解,否则，令kk+1返回步骤（2）,例题4.1,例题4.1 用坐标轮换法求目标函数 的无约束最优解。给定初始点 x(0)=0,0T，精度要求=0.1,解：做第一轮迭代计算,沿e1方向进行一维搜索,式中，为第一轮的起始点，取,按最优步长原则确定最优步长1，即极小化,暂且用微分学求导解出，

7、令其一阶导数为零,以 为新起点，沿 e2 方向一维搜索,以最优步长原则确定2，即为极小化,对于第一轮按终止条件检验,继续进行第2轮迭代计算。,计算5轮后，有,故近似优化解为,坐标轮换法的流程图,-,-,+,+,小结,坐标轮换法程序简单，易于掌握。但是计算效率比较低，尤其是当优化问题的维数较高时更为严重。一般把此种方法应用于维数小于10的低维优化问题。优化效率在很大程度上取决于目标函数的形态,4.2 鲍威尔(Powell)法,鲍威尔法是直接搜索法中一个十分有效的算法。该算法是沿着逐步产生的共轭方向进行搜索的，因此本质上是一种共轭方向法。其收敛速度较快，一般认为对于维数 n 20 的目标函数是成功

8、的。1964年，鲍威尔提出该种算法，其基本思想是直接利用迭代点的目标函数值来构造共轭方向，然后从任一初始点开始，逐次沿共轭方向做一维搜索。,4.2.1 鲍威尔基本算法,4.2.1 鲍威尔基本算法,三维二次目标函数的鲍威尔基本算法的搜索过程,三维二次目标函数的鲍威尔算法搜索过程,基本方向组：任选初始点x0(1)，按照单位坐标矢量系依次沿e1,e2,e3作一维搜索，得各自方向上的极小点：x1(1),x2(1),x3(1)。然后将始末两点相连作为新生方向：S1=x3(1)-x0(1)，再沿此方向作一维搜索，得到该方向上的一维极小点 x(1)，并作为下一环的初始点。,第一环迭代：,基本方向组：e2,e

9、3，S1 将上环的第一个方向淘汰，上环的新生方向补入本环的最后。依次沿这些方向做一维搜索后产生一个新方向:S2=x3(2)-x0(2)，再沿此方向一维搜索得第三环的迭代终点 x(2)，并作为下一轮迭代的始点。这样就形成了算法的循环。,第二环迭代：,第三环迭代：,基本方向组：e3,S1，S2，新生方向为S3=x3(3)-x0(2),三维二次目标函数的鲍威尔算法搜索过程,共轭方向：,依次产生的新生方向：S1,S2,S3 是一组共轭矢量。三维优化问题从本质上看，就是从初始点x0(1)开始依次沿着共轭方向S1,S2,S3 进行了一维搜索，经由点x(1)、x(2)到达x(3)。而每环中沿基本搜索方向组的

10、一维搜索和各环方向组内方向的依次变更只是为了逐次产生新方向，并使新生方向成为共轭方向组,如目标函数是三维二次正定函数，则顺次经过三个共轭方向S1,S2,S3 的一维搜索，由共轭矢量的性质可断定x(3)就是该函数的理论最优点；,注意：,如目标函数是非二次函数，则迭代需继续。一般是重复上述做法，即重置基本搜索方向组e1,e2,e3循环下去。每三环组成一轮，每一轮开始都以单位坐标矢量作为第一环方向组,鲍威尔基本算法的搜索过程,推广到 n 维优化问题,第一环基本方向组取单位坐标矢量系e1,e2,en，沿这些方向依次做一维搜索后将始末两点相连做新生方向，再沿新生方向一维搜索，完成一环的迭代。以后每环的基

11、本方向组都是将上环的第一个方向淘汰，上环的新生方向补入本环最后而构成。n维目标函数完成 n 环的迭代过程称为一轮。,对于二次正定目标函数，一轮的终点即为最优点；,对于非二次函数，重置初始基本方向组为单位坐标矢量系进行第二轮迭代，依次做第三轮、第四轮直到在某轮中第 k 环的始末两点距离达到预期的精度要求时：终止迭代,鲍威尔基本算法的缺陷,若在优化搜索过程中出现1(k)=0(或近似等于0)，则方向 Sk 表示为S2(k),S3(k),Sn(k)的线性组合，则第 k+1 环搜索方向组S2(k),S3(k),Sn(k),Sk是一个线性相关矢量系，以后的各次搜索将在降维的空间进行，无法得到 n 维空间的

12、函数极小值，计算将失败。这种现象称为“退化”。,基本方向组为：,各方向最优步长：,新生方向：,鲍威尔基本算法有一个缺陷，它有可能在某环迭代中出现基本方向组为线性相关的矢量系，说明如下：如在第k 环中，,鲍威尔基本算法的退化,x1,x2,x3,1=0,2e2,3e3,S1,如图所示为一个三维优化问题的示例，设第一环中1=0，则新生方向与e2、e3 共面，随后的各环方向组中，各矢量必在该平面内，使搜索局限于二维空间，不能得到最优解。,4.2.3 鲍威尔修正算法,在某环已经取得的n+1各方向中，选取 n 个线性无关的并且共轭程度尽可能高的方向作为下一环的基本方向组,(一)鲍威尔修正算法的搜索方向,初

13、始点：,新生方向上的极小点：,在第k环中：基本方向组为：,新生方向：,映射点：,记：,其中：是在第k 环方向组中，依次沿各方向优化搜索函数值下降量的最大值，即Sm(k)方向函数下降量最大,鲍威尔修正算法的方向淘汰,(F3),(F2),(F1),映射点,函数下降量,判别式,(1)至少一个不等式成立，则第 k+1 环的基本方向仍用老方向组 S1(k),S2(k),Sn(k)。k+1环的初始点取 x0(k+1)=xn(k)F2 F3 x0(k+1)=xn+1(k)F2 F3,判别式,(2)两式均不成立，则淘汰函数值下降最大的方向，并用第 k 环的新生方向补入 k+1 环基本方向组的最后，即 k+1

14、环的方向组为：S1(k),S2(k),Sm-1(k),Sm+1(k),Sn(k),Sn+1(k)k+1环的初始点取 x0(k+1)=x(k)x(k)是第k 环沿Sn+1(k)方向搜索的极小点,鲍威尔修正算法的终止条件：|x(k)-x0(k)|,修正算法的迭代步骤及流程图,第一步：任选初始迭代点 xn(1)，选定迭代精度，取初始基本方向组为单位坐标矢量系,令k=1（环数）开始下面的迭代,第二步：沿Si(k)诸方向依次进行 n 次一维搜索，确定各步长 ai(k)使,i=1，2n,得到点阵:,构成新生方向:,沿 方向进行一维搜索求得优化步长，得,第三步：判断是否满足迭代终止条件。如满足,则可结束迭代

15、，最优解为,停止计算。否则，继续进行下步。,第四步：计算各迭代点的函数值 F(xi(k)，并找出相邻点函数值差 最大者:,（1mn）,及与之相对应的两个点 xm-1(k)和 xm(k)，并以Sm(k)表示两点的连线方向,第五步：确定映射点，,并计算函数值,检验鲍威尔条件,若至少其中之一成立转下步，否则转步骤,第六步：置k+1环的基本方向组和起始点为,（即取老方向组）,当F2F3,当F2F3,令kk+1，返回步骤二,第七步：置k+1环的方向组和起始点为,令kk+1，返回步骤二,修正算法与基本算法的区别,修正算法除了第一环以单位坐标矢量系为基本方向组外，以后每轮开始就不必重置单位坐标矢量系，只要一

16、环接一环继续进行即可。随着逐环迭代的继续，各环的基本方向组将渐趋共轭。修正了的鲍威尔算法不具有二次收敛性，但是克服了退化的不利情形，同时仍能够有效地、越来越快地收敛于无约束最优点。,例题4.2,例题4.2 试用鲍威尔修正算法求目标函数,的最优解。已知初始点 x0=1,1T，迭代精度=0.001,解：第一环迭代计算,沿第一坐标方向e1进行一维搜索,1=2,以 x1(1)为起点，改沿第二坐标轴方向 e2 进行一维搜索,2=0.5,构成新方向,沿S1方向进行一维搜索得极小点与极小值,计算点距,需进行第二环迭代计算,第二环迭代计算,首先确定上环中的最大函数下降量及其相应方向：,映射点及其函数值：,检查

17、鲍威尔条件,于是可知,鲍威尔条件两式均不成立。第二环取基本方向组和起始点为,沿 e2 方向作一维搜索得,以x1(2)为起点沿 S1 方向一维搜索得,构成新生方向：,沿 S2 方向一维搜索得：,检查迭代终止条件：,需再作第三环迭代计算。,根据具体情况来分析，S1，S2 实际上为共轭方向，见下图。本题又是二次函数，由共轭方向的二次收敛性，上面结果就是问题的最优解。可以预料，如果做第三环迭代，则各一维搜索的步长一定为零，必有,故得最优解：,4.3 梯度法,梯度法是求解无约束优化问题的解析法之一，在理论上，这个方法极为重要，因为它不仅提供了一个简单的、在一定场合令人满意的优化算法，而且许多更有效和实用

18、的算法也常常是在这个基本算法基础上建立起来的。函数的梯度方向是函数值增加最快的方向，则负梯度方向必然是函数值下降最快的方向。采用负梯度矢量作为一维搜索的方向，因而又称作最速下降法,4.3 梯度法(最速下降法),一、迭代公式,其中：,g(k):函数在迭代点 x(k)处的梯度F(x(k)a(k):一般采用最优步长，即通过一维极小化函数获得：,4.3 梯度法,据一元函数极值条件和多元复合函数求导公式，得,即(f(x(k+1)T g(k)=0,或(g(k+1)T g(k)=0,此式表明，相邻的两个迭代点的梯度是彼此正交的。也即在梯度的迭代过程中，相邻的搜索方向相互垂直。梯度法向极小点的逼近路径是锯齿形

19、路线，越接近极小点，锯齿越细，前进速度越慢。,这是因为梯度是函数的局部性质，从局部上看，在该点附近函数的下降最快，但从总体上看则走了许多弯路，因此函数值的下降并不快。,4.3 梯度法,二、迭代终止条件,常用梯度准则：,三、迭代步骤,（4）从x(k)点出发，沿-g(k)方向作一维搜索求最优步长(k)。得下一迭代点 x(k+1)=x(k)-(k)g(k),令k=k+1，返回步骤(2)。,（1）任选初始迭代点x(0)，选收敛精度；,（2）确定x(k)点的梯度（开始 k=0)；,（3）判断是否满足终止条件|g(k)|？若满足输出最优解，结束计算。否则转下步；,入口,给定：x(0)，,k=0,|g(k)

20、|？,x*=x(k)f*=f(x(k),出口,x(k)=x(0),计算：g(k),k=k+1,沿g(k)方向一维搜索，求最优步长(k)。x(k+1)=x(k)-(k)g(k)/|g(k)|,N,Y,梯度法流程图,例题 4.3,例题4.3 用梯度法求目标函数 的最优解。已知初始点x(0)=2,2T，迭代精度=0.005,解：函数的梯度,第一次迭代：以x(0)为起点沿一 方向作一维搜索,得第一个迭代点,继续第二次迭代,到第五次迭代结束时，有,故迭代可终止，最优解为:,梯度法的特点,优点：程序结构简单，每次迭代所需的计算量及存储量也小，而且当迭代点离最优点较远时函数值下降速度很快,缺点：在迭代点到达

21、最优点附近时，进展十分缓慢，而且常常由于一维搜索的步长误差而产生的挠动不可能取得较高的收敛精度,4.4 共轭梯度法,共轭梯度法是共轭方向法的一种，因为该方法中每一个共轭向量都是依赖于迭代点处的负梯度而构造出来的，所以称作共轭梯度法。,一、共轭梯度法的搜索方向,共轭梯度法的搜索方向是在采用梯度法基础上的共轭方向，目标函 F(x)在迭代点 x(k+1)处的负梯度为-F(x(k+1)，该方向与前一搜索方向S(k)互为正交，在此基础上构造一种具有较高收敛速度的算法。,共轭梯度法的搜索方向,搜索方向S(k+1)满足以下两个条件：,(1)是-f(x(k+1)与 S(k)的线性组合。即 S(k+1)=-f(

22、x(k+1)+k S(k),(2)以 S(k)与-f(x(k+1)为基底的子空间中，矢量相共轭，即满足：S(k+1)TAS(k)=0,其中：,共轭梯度法的搜索方向,（4）计算 f(x(k+1)，若|f(x(k+1)|，则终止迭代，取x*=x(k+1)；否则进行下一步;,共轭梯度法的算法,（1）选初始点 x(0)和收敛精度；,（2）令k=0，计算S(0)=-f(x(0);,（3）沿S(k)方向进行一维搜索求(k)，得 x(k+1)=x(k)+(k)S(k);,（5）检查搜索次数，若 k=n，则令x(0)=x(k+1)，转(2)，否则，进行下一步;,（6）构造新的共轭方向：S(k+1)=-f(x(

23、k+1)+k S(k)，令k=k+1，转(3);,重置负梯度方向,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,N,Y,Sk+1=-f(xk+1)+kSk,K=K+1,共轭梯度法的计算框图,共轭梯度法的特点,共轭梯度法属于解析法，其算法需求一阶导数，所用公式及算法简单，所需存储量少。该方法以正定二次函数的共轭方向理论为基础，对二次型函数可以经过有限步达到极小点，所以具有二次收敛性。但是对于非二次型函数，以及在实际计算中由

24、于计算机舍入误差的影响，虽然经过 n 次迭代，仍不能达到极小点，则通常以重置负梯度方向开始，搜索直至达到预定精度，其收敛速度也是较快的。,4.5 牛顿法,牛顿法是求无约束最优解的一种古典解析算法；牛顿法可以分为原始牛顿法和阻尼牛顿法(或称修正牛顿法)两种；现在实际中应用较多的是阻尼牛顿法。,4.5.1 原始牛顿法,在第 k 次迭代的迭代点 x(k)邻域内，用一个二次函数去近似代替原目标函数 F(x)，然后求出该二次函数的极小点作为对原目标函数求优的下一个迭代点，依次类推，通过多次重复迭代，使迭代点逐步逼近原目标函数的极小点。,一、原始牛顿法的基本思想,二、原始牛顿法的迭代公式,设目标函数 F(

25、x)具有连续的一、二阶导数，在 x(k)点邻域的二次逼近函数(x)可写为F(x)的二次泰勒多项式,二、原始牛顿法的迭代公式,设 x*为(x)极小点，根据极值的必要条件，应有(x)的梯度等于零，即：,牛顿法迭代公式,S(k)=-Hk-1gk称为牛顿方向,三、原始牛顿法的特点,优点：具有二次收敛性。对于二次函数，构造的逼近函数与原目标函数是完全相同的二次式，其等值线完全重合，故从任一点出发，迭代一次即可得到最优解。对于非二次函数，若函数二次性较强或迭代点已经进入最优点的较小邻域，则收敛速度也很快。缺点：步长恒等于1。由于迭代点的位置是按照极值条件确定的，并不能保证函数值稳定的下降，严重的情况下甚至

26、可能造成点列的发散而导致计算的失败。,三、原始牛顿法的特点,目标函数值上升,4.5.2 阻尼牛顿法/修正牛顿法,为解决原始牛顿法的不足，加入最优步长因子(k)，迭代公式变为：,这就是阻尼牛顿法的迭代公式，最优步长(k)也称为阻尼因子，是沿牛顿方向一维搜索得到的最优步长。,牛顿法算法步骤,任选初始点 x(0)，给定精度，置k0,计算x(k)点的梯度矢量及其模,牛顿法算法步骤,检验迭代终止条件,如满足，则输出最优解：,否则，转下步,计算x(k)点处的海塞矩阵,i，j=1,2,n,并求其逆矩阵,确定牛顿方向,并沿牛顿方向作一维搜索，求出在S(k)方向上的最优步长a(k),计算第k+1个迭代点,置kk

27、+1，返回步骤,牛顿法流程图,例题4.5,例题4.5 用牛顿法求函数,的最优解。初始点，,解：函数的梯度,和海赛矩阵及其逆,在 x(0)点处：,沿 S(0)方向一维搜索求得最优步长a(0)=1，故新迭代点为：,该点的梯度,迭代即可结束,由于目标函数是二次正定函数，故迭代一次即达到最优点,阻尼牛顿法的特点,优点：由于阻尼牛顿法每次迭代都在牛顿方向进行一维搜索，避免了迭代后函数值上升的现象，从而保持了牛顿法的二次收敛性，而对初始点的选择没有苛刻的要求。,阻尼牛顿法的特点,缺点：(1)对目标函数要求苛刻，要求函数具有连续的一、二阶导数；为保证函数的稳定下降，海赛矩阵必须正定；为求逆阵要求海赛矩阵非奇

28、异。(2)计算相当复杂，除了求梯度以外，还需计算二阶偏导数和它的逆矩阵，占用机器的储存量也很大。故在工程优化设计中的应用受到一定的限制。,梯度法和牛顿法的对比,牛顿法比梯度法更有效和收敛更快，这种说法是有前提的。就是当初始点 x(0)与最优点 x*比较接近，且两点的海赛矩阵非常接近，否则用梯度法要比牛顿法更好,4.6 DFP变尺度法,变尺度法也称拟牛顿法，它是基于牛顿法的思想而又作了重大改进的一类方法。我们所介绍的变尺度法是由 Davidon 于1959年提出又经 Fletcher 和 Powell 加以发展和完善的一种变尺度法，故称为DFP变尺度法。,一、变尺度法的基本思想,牛顿法的搜索方向

29、为-Hk-1 gk，不仅需要计算一阶偏导数，而且要计算二阶偏导数及其逆阵，计算量很大，但牛顿法具有二次收敛性，当迭代点接近最优点时，收敛速度很快。,梯度法:,牛顿法:,梯度法的搜索方向为-gk，只需计算函数的一阶偏导数，计算量小，当迭代点远离最优点时，函数值下降很快，但当迭代点接近最优点时收敛速度极慢,二、变尺度法的迭代公式,(2)变尺度法的搜索方向:S(k)=-Ak gk，称为拟牛顿方向。,(1)Ak为构造的 n n 阶对称矩阵，它随迭代点的位置变化而变化，对梯度起到改变尺度的作用，又称为变尺度矩阵。,若Ak=I，上式为梯度法的迭代公式若Ak=Hk-1，上式为阻尼牛顿法的迭代公式,三、DFP

30、法变尺度矩阵的产生,拟牛顿方向 S(k)=-Ak gk 必须具有下降性、收敛性和计算的简便性。,下降性要求变尺度矩阵为对阵正定矩阵；,收敛性要求变尺度矩阵逐渐逼近Hk-1，满足拟牛顿条件；,简便性希望变尺度矩阵有如下递推形式：Ak+1=Ak+Ak,下降性,下降性：要求S(k)与-gk之间的夹角小于90o，即：,拟牛顿方向 S(k)=-Ak gk,-S(k)T gk0,将拟牛顿方向带入上式，得：,-S(k)T gk=Ak gkTgk=gkTAk gk 0,所以只要 Ak 为对阵正定矩阵，S(k)就是下降方向。,简便性,变尺度矩阵是随迭代过程的推进而逐次改变的，因而它是一种矩阵序列,选取初始矩阵A

31、0，并以梯度方向快速收敛，通常取单位矩阵E 作为初始矩阵，即A0=E。而后的矩阵均是在前一构造矩阵的基础上校正得到，令,推广到一般的k+1次构造矩阵,Ak，k=1，2，,A1=A0+A0,Ak+1=Ak+Ak,矩阵序列的基本迭代式,Ak 称为校正矩阵,拟牛顿条件,构造矩阵Ak+1应该满足一个重要条件拟牛顿条件,变尺度法采用构造矩阵来代替牛顿法中海赛矩阵的逆阵，主要目的之一就是为了避免计算二阶偏导数和逆矩阵，力图仅用梯度和其他一些易于获得的信息来确定迭代方向，因此，拟牛顿条件是关于海赛矩阵和梯度之间的关系。,拟牛顿条件,设F(x)为一般形式 n 阶的目标函数，并具有连续的一、二阶偏导。在点 x(

32、k)处的二次泰勒近似展开,该近似二次函数的梯度为：,式中，若令，则有,上式中，x(k+1)x(k)称之为位移矢量，并简化书写:,而gk+1-gk 是前后迭代点的梯度矢量差，简化书写：,由以上三式得：,海赛矩阵与梯度间的关系式,拟牛顿条件,按照变尺度法产生构造矩阵的递推思想，期望能够借助前一次迭代的某些结果来计算下一个构造矩阵，因此可以根据上式，用第 k+1 次构造矩阵 Ak+1 近似代替 Hk-1，则,上式即产生构造矩阵 Ak+1 应满足的一个重要条件，通常称为拟牛顿条件或拟牛顿方程,DFP法变尺度矩阵的递推公式,经过数学推导，可得DFP法变尺度矩阵的递推公式为：,DFP公式,由上式可以看出，

33、构造矩阵Ak+1的确定取决于第 k 次迭代中的下列信息：,上次的构造矩阵：Ak迭代点的位移矢量：迭代点的梯度增量：,因此，不必作二阶导数矩阵及其求逆的计算,DFP法构造矩阵的递推公式,DFP算法的特点,DFP算法的收敛速度介于梯度法和牛顿法之间。,(2)DFP法具有二次收敛性(搜索方向的共轭性)。,对于二次函数 F(x)，DFP法所构成的搜索方向序列S(0),S(1),S(2),为一组关于海赛矩阵H共轭的矢量，即DFP法属于共轭方向法，具有二次收敛性。在任何情况下，这种方法对于二次目标函数都将在n步内搜索到目标函数的最优点，而且最后的构造矩阵 An 必等于海赛矩阵H。,DFP算法的特点,(3)

34、关于算法的稳定性。数值计算稳定性较差。,算法的稳定性是指算法的每次迭代都能使目标函数值单调下降。构造矩阵正定性从理论上肯定了DFP法的稳定性，但实际上，由于每次迭代的一维搜索只能具有一定的精确度，且存在机器运算的舍入误差，构造矩阵的正定性仍然有可能遭到破坏；为了提高实际计算中的稳定性，一方面应对一维搜索提出较高的精度要求，另一方面，当发生破坏正定性时，将构造矩阵重置为单位矩阵E重新开始，通常采用的简单办法是在 n 次迭代后重置单位矩阵,DFP算法的迭代步骤,任取初始点 x(0)给出迭代精度.计算初始点精度 及其模。若 转步骤，否则进行下一步,置k0，取 AkE,计算迭代方向，沿S(k)方向做一

35、维搜索求优化步长 a(k)，使,确定下一个迭代点,计算x(k+1)的梯度gk+1及其模，若 则转步骤，否 则转下一步,计算位移矢量 和梯度矢量,按DFP公式计算构造矩阵,置kk+1。若kn(n为优化问题的维数)返回步骤，否则返回 步骤,输出最优解（x*，F*），终止计算,例题4.6,例题4.6 用DFP尺度法求目标函数,的最优解。已知初始点，迭代精度=0.01,解：第一次迭代：,式中最优步长应用一维搜索方法在计算机上求解。为了说明问题，又因为此例目标函数简单，所以用解析法来求：,为求极小，将上式对求导，并令f()=0,得：,于是：,第二次迭代：,确定x(1)点的拟牛顿方向S(1),按DFP公式

36、计算构造矩阵,将数据代入得,则拟牛顿方向为,沿 S(1)方向进行一维搜索求最优点x(2),求一维搜索步长,则：,迭代即可结束，输出优化解,讨论：,该题的理论最优点是。按DFP搜索方向为共轭的性质，本题为二元二次函数在两次迭代后即达到最优点，本题计算结果稍有误差，这是由于一维搜索的不精确性产生的。,若在已知A1的基础上，再用DFP公式递推下一次的构造矩阵，可计算得,而计算目标函数海赛矩阵的逆阵有,DFP算法的流程图,k=n？,入口,出口,+,-,+,-,BFGS变尺度法,DFP算法由于舍入误差和一维搜索的不精确，有可能导致Ak奇异，而使数值稳定性方面不够理想。所以1970年，Broyden、Fl

37、etcher、Goldstein、Shanno等人提出一种更稳定的算法，称为BFGS算法。其校正公式为：,无约束优化问题的评价准则,1、可靠性。即在合理的精度要求下，在一定允许时间内能解出各种不同类型问题的成功率。能够解出的问题越多，则算法的可靠性越好2、有效性。即算法的解题效率。它有两个衡量标准。其一是对同一题目，在相同精度和初始条件下，比较机时多少。其二是在相同精度下，计算同一题目所需要的函数的计算次数3、简便性。一方面指实现该算法的准备工作量的大小。另一方面指算法占用存储单元的数量。,为了比较各种优化方法的特性，必须建立合理的评价准则。无约束优化方法的评价准则主要包括以下几个方面：,可靠

38、性：牛顿法较差，因为它对目标函数要求太高，解题成功率较低有效性：坐标变换法和梯度法的计算效率较低，因为它们从理论上不具有二次收敛性简便性：牛顿法和变尺度法的程序编制较复杂，牛顿法还占用较多的存储单元。,下面讨论本章所介绍的几种优化方法的适用范围：,1、一般而言，对于维数较低或者很难求得导数的目标函数，使用坐标轮换法或鲍威尔法较合适。2、对于二次性较强的目标函数，使用牛顿法效果好。3、对于一阶偏导数易求的目标函数，使用梯度法可使程序编制简单，但精度不宜过高。4、综合而言，鲍威尔法和DFP法具有较好的性能。,在选用无约束优化方法时，一方面要考虑优化方法的特点，另一方面要考虑目标函数的情况。,作业,试用鲍威尔修正算法求目标函数：F(x)=10(x1+x2-5)2+(x1-x2)2 的最优解。已知x(0)=0,0T,迭代精度=0.001,试用梯度法求目标函数：F(x)=1.5x12+0.5x22-x1x2-2x1 的最优解。已知x(0)=-2,4T,迭代精度=0.02,试用DFP变尺度法求目标函数 F(x)=x12+2x22-2x1x2-4x1 的最优解。已知x(0)=1,1T,迭代精度=0.01,