（运筹学与控制论专业论文）带函数值的多步拟牛顿法.pdf

硕士论文 带函数值的多步拟牛顿法 摘要 多步拟牛顿方法是在拟牛顿方法的基础上发展起来的 它剩用插值多项式将前n l 步的迭代信恳值都纳入下一步的迭代 有效提高了收敛速度和迭代效率 在多步拟牛顿 法发展的同时 单步拟牛顿的研究也是如火如荼 例如张建中的带函数值的拟牛顿等有 效算法 本文综合研究7 近年来在拟牛顿方法和多步拟牛顿方法中较好的逼近方程 提出了 两种带函数值的多步拟牛顿算法 通过数值计算比较了这两种算法与前人的算法n 瑚1 数值结果表明本文算法在应用于中高维函数时收敛速度更快 应用于高维函数第二种方 法的优势更骥显 在迭代效率方面相比翦人的研究并无太大优势 但第一种方法的迭代 效率相对第 种更好一些 关键词 秃约束优化 多步法 撅牛顿方法 带蘧数值的多步拟牛顿法 数值计算 a b s t r a c t b a s e do nt h e q u a s i n e w t o na l g o r i t h m m u l t i s t e pq u a s i n e w t o nm e t h o du t i l i z e s i n t e r p o l a t e dp o l y n o m i a l sw h i c hi sd e t e r m i n e db yt h ep r e v i o u smi t e r a t i o n s t oa s s i s ts o l u t i o n u p d a t i n gi nt h en e x ti t e r a t i o ns t e p t h u sr e d u c i n gi t e r a t i o ns t e p sa n di m p r o v i n gc o m p u t a t i o n a l e f f i c i e n c ye f f e c t i v e l y i nt h em e a n w h i l e t h es i n g l e s t e pv e r s i o na l g o r i t h mi sb e i n gr e s e a r c h e d a sw e l l s u c ha sz h a n g sq u a s i n e w t o nm e t h o du s i n gf u n c t i o nv a l u e i nt h i sp a p e r b a s e do n as u r v e yo fp r e v i o u sw o r ki nt h el i t e r a t u r e ip r o p o s e dt w ok i n d s o fm o d i f i e dm u l t i s t e pq u a s i n e w t o nm e t h o du s i n gf u n c t i o nv a l u e a n dc o m p a r et h e i r a d v a n t a g e s a n dd i s a d v a n t a g e sw i t ht h e p r e v i o u sa l g o r i t h m s t h er e s u l t so fn u m e r i c a l e x p e r i m e n t ss h o wt h a tt h en e wm e t h o d sp e r f o r mb e t t e rw h e nu s e di nm i d d l ea n dh i 幽 d i m e n s i o nf u n c t i o n s a n dt h es e c o n do n eh a sq u i c k e rc o n v e r g e n tr a t ea th i g hd i m e n s i o n b u t t h et w on e wm e t h o d sb o t hh a v e n ts om u c ha d v a n t a g ei ni t e r a t i o ne f f i c i e n c yc o m p a r e dw i t h t h ep r e v i o u sm e t h o d s b u tw ea l s ok n o wf r o mt h en u m e r i c a le x p e r i m e n t st h ef i r s to n e p e r f o r m sb e t t e rt h a nt h es e c o n do n ei ni t e r a t i o ne f f i c i e n c y k e y w o r d s u n c o n s t r a i n e do p t i m i z a t i o n m u l t i s t e pm e t h o d s q u a s i n e w t o nm e t h o d s m u l t i s t e pq u a s i n e w t o nm e t h o d s n u m e r i c a le x p e r i m e n t s 声明尸i 刃 本学位论文是我在导师的指导下取得的研究成果 尽我所知 在 本学位论文中 除了加以标注和致谢的部分外 不包含其他人已经发 表或公布过的研究成果 也不包含我为获得任何教育机构的学位或学 历而使用过的材料 与我一同工作的同事对本学位论文做出的贡献均 已在论文中作了明确的说明 研究生签名 萼出 2 吁年莎月严日 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档 可以借阅 或上网公布本学位论文的部分或全部内容 可以向有关部门或机构送 交并授权其保存 借阅或上网公布本学位论文的部分或全部内容 对 于保密论文 按保密的有关规定和程序处理 研究生签名 班 金堑 z 彳年6 月垆日 硕士论文 带函数值的多步拟牛顿法 1 引言 无约束最优化问题的主要求解方法有最速下降法 牛顿法及其改进和拟牛顿法 这 些方法各有特色 适应面也不尽相同 但它们都是求解无约束最优化问题的最基本 最 重要的算法 无约束优化问题的许多其他求解方法乃至一些约束优化问题的求解法都是 以它们为基础发展起来的 最速下降法以负梯度方向作为极小化算法的下降方向 又称 梯度法 是无约束最优化中最简单的方法 具有结构简单 计算量小的优点 但其收敛 速度较慢 牛顿法的基本思想是利用目标函数的二次t a y l o r 展式 并将其极小化 虽然 收敛速度快 但在迭代过程中的每一步构造搜索方向时 首先要计算目标函数的海森矩 阵 然后需要解一个线性方程组 计算工作量很大 拟牛顿法构造搜索方向只需利用目 标函数及其一阶导数的信息 避免了海森阵的计算 减少了计算量 且具有超线性收敛 性 就这些方法本身而言 特别是拟牛顿法 还有许多不完善之处 仍有一些重要的问 题还没解决 有待深一步的研究 拟牛顿法作为求解无约束最优化问题最有效的方法之一 一直以来都是学者的热 点 近年来 又出现了带函数的拟牛顿法 伪拟牛顿法以及多步拟牛顿法 本文将以多 步拟牛顿法为基础 提出两种带函数值的多步拟牛顿法 并与以往的单步拟牛顿法和多 步拟牛顿法进行数值比较 下面先介绍一下多步拟牛顿法 1 1 多步拟牛顿法 无约束最优化问题的一般模型为 m i n f c x x r 1 1 这里目标函数f r 9 r 是二次连续可微的 即在空间r 上寻找使目标函数f x 达到 极小或最小值的点x 宰 认识多步拟牛顿法之前 我们先来介绍一下多步拟牛顿法的 祖先 牛顿法和 拟牛顿法 1 1 1 牛顿法的思想 牛顿法的基本思想是在目标函数f x 的极小点x 幸的近似点x 附近将f x 二阶 t a y l o r 展开 用展开的二次函数去逼近厂 工 将这个二次函数的极小点作为x 的一个 新的近似点吒 用一系列二次函数的极小点 k 去逼近f x 的极小点z 奉 设f x 二阶连续可微 g x 和c x 分别代表f x 的梯度和h e s s i a n 矩阵 屯是x 的一个近似点 由t a y l o r 公式有 1 引言硕士论文 f x q k x f x k g x i 7 x 一以 寺 x 一以 7g t x 一吒 二 令vq x g x 七 g x i x x t 0 即 g x 量 x x i g x i 若g x k 正定 则g 吒 1 存在 由此解出x x k 就是二次函数吼 x 的极小点 即 h l 以一g x 叫g x t x kg x k 1 2 h l2 以一j j 我们将 作为x 的一个新的近似点 给定x 的初始近似点毛后 迭代点列 由公式 1 2 产生 称 1 2 式为牛顿迭代 公式 相应的算法称为牛顿法 对于一般函数厂 x 牛顿法是局部收敛的且具有二阶收 敛速度口1 1 2 1 拟牛顿法的思想 拟牛顿法是目前仅使用目标函数的值及其一切导数的最有效的非线性优化技术 仅 利用目标函数值厂和一阶导数g 的信息 构造出目标函数的曲率近似 而不需要明显形 成h e s s i a n 矩阵 同时具有收敛速度快的优点 拟牛顿法用一个对称矩阵b 逼近h e s s i a n 矩阵 反 需满足一个所谓的拟牛顿条 件 即拟牛顿条件 通常 拟牛顿方程是根据当前步骤和梯度差向量定义的 也可以 由对厂 x 的二次插值或者对g x 的一个线性插值得出 下面给出推导过程 由微分中值定理可得 g x k 1 一g x d g x k o s k x l x k 口 0 1 1 3 令s k x k l x k 儿 g 矗 1 一g x k 因为盈 近似二次曲率 所以由 1 3 式可得拟牛顿方程 反 儿 1 4 在给定初始矩阵8 0 常取为单位矩阵 后 只要构造的反 嘎 蛾满足拟牛 顿方程 1 4 相应的算法称为拟牛顿法 相应的搜索方向d k 一反 1 9 x k 称为拟牛顿 方向 4 有关收敛性与收敛速度等证明详见 6 7 8 1 3 1 多步拟牛顿法的思想 最优化求解过程中 牛顿法的缺陷是显而易见的 其成功关键是利用了h e s s i a n 矩 阵提供的曲率信息 而计算目标函数的h e s s i a n 矩阵工作量大 并且有的目标函数的 h e s s i a n 矩阵很难算 甚至根本无法求出 这就导致仅利用目标函数一阶导数的拟牛顿 方法 然而在通常的拟牛顿方法里只用了前后两步的梯度信息 如果能将前m 步的梯度 值都纳入计算过程 结果是否会更好 基于这样的想法j a f o r d 和l a m o g h r a b i 于 1 9 9 3 1 9 9 4 e 5 年提出了多步拟牛顿方法 下面推导多步拟牛顿方程 记x 为足 中的一条可微路径 t r 直接对向量函数g x f 应用链式法则 可 2 硕士论文带函数值的多步拟牛顿法 得g x t 必须满足 6 x f 乳 瓤 5 再从这个关系式来看单步拟牛顿方程 记 s k x k l x k y k 1 g k 将 x f 视为一条两点插值的直线 即 x t 磁 t s k x o x k x 1 x k l 1 6 显然 兰 黾 v f 并且皇呈i 1 g x 1 一g x o g 黾 1 一g x k y k t l ta t 代入 1 5 式 取t l 可得 g x k 1 y k 1 7 这其实就是单步拟牛顿法的拟牛顿条件 同样地 对于多步拟牛顿法的拟牛顿条件 我们也将x f 视为 中的一条可微路 径 但是由于前m 步产生的迭代点都是可用的 所以x r 不再是一条直线 我们可以将 之定义为一条m 次的插值多项式 比较 1 6 插值点如下 x i 磊一朋 一1 o l m 1 8 而多项式x o 的形式则依赖于 t m 的取值 由 1 5 一 1 7 气 一个显然的取 法是 七一m l k 0 1 m 当然还有很多其他的有效方法 这里暂且不谈 1 5 一 1 7 则是m l 及t o o 1 的情况 我们可以很方便地写出x 的l a g r a n g e 形插值多项式 x o l t x k 1 9 这里厶 f no t j t 一0 j o j 刮 将g o 嘞看成f 的函数 从 1 5 一 1 7 的推导过程及 1 9 式 很自然地写出它 的l a g r a n g e 插值多项式 g x r l t g x k i 1 1 1 0 由于吆 对应于f t m 为了得出一个约束g 吒 的拟牛顿条件 在 1 5 中令f 甚0 因此 现在我们来求鱼掣和叠墅鍪逆 a ta t 对 1 9 求导得 x k 乙 黾一朋 三r k 1 1 1 对 1 1 0 求导得 这里 笺业 姜 舭m 竺 驴纯训一1 r a l 再t t j l 乙 乙一0 一 类似于 1 4 的形式 可得多步拟牛顿方法的拟牛顿方程b r k 根据l a g r a n g e 插值的性质可以导出吃和 更紧凑的形式 如下 肼 由代数学基本原理可知 l k t 1 对 1 1 4 式在 乙点求导可得 t 乙 o 然后我们再来看一下吃的表达式 珞 l c j t x k m i 0 m 2 t f 厶 o 厶一 f 肘 k 乙 坼 乙 l 埘 厶一l 一l 厶 f 册 厶一 乙 l 一 f 卅 k 一 乙 而一删 t o m i研 甄吖 乙 这里 一 乙 m i 同理可得 w t e 儿一 瓯一 j o 4 我们回顾一下 单步拟牛顿方程 多步拟牛顿方程 1 1 2 1 1 3 1 1 4 1 1 5 1 1 6 肿 口 脚 i i 硕士论文 带函数值的多步拟牛顿法 显而易见的 我们可以将拟牛顿方程最 r k w k 作为拟牛顿方程的普遍形式 选择 r k s k w k 以时是单步拟牛顿方程 5 1 1 2 拟牛顿校正公式 上面花那么多篇幅讨论了矩阵取 吼 峨逼近h e s s i a n 矩阵所要满足的拟牛顿条 件 接下来我们就来讨论一下这么多年大家一直用的拟牛顿校正公式 无约束最优化问 题 1 1 其海森矩阵一般是对称的 因此研究具有对称性的校正公式有重要意义 现在 先来介绍具有对称性传递性的拟牛顿校正公式 1 2 1 秩一修正法 因为风 b k a b k 最简单的校正形式是衄的秩为一 此时色 的修正公式可写 成 壤 1 毋 p v r 1 1 7 使最 满足拟牛顿方程 1 1 6 其中 r 通过分析推导 当v r r k 0 时 可以得到 一般的秩一修正矩阵 反 l 反 鲤季监 1 1 8 从 1 1 8 容易看出 当反为对称矩阵 最 也为对称矩阵的充要条件是 w k 一反气 1 1 9 此时 却 掣 n 2 1 2 0 是唯一的秩一对称拟牛顿修正 它首先由d a v i d o n 于1 9 5 9 年得到 b r o y d e n 于1 9 6 7 年又重新导出这一算式 在 1 1 7 q 口 不同的1 得到不同的算法 也可以取为吃或者是 心 然而 秩一修正公式不能保证 最 的正定性 另外 分母可能取零 于是修正公 式不再有意义 因此 需要改进 但是 它有一个突出的优点 就是往往比别的修正公 式逼近g 五 的程度高 利用这个特点 近年来把它用在其他类型的算法框架中 如信 赖域算法 取得了很好的效果叩1 1 2 2b r o y d e n 族算法 为克服秩一对称拟牛顿算法数值计算的困难 p o w c l l 提出一种用秩一方法构造对称 拟牛顿法的技巧 利用这种技巧可以导出很多常见的拟牛顿校正公式 设对称矩阵最 r 开始按照秩一修正的方式构造矩阵q 一般c 1 不对称 根据 c l 构造对称矩阵乞 一般乞不满足拟牛顿方程 再从c 2 出发 按照秩一修正的方式构造 l 引言 硕士论文 矩阵岛 然后将岛对称化 如此继续f 去 得剑一个有极限的矩阵序歹u 把极限记为嘎 l 则 嘶爿 哪咖 心嘞 r 喈 1 2 1 1 2 1 是一类重要的具有对称性传递性的拟牛顿修正 它是秩二修正 若对于 1 2 1 中的1 r k 则得到 钆瑚瓤 机 玎 学群 1 2 2 称为p s b 校正 p o w e l l 导出的对称b m y d e n 校正公式 在 1 2 1 式中 适当选择1 还可以使之具有正定性的传递性 这是重要的一类算 法 使得搜索方向总是下降方向 分析反 正定的条件可知 当v 满足条件 此时 1 2 1 式变成为 唧铧 甓 旭 耐 1 2 3 其中q 2 老一孑惫i 1 2 3 最早由 a v i d o n 1 9 5 9 导出 并由f l e t c h e r 与p w e l l 1 9 6 3 所改善 现称为d f p 校正 当y 再杀 仇取吃 其中仇 舞 j 也满足条件 此时 1 2 1 式变成为 却岳一掣 1 2 4 m 咯吃 4 现称为b f g s 校正 因为q 丁 o 故对 1 2 3 式中含q q r 的项前乘以非负常数 便得到一个依赖于 参数 的一族校正公式反 反 满足拟牛顿条件且保持正定性 n k l 反一样 甓州反 耐加 0 l 1 2 5 1 2 5 式称为布鲁丹族拟牛顿校正公式 当 0 1 时 我们称为限制布鲁丹族拟牛顿 校正公式 可以看出在上式中 令 1 即得d f p 校正公式 令 o 即得b f g s 校正 公式 以上是比较常用的色的校正公式 有时为了减少计算工作量 我们利用巩的校正 公式 其中阢是髓的逆矩阵 此时拟牛顿方程可以写成 6 硕士论文 带函数值的多步拟牛顿法 风 1 w k r k 布鲁丹族拟牛顿校正公式的逆矩阵为 其中 h k 1 0 也 岳一等掣 p 如 m 2 6 p 11二丛兰 丛2 1 一 7 矽 r b 屹r 以 气 而r k 一丽h k w 当 1 时 口 0 从 1 1 3 式得关于珥的d f p 校正公式 峨 岳r k 一掣h k w k嵫 坛 当 0 时 0 1 从 1 1 3 式得关于风的b f g s 校正公式 风 巩 型w k r k 璺监w k 牲h w k 7 风 气 r 通过比较两种形式的d f p 公式和b f g s 公式 可以看出在关于盈的d f p 公式中 将最换为峨 心与气互换 便得关于吼的b f g s 公式 在关于反的b f g s 公式中 作同样的变换 便得关于皿的d f p 公式 这种现象称为对偶现象 即d f p 公式与b f g s 公式互为对偶嘲 1 2 3h u a n g 族算法 1 9 7 0 年n 1 1 h u a n g 提出了一类比b r o y d e n 族更广的算法族 该算法族中包含三个自 由参数 将b r o y d e n 族算法要求的条件放松 他的条件是 1 矩阵风不要求对称性 2 不要求校正矩阵满足拟牛顿方程 而是满足广义拟牛顿方程 风 l y k2c o s c o r 3 要求当算法应用于二次凸函数 1 q t x 二x r g 膏 6 r x c 7 2 时 产生的方向关于g 互相共轭 从而具有二次有限终止性 根据上述要求 他导出了一类新的含三参数的h u a n g 算法族 当算法中的巩满足 对称性要求且参数中的国 1 时 h u a n g 算法族就变成含一个参数的b r o y d e n 族 因此 7 l 引言 硕士论文 b r o y d e n 算法族是h u a n g 算法族的子集 记校正矩阵为耳 迭代方向吭由 吮 一致 g k 1 2 7 给出 按照上述条件 他导出了h u a n g 族校正公式的形式及关系式如下 皿 l h k r k l u l h k w k v r 1 2 8 其中向量 口l l r k q 2 风7 心 1 2 9 v q 2 r k 口2 2 峨1w k 1 3 0 且满足关系式 鬈 1 3 1 y w k2 一l 由于关系式 1 3 1 五个参数口l 0 1 a 2 口2 国中只有三个自由参数 在公式 1 2 s 中 利用条件 1 3 1 便得 吼 l 心 t a r k 1 3 2 当彩 1 时 1 3 2 变成拟牛顿方程 而缈 1 时 h u a n g 族不是拟牛顿算法 通常称 为h u a n g 族变尺度算法 h u a n g 族校正公式依赖于三个参数 选取不同的参数 便得不 同的算法 事实上 当缈 l 若让凰是对称矩阵 只要q a 2 则巩 也对称 这 时h u a n g 族只有一个参数 例如 o l 取为自由参数 若令 儡 w j h k w 8 q l2 而 r 气 2 联合 1 2 9 1 3 0 1 3 1 式可得 q 22 岛l 一一w r r k 2 而 将这些参数代入 1 2 8 式 便得 珥 岳一样 秒 怕 其中 去一硒h k 丽w k 这就是关于风的布鲁丹族拟牛顿校正公式 所以在h u a n g 族校正公式中 令 l 秒 0 得q 2 a 2 l 0 便得d f p 校正公式 硕士论文带函数值的多步拟牛顿法 令国 1 o 1 4 4 a 2 a 2 l 一 a 2 2 0 便得b f g s 校正公式 1 3 迭代步长的选取 在用拟牛顿法求解无约束优化问题的迭代过程中 为了保证函数值的 充分下降 和迭代序列的全局收敛性 我们引入了步长因子 其中 由线性搜索策略确定 求吼 的方法有精确线性搜索法 直接搜索法 插值法和不精确线性搜索法等几类 各类方法 具有各自的特色 在拟牛顿方法中经常使用的是精确线性搜索和不精确线性搜索法 1 精确线性搜索 精确线性搜索就是要求选择步长吼满足 厂 以 m 卸i n 厂 矗 口巩 以便获得厂 x 最大可能的下降 精确线性搜索使得目标函数在迭代过程中下降量最大 但是精确线性搜索的计算量较大 况且在迭代过程中 在求目标函数的最优解的时候 往往没有必要把线性搜索搞得十分精确 特别在计算的初始阶段更是如此 过分的追求 线性搜索的精确度会影响整个方法的效率 因此我们在求解无约束优化问题时 放松对 瓯的要求 只要求目标函数在迭代的每一步都有充分的下降即可 通常采取不精确线 性搜索求解迭代步长吼 然而 精确线性搜索具有理论价值 许多无约束最优化算法 的收敛性和收敛速度都基于精确线性搜索 2 非精确线性搜索主要方法 1 戈德史丹准则 给定 盯 0 仃 0 满足 z f x k 一f x k 瓯 一 v 厂 黾 14 耵 鼍 瓯 7 瓯 a 夥 稚 1 反 一般而言 盯越小 线性搜索越精确 然而 盯越小 工作量越大 通常取 o 1 盯 0 6 0 8 在拟牛顿算法中 用得最多的就是沃尔夫准则 9 1 引言硕士论文 3 试探性的阿弥佳准则 给定 0 1 0 i 1 y 0 令m 0 1 2 检验不等式 上 f x k 一厂 黾 r s k 一 声脚7 v f x k 7 暖 是否成立 记使得上面不等式成立的第一个朋为 则令 a k 帆y 因为盈是下降方向 当m 充分大时 上面不等式总是成立 因此上述的 总是存 在 1 4 本文的工作 1 4 1 本文的思想 本文利用二步拟牛顿法推导出两种修正二步拟牛顿法 第一种利用1 9 9 9 年张建中的 提出对梯度进行多项式插值以引入函数值信息的方法 结合二步拟牛顿法 得出一种带 函数值的二步拟牛顿方程 第二种方法利用1 9 9 6 年j a f o r d 提出的对积分路径x 进行 有理插值的方法 得出一个带函数值的多步拟牛顿方程 本文选取有效的 f 雳 得到另 一种带函数值的二步拟牛顿方法 并对两种方法进行数值验证 1 4 2 本文的结构 第一章 绪论给出拟牛顿法的由来 以及经典拟牛顿算法 第二章 综述了拟牛顿算法的研究现状 第三章 具体介绍多步拟牛顿方程 并推导出两种带函数值的拟牛顿方程 给出相应 b f g s 拟牛顿算法 第四章 进行数值验证 比较单步b f g s 拟牛顿算法 二步b f g s 拟牛顿算法 以及本 文推导的两种二步拟牛顿算法的收敛速度及迭代效率 第五章 结论 1 0 硕士论文 带函数值的多步拟牛顿法 2 多步拟牛顿法的发展历史 2 1 拟牛顿法的发展 1 9 5 9 年 d a v i d o n 提出了第一个拟牛顿法 并于1 9 6 3 年嘲由f l e t c h e r 和p o w e l l 改 进 得到了我们通常称为d f p 方法的拟牛顿法 通常 拟牛顿方程反应了当前迭代的 开始时与结束时的梯度偏差 但是忽略了当前迭代的函数值的可用性 为了能使用更多 有效信息 前人在修改拟牛顿迭代公式 拟牛顿方程和局部逼近模型这些方面做了很多 努力 1 9 7 0 年n h u a n g 在通常的拟牛顿方程中引入一个参数使得相应的更新算法保持 了遗传性 即h u a n g 族拟牛顿算法 1 9 7 1 年n 幻 b i g g s 给出了拟牛顿算法的一种修正形式 修正公式为 钆嘶掣 气糕 其中气为参数 气 了导 矗 一厂 r g k 卜2 o i 七 这个修正公式与b f g s 公式比较只差参数t 当气 1 时 2 1 t i p 为b f g s 公式 1 9 8 0 年n 阳 基于对f x 的一个逼近 d a v i d o n 提出了一个非二次逼近模型 叫做 c o n i c 模型 这个模型不仅使用了梯度值而且使用了当前迭代的函数值 本文只考虑局 部二次逼近 我们把注意力集中在对拟牛顿迭代及拟牛顿方程的改进上 1 9 8 1 年n 钔 s p e d i c a t o 提出了参数的一个特殊选择使得在矩阵迭代中可以使得在矩 阵迭代中可以使用当前迭代的函数值 对h u a n g 族拟牛顿算法中的缈取一特殊值 s y k 面习i 磊习 得到一族正定秩一迭代 1 9 9 1 年n 副 根据 x 的二次近似与某些插值条件 袁亚湘提出了一个改进的b f g s 修正算法 引入了当前迭代的函数值 得到与 2 1 式类 f n j l 拘修正公式 他的公式中气的 取值为气 2 f x k f x k l s k r g k l r y k 1 9 9 3 年 副 a n j o s 将袁亚湘的改进扩展到了整个b r o y d e n 族 1 9 9 9 年 张建中 邓乃扬利用f x f x 川 既 g 川的值对g x 进行二次插值 给出了一新的拟牛顿方程 2 多步拟牛顿法的发展历史 硕士论文 b k l s k 蠢 其中 3 g k l r s k 6 f k 1 一五 2 0 0 1 年n 7 1 张建中 徐成贤利用张量分析得到一类拟牛顿方程 2 2 盈 l s k n 军 2 3 a kp 其中厂 3 g t l r s k 一6 五 一五 r 且 7 l 0 从 2 3 式可以看出 当 时 就是新拟牛顿方程 宅 2 所以新拟牛顿方程是 2 3 式的特例 当 以时 2 3 式可写成毋 i1 牛i n 属于h u a n g 族拟牛顿法 而且这族拟牛顿方程具 有和新拟牛顿方程一样b 摧船 2 2 多步拟牛顿法的发展 1 9 9 4 年嵋1 j f o r d 和i a m o g h r a b i 正式提出了多步拟牛顿方程 多步拟牛顿方程是 用一个多项式逼近g x 导出的 这个逼近是在一个由最后m 次迭代形成的曲线路径上 的 并使用了最后m 次迭代的梯度值 用l a g r a n g e 插值逼近x r 和g r 公式如下 x r 厶 f 砟 2 4 g y 厶 r 其中 这样得出 拟牛顿方程 厶 f 兀 t t y t t 户o 2 5 反 乙 黾一朋m 乙 一删 2 6 t 0i o 经大量数值验证结果可知 因震荡性等原因当m 2 时是最有效的 1 9 9 3 年n 耵 j f o r d 和i a m o 蛳i 已提出了矩阵参数的多步拟牛顿法 主要是对于f 即积分路径参数的度量 引入了椭圆范数 这样能更好的反映迭代步骤 黾 间的距离 以二步拟牛顿法为例 对于 气 i 汉t 2 0 定义如下 乞 t l i i x t 2 一x 0 m u x 一吒0 m i l s ku m 1 2 硕士论文带函数值的多步拟牛顿法 r o r 2 一f 0 0 x 乞 一x r 0 i i m l i s t 一 i i 材 这里m 的取法大致有三种 m i m 盈 m 反 l 大量数值计算表明m 盈最有效 1 9 5 9 年d a v i d o n 也曾有过这样的思想 1 9 1 1 9 7 8 年 s h a n n o 提出这类的方法 2 0 不过并未应用于多步拟牛顿方法 1 9 9 6 年口1 j a f o r da n di a m o g h r a b i x 提出利用对积分路径z 的有理插值 在多 步拟牛顿法中引入函数信息 具体方法如下 g 缸 瓤 2 7 这里 取积分路径x t 0 兰q t 1 o 这里g r 是t 的二次型的向量 经计算可得拟牛 顿方程 最 l 气 w 七 r k 2 万 o s k 0 8 s k l w k 2 8 1 臼 儿 秒一万 儿一l 这里万 是t 的当前步长成 t 2 t i 与前一步长成一l 一f 0 之比 0 呶 1 9 9 7 年乜 j f o r d 和i a m o g h r a b i 提出单步与多步交替的拟牛顿法 具体如下 由于 1 9 9 3 年提出的矩阵参数的多步拟牛顿法计算量很大 于是作者借助于b 一 y k 一 和 破 巧1 9 k 简化了一f 0 和一 的计算 但是在多步拟牛顿方法中反s k 一 y k 一 并不满足 很 有可能直接导致一 变成负数 这就产生了交替的多步拟牛顿法 先使用单步拟牛顿法 满足拟牛顿条件反 一 儿一 再在第二步的时候使用多步拟牛顿法 这样既可简化 一f 0 和一f 1 的计算 又可以保证计算结果的正确性 从计算效率 调用函数值次数 迭代次 数 来讲这个方法很成功 2 0 0 1 年1 2 2 j f o r d 将矩阵参数的多步拟牛顿法中记录代过程中的有效数据 或者利 用忍 一 儿一 等近似条件来降低 0 和 的计算复杂度的方法整理成了文章 并命名为 多步拟牛顿法的隐式 同年乜引 i a m o g h r a b i 对矩阵参数的多步拟牛顿法这个方向进行了更深入的研究 对于椭圆范数中m 的选择提出了如下几种方案 m 色 m b f g s b k s k y k m b f g s b k r k m 并在迭代过程中记录一些有效数据来简化 f 0 和1 的计算 当然文章后的数值验证表明 最有效的当属m b f g s b i y k 2 0 0 3 年又有提出新的m 的选择 2 5 1 关于拟牛顿方 法及多步拟牛顿法更多的性质参见 2 6 2 0 0 7 年幽 怀丽波也用张建中的方法在多步拟牛顿方法中引入了函数值 但本文推 2 多步拟牛顿法的发展历史 硕士论文 导出的拟牛顿方程并不与之相同 原因在于 1 本文对梯度的逼近函数用了四次多项式 五个未知数 而怀丽波用了三次多项 式 四个未知数 但是在解系数的时候都是有五个方程 所以怀丽波的推导结 果有待商榷 2 然而在怀丽波的文章里 用的是等距度量 在这点上跟结果也有所不符 从这几年的研究结果来看 多步拟牛顿方法大体上提出了如下几种改进 一 增加有效信息 l 改进积分路径参数 t m 的度量 引入椭圆范数 更好的反映迭代步骤 故 间的 距离 2 对积分路径x 进行有理插值 引入函数值信息 二 降低计算复杂度 l 利用拟牛顿校正公式 最 一 一 和以 何1 9 k 以及记录迭代过程中的有效数 据以简化积分路径参数 气 慨 一 忆等 的计算 2 单步与多步交替的拟牛顿法 以满足 一 儿 保证简化计算的过程中积分 路径参数瓴 不出现奇异情况 大量的数值验证表明 第一类方法的确在高维函数的迭代过程中提高了迭代效率 调 用函数值次数 迭代次数 以及收敛速度 但是在中低维时效果并不明显 而第二类方 法都只是提高了迭代效率 对收敛速度并无显著改善 1 4 硕士论文 带函数值的多步拟牛顿法 带函数值的二步拟牛顿算法 3 1 多步拟牛顿方程 1 9 9 3 1 9 9 4 年j a f o r da n di a m o g h r a b i 名e 大量的数值结果嘲 中发现 二步拟牛顿 方法是最有效的 这里就从二步拟牛顿方法开始 假设已知前m l 朋 2 个迭代点 1 黾 矗 以及相应的梯度g k l l 所以积分路径x o 的插值基点 x f 0 1 2 3 1 对于变量 的选择方法各异 本文的第一种方法用了等距度量 也就是 r i f m 1 f 0 1 朋 3 2 构造l a g r a n g e 插值函数 2 x f l t x k j l 3 3 2 这里厶 r i i t t j t t j o i 注意 m i 一t 一乙 1 兀孚 i 使用等距度量 我们有 d d t g x t k g x t a x t d t i 爿2 3 7 即 g x f x 吼 f 2 g 协 f i 咆 3 8 变i t 选择等距度量t f 一1 f 0 1 2 设 q t a t 4 b t 3 c t 2 出 口 3 9 这里a b c d e r 根据已知的梯度值 可知函数g 满足下列条件 9 一1 g 黾一1 g 3 1 0 g 0 g 吒 鼠 3 1 1 q 1 g 矗 1 g k l 3 1 2 f f 科x o d r j i g f r d x f x f 吧t t l 3 1 3 五 一以州 扛o 1 3 1 3 是两个方程 f 0 1 时分别一个方程 由 3 8 3 1 2 可以解得 e g k 3 1 4 a b c d e g k l 3 1 5 1 6 a b c d e g k 1 3 1 6 c 一 一 c 詈 亨 三 詈 争 五 一石 3 7 s k l s 6 一詈 三一了d j e 以一石一 硕士论文带函数值的多步拟牛顿法 由 3 1 4 一 3 1 7 司得 口 垒 l 二兰鱼 垒 1 2 一g 三五二五 l 二五 1 2 2 s k t s k 6 星幽二鱼 一 五 二五 1 6 3 s k s k 1 弘丝 趔一g k i2 3 1 8 j 七一1 一j i d 五 二五 一兰 鱼 二鱼 1 2 4 s k s k 1 4 p22 将解得的值代入 3 9 然后求g f 的导数 得 g x lr b g ir吃24 一 一29t 繇 一三三垡羔掣 3 1 9 知训一等等 再将 3 1 9 代入 3 8 注意 3 6 我们可得拟牛顿方程 忍 i 3 一j i 一 4 一 一2 9 t 一 塑三急掣 3 2 b 训一等等 回忆一下 我们构造这个拟牛顿方程的过程 原始拟牛顿方程 反 以 多步拟牛顿方程 最 肘 小 乙 小 t ot o 二步拟牛顿方程 反 一丢 一1 儿一i 1y 改进的二步拟牛顿方程 b 兰 一i 1 一 4 g t i 2 g t 一 至里尘掣 b 训一等等 至此 我们得到改进的二步拟牛顿方程 1 7 3 带函数值的二步拟牛顿法硕士论文 反 l r k 吼 31 r k2 i 一i 一l 吼 4 g k q 2 9 k g k 1 一堡殳掣 o 2 1 s k i 一 g k 1 g k q 一畿岩 3 3 修正拟牛顿法1 的正定遗传性 根据徐成贤 近代优化方法 引理3 3 3 和定理3 3 4 我们知道对b r o y d o n 族拟牛顿校 正公式 当 s k 0 时 只要 0 砭 保持正定 这个结论在2 0 0 0 年的时候 对于任何可以写成嘎 圪 哝的拟牛顿方程 徐成贤又 将其扩展到了当 气 o 1 一肾 b k l 保持正定 对于二步拟牛顿方程 反 l 一j 1 1 儿一 y 我们记 d 1 喜 2 j j 一 r 砭 y 欺一 r 易见 咯 一号 一 q 儿一吾几一1 儿 q2 儿一i 几一 l 儿 s d 如此 吒 o 也就是d r 虼 d o 易见这里只需矩阵k 正定 即 盼s k 袅 i 吐 豇 一 j 根据正定矩阵的性质 我们知道 0 i k k 一1 而这可以在精确线性搜索及 o l f e 搜索准则的过程中满足 见徐成贤 近代优化方法 p 1 3 0 对于改进的二步拟牛顿算法 我们要求 咯 o 为保证搜索方向的下降 必须保 证b k 或h 的正定性 若上式小于零 我们采取降阶计算的方法 1 8 i l川 v 一 硕士论文带函数值的多步拟牛顿法 3 4 修正二步拟牛顿算法1 p t b f g s 下面给出基于改进的二步拟牛顿方程冉勺基本算法 1 给出初始点x o r 和初始正定矩阵岛或凰 j i c 给 丢 仃 1 选择 充分小的f 0 令k 0 2 如果0 忙占 停止 否则 转 3 3 解方程忍反 o 或反 一吼 得搜索方向5 4 求矗 l x k 哝且 0 其中 满足精确线性搜索准则 即 f x k o t k d m 删i n f x k 蒯 或起始用口 l 来试的w o l f e 线性搜索准则 即 五 l a a a f k g k r 吨 g 0d t o g d 5 利用最或也的b r o y d o n 迭代公式产生反 或巩 l 即 或者 其中 最 l 反一 魂矗 面 0 1 聃也 等 t 一型c o k 鲤h k 国k 目 风孟 国i i 0 1 一矽 面卜r t 2 1 一矽 荔r 可 妒 矗7 反矗 七 k2 1 6 t 矗 3 s 1 i 一l p 占 k 1 蔬7 也赢 1 9 釜 赢l i 纨 厂一 堕雨 一九 i n 毋一 3 带函数值的二步拟牛顿法 硕士论文 o k2 4 g k q 2 9 k g k 一型誊k 掣 一l4 七 g k l g k l 一等等p t k l 一了 一 p 2 国i r k 6 令k k l 转入第二步 3 5 修正二步拟牛顿方程2 上节的修正二步拟牛顿法是根据张建中的方法对梯度值进行多项式插值引入函数 值 而1 9 9 6 年j a f o r da n di a m o g h r a b 提出用一个有理式去逼近积分路径x o 引入 函数值信息 具体如下 假设 x f p q t 1 o r 4 1 这里g f 是t 的二次型 并r x t 秽 t l 歹 0 1 2 同样的问题 如何定义步长p 当然我们可以用等距步长 但是我们可以考虑 一下2 0 0 1 年i a m o g h r a b 提出的椭圆范数 这样能更好的反映迭代步骤 h 间的距离 对于 f 茁 取 i 0 定义如下 臻 t o 蚓 t o x t i x t 2 捌x t l l m 锩i x 二尝i s l l 2 如一 f 2 i 一 i l 一黾0 材 lj l f 1 9 9 6 年 j a f o r da n di a m o g h r a b 取m i 这里我们将取更有效的m e 不管怎样我们定义 p k 一 o i i s 一 l l a 2 l l s i l m 4 1 3 同时 为了在拟牛顿方程中引入函数值信息 我们来看下面的分析 首先 我们定义 矽 f 0 f x t 口 然后 e o p 厂 一厂 黾一 营段 f p a i 五一 4 4 又 由积分中值定理我们可知 亡矽v 口 见 成一1 o p 级 级一1 i x o 秒 g 吒 4 5 n l 联合 4 4 和 4 5 式 我们可得 硕士论文 带函数值的多步拟牛顿法 o k 成一1 x o 口 g 故 五 l 一五一l 4 6 对于 4 6 中的x o 0 我们回顾 4 1 式可得 x o 9 g 一觎o 9 1 所 4 7 现在我们再来看一下g f f 的二次型 我们可以像第三节里一样对x 秒 进行多项式插 值 又因为q t 1 o t x t 0 所以我们可以写出q t 的l a g r a n g e 型插值 g f 耥 1 l 号 黾 耥 1 l 4 8 对 4 5 式求导可得 同时将 4 3 式代入 g r j 粤 1 饥 一丝业薯 凳 1 一锻一 砟4 4 9 n n 一广展 o k l 成 o k 1i 依一 o k i j 这样我们可得 g 0 1 万 1 1 6 j 吼 以 l 一 万一一万 t 一8 1 岛吼一1 黾一l 这里艿 级 级一l 成 反一l q o o x o 9 g t 0 一日磁 1 艿 1 万 一l 日嚷一l 一岛 一l 因此我们可知对于 4 6 式中的x t o 0 x o 0 q o o x o 0 l u 1 万 1 万 一l 岛 一l o p k s k 1 所以 4 6 式转化为 万 1 仃k 6 吒一l i 岛嚷一l 仃矗一6 1 吼吼一l j 一五 l 五一l 0 这里 s r g x j 若令0 饥 易见 0 五 l 一五一l 一万 1 一占吒一l 万一1 一吼一l i 对于拟牛顿方程g f x t f k g x 响 易见 x f i 咄 x 反 0 q 展 一o x p k 0 1 p 1 9 1 2 艿 1 o s k 口一万 一l 同样的方法 我们可得 g f l 厶 g 反 0 1 p 1 2 万 1 口 儿 p 万 儿一i 这样我们就得到了一个新的拟牛顿方程 毋 咯 w k 这罩 4 1 0 4 1 1 4 1 2 4 1 3 4 1 4 4 1 5 4 1 6 r k 2 万一1 劢 万一8 s k 1 w k 2 万一1 石 儿 万一万 败一l 最后 鉴于我们对曲线x o 的定义 单调有理式 在积分区间 r 0 t 2 内x f 的符号 应该不变 由于f l 0 我们只需考虑 2 l 3 带函数值的二步拟牛顿法 硕士论文 也就是 由此易得 一1 0 0 1 吼 0 1 一既一l 0 l 0 3 6 修正二步拟牛顿算法2 r t b f g s 为了保证毋的正定性以及x f 的定义的非奇异性 若是在迭代过程中不满足 o 或一1 口 0 令k 0 2 如果8 i l o 其中吼满足精确线性搜索准则 即 x 似 a k d p 嘧厂 x 似 口d p 或起始用口 1 来试的w o l f e 线性搜索准则 即 5 如果k 1 计算 五 l 以 a a k g k7 反 g k o d t b g d k 级一 恢一 忆 既 l l s l m 忍 0 4 武g b 6 k p k p k l k p t p k 仇 以 i 一五一l 一瓯 1 一暖吒一l j 瓯 1 一吼 l i 6 利用最或风的b r o y d o n 迭代公式产生嘎 或4 l 即 或者 2 2 钆训 反一掣掣 攀坼r 酬蔬r 加 o 1 r kb k r k kr k 硕士论文带函数值的多步拟牛顿法 其中 0 巩 风 一 风 圣婺一兰竺m 尘t 垄w 堕 p 赢r 峨孟 气 r 魄r k o kh 1 0 9 k j 1 一矽 面r 五 2 元7 岛元 赢r 峨五 一r k a t a t k u 1 9 t 2 磊一苏而 ks k kn