常用的无约束优化方法课件

《常用的无约束优化方法课件》由会员分享，可在线阅读，更多相关《常用的无约束优化方法课件（103页珍藏版）》请在装配图网上搜索。

1、第四章第四章 常用的无约束优化常用的无约束优化 方法方法王桂从#无约束优化问题的数学模型求上述问题最优解求上述问题最优解(x*,F*)的方法称为的方法称为无约束优化方法无约束优化方法无约束优化方法理论研究开展的比较早，构成的优无约束优化方法理论研究开展的比较早，构成的优化方法已很多，也比较成熟。使用无约束优化方法，化方法已很多，也比较成熟。使用无约束优化方法，不仅可以直接求无约束优化设计问题的最优解，而不仅可以直接求无约束优化设计问题的最优解，而且通过对无约束优化方法的研究给约束优化方法建且通过对无约束优化方法的研究给约束优化方法建立明确的概念及提供良好的基础，某些优化设计方立明确的概念及提供

2、良好的基础，某些优化设计方法就是先把优化设计问题转化为无约束问题后，再法就是先把优化设计问题转化为无约束问题后，再直接用无约束优化方法求解。直接用无约束优化方法求解。#无约束优化问题的求解方法间接法间接法直接法直接法坐标轮换法坐标轮换法鲍威尔法鲍威尔法梯度法梯度法共轭梯度法共轭梯度法牛顿法牛顿法变尺度法变尺度法Y解析法解析法(间接法间接法)：用函数的一阶、二阶导数进行求解的算法：用函数的一阶、二阶导数进行求解的算法Y直接搜索法直接搜索法(直接法直接法)：只利用函数值求最优解的解法：只利用函数值求最优解的解法解析法的收敛速率较高，直接法的可靠性较高。解析法的收敛速率较高，直接法的可靠性较高。#无

3、约束优化方法的基本过程p从选定的某从选定的某初始点初始点x(k)出发，沿着以一定规律产生的出发，沿着以一定规律产生的搜索方搜索方向向S(k)，取适当的，取适当的步长步长a(k)，逐次搜寻函数值下降的，逐次搜寻函数值下降的新迭代点新迭代点x(k+1)，使之逐步逼近，使之逐步逼近最优点最优点x*。p初始点初始点x(k)、搜索方向搜索方向S(k)、迭代步长迭代步长a(k)称为优化方法算法称为优化方法算法的的三要素。三要素。其中以其中以搜索方向搜索方向S(k)更为突出和重要，它从根本上更为突出和重要，它从根本上决定着一个算法的成败、收敛速率的快慢等决定着一个算法的成败、收敛速率的快慢等p所以，一个算法

4、的所以，一个算法的搜索方向搜索方向成为该优化方法的成为该优化方法的基本标志基本标志，分析、确定搜索方向分析、确定搜索方向S(k)是研究优化方法的最根本的任务之一是研究优化方法的最根本的任务之一#4.1 坐标轮换法p坐标轮换法由坐标轮换法由Desopo于于1959年提出；年提出；p坐标轮换法是每次搜索只允许一个变量变化，坐标轮换法是每次搜索只允许一个变量变化，其余变量保持不变，即沿坐标方向轮流进行搜其余变量保持不变，即沿坐标方向轮流进行搜索的寻优方法；索的寻优方法；p坐标轮换法把多变量的优化问题轮流地转化成坐标轮换法把多变量的优化问题轮流地转化成了单变量的优化问题。了单变量的优化问题。属于直接搜

5、索法。即只需要目标函数的数值信属于直接搜索法。即只需要目标函数的数值信息而不需要目标函数的导数；息而不需要目标函数的导数；#4.1 坐标轮换法-基本原理既可以用于无约束优化问题的求解，又可以经过适既可以用于无约束优化问题的求解，又可以经过适当的处理用于约束优化问题；当的处理用于约束优化问题；基本特征基本特征：将：将迭代方向迭代方向 S 取为一系列按序号排列的取为一系列按序号排列的坐标轴方向，通常都用坐标轴方向，通常都用单位矢量单位矢量 ei 作为迭代的方向矢作为迭代的方向矢量。对于量。对于n 维优化问题，当维优化问题，当 n 个坐标轴方向依次取过个坐标轴方向依次取过一次后，称为完成了一轮迭代。

6、一次后，称为完成了一轮迭代。基本原理基本原理：将一个：将一个 n 维的无约束最优化问题转化为维的无约束最优化问题转化为一系列沿坐标轴方向的一维搜索问题来求解。在每一一系列沿坐标轴方向的一维搜索问题来求解。在每一次迭代中，只改变次迭代中，只改变 n 个变量中的一个，其余变量固定个变量中的一个，其余变量固定不动，因此常称为不动，因此常称为单变量法单变量法或或变量交错法变量交错法或或降维法降维法#4.1 坐标轮换法-迭代步长的确定在沿坐标轴方向的搜索中，利用一维优化方法来确定沿该方向在沿坐标轴方向的搜索中，利用一维优化方法来确定沿该方向上具有最小目标函数值的步长，即：上具有最小目标函数值的步长，即：

7、先选择一个不大的初始步长先选择一个不大的初始步长 a0，在每次一维搜索中都是先沿正，在每次一维搜索中都是先沿正向从向从 a 到到 a0，开始做试探计算函数值，若函数值下降，则以倍，开始做试探计算函数值，若函数值下降，则以倍增的速度加大步长，步长序列为增的速度加大步长，步长序列为a0,2a0,4a0 直到函数值保持直到函数值保持下降的最后一个步长为止。下降的最后一个步长为止。(1)最优步长最优步长(2)加速步长加速步长在无约束优化问题求解中采用最优步长方法是方便的。在无约束优化问题求解中采用最优步长方法是方便的。#4.1 坐标轮换法坐标轮换法-迭代过程迭代过程第一轮迭代：第一轮迭代：(2)以以

8、x1(1)为新起点，沿第二为新起点，沿第二坐标轴的方向坐标轴的方向e2=0 1T作作一一维搜索，确定步长维搜索，确定步长 2(1)，得，得第一轮的第二个迭代点第一轮的第二个迭代点：x2(1)=x1(1)+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(

9、2)+1(2)e1x2(2)=x1(2)+2(2)e2第二轮第二轮迭代：迭代：依次依次类推类推,可进行第三轮、第可进行第三轮、第四轮四轮迭代迭代注意：右上角括号内的数字表注意：右上角括号内的数字表示轮数，右下角数字表示该轮示轮数，右下角数字表示该轮中的第几个迭代点号中的第几个迭代点号#4.1 坐标轮换法坐标轮换法-终止准则终止准则采用点距准则采用点距准则 注意注意：若采用点距准则或函数值准则，其中采用的点应该若采用点距准则或函数值准则，其中采用的点应该是一轮迭代的始点和终点，而不是某搜索方向的前是一轮迭代的始点和终点，而不是某搜索方向的前后迭代点。后迭代点。#4.1 坐标轮换法坐标轮换法-计算

10、步骤计算步骤 任选初始点任选初始点作为第一轮的起点作为第一轮的起点 ，置，置n个坐标轴方向矢量为单位坐标矢量：个坐标轴方向矢量为单位坐标矢量：#按照下面迭代公式进行迭代计算按照下面迭代公式进行迭代计算k为迭代轮数的序号，取为迭代轮数的序号，取 k=1，2，；i为该轮中一维搜索的序号，取为该轮中一维搜索的序号，取 i=1，2，n步长步长一般通过一维优化方法求出其最优步长一般通过一维优化方法求出其最优步长 按下式判断是否终止迭代按下式判断是否终止迭代如满足，迭代终止，如满足，迭代终止，如满足，迭代终止，如满足，迭代终止，并输出最优解并输出最优解并输出最优解并输出最优解最优解最优解否则，令否则，令否

11、则，令否则，令k kk+1+1返回步骤（返回步骤（返回步骤（返回步骤（2 2）#例题例题4.1例题例题4.1 用坐标轮换法求目标函数用坐标轮换法求目标函数 的无约束最优解。给定初始点的无约束最优解。给定初始点 x(0)=0,0T，精度要求，精度要求=0.1解：解：做第一轮迭代计算做第一轮迭代计算沿沿e1方向进行一维搜索方向进行一维搜索式中，式中，为第一轮的起始点，取为第一轮的起始点，取按最优步长原则确定最优步长按最优步长原则确定最优步长1，即极小化，即极小化#暂且用微分学求导解出，令其一阶导数为零暂且用微分学求导解出，令其一阶导数为零以以 为新起点，沿为新起点，沿 e2 方向一维搜索方向一维搜

12、索以最优步长原则确定以最优步长原则确定2，即为极小化，即为极小化#对于第一轮按终止条件检验对于第一轮按终止条件检验继续进行第继续进行第2轮迭代计算。轮迭代计算。计算计算5轮后，有轮后，有故近似优化解为故近似优化解为#坐标轮换法的流程图-+#小结坐标轮换法程序简单，易于掌握。但是计算效率比较坐标轮换法程序简单，易于掌握。但是计算效率比较低，尤其是当优化问题的维数较高时更为严重。一般低，尤其是当优化问题的维数较高时更为严重。一般把此种方法应用于维数小于把此种方法应用于维数小于10的低维优化问题。的低维优化问题。优化效率在很大程度上取决于目标函数的形态优化效率在很大程度上取决于目标函数的形态#4.2

13、 鲍威尔(Powell)法鲍威尔法是鲍威尔法是直接搜索法直接搜索法中一个十分有效的算法。该算中一个十分有效的算法。该算法是沿着逐步产生的法是沿着逐步产生的共轭方向共轭方向进行搜索的，因此本质上进行搜索的，因此本质上是一种是一种共轭方向法共轭方向法。其其收敛速度较快收敛速度较快，一般认为对于维数，一般认为对于维数 n 20 的目标函的目标函数是成功的。数是成功的。1964年，鲍威尔提出该种算法，其基本思想是直接利年，鲍威尔提出该种算法，其基本思想是直接利用迭代点的目标函数值来构造共轭方向，然后从任一初用迭代点的目标函数值来构造共轭方向，然后从任一初始点开始，逐次沿共轭方向做一维搜索。始点开始，逐

14、次沿共轭方向做一维搜索。#4.2.1 鲍威尔基本算法鲍威尔基本算法#4.2.1 鲍威尔基本算法三维二次目标函数的鲍威尔基本算法的搜索过程三维二次目标函数的鲍威尔基本算法的搜索过程#三维二次目标函数的鲍威尔算法搜索过程基本方向组：基本方向组：任选初始点任选初始点x0(1)，按照单位，按照单位坐标矢量系依次沿坐标矢量系依次沿e1,e2,e3作作一维搜索，得各自方向上的极小点：一维搜索，得各自方向上的极小点：x1(1),x2(1),x3(1)。然后将始末两点。然后将始末两点相连作为相连作为新生方向新生方向：S1=x3(1)-x0(1)，再沿此方向作一维搜索，再沿此方向作一维搜索，得到该得到该方向上的

15、一维极小点方向上的一维极小点 x(1)，并作为下一环的初始点。，并作为下一环的初始点。第一环迭代：第一环迭代：基本方向组：基本方向组：e2,e3，S1 将上环的第一个方向淘汰，上环的新生方将上环的第一个方向淘汰，上环的新生方向补入本环的最后。依次沿这些方向做一维搜索后产生一个向补入本环的最后。依次沿这些方向做一维搜索后产生一个新方向新方向:S2=x3(2)-x0(2)，再沿此方向一维搜索得第三环的迭代终点，再沿此方向一维搜索得第三环的迭代终点 x(2)，并作为，并作为下一轮迭代的始点。这样就形成了算法的循环。下一轮迭代的始点。这样就形成了算法的循环。第二环迭代：第二环迭代：第三环迭代：第三环迭

16、代：基本方向组：基本方向组：e3,S1，S2，新生方向，新生方向为为S3=x3(3)-x0(2)#三维二次目标函数的鲍威尔算法搜索过程共轭方向：共轭方向：依次产生的依次产生的新生方向新生方向：S1,S2,S3 是一组共轭矢量。三维优化问题是一组共轭矢量。三维优化问题从本质上看，就是从初始点从本质上看，就是从初始点x0(1)开始依次沿着共轭方向开始依次沿着共轭方向S1,S2,S3 进进行了一维搜索，经由点行了一维搜索，经由点x(1)、x(2)到达到达x(3)。而每环中沿基本搜索方向。而每环中沿基本搜索方向组的一维搜索和各环方向组内方向的依次变更只是为了逐次产生组的一维搜索和各环方向组内方向的依次

17、变更只是为了逐次产生新方向，并使新生方向成为共轭方向组新方向，并使新生方向成为共轭方向组u如目标函数是三维二次正定函数，则顺次经过三个共轭方向如目标函数是三维二次正定函数，则顺次经过三个共轭方向S1,S2,S3 的一维搜索，由共轭矢量的性质可断定的一维搜索，由共轭矢量的性质可断定x(3)就是该函数的理论最优就是该函数的理论最优点；点；注意：注意：u如目标函数是非二次函数，则迭代需继续。一般是重复上述做法，如目标函数是非二次函数，则迭代需继续。一般是重复上述做法，即重置基本搜索方向组即重置基本搜索方向组e1,e2,e3循环下去。每三环组成一轮，每一循环下去。每三环组成一轮，每一轮开始都以单位坐标

18、矢量作为第一环方向组轮开始都以单位坐标矢量作为第一环方向组#鲍威尔基本算法的搜索过程推广到推广到 n 维优化问题维优化问题第一环基本方向组取单位坐标矢量系第一环基本方向组取单位坐标矢量系e1,e2,en，沿这些方向依，沿这些方向依次做一维搜索后将始末两点相连做新生方向，再沿新生方向一次做一维搜索后将始末两点相连做新生方向，再沿新生方向一维搜索，完成维搜索，完成一环一环的迭代。以后每环的基本方向组都是将上环的迭代。以后每环的基本方向组都是将上环的第一个方向淘汰，上环的新生方向补入本环最后而构成。的第一个方向淘汰，上环的新生方向补入本环最后而构成。n维维目标函数完成目标函数完成 n 环的迭代过程称

19、为环的迭代过程称为一轮一轮。u对于二次正定目标函数，一轮的终点即为最优点；对于二次正定目标函数，一轮的终点即为最优点；u对于非二次函数，重置初始基本方向组为单位坐标矢量系进行对于非二次函数，重置初始基本方向组为单位坐标矢量系进行第二轮迭代，依次做第三轮、第四轮第二轮迭代，依次做第三轮、第四轮直到在某轮中第直到在某轮中第 k 环的环的始末两点距离达到预期的精度要求时：终止迭代始末两点距离达到预期的精度要求时：终止迭代#鲍威尔基本算法的缺陷若在优化搜索过程中出现若在优化搜索过程中出现 1(k)=0(或近似等于或近似等于0)，则方向，则方向 Sk 表示为表示为S2(k),S3(k),Sn(k)的线性

20、组合，则第的线性组合，则第 k+1 环搜索方环搜索方向组向组S2(k),S3(k),Sn(k),Sk是一个线性相关矢量系，以后的是一个线性相关矢量系，以后的各次搜索将在降维的空间进行，无法得到各次搜索将在降维的空间进行，无法得到 n 维空间的函数维空间的函数极小值，计算将失败。这种现象称为极小值，计算将失败。这种现象称为“退化退化”。基本方向组为：基本方向组为：各方向最优步长：各方向最优步长：新生方向：新生方向：鲍威尔基本算法有一个缺陷，它有可能在某环迭代中出现基鲍威尔基本算法有一个缺陷，它有可能在某环迭代中出现基本方向组为线性相关的矢量系，说明如下：如在第本方向组为线性相关的矢量系，说明如下

21、：如在第k 环中，环中，#鲍威尔基本算法的退化x1x2x31=02e23e3S1如图所示为一个三维优如图所示为一个三维优化问题的示例，设第一化问题的示例，设第一环中环中 1=0，则新生方，则新生方向与向与e2、e3 共面，随后共面，随后的各环方向组中，各矢的各环方向组中，各矢量必在该平面内，使搜量必在该平面内，使搜索局限于二维空间，不索局限于二维空间，不能得到最优解。能得到最优解。#4.2.3 鲍威尔修正算法在某环已经取得的在某环已经取得的n+1各方向中，选取各方向中，选取 n 个线性无关的并且共轭程度尽个线性无关的并且共轭程度尽可能高的方向作为下一环的基本方向组可能高的方向作为下一环的基本方

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

23、方向组 S1(k),S2(k),Sn(k)。k+1环的初环的初始点取始点取 x0(k+1)=xn(k)F2 0将拟牛顿方向带入上式，得：将拟牛顿方向带入上式，得：-S(k)T gk=Ak gkTgk=gkTAk gk 0所以只要所以只要 Ak 为对阵正定矩阵，为对阵正定矩阵，S(k)就是下降方向。就是下降方向。#简便性简便性变尺度矩阵是随迭代过程的推进而逐次改变的，因而它是变尺度矩阵是随迭代过程的推进而逐次改变的，因而它是一种矩阵序列一种矩阵序列选取初始矩阵选取初始矩阵A0，并以梯度方向快速收敛，通常取单位矩，并以梯度方向快速收敛，通常取单位矩阵阵E 作为初始矩阵，即作为初始矩阵，即A0=E。

24、而后的矩阵均是在前一构造。而后的矩阵均是在前一构造矩阵的基础上校正得到，令矩阵的基础上校正得到，令推广到一般的推广到一般的k+1次构造矩阵次构造矩阵 Ak，k=1，2，A1=A0+A0Ak+1=Ak+Ak矩阵序列的矩阵序列的基本迭代式基本迭代式 Ak 称为称为校正矩阵校正矩阵#拟牛顿条件拟牛顿条件构造矩阵构造矩阵Ak+1应该满足一个重要条件应该满足一个重要条件拟牛顿拟牛顿条件条件变尺度法采用构造矩阵来代替牛顿法中海赛矩变尺度法采用构造矩阵来代替牛顿法中海赛矩阵的逆阵，主要目的之一就是为了避免计算二阵的逆阵，主要目的之一就是为了避免计算二阶偏导数和逆矩阵，力图仅用梯度和其他一些阶偏导数和逆矩阵，

25、力图仅用梯度和其他一些易于获得的信息来确定迭代方向，因此，易于获得的信息来确定迭代方向，因此，拟牛拟牛顿条件是关于海赛矩阵和梯度之间的关系顿条件是关于海赛矩阵和梯度之间的关系。#拟牛顿条件拟牛顿条件设设F(x)为一般形式为一般形式 n 阶的目标函数，并具有连续的一、二阶的目标函数，并具有连续的一、二阶偏导。在点阶偏导。在点 x(k)处的二次泰勒近似展开处的二次泰勒近似展开该近似二次函数的梯度为：该近似二次函数的梯度为：式中，式中，若令，若令 ，则有，则有#上式中，上式中，x(k+1)x(k)称之为称之为位移矢量位移矢量，并简化书写，并简化书写:而而gk+1-gk 是前后迭代点的是前后迭代点的梯

26、度矢量差，梯度矢量差，简化书写：简化书写：由以上三式得由以上三式得：海赛矩阵与海赛矩阵与梯度间的关系式梯度间的关系式#拟牛顿条件拟牛顿条件按照变尺度法产生构造矩阵的递推思想，期望能够借助前按照变尺度法产生构造矩阵的递推思想，期望能够借助前一次迭代的某些结果来计算下一个构造矩阵，因此可以根一次迭代的某些结果来计算下一个构造矩阵，因此可以根据上式，用第据上式，用第 k+1 次构造矩阵次构造矩阵 Ak+1 近似代替近似代替 Hk-1，则，则上式即产生构造矩阵上式即产生构造矩阵 Ak+1 应满足的一个重要条件，应满足的一个重要条件，通常称为通常称为拟牛顿条件拟牛顿条件或或拟牛顿方程拟牛顿方程#DFP法

27、变尺度矩阵的递推公式法变尺度矩阵的递推公式经过数学推导，可得经过数学推导，可得DFP法变尺度矩阵的递推公式为：法变尺度矩阵的递推公式为：DFP公式公式#由上式可以看出，构造矩阵由上式可以看出，构造矩阵Ak+1的确定取决于第的确定取决于第 k 次迭代次迭代中的下列信息：中的下列信息：上次的构造矩阵：上次的构造矩阵：Ak迭代点的位移矢量：迭代点的位移矢量：迭代点的梯度增量：迭代点的梯度增量：因此，不必作二阶导数矩阵及其求逆的计算因此，不必作二阶导数矩阵及其求逆的计算DFP法构造矩阵的递推公式法构造矩阵的递推公式#DFP算法的特点算法的特点 DFP算法的收敛速度介于梯度法和牛顿法之间。算法的收敛速度

28、介于梯度法和牛顿法之间。(2)DFP法具有二次收敛性法具有二次收敛性(搜索方向的共轭性搜索方向的共轭性)。对于二次函数对于二次函数 F(x)，DFP法所构成的搜索方向序列法所构成的搜索方向序列S(0),S(1),S(2),为一组关于海赛矩阵为一组关于海赛矩阵H共轭的矢量，共轭的矢量，即即DFP法属于法属于共轭方向法共轭方向法，具有，具有二次收敛性二次收敛性。在任。在任何情况下，这种方法对于二次目标函数都将在何情况下，这种方法对于二次目标函数都将在n步内步内搜索到目标函数的最优点，而且最后的构造矩阵搜索到目标函数的最优点，而且最后的构造矩阵 An 必等于海赛矩阵必等于海赛矩阵H。#DFP算法的特

29、点算法的特点(3)关于算法的稳定性。数值计算稳定性较差。关于算法的稳定性。数值计算稳定性较差。l算法的稳定性算法的稳定性是指算法的每次迭代都能使目标函数是指算法的每次迭代都能使目标函数值单调下降。值单调下降。l构造矩阵正定性从理论上肯定了构造矩阵正定性从理论上肯定了DFP法的稳定性，法的稳定性，但实际上，由于每次迭代的一维搜索只能具有一定的但实际上，由于每次迭代的一维搜索只能具有一定的精确度，且存在机器运算的舍入误差，构造矩阵的正精确度，且存在机器运算的舍入误差，构造矩阵的正定性仍然有可能遭到破坏；定性仍然有可能遭到破坏；l为了提高实际计算中的稳定性，为了提高实际计算中的稳定性，一方面一方面应

30、对一维搜应对一维搜索提出较高的精度要求，索提出较高的精度要求，另一方面另一方面，当发生破坏正定，当发生破坏正定性时，将构造矩阵重置为单位矩阵性时，将构造矩阵重置为单位矩阵E重新开始，重新开始，通常通常采用的简单办法是在采用的简单办法是在 n 次迭代后重置单位矩阵次迭代后重置单位矩阵#DFP算法的迭代步骤算法的迭代步骤 任取初始点任取初始点 x(0)给出迭代精度给出迭代精度.计算初始点精度计算初始点精度 及其模及其模 。若。若 转步骤转步骤，否则进行下一步，否则进行下一步 置置k0，取，取 AkE 计算迭代方向计算迭代方向 ，沿，沿S(k)方向做一维搜索求优化步长方向做一维搜索求优化步长 a(k

31、)，使，使确定下一个迭代点确定下一个迭代点#计算计算x(k+1)的梯度的梯度gk+1及其模及其模 ，若，若 则转步骤则转步骤，否否 则转下一步则转下一步 计算位移矢量计算位移矢量 和梯度矢量和梯度矢量按按DFP公式计算构造矩阵公式计算构造矩阵 置置kk+1。若。若kn(n为优化问题的维数为优化问题的维数)返回步骤返回步骤，否则返回，否则返回 步骤步骤 输出最优解（输出最优解（x*，F*），终止计算），终止计算#例题例题4.6例题例题4.6 用用DFP尺度法求目标函数尺度法求目标函数的最优解。已知初始点的最优解。已知初始点 ，迭代精度，迭代精度=0.01解：解：第一次迭代：第一次迭代：#式中最优

32、步长应用一维搜索方法在计算机上求解。为了说明问题，式中最优步长应用一维搜索方法在计算机上求解。为了说明问题，又因为此例目标函数简单，所以用解析法来求：又因为此例目标函数简单，所以用解析法来求：为求极小，将上式对为求极小，将上式对求导，并令求导，并令f()=0得：得：于是：于是：#第二次迭代：第二次迭代：确定确定x(1)点的拟牛顿方向点的拟牛顿方向S(1)按按DFP公式计算构造矩阵公式计算构造矩阵#将数据代入得将数据代入得则拟牛顿方向为则拟牛顿方向为沿沿 S(1)方向进行一维搜索求最优点方向进行一维搜索求最优点x(2)求一维搜索步长求一维搜索步长#则：则：迭代即可结束，输出优化解迭代即可结束，输

33、出优化解#讨论：讨论：该题的理论最优点是该题的理论最优点是 。按。按DFP搜索方向为共轭的性搜索方向为共轭的性质，本题为二元二次函数在两次迭代后即达到最优点，本题计算质，本题为二元二次函数在两次迭代后即达到最优点，本题计算结果稍有误差，这是由于一维搜索的不精确性产生的。结果稍有误差，这是由于一维搜索的不精确性产生的。若在已知若在已知A1的基础上，再用的基础上，再用DFP公式递推下一次的构造矩阵，可公式递推下一次的构造矩阵，可计算得计算得而计算目标函数海赛矩阵的逆阵有而计算目标函数海赛矩阵的逆阵有#DFP算法的流程图k=n？入口入口出口出口+-+-#BFGS变尺度法变尺度法DFP算法由于舍入误差

34、和一维搜索的不精确，有可能导致算法由于舍入误差和一维搜索的不精确，有可能导致Ak奇异，而使数值稳定性方面不够理想。所以奇异，而使数值稳定性方面不够理想。所以1970年年，Broyden、Fletcher、Goldstein、Shanno等人等人提出提出一种一种更稳更稳定的算法，称为定的算法，称为BFGS算法。其校正公式为算法。其校正公式为：#无约束优化问题的评价准则无约束优化问题的评价准则1、可靠性、可靠性。即在合理的精度要求下，在一定允许时间内。即在合理的精度要求下，在一定允许时间内能解出各种不同类型问题的成功率。能够解出的问题越能解出各种不同类型问题的成功率。能够解出的问题越多，则算法的可

35、靠性越好多，则算法的可靠性越好2、有效性、有效性。即算法的解题效率。它有两个衡量标准。其。即算法的解题效率。它有两个衡量标准。其一是对同一题目，在相同精度和初始条件下，比较机时一是对同一题目，在相同精度和初始条件下，比较机时多少。其二是在相同精度下，计算同一题目所需要的函多少。其二是在相同精度下，计算同一题目所需要的函数的计算次数数的计算次数3、简便性、简便性。一方面指实现该算法的准备工作量的大小。一方面指实现该算法的准备工作量的大小。另一方面指算法占用存储单元的数量。另一方面指算法占用存储单元的数量。为了比较各种优化方法的特性，必须建立合理的评价准则。为了比较各种优化方法的特性，必须建立合理

36、的评价准则。无约束优化方法的评价准则主要包括以下几个方面：无约束优化方法的评价准则主要包括以下几个方面：#可靠性可靠性：牛顿法较差，因为它对目标函数要求太高，：牛顿法较差，因为它对目标函数要求太高，解题成功率较低解题成功率较低有效性有效性：坐标变换法和梯度法的计算效率较低，因：坐标变换法和梯度法的计算效率较低，因为它们从理论上不具有二次收敛性为它们从理论上不具有二次收敛性简便性简便性：牛顿法和变尺度法的程序编制较复杂，牛：牛顿法和变尺度法的程序编制较复杂，牛顿法还占用较多的存储单元。顿法还占用较多的存储单元。下面讨论本章所介绍的几种优化方法的适用范围：下面讨论本章所介绍的几种优化方法的适用范围

37、：#1 1、一般而言，对于维数较低或者很难求得导数的目标、一般而言，对于维数较低或者很难求得导数的目标函数，使用坐标轮换法或鲍威尔法较合适。函数，使用坐标轮换法或鲍威尔法较合适。2 2、对于二次性较强的目标函数，使用牛顿法效果好。、对于二次性较强的目标函数，使用牛顿法效果好。3 3、对于一阶偏导数易求的目标函数，使用梯度法可使、对于一阶偏导数易求的目标函数，使用梯度法可使程序编制简单，但精度不宜过高。程序编制简单，但精度不宜过高。4 4、综合而言，鲍威尔法和、综合而言，鲍威尔法和DFPDFP法具有较好的性能。法具有较好的性能。在选用无约束优化方法时，一方面要考虑优化方法的特点，在选用无约束优化

38、方法时，一方面要考虑优化方法的特点，另一方面要考虑目标函数的情况。另一方面要考虑目标函数的情况。#作业作业1.试用试用鲍威尔修正算法鲍威尔修正算法求目标函数求目标函数：F(x)=10(x1+x2-5)2+(x1-x2)2 的最优解。已知的最优解。已知x(0)=0,0T,迭代精度迭代精度=0.0012.试用试用梯度法梯度法求目标函数：求目标函数：F(x)=1.5x12+0.5x22-x1x2-2x1 的最优解。已知的最优解。已知x(0)=-2,4T,迭代精度迭代精度=0.023.试用试用DFP变尺度法变尺度法求目标函数求目标函数 F(x)=x12+2x22-2x1x2-4x1 的最优解。已知的最优解。已知x(0)=1,1T,迭代精度迭代精度=0.01