《无约束优化方法》PPT课件.ppt

1,第四章 常用的无约束优化方法,4.1 坐标轮换法 4.2 鲍威尔(Powell)法 4.3 梯度法 4.5 牛顿法 4.6 DFP变尺度法 4.7 BFGS变尺度法 无约束优化方法的评价准则及选用,2,若存在 则称X*点为无约束最优点，F(X) 为无约束最优值。 直接搜索法：坐标轮换法、鲍威尔法 方法 间接法：梯度法、牛顿法、变尺度法 直接搜索法：只需进行函数值的计算与比较来确定迭代方向和步长 间接法：利用函数的一阶或二阶偏导数矩阵来确定迭代方向和步长,对于无约束优化问题:,3,4.1 坐标轮换法,基本思想：把一个n维无约束最优化问题转化为依次沿n个坐标轴方向的一维最优化问题。 即迭代方向依次为:,第一轮: 任取一初始点X(0),第二轮:,4,终止准则:,上式点距准则中的两点应是一轮迭代的始点与终点,利用一维优化方法确定沿该方向上具有最小目标函数值的步长， 即: minF(X(k)+S(k)=F(X(k)+(k)S(k),迭代步长的确定:,5,坐 标 轮 换 法 的 流 程 图,6,坐标轮换法的特点:,具有程序结构简单，易于掌握等优点。但收敛慢， 适用于n10的低维优化问题 。 另收敛速度与等值线的形状有关,7,例题4.1,用坐标轮换法求目标函数 的无约束最优解。给定初始点 精度要求=0.1,解：作第一轮迭代计算。 沿e1方向进行一维搜索,按最优步长原则确定步长1，即极小化,此问题可用某种一维优化方法求出1。在这里，我们暂且借用微分学求导解出，令其一阶导数为零，1=5,以最优步长原则确定2，即极小化,得2=4.5，,对于第一轮按终止条件检验,8,例题4.1,对于第一轮按终止条件检验:,继续第二轮迭代计算。以下各轮的计算结果列于表4.1。,9,例题4.1,计算五轮后有,故近似优化解为,F*F(x*)=7.95025,10,例题4.1 用解析法验证,解:令,正定,11,4.2 鲍威尔(Powell)法,鲍威尔法是直接搜索法中一个十分有效的算法。该算法是沿着逐步产生的共轭方向进行搜索的，因此本质上是一种共轭方向法，鲍威尔法的收敛速率较快。 以共轭方向作为搜索方向，不只限于鲍威尔法，也用于其他一些较为有效的方法，可以统称为共轭方向法。因此，共轭方向的概念在优化方法研究中占有重要的地位。 共轭方向在最优化问题中的应用是基于其具有一个重要性质，即：设 S1、S2、Sn是关于A的n个互相共轭的向量，则对于求正定二次函数 的极小点，从 任意初始点出发，依次沿Si （i=1，2，n)方向进行一维最优化搜索，至多n步便可以收敛到极小点,12,2.5 关于优化方法中搜寻方向的理论基础 2.5.2 共轭方向(见第二章),一、共轭方向的基本概念 若有两个n维矢量S1、S2，对nn阶对称正定矩阵A能满足:,称n维空间矢量S1与S2对A共轭 共轭矢量所代表的方向称为共轭方向。,正交:可以看作是共轭的特例,例:(1),共轭并正交,13,例:(2),共轭但不正交,设A为nn阶实对称正定矩阵，有一组非零的n维矢量S1、S2、Sq，若满足 ij 则称矢量系Si(i1，2，qn)对于矩阵A共轭,14,以二维函数为例: 二维正定二次函数具有两个重要特性：,1）二维正定二次函数的等值线是同心的椭圆族，且椭圆中心就 是正定二元二次函数的极小点。 2) 过同心椭圆族中心x*作任意直线，此直线与诸椭圆交点处的切线相互平行。或者说：两条平行的任意方向的切线,其切点的连线必通过椭圆簇的中心。,可以证明上诉S1和S2方向是 关于矩阵A的共轭方向。,15,S1与S2是对A共轭的一对矢量,证明：,梯度,而,即,结论: 两个平行方向的极小点构成的新方向与原方向相互共轭 即S1与S2对A共轭,也即对于二维正定二次函数只要分别沿两个共轭方向寻优即可找到最优点.,16,与此类似，可以推出对于n维正定二次函数，共轭方向的一个十分重要的极为有用的性质：从任意初始点出发，依次沿n个线性无关的与A共轭的方向S1，S2，Sn各进行一维搜索，那么总能在第n步或n步之前就能达到n维正定二次函数的极小点；并且这个性质与所有的n个方向的次序无关。简言之，用共轭方向法对于二次函数从理论上来讲，n步就可达到极小点。因而说共轭方向法具有有限步收敛的特性。通常称具有这种性质的算法为二次收敛算法。 共轭矢量之所以引起优化研究者的重视，就是因为它的这些性质对提高优化方法的收敛速率极为有用。,17,例,解： (1) 第一个搜索方向,(2) 函数的海赛矩阵 对称正定,18,例,解： (4) 任取另初始点,沿S1方向一维搜索求得该方向极小点x(2),X(2)=,(5) 求与S1相共轭的方向S2,S2=X(2)-X(1)=,核验计算,矢量S1与S2确为对A矩阵共轭。,(6) 从x(1)点出发，沿S2方向作一维搜索，得极小点 X*=0 0T,19,4.2.1 鲍威尔基本算法（共轭方向的原始构成）,20,4.2.1 鲍威尔基本算法,任取一初始点 X(0) X0(1) 第一环: e1, e2, e3 S1 第二环: e2, e3 , S1 S2 第三环: e3 , S1 , S2 S3,第 一 轮,S1 , S2 , S3 两两共轭,由前结论: 两个平行方向的极小点构成的新方向与原方向相互共轭,21,4.2.1 鲍威尔基本算法,第一环: e1, e2, e3 S1 第二环: e2, e3 , S1 S2 第三环: e3 , S1 , S2 S3,第 一 轮,S1是e1, e2, e3 的线性组合 S2是e2, e3 , S1的线性组合 S3是e3 , S1 , S2的线性组合,新一环方向组: e2, e3 , S1 线性相关!,降维,22,鲍威尔法的基本思想: 对原始共轭方向法进行修正,即在某环已取得的n+1个方向中,选取n 个线性无关,共轭程度尽可能高的方向作为下一环的基本方向组,从而避免出现“退化”现象. 鲍威尔法与原始共轭方向法的主要区别是： 在构成K+1环基本方向组时，不再总是淘汰前一环(K环)中的第一个方向，而是根据条件式 是否得到满足分两种情况来处理。,4.2.1 鲍威尔修正算法,23,映射点,一、Powell 修正算法的搜索方向,Powell 判别式,24,情况一： Powell 判别式中若至少 有一个不等式成立，则 第K+1环的方向组仍用老方向组,初始点:,当F2 F3时, 当F2F3时,情况二： Powell 判别式中若两个 不等式均不成立，则 第K+1环的方向组,去掉函数值下降最大的方向,补上新增的方向 初始点:,25,以二维为例: 两条件式至少有一成立且F2F3,26,两条件式均不成立且m=1 两条件式均不成立且m=2,27,终止准则:,采用了上述产生基本方向组的新方式后，除了第一环以单位坐标矢量系为基本方向组外，以后每轮开始就不必重置单位坐标矢量系，只要一环接一环继续进行即可。随着逐环迭代的继续，各环的基本方向组将渐趋共轭。因此，这个修正了的鲍威尔算法，虽然已不再像基本算法那样具有二次收敛的性质，但修正算法确实克服了退化的不利情形，同时仍能够有效地、越来越快地收敛于无约束最优点x*。,二、修正算法的迭代步骤及流程图,28,29,解：第一环迭代计算,沿第一坐标方向e1进行一维搜索,沿第二坐标轴方向e2进行一维搜索,30,例题,沿s1方向一维搜索得极小点与极小值,需进行第二环迭代计算。,第二环迭代计算： 首先确定上环中的最大函数下降量及其相应方向,映射点及其函数值,31,检验鲍尔条件,鲍威尔条件两式均不成立。第二环基本方向组和起始点为,沿e2方向作一维搜索得,沿S1方向一维搜索得,构成新生方向,沿S2方向一维搜索得,去掉函数值下降最大的方向,补上新增的方向 初始点取新增方向的极小点,32,例题 4.2,检查迭代终止条件,需再作第三环迭代计算。,根据具体情况来分析，S1、S2实际上为共轭方向的（见图4.9）。本题又是二次函数，按共轭方向的二次收敛性质，上面的结果就是问题的最优解。可以预料，如果作第三环迭代，则一定各一维搜索的步长为零，必有,故得最优解,33,解:令,正定,用解析法验证,得:,34,鲍威尔法的特点: 是到目前为止求解无约束优化问题的最有效的方法。不需求导数,只需计算目标函数值。适用中、小型问题。,35,梯度法的基本思想:利用函数在其负梯度方向函数值 下降最快这一局部性质，将n维无约束优化问题转化 为一系例的沿目标函数负梯度方向的一维寻优问题。,4.3 梯度法,终止准则:,取：,所以：,36,例题4.3 用梯度法求目标函数F(x)= +25 的最优解。已知初始点x(0)2 2T，迭代精度取=0.005。 解：函数的梯度,第一次迭代：以x(0)为起点沿-g(0)方向作一维搜索,初始点函数梯度值:,第一点函数梯度值:,37,38,解:令,正定,得:,用解析法验证,39,梯度法的特点:,几何概念直观,方法和程序简单,远离极小点时收敛速度快。 但越接近极小点收敛速度越慢。,40,原始牛顿法基本思想： 在点 x(k) 领域内用一个二次函数（x) 去近似代替原目标函数F(x)，然后求出这个二次函数的极小点，以该点 作为对原目标函数求优的下一个选代点 x(k+1） ，这样通过重复若干次迭代，使迭代点逐步逼近原目标函数的极小点 X* 。,4.5 牛顿法,41,注意：与一维优化方法的二次插值法的不同,每次迭代所用的二次函数就是在迭代点展开的泰勒二次多项式,42,4.5.1 原始牛顿法,一元函数f(x)在x(k)点的泰勒展开式：,n元函数F(X)在X(k)点的泰勒展开式：,43,即:,牛顿方向:,(定步长),等号两边左乘,为求极小点,令一阶导数等于零,由前：,即迭代方向：:,44,牛顿法具有二次收敛性。对于二次正定函数，迭代一次即可到达最优点；对于非二次函数，若函数的二次性态较强或迭代点已进入最优点的较小邻域，则其收敛速度也是很快的。 但原始牛顿法还存在一个问题：由于在全部迭代过程中，取步长(k)1，这种定步长有时造成函数值反而有所增大 。,45,阻尼牛顿法基本思想:阻尼牛顿法的迭代方向仍是上述牛顿方向，但每次迭代需沿此方向作一维搜索，求其最优步长因子,即迭代公式为：,4.5.2 阻尼牛顿法,46,47,例题4.5 用牛顿法求函数F(x)4(x11)22(x21)2x1x210的最优解。初始点x(0)0 0T，105。 解：函数的梯度 海赛矩阵及其逆 在x(0)点处,48,沿S(0)方向一维搜索求最优步长得 代入函数解得： (0)=1 故新迭代点为 该点的梯度 满足终止条件，迭代即可结束,49,补充: 求逆矩阵,称作矩阵A的伴随方阵, 中元素,是 中元素 的代数余子式,划去 所在行列后余下的n-1阶子式,例:,50,解:令,正定,用解析法验证 F(x)4(x11)22(x21)2x1x210,得:,51,牛顿法的特点：,牛顿法具有二次收敛性，对正定二次函数一次迭代即可达 到极小点。对目标函数性态较好或当初始点取在极小点附 近时收敛速度快。 但对目标函数有较高的要求，必须存在一阶、二阶偏导 数，H（ x(k) ）需正定且非奇异。计算复杂，计算量大。,52,梯度法和牛顿法对比,53,观察梯度法和牛顿法的迭代式： 变尺度法的基本思想：设法构造一个对称正定阵Ak代替 ,并在选代计算中，使其逐渐逼近 。因此，一旦达到极值点附近，就可望达到牛顿法的收敛速度，同时又避免了矩阵的求逆计算。 其选代公式： Ak是是根据需要构造的nn阶对称矩阵，它是随着迭代点位置的变化而变化的。,梯度法:,牛顿法:,4.6 DFP变尺度法,54,4.6.2 变尺度法构造矩阵的产生,递推方法产生:,校正矩阵,变尺度法采用构造矩阵来代替牛顿法中海赛矩阵的逆阵，其主要目的之一是为了避免计算二阶偏导数和计算它的逆矩阵，力图仅用梯度和其他一些易于获得的信息来确定迭代方向。 分析一下海赛矩阵与梯度之间的关系。,55,4.6.2 变尺度法构造矩阵的产生,海赛矩阵与梯度之间的关系,位移矢量,梯度矢量差,拟牛顿条件( 拟牛顿方程 ),PII-(84-85),DFP公式,56,4.6.3 对DFP法几个问题的说明与讨论,(1) DFP公式总有确切的解。 (2) 构造矩阵的正定性。 (3) DFP法搜索方向的共轭性。 (4) 关于算法的稳定性。 为了提高实际计算中的稳定性，一方面应对一维搜索提出较高的精度要求，另一方面在发生破坏正定性时，将构造矩阵重置为单位矩阵E重新开始，通常采用的简单办法是在n次迭代后重置单位矩阵。,4.6.4 DFP算法的迭代步骤,57,例题 4.6,用DFP变尺度法求目标函数F(x)4(x15)2(x26)2的最优解。已知初始点x(0)8 9T，迭代精度0.01。 解：第一次迭代：,式中最优步长(0)应该用一维搜索方法在计算机上求解。为了说明问题，又因为此例目标函数简单，所以用解析法来求：,58,例题 4.6,为求极小，将上式对求导，并令f ()0 得,第二次迭代： 确定x(1)点的拟牛顿方向S(1),按DFP公式计算