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

第四章常用的无约束优化方法 王桂从 无约束优化问题的数学模型 求上述问题最优解 x F 的方法称为无约束优化方法 无约束优化方法理论研究开展的比较早 构成的优化方法已很多 也比较成熟 使用无约束优化方法 不仅可以直接求无约束优化设计问题的最优解 而且通过对无约束优化方法的研究给约束优化方法建立明确的概念及提供良好的基础 某些优化设计方法就是先把优化设计问题转化为无约束问题后 再直接用无约束优化方法求解 无约束优化问题的求解方法 解析法 间接法 用函数的一阶 二阶导数进行求解的算法 直接搜索法 直接法 只利用函数值求最优解的解法 解析法的收敛速率较高 直接法的可靠性较高 无约束优化方法的基本过程 从选定的某初始点x k 出发 沿着以一定规律产生的搜索方向S k 取适当的步长a k 逐次搜寻函数值下降的新迭代点x k 1 使之逐步逼近最优点x 初始点x k 搜索方向S k 迭代步长a k 称为优化方法算法的三要素 其中以搜索方向S k 更为突出和重要 它从根本上决定着一个算法的成败 收敛速率的快慢等所以 一个算法的搜索方向成为该优化方法的基本标志 分析 确定搜索方向S k 是研究优化方法的最根本的任务之一 4 1坐标轮换法 坐标轮换法由D esopo于1959年提出 坐标轮换法是每次搜索只允许一个变量变化 其余变量保持不变 即沿坐标方向轮流进行搜索的寻优方法 坐标轮换法把多变量的优化问题轮流地转化成了单变量的优化问题 属于直接搜索法 即只需要目标函数的数值信息而不需要目标函数的导数 4 1坐标轮换法 基本原理 既可以用于无约束优化问题的求解 又可以经过适当的处理用于约束优化问题 基本特征 将迭代方向S取为一系列按序号排列的坐标轴方向 通常都用单位矢量ei作为迭代的方向矢量 对于n维优化问题 当n个坐标轴方向依次取过一次后 称为完成了一轮迭代 基本原理 将一个n维的无约束最优化问题转化为一系列沿坐标轴方向的一维搜索问题来求解 在每一次迭代中 只改变n个变量中的一个 其余变量固定不动 因此常称为单变量法或变量交错法或降维法 4 1坐标轮换法 迭代步长的确定 在沿坐标轴方向的搜索中 利用一维优化方法来确定沿该方向上具有最小目标函数值的步长 即 先选择一个不大的初始步长a0 在每次一维搜索中都是先沿正向从a到a0 开始做试探计算函数值 若函数值下降 则以倍增的速度加大步长 步长序列为a0 2a0 4a0 直到函数值保持下降的最后一个步长为止 1 最优步长 2 加速步长 在无约束优化问题求解中采用最优步长方法是方便的 4 1坐标轮换法 迭代过程 第一轮迭代 2 以x1 1 为新起点 沿第二坐标轴的方向e2 01 T作一维搜索 确定步长 2 1 得第一轮的第二个迭代点 x2 1 x1 1 1 1 e2 1 任取一初始点x 0 作为初始点x0 1 先沿第一坐标轴的方向e1 10 T作一维搜索 用一维优化方法确定最优步长 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坐标轮换法 终止准则 采用点距准则 注意 若采用点距准则或函数值准则 其中采用的点应该是一轮迭代的始点和终点 而不是某搜索方向的前后迭代点 4 1坐标轮换法 计算步骤 任选初始点 作为第一轮的起点 置n个坐标轴方向矢量为单位坐标矢量 按照下面迭代公式进行迭代计算 k为迭代轮数的序号 取k 1 2 i为该轮中一维搜索的序号 取i 1 2 n步长 一般通过一维优化方法求出其最优步长 按下式判断是否终止迭代 如满足 迭代终止 并输出最优解 最优解 否则 令k k 1返回步骤 2 例题4 1 例题4 1用坐标轮换法求目标函数的无约束最优解 给定初始点x 0 0 0 T 精度要求 0 1 解 做第一轮迭代计算 沿e1方向进行一维搜索 式中 为第一轮的起始点 取 按最优步长原则确定最优步长 1 即极小化 暂且用微分学求导解出 令其一阶导数为零 以为新起点 沿e2方向一维搜索 以最优步长原则确定 2 即为极小化 对于第一轮按终止条件检验 继续进行第2轮迭代计算 计算5轮后 有 故近似优化解为 坐标轮换法的流程图 小结 坐标轮换法程序简单 易于掌握 但是计算效率比较低 尤其是当优化问题的维数较高时更为严重 一般把此种方法应用于维数小于10的低维优化问题 优化效率在很大程度上取决于目标函数的形态 4 2鲍威尔 Powell 法 鲍威尔法是直接搜索法中一个十分有效的算法 该算法是沿着逐步产生的共轭方向进行搜索的 因此本质上是一种共轭方向法 其收敛速度较快 一般认为对于维数n 20的目标函数是成功的 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 e3 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 而每环中沿基本搜索方向组的一维搜索和各环方向组内方向的依次变更只是为了逐次产生新方向 并使新生方向成为共轭方向组 如目标函数是三维二次正定函数 则顺次经过三个共轭方向S1 S2 S3的一维搜索 由共轭矢量的性质可断定x 3 就是该函数的理论最优点 注意 如目标函数是非二次函数 则迭代需继续 一般是重复上述做法 即重置基本搜索方向组e1 e2 e3循环下去 每三环组成一轮 每一轮开始都以单位坐标矢量作为第一环方向组 鲍威尔基本算法的搜索过程 推广到n维优化问题 第一环基本方向组取单位坐标矢量系e1 e2 en 沿这些方向依次做一维搜索后将始末两点相连做新生方向 再沿新生方向一维搜索 完成一环的迭代 以后每环的基本方向组都是将上环的第一个方向淘汰 上环的新生方向补入本环最后而构成 n维目标函数完成n环的迭代过程称为一轮 对于二次正定目标函数 一轮的终点即为最优点 对于非二次函数 重置初始基本方向组为单位坐标矢量系进行第二轮迭代 依次做第三轮 第四轮 直到在某轮中第k环的始末两点距离达到预期的精度要求时 终止迭代 鲍威尔基本算法的缺陷 若在优化搜索过程中出现 1 k 0 或近似等于0 则方向Sk表示为S2 k S3 k Sn k 的线性组合 则第k 1环搜索方向组S2 k S3 k Sn k Sk是一个线性相关矢量系 以后的各次搜索将在降维的空间进行 无法得到n维空间的函数极小值 计算将失败 这种现象称为 退化 基本方向组为 各方向最优步长 新生方向 鲍威尔基本算法有一个缺陷 它有可能在某环迭代中出现基本方向组为线性相关的矢量系 说明如下 如在第k环中 鲍威尔基本算法的退化 x1 x2 x3 1 0 2e2 3e3 S1 如图所示为一个三维优化问题的示例 设第一环中 1 0 则新生方向与e2 e3共面 随后的各环方向组中 各矢量必在该平面内 使搜索局限于二维空间 不能得到最优解 4 2 3鲍威尔修正算法 在某环已经取得的n 1各方向中 选取n个线性无关的并且共轭程度尽可能高的方向作为下一环的基本方向组 一 鲍威尔修正算法的搜索方向 初始点 新生方向上的极小点 在第k环中 基本方向组为 新生方向 映射点 记 其中 是在第k环方向组中 依次沿各方向优化搜索函数值下降量的最大值 即Sm k 方向函数下降量最大 鲍威尔修正算法的方向淘汰 F3 F2 F1 映射点 函数下降量 判别式 1 至少一个不等式成立 则第k 1环的基本方向仍用老方向组S1 k S2 k Sn k k 1环的初始点取x0 k 1 xn k F2 F3x0 k 1 xn 1 k F2 F3 判别式 2 两式均不成立 则淘汰函数值下降最大的方向 并用第k环的新生方向补入k 1环基本方向组的最后 即k 1环的方向组为 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 2 n 得到点阵 构成新生方向 沿方向进行一维搜索求得优化步长 得 第三步 判断是否满足迭代终止条件 如满足 则可结束迭代 最优解为 停止计算 否则 继续进行下步 第四步 计算各迭代点的函数值F xi k 并找出相邻点函数值差最大者 1 m n 及与之相对应的两个点xm 1 k 和xm k 并以Sm k 表示两点的连线方向 第五步 确定映射点 并计算函数值 检验鲍威尔条件 若至少其中之一成立转下步 否则转步骤 第六步 置k 1环的基本方向组和起始点为 即取老方向组 当F2 F3 当F2 F3 令k k 1 返回步骤二 第七步 置k 1环的方向组和起始点为 令k k 1 返回步骤二 修正算法与基本算法的区别 修正算法除了第一环以单位坐标矢量系为基本方向组外 以后每轮开始就不必重置单位坐标矢量系 只要一环接一环继续进行即可 随着逐环迭代的继续 各环的基本方向组将渐趋共轭 修正了的鲍威尔算法不具有二次收敛性 但是克服了退化的不利情形 同时仍能够有效地 越来越快地收敛于无约束最优点 例题4 2 例题4 2试用鲍威尔修正算法求目标函数 的最优解 已知初始点x0 1 1 T 迭代精度 0 001 解 第一环迭代计算 沿第一坐标方向e1进行一维搜索 1 2 以x1 1 为起点 改沿第二坐标轴方向e2进行一维搜索 2 0 5 构成新方向 沿S1方向进行一维搜索得极小点与极小值 计算点距 需进行第二环迭代计算 第二环迭代计算 首先确定上环中的最大函数下降量及其相应方向 映射点及其函数值 检查鲍威尔条件 于是可知 鲍威尔条件两式均不成立 第二环取基本方向组和起始点为 沿e2方向作一维搜索得 以x1 2 为起点沿S1方向一维搜索得 构成新生方向 沿S2方向一维搜索得 检查迭代终止条件 需再作第三环迭代计算 根据具体情况来分析 S1 S2实际上为共轭方向 见下图 本题又是二次函数 由共轭方向的二次收敛性 上面结果就是问题的最优解 可以预料 如果做第三环迭代 则各一维搜索的步长一定为零 必有 故得最优解 4 3梯度法 梯度法是求解无约束优化问题的解析法之一 在理论上 这个方法极为重要 因为它不仅提供了一个简单的 在一定场合令人满意的优化算法 而且许多更有效和实用的算法也常常是在这个基本算法基础上建立起来的 函数的梯度方向是函数值增加最快的方向 则负梯度方向必然是函数值下降最快的方向 采用负梯度矢量作为一维搜索的方向 因而又称作最速下降法 4 3梯度法 最速下降法 一 迭代公式 其中 g k 函数在迭代点x k 处的梯度 F x k a k 一般采用最优步长 即通过一维极小化函数获得 4 3梯度法 据一元函数极值条件和多元复合函数求导公式 得 即 f x k 1 Tg k 0 或 g k 1 Tg k 0 此式表明 相邻的两个迭代点的梯度是彼此正交的 也即在梯度的迭代过程中 相邻的搜索方向相互垂直 梯度法向极小点的逼近路径是锯齿形路线 越接近极小点 锯齿越细 前进速度越慢 这是因为梯度是函数的局部性质 从局部上看 在该点附近函数的下降最快 但从总体上看则走了许多弯路 因此函数值的下降并不快 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 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 2 T 迭代精度 0 005 解 函数的梯度 第一次迭代 以x 0 为起点沿一方向作一维搜索 得第一个迭代点 继续第二次迭代 到第五次迭代结束时 有 故迭代可终止 最优解为 梯度法的特点 优点 程序结构简单 每次迭代所需的计算量及存储量也小 而且当迭代点离最优点较远时函数值下降速度很快 缺点 在迭代点到达最优点附近时 进展十分缓慢 而且常常由于一维搜索的步长误差而产生的挠动不可能取得较高的收敛精度 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 x k 1 kS 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 k 1 kS 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 共轭梯度法的计算框图 共轭梯度法的特点 共轭梯度法属于解析法 其算法需求一阶导数 所用公式及算法简单 所需存储量少 该方法以正定二次函数的共轭方向理论为基础 对二次型函数可以经过有限步达到极小点 所以具有二次收敛性 但是对于非二次型函数 以及在实际计算中由于计算机舍入误差的影响 虽然经过n次迭代 仍不能达到极小点 则通常以重置负梯度方向开始 搜索直至达到预定精度 其收敛速度也是较快的 4 5牛顿法 牛顿法是求无约束最优解的一种古典解析算法 牛顿法可以分为原始牛顿法和阻尼牛顿法 或称修正牛顿法 两种 现在实际中应用较多的是阻尼牛顿法 4 5 1原始牛顿法 在第k次迭代的迭代点x k 邻域内 用一个二次函数去近似代替原目标函数F x 然后求出该二次函数的极小点作为对原目标函数求优的下一个迭代点 依次类推 通过多次重复迭代 使迭代点逐步逼近原目标函数的极小点 一 原始牛顿法的基本思想 二 原始牛顿法的迭代公式 设目标函数F x 具有连续的一 二阶导数 在x k 点邻域的二次逼近函数 x 可写为F x 的二次泰勒多项式 二 原始牛顿法的迭代公式 设x 为 x 极小点 根据极值的必要条件 应有 x 的梯度等于零 即 牛顿法迭代公式 S k Hk 1gk称为牛顿方向 三 原始牛顿法的特点 优点 具有二次收敛性 对于二次函数 构造的逼近函数与原目标函数是完全相同的二次式 其等值线完全重合 故从任一点出发 迭代一次即可得到最优解 对于非二次函数 若函数二次性较强或迭代点已经进入最优点的较小邻域 则收敛速度也很快 缺点 步长恒等于1 由于迭代点的位置是按照极值条件确定的 并不能保证函数值稳定的下降 严重的情况下甚至可能造成点列的发散而导致计算的失败 三 原始牛顿法的特点 目标函数值上升 4 5 2阻尼牛顿法 修正牛顿法 为解决原始牛顿法的不足 加入最优步长因子 k 迭代公式变为 这就是阻尼牛顿法的迭代公式 最优步长 k 也称为阻尼因子 是沿牛顿方向一维搜索得到的最优步长 牛顿法算法步骤 任选初始点x 0 给定精度 置k 0 计算x k 点的梯度矢量及其模 牛顿法算法步骤 检验迭代终止条件 如满足 则输出最优解 否则 转下步 计算x k 点处的海塞矩阵 i j 1 2 n 并求其逆矩阵 确定牛顿方向 并沿牛顿方向作一维搜索 求出在S k 方向上的最优步长a k 计算第k 1个迭代点 置k k 1 返回步骤 牛顿法流程图 例题4 5 例题4 5用牛顿法求函数 的最优解 初始点 解 函数的梯度 和海赛矩阵及其逆 在x 0 点处 沿S 0 方向一维搜索求得最优步长a 0 1 故新迭代点为 该点的梯度 迭代即可结束 由于目标函数是二次正定函数 故迭代一次即达到最优点 阻尼牛顿法的特点 优点 由于阻尼牛顿法每次迭代都在牛顿方向进行一维搜索 避免了迭代后函数值上升的现象 从而保持了牛顿法的二次收敛性 而对初始点的选择没有苛刻的要求 阻尼牛顿法的特点 缺点 1 对目标函数要求苛刻 要求函数具有连续的一 二阶导数 为保证函数的稳定下降 海赛矩阵必须正定 为求逆阵要求海赛矩阵非奇异 2 计算相当复杂 除了求梯度以外 还需计算二阶偏导数和它的逆矩阵 占用机器的储存量也很大 故在工程优化设计中的应用受到一定的限制 梯度法和牛顿法的对比 牛顿法比梯度法更有效和收敛更快 这种说法是有前提的 就是当初始点x 0 与最优点x 比较接近 且两点的海赛矩阵非常接近 否则用梯度法要比牛顿法更好 4 6DFP变尺度法 变尺度法也称拟牛顿法 它是基于牛顿法的思想而又作了重大改进的一类方法 我们所介绍的变尺度法是由Davidon于1959年提出又经Fletcher和Powell加以发展和完善的一种变尺度法 故称为DFP变尺度法 一 变尺度法的基本思想 牛顿法的搜索方向为 Hk 1gk 不仅需要计算一阶偏导数 而且要计算二阶偏导数及其逆阵 计算量很大 但牛顿法具有二次收敛性 当迭代点接近最优点时 收敛速度很快 梯度法 牛顿法 梯度法的搜索方向为 gk 只需计算函数的一阶偏导数 计算量小 当迭代点远离最优点时 函数值下降很快 但当迭代点接近最优点时收敛速度极慢 二 变尺度法的迭代公式 2 变尺度法的搜索方向 S k Akgk 称为拟牛顿方向 1 Ak为构造的n n阶对称矩阵 它随迭代点的位置变化而变化 对梯度起到改变尺度的作用 又称为变尺度矩阵 若Ak I 上式为梯度法的迭代公式若Ak Hk 1 上式为阻尼牛顿法的迭代公式 三 DFP法变尺度矩阵的产生 拟牛顿方向S k Akgk必须具有下降性 收敛性和计算的简便性 下降性 要求变尺度矩阵为对阵正定矩阵 收敛性 要求变尺度矩阵逐渐逼近Hk 1 满足拟牛顿条件 简便性 希望变尺度矩阵有如下递推形式 Ak 1 Ak Ak 下降性 下降性 要求S k 与 gk之间的夹角小于90o 即 拟牛顿方向S k Akgk S k Tgk 0 将拟牛顿方向带入上式 得 S k Tgk Akgk Tgk gk TAkgk 0 所以只要Ak为对阵正定矩阵 S k 就是下降方向 简便性 变尺度矩阵是随迭代过程的推进而逐次改变的 因而它是一种矩阵序列 选取初始矩阵A0 并以梯度方向快速收敛 通常取单位矩阵E作为初始矩阵 即A0 E 而后的矩阵均是在前一构造矩阵的基础上校正得到 令 推广到一般的k 1次构造矩阵 Ak k 1 2 A1 A0 A0 Ak 1 Ak Ak 矩阵序列的基本迭代式 Ak称为校正矩阵 拟牛顿条件 构造矩阵Ak 1应该满足一个重要条件 拟牛顿条件 变尺度法采用构造矩阵来代替牛顿法中海赛矩阵的逆阵 主要目的之一就是为了避免计算二阶偏导数和逆矩阵 力图仅用梯度和其他一些易于获得的信息来确定迭代方向 因此 拟牛顿条件是关于海赛矩阵和梯度之间的关系 拟牛顿条件 设F x 为一般形式n阶的目标函数 并具有连续的一 二阶偏导 在点x k 处的二次泰勒近似展开 该近似二次函数的梯度为 式中 若令 则有 上式中 x k 1 x k 称之为位移矢量 并简化书写 而gk 1 gk是前后迭代点的梯度矢量差 简化书写 由以上三式得 海赛矩阵与梯度间的关系式 拟牛顿条件 按照变尺度法产生构造矩阵的递推思想 期望能够借助前一次迭代的某些结果来计算下一个构造矩阵 因此可以根据上式 用第k 1次构造矩阵Ak 1近似代替Hk 1 则 上式即产生构造矩阵Ak 1应满足的一个重要条件 通常称为拟牛顿条件或拟牛顿方程 DFP法变尺度矩阵的递推公式 经过数学推导 可得DFP法变尺度矩阵的递推公式为 DFP公式 由上式可以看出 构造矩阵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 关于算法的稳定性 数值计算稳定性较差 算法的稳定性是指算法的每次迭代都能使目标函数值单调下降 构造矩阵正定性从理论上肯定了DFP法的稳定性 但实际上 由于每次迭代的一维搜索只能具有一定的精确度 且存在机器运算的舍入误差 构造矩阵的正定性仍然有可能遭到破坏 为了提高实际计算中的稳定性 一方面应对一维搜索提出较高的精度要求 另一方面 当发生破坏正定性时 将构造矩阵重置为单位矩阵E重新开始 通常采用的简单办法是在n次迭代后重置单位矩阵 DFP算法的迭代步骤 任取初始点x 0 给出迭代精度 计算初始点精度及其模 若转步骤 否则进行下一步 置k 0 取Ak E 计算迭代方向 沿S k 方向做一维搜索求优化步长a k 使 确定下一个迭代点 计算x k 1 的梯度gk 1及其模 若则转步骤 否则转下一步 计算位移矢量和梯度矢量 按DFP公式计算构造矩阵 置k k 1 若k n n为优化问题的维数 返回步骤 否则返回步骤 输出最优解 x F 终止计算 例题4 6 例题4 6用DFP尺度法求目标函数 的最优解 已知初始点 迭代精度 0 01 解 第一次迭代 式中最优步长应用一维搜索方法在计算机上求解 为了说明问题 又因为此例目标函数简单 所以用解析法来求 为求极小 将上式对 求导 并令f