（运筹学与控制论专业论文）基于新拟牛顿方程的一类强迫正定算法的收敛性分析.pdf

硕士论文基于新拟牛顿方程的一类强迫正定算法的收敛性分析 ab s t r a c t 伽韶 1 n e 八 o n m e 比 o d s are re g a r d e d asth e m o s t e ffi c i ent one s for s o 1 v m g unc o nst r a i n e d 叩u m 面t i onp r o b l e r o sm e a n w hi l e th e m ai n i d e a o f themcan b e us e d toso lve c o 蛇 r a i 二d 叩t 面乙 时 i on p r o bl e 坟 a swe al l b l o w q uas i n e wto ne q u a t l o ns l ay th eb as i so f q uasi n e 节 八 o n m e t h o ds 即 c o rd ingtothe ti m e w ll enthe q u as i 一e v 盆 o n e q 让 at l o n s appear we c 幼d as si fyth e mas the orig in a l and th e newo nesthe orig in a q l la s i n e wto ne q uat l on 川 y e x p l o i t s ti l e gr a d i e n t di ffer e n c e o f th e rece n t t w 0 ite1 a t e s w h 1 1 e i g n o ri l 1 g t h c a v ai l able 血 加t l on v a u e j n fo rma t i on ino r d e r tog a l n幻 n o r e p re ci seq uas i 书e 比 n e q u a t l o ns a g r e at m 助y spe ci allstsli a v e m a d e modi fl c a t i o n o n the o ri g i n a l q u as i n e 比 o n e q u a t i o n orp r o p o se d n e wqua s i 一 n e wto ne q p a t ions w h 1 c h coul de x p 1 o itb o ththe gr adi ent d i 月 七 r e n c e a n d丘 m c t l on v a l u e ai 6 r s t some o b s ervation o f the re cen t n e vq uas i n e wio ne q uat i o ns 认 七 i ch p o ss ess b e tt e r a p p r o x i m a t i on p r o p e rt yi s n 1 a d e in而s p ape r a ll ds omeo f thes eq uas i n e 明 戎 o n e q uat 1 o n s are w ri tt e n ina l l1 l 1 fi e d fonn t b 1 s cl ass o f q uas i 目 n e wton e q ua石 ons inc l l l d e s t h e q uasi 一 比 o n eq uationp ro p o sed b y ji 剐 石 由 o ngz h a n g 3v the o nep r o p os edbyy 山 th a i 兄 ao i39land 也 e origin目 q u as i 书 ewton明 uatio n b as e d o n d on g h u i l i 5 26 l m o d i fi c ati on i d e a we m akes omemo d i fi c atio no f thisc l 韶sto脚 an e vc l as s of q uas i 一e 沈 o n e q uali ons t b e s e c o n d c o n s t ru c t the b f g sq uas i 一e v 比 o n 力 l e l h o d b as e donthis c lass o f mo d i fi ed q uas i n e wto ne q u a t i o ns u n d e rc o n v e xcoll d i t o n p r o o fo fth egi o b al c o n v e r g e n c eo f 而s m e t h o d b as e don th ecl as s o f mo di fi ed q u asi一e v 八 o ne q l lat l ons is g v e n as re g ar d i n g tot b e n ew q uasi n e 节 比 o n e q uat i o ns the gl o b alc onv e r g e n c e p r 0 p e rty i s a l w a y s g l v e 幻 助d e r 小 e u 垃 fo n n c o nvexc o n d i t ion声 b 七 w o r k c o 切 p n s e p aper 5 1 2 5 61 助d s o o n ai l ast this p al r c o m p 1 e t e s the l o c aland s uperlinearc o n v e r g enc e o f b f g s 功 e 出 o d 明d d f p m e t h o d b as edo n t h e c l as s o f m o di fi e d q u as i ne 沈 o n equat i onsw 七 al so m 欧 c ano b s ervati o n o f thesultable choiceo f t rk and thee ffecti vene s s o f numenc ai 己 x p e d m e n t i s gi v e n k e y w o rds qu a s l n e wton e q u a t i o n b f g sme t l l o d d f pm e t h o d glo b al c o n v e 笔e n c e l o c als uperlinearc o n v e rgenc e n 声明 本学位论文是我在导师的指导下取得的研究成果 尽我所知 在本 学位论文中 除了加以 标注和致谢的部分外 不包含其他人已经发表或 公布过的 研究成果 也不包含我为获得任何教育机构的学位或学历而使 用过的 材料 与我一同工作的同事对本学位论文做出的贡献均己 在论文 中作了明确的说明 研 究 生 签 名 移夯 呼 习 年 7 月 乙 日 学位论文使用授权声明 南京理工大学有权保存本学位论文的电 子和纸质文档 可以 借阅或 上网 公布本学位论文的部分或全部内容 可以向 有关部门或机构送交并 授权 其保存 借阅或上网 公布本学位论文的 部分或全部内 容 对于保密 论文 按 保密的有关规定和程序处理 研 究 生 签 名 开未 肾 叮 年7 月 如 硕士论文 荃于新拟牛顿方程的一类强迫正定算法的收敛性分析 第一章绪论 1 拟牛顿法的 起源 拟牛顿法思想是基于 对牛顿法的 讨论而 产生的 我们考虑无约 束最优化问题 二 f x x o r 1 1 其中f r 一r 是二阶连续可微函 数 牛 顿 法的 基 本思 想 是 在目 标函 数f x 的 极小 点x 的 近似 点xk 将f x 二阶 泰勒 展开 即用该二次展开式去逼近f x f x 二 f 十 二 r x 一 告 一 r v zf xk 一 将 该 二次 函 数的 极 小 点xk 十 作 为x 的 一 个 新的 近 似点 对上式两端关于x 求导 且令 v 叽 x vf xx卜v z f x x一 乓 即v z f x 一 乓 一 vf 若v 2 f 乓 正 定 则v 2 f 介 丫 存在 由 此 解 得的 就 是 二 次函 数的 极 小 值点 x 一 一 护 f xk 厂 vf x 给 定x 的 初 始 近 似 点x 后 迭 代点 列卜 由 上 述公 式 产 生 上述 公式 称为 牛 顿迭 代公式 相应的算法称为牛顿法 从以上推导过程可以看出 牛顿法存在以 下严重不 足 若 求 新的 近 似点 l 需要 计 算目 标函 数 的 海 森 阵 及 其 逆 矩阵 计 算 量很 大 在计算机中 实现会耗费大量时间 2 海森阵的 逆矩阵可能不存在 使得牛顿法无法进行 初始点的 选取只能在x 的 适 当 邻 域内 然 而x 是 待求 的 因 而很 难 检验xo 是 否 靠 近x 则 算 产 生的点列可能不收敛 3 只 有当 海 森 阵 正 定 求 得 的 搜 索方向 才 是 下降 方向 序 列 才能 充 分 接 近极小点x 算法才有意义 为了 在保留牛顿法优点的同时 克服其缺点 需要寻求新算法 牛顿法是利用二 次 函 数 逼 近目 标函 数 的 算 法 因 此 人们 设 想能 否以 某 种正 定 矩阵 凡来 代替 海 森阵q 并 使 迭 代 具 有 牛 顿法 的 性 质 为 此目 的 我 们将f x 在 1 处 作 泰 勒 展开 得 二 xk vf 了 x 一 x 1 合 x 一 十 r v z x 一 于是 硕士论文基于新拟牛顿方程的一类强迫正定算法的收敛性分析 vf 小 w v f x x 一 乓 l 令x 则 vf xk 二 vf 乓 l v f x 乓一 1 即 v z f l xk l一 vf 瓜 一 vf 乓 作为 护f 乓 的 近 似 用凡l 替 代铲f t 要 求 满 足 凡 l 几 儿 1 2 其中 个xk 一 乓 儿 一 vf x 小 vf xx 我们称 1 2 式为拟牛顿方程 亦即原始的拟牛顿方程 如 何寻找适 合方 程 l2 的 矩阵凡 十 有许多 方法 我们常 用的是采用修正方 法 即 令凡 1 凡 凡 当凡已 知时 给出 修正矩阵 凡 可得到凡十 1 修正矩阵不同 得到的 凡 不同 由 此形 成的迭 代算法也不同 我们统 称这类算法为拟牛顿算法 1 2基本的拟牛顿迭代公式 无约束最优化问 题 1 1 其海森矩阵是对称的 因 此研究具有对称性的迭代公 式有重要意义 l 2 1 秩一修正公式 凡 风十儿 一 b k 么 凡 一 凡 凡 r 八 一 凡 氏 r 么 1 3 其中 尹一 凡爪 r 爪护 当 将它用于正定 二次函 数求极小点时 至多经过有限 次便可以得到其极小点 且 在此过程中前次的步长 是任意选取的 而且具有二次终 止性 其缺点 是算法不能 保证 正定性 另外 分母 取值会随 着迭代进行而变的很小 导 致计算过程中 数值不稳定 这使得对称秩1 公式的 应用受到限制 l 2 2秩2 修正公式 b r o y d e n 族算法 为克服秩一 对称拟牛顿算法数值计算的困难 p e n 翎 提出一种用秩一方法构造 对称拟牛顿法的 技巧 利用这种技巧可以导出很多 常见的拟牛顿校正公式 硕士论文基于新拟牛顿方程的一类强迫正定算法的收敛性分析 1 p s b 校正 凡 1一 渝 际 一 从 犷 y 一 叭 了 丛 韶丛 叨 1 4 即p 湃ell 导出的对称b roy d en校正公式 2 d 即 公式 一 一 等 箫 二 兴 从 叭 1 5 最早由d a v i d o n 1 9 5 9 冈导出 并由p l e t c h e r 与p 叩e l l 1 9 6 3 所改善 现称 为 d fp 校正 3 b pgs 公式 一 斋 凡 凡 凡 几 r 凡 t 凡久 1 句 此公式由b ro y d e n f l etch e r g of d 五 址 b 一 s h a n n o 提出 4 b r o y d e n 族拟牛顿校正公式 凡 凡 凡 凡 儿 yk r 五 1 凡 1 一 凡 一穿 乖 扮十 舒 言 以 刃 凡 叼 叭 叭 沪 0 l j 乃 当 尹 0 1 时 我 们 称 为 限 制 布 鲁 丹 族 拟 牛 顿 校 正 公 式 可以 看出 在 上 式 中 令护 1 即 得d pp校正公式 令沪 0 即 得b fg s 校正公式 zhuang 族算法 19 70年 hu ang t44 提出了 一 类比broy de n 族更 广的 算法 族 该 算 法 族中 包含三个 自 由 参数 将b roy d en族算法要求的条件放松 他的条件是 l 矩阵风不 要 求 对 称性 仅 要 求从月 hk 从 2 满足广义拟牛顿方程而非拟牛顿方程 风 l 儿 户 么 pc r 3 要求当算法应用于二次凸函数 h x 工 x t 份 b r x 时 产生的方向关于g 互相共扼 从而具有二次有限终止性 根 据 上 述要 求 导出 了 一 类新的 含 三 参数的huan g 算法族 当 算 法中 的凡满足 对 称 性要 求 且 参 数中 的p 1 时 huang 算 法 族就 变 成 含单参数的broyd en族 因 此 bro y den 族是huang 族的 子集 硕士论文基于新拟牛顿方程的一类强迫正定算法的收敛性分析 记 校 正 矩 阵 为 凡 迭 代 方 向 人由 吸 一 从 r gk 得到 关于从的 布鲁丹族拟牛顿 校正公式 1 8 hk十 凡 十 从儿 儿 t 从儿 氏 凡 r 儿 了 凡等 姿 兴 瓶 其中 红 儿 t 凡 以上的huang 族校正公式中包含了dfp公式和b f g s 公式 3线性搜索准则 在用拟牛顿法求解无约束优化问题的迭代过程中 为了保证函数值的 充分 下降 和迭 代序 列的 全局 收 敛性 我 们需 要引 入了 步 长因 子气 其中气由 线 性 搜索 准 则 确定 求气的 方 法 有 直 接搜 索 法 插 值 法 精确 线 性 搜 索 和非 精 确线 性 搜索法等几类 在拟牛顿方法中使用的 最频繁的是精确线性搜索和非精确线性搜 索法 l l l 精确线性搜索 精 确 线性 搜 索 就是 要求 选 择步 长气由 下式 产生 f x 气 司 吵f 乓 引 以 便 获 得 f x 最 大 可 能 的 下 降 但 是 精 确 线 性 搜 索 的 计 算 量 较 大 实 际 上 在 求 目 标函 数最优解时 往往没有必要把线性搜索计算得十分精确 特别在计算的初 始阶段更是如此 过分的追求线性搜索的 精确度会影响整个方法的效率 因 此我们 在求解无约束优化问题时 只要求目 标函数在迭代的每一步都有充分的下降 得 到可接受的步长就可以了 这便是下面要讨论的非精确线性搜索方法 1 3 2 非精确线性搜索主要有以 下三种方法 1 戈德史丹准则 给 定产 口 0 尸 口 0 及常数 c 令k 0 价月曰并 4住临一 2由人 s t 邸 如 果 乱 卜 停 止 否 nij s t e p 3 st 印3解方 程凡 峨十 gk 0 得搜索方向 st印 4采用w o lfe 线性搜索 准则 人 十 人 产 气 及 t 吸 及 十厂 峨之 乳t 峨 来计算步 长 若气二 1 满足 2 4 则取气 1 s t e p s xk x 气人 s t e p 6 氏 气峨 叭二 儿 t 蕊 1 凡 j z 式 儿 ock 几 凡 乓 0 c l 此处 元 凡十 日 q么 st印 7 利 用b 邢 5 迭 代公式 产生凡十 1 即凡 1 二 凡 凡 4 凡 氏 t 凡 从 一 宁 二尸 少 一 八 乓 汽儿 入 其中 式 儿 夕 q十 乓 凡 q 及 十 乱 r 凡 一 2 左 一 人 11爪 112 s t e p s 令k 片k 1 转入s t e p z 为了证明的需要 我们总假设梯度是李氏连续的 即存在一个常数工 9 x 一 9 y 妇 x 一 列 瓶y 尸 2 3 修正的b g s 拟牛顿算法的 全局收敛性 下面进行全局收敛性分析 假 定 水 平 集 xlf x f x0 是 有 界的 则由 2 4 的 第一 个 式子 知 道 非 增 的 从 而 保 证 存 在 厂 忽f 引理2 1算法中 提 到的叭 是有界的 即存在l 使得 爪1 l l 2 f 乓 是 2一 5 硕士论文墓于新拟牛顿方程的一类强迫正定算法的收敛性分析 证 明 由 于 裔 6ck 所 以 卜 需 丛 书 普 黔 q 卜 一鲤喋俨迎一 一 互丛 土里二 更 兴 瓮 鲁 二 置 丝 玉 一 1鱼 1碳 爷 丛 一一 玉丛 示 鬓 黔 镖 刑 十 幂一 2 艺 所以 叭1 厂 俐q 若 2 叮 l 2 必 厂 若取l l 2 的 厂 则 叭阵 l 由 上 面的 分 析知 道仇 十 乓 l c 即 叭 十 乓 上 有 界 笼 叭十 乓 下 有 界 即 存 在 一 个 充 分 小 的 数二 使得叭十 几之 e 关 于 认 的 选 取 后 面 将 单 独 讨 论 引 理2 2若卜 是由 算 法 产 生的 点 列 则 我 们 有 为证明全局收敛性 需要 2 6 艺 一 gk t 凡 0最 后 一 个 不等 式蕴 含 着 2 1 0 引理2 4 对于充分大的k 存在一个常数c 使得 fl马 c 考 2 1 1 证明 同l i 一 d o n g h u i 国 引理33 定 理2 5设仇 由 修 正 的bfgs 方 法 产 生 凡 由 迭 代 公 式 产 生 得 到 那 么 l i minf 9 卜0 2 12 k 证明 假设v k ll gki阵 厂 0 由 于凡氏 ak风 吸 一 气乱 那么 由 2 7 知道 00 艺 一 及 r 几 凡 凡 凡 1 气 同a艺同 一一 一 矛 宣 鱼土 漏 1 风八 凡 t bk 几 一 d引1 气 凡 t 凡 爪 bk 凡 2 尸 艺气么 t 凡 乓 凡 氏 2 从而 对于任意杏 存在一个整数ko 使得对于任意的正整数q 脾次 t 及次 粤 软获 t 及 次 q t l l ak丫 犷 户贪 5乙 a 1志丫 右 k 与 lij刀k 口k k 与 l 刀互 u kl l 其中 左边的不等式由几何不等式得到 所以 盒 戴 俏 硕士论文基于新拟牛顿方程的一类强迫正定算法的收敛性分析 冬 窗 q k 二 牙 1 11 凡 氏平 凡 t 风凡 乓 窗 q诬 面 凡 氏 2 凡 t 凡 几 当q 趋于 时 右边 趋于0 这样 我们得到 2 1 2 以凡 十 q 1 一 犷 一 2 以r q 由引理2 4 得到上面不等式的左面大于一个正数 上面的定理表明基于张建中等新方程的修正的方法在目 标函数是凸函数的情况下 具有全局收敛性 硕士论文基于新拟牛顿方程的一类强迫正定算法的收效性分析 第三章 基于修正的拟牛顿方程的b f g s 算法及d f p 算法的局部超线性 收敛性 3 b f g s算法的 局部超线性收敛性 下面我们来证明算法的超线性收敛性 为此 我们需要以下的假设 假设条件 a 1 f x 于x 处是 二次 连 续 可 微 s 1 2 卜x x 0 g x 正 定 3 2 3 g x 于 犷 逊是ho lde 连 续 也 就 是 存 在 常 数 0 从 0使 得 在 x 的 邻 域 x 内 的 任 意 x 均 有 ii g x 卜 g x 卜 峡 l x 一 x 成 立 3 3 4 r 满 足 艺乓 0 11 x 月 x 一 x 11之 m l x 一 x jl 使得对于任意的x o u x 3 介 j t g x 之 m il j llz j 及 月 特殊的 当k 充 分大时 3 5 3 6 对于x 气成立 3 6 用 益 表示几 凡 么之间 的 角 度 即co s 乱 爪 t 凡 氏 氏 bk几 1 及 t 氏 及 川 凡1 引 理3 1 在 假 设 条 件 a 下 存在常 数马 0 可 几 且k 使 得 7 8 幻 跳 co s 氛到剐 引1 系 co s 矗 flc o s 爵 几 k k 万 3 3 证明 类似yuan y x 国 引理 3 2在假设条件 a 的 1 2 下 对于任意的v 0 有 酬 x l 一 x lr 3一 9 田 乓 艺祠 习 q jll 使得对于所有的充分大的k 均成立 人 l 一 厂 0 一 气 co s 要 x 人一 厂 3 12 事实上 2 4 暗含着 人 i 一 厂 人 一 厂 产 乱 r 凡 为了 证明 3 1 2 因 此 要 证 存在一 个常 数凡 使 得 当k 充 分 大时 有 及 t 凡 一 凡 co s z 盈 认一 厂 口 13 由 于 x 满 足 x 卜 根 据 泰 勒 展 开 式 知 道 存 在 一 个 常 数 城 使 得 对 于 充 分 大 的 k 有 人 一 厂 从 乓 一 x 因 此 由 3 5 和 3 7 我 们 推 出 当 k 充 分 大 时 跳 气 一 乱flll 剐 co s 么 一 气 1 跳1 2 0 5 益 一 可 m 乓 一 x liz co s 2 么 一 呵 岑 co 劲 人 一 厂 八 生 3 令气 可 妈 城 现在 我们证明 3 得到 3 1 3 因此有 3 1 2 9 从引理 3 1 和上面的讨论知道 成立 存在一 个指 标鲜 使得 当k 之 叮 人 1 3 8 和 3 1 2 成立 因此 一 厂 l 一 几 co s z 鑫 认一 厂 f 一 f fl l 一 气 c o s 厅 咦 l k 一 气 1 艺 l 一 内 co 铲 吞 reseses il 产 f 一 友 广口 一 1 告 飞 十 st 大一 j 1 1 一几 一 万一 了夕 c o s 一 蚕 1 ik一 尤 厂二 1 l 分 月 ij 一 f 卜 一 六 l 气 毛 有 1 c o s z 卖 惫 叫 1石 一 1 k 一 匆 1 1 一 气 ijco s 奋 卜 l叮co s 劲 1 0 一呻 t汽 l f 呱 一一 f 一 f 1 一 气 气 峋 其中 最 后 一 个 不 等 式由 引 理3 1 的 3 8 得 到 由 于耳 是 一 个 常 数 最 后 方 括 号内 的 l 7 硕士论文基于新拟牛顿方程的一类强迫正定算法的收效性分析 第二项随着k 趋于co 使得当k 充分大时 有 根据泰勒展开式及 3 而 趋 于 一 个 正 常 数 因 此 我 们 得 到 存 在 一 个 常 数pi 0 1 五 习 一 厂 f 一 厂 pi 以 l 6 那么 对 于 充 分 大 的 有 k 人 一 厂 答 i l xx 一 二 112 名 xk 习 一 x ll 嘴 味 1一 厂 li 祠 一和 冷 一 f ji杯 一 隽 而 因此 对于任意的v 0 有 3 由 于几月 瓜一 x v 1 l 一 x 厂 9 成立 则从 3 9 直接得到 3 10 下面证明 3 1 1 由 于q 乳 及 t 爪 一 2 人 一 人 11凡 jlz 及 乱 了 凡 一 2 鑫 t 凡 一 凡 爪 凡 1 氏 11 及 一 r 么 一 爪 r g 从 爪 jl凡 1 蒸 七 飞 久 一 乓 t g 从 凡 爪 其 中从 二 气 戏 乓 一 叭 十 八 乓 一 孔 月 0 1 几 0 1 则 艺 q l 一 交 业血蜂 军业丛了 全 g x 一 g 十 g x 一 g 漏 州 一石 艺峡 x 一 州if 亿 峡 x 一 引r 从 而 艺 q 11 0 使 得 月 以 iih q 系 1 一 跳 口 q rl 爪 li 刹 q gk l 一 及 卜1 口 q rk 1 i q 氏 之 们 场 一 乓 一 日 q rk llj 旧 剐1 3 21 b 一 11 夕 q rk 1 卜 i q 爪 其中第二个不等式 由于g x 的正定性 以及 瓜峥x 得到 由于 夕 q 动圳 分0 乓斗0 则 存 在 一 个 常 数c 0 使 得竹 甄 1律 自 凡 对 于 充 分 大 的k 均成立 由 3 2 0 知 纵 一 一 凡 卜 c 从 11 暇 1 以 硕士论文基于新拟牛顿方程的一类强迫正定算法的收敛性分析 所 以 当 足 够 大 时 存 在 常 数 0 约 使 得 j j iiqv 一 q 一 刚 列 qv ii 因 此 由 文 献国的 引 理3 1 知 道 存在 一 个常 数a 0 1 呵 八 0使得 一 x 一 厨 黯 裂 一 x 黯剖 3 2 2 由 3 2 0 知道 平 一 x 一 yk 11口 以 一 一 凡 1 llqv if llqll 以 一 q l引 1 以 1 ijqlll以 一 q 一 玩 日 11411 一 回 峡乓 卜 夕 q rk ll 3 2 3 上式联合 3 2 2 3 2 1 3 1 9 式可得 3 1 5 11 一 g x 忆 一 1 一 g x 1匕 二 凡 一 g x 11 1 呱 11 一 x 一 峪 一 卜 一 g x 一 ilrt 入 11 暇十 1 1 1 从 一 g x 1 1 b6 lj 叽 11 因 为 外 使得 从 一 g 一 t 卜 一 x 一 肤 卜 告 2 jj 一 g 一 j少 一 m4 乓 q 2了 s 尹 成立 l 2 反 p 尸 口 左 2 一 二 一 一 1 一 g 一 几 一 城 乓 城 1 q 假设凡是使得 3 1 5 式成立的 充分大的 整数 那么 从气开 始对上面的不等式 两边分 别求和 从而 告 咬 二 卜 一 g x 一 肛 一 所以 忽 二 卜 一 x l七 二 也就是 1 一 一 g x 一 她 丫 一瑞渝 一尸址 一 0 一 勿飞 一 1 1 从 一 g x 一 1 1 写 由 于 111 凡一 9 怀 r 有 界 我 们 可 以 得 到 刀 j f 口 一 从一 x 一 1 忽 监 一面衬一 0 一 一 g 一 一 g x 一 g x 一 1 3 2 5 月声翎川川 g x 一 11 q 一 从 g x 一 汽 卜 g x 一 么 一 g x 一 g x 一 一 g x 一 卜卜 11 二 1 一 二 一 x 因 川 邸国是 有 界 的 卜 一 x 1匕 收 敛 并 且 g x 是 连 续 的 q 一 hk g 一 一 g 一 32 6 那么我们有 硕士论文基于新拟牛顿方程的一类强迫正定算法的收效性分析 凡 g x 一 g x 一 g x 几 一 凡 g x 一 凡 g x 一 g x 一 g 凡 g 凡 一 1 g x 一 g x 一 iig x 一 g xk jlll 11 1 g 凡 一 11 万拭拭 口qq 一一 0 氏 11 且 11 iji 一 g 二 一 g 二 一 1 rk 11 一 g x 一 g 一 1 11 一 1 凡 根 据 3 26 式 可 知 存 在正 常数叭 使 得 一 一 g 一 jl之 11 g 一 爪 11一 1 氏 ij 另 外 由 儿 115 l c 么 k 1 2 知 道 qv 1国qll 万 到l c qll 几 根据 3 2 8 3 2 9 3 2 5 式可知 1 刀 一 g x 次 u mj 二 es 一 一 一 一 二 一 二 卫 0 卜 llsk 下面证明 当k 充分大时 气 1 由 于 dk 川凡及1 峥0 f xk 十 动一 f x 一 扩吸 一 l 一 川 盯峨 执 x 几 岛2 3 2 乃 3 2 8 3 2 9 根据泰勒展开式 我们得到 t 合 tg x 十 一 产 tbk 一 告 r 一 g x 一 川魂 t 凡 d o l dkll 刃咭号 其中可 0 1 最 后 一 个不等式根 据 3 2 4 得 到 因 此对 于 充 分 大 的 k 有 f dk 一 f 乓 一 尸 跳 t 人 0 另一方面 我们有 及 了 峨 一 口 扩dk 乱 l 一 动r dk 0 一 司 扩吸 刃g xk十 可dk d 一 l 一 魂 t 凡 峨 峨 t g 十 可峨 魂一 l 一 dk 了 g xk 魂 o l 魂112 峨 t g 峨 o l 峨112 其中 0 1 所以 我 们 有乱 1 r 么全 乱 r 凡 从 而 对 于 充 分 大的k ak满 足 2 4 的第二个不等式 当k 充分大时 单位步长是可取的 从而算法超线性收敛 23 硕士论文墓于新拟牛顿方程的一类强迫正定算法的收敛性分析 3 2 关 于 序 列 r 的 适 当 的 选 取 方 法 在 前 面 我 们 提 出 了 一 个 修 正 的 拟 牛 顿 方 法 而 且 我 们 证 明 了 若 时的 选 取 能够满足 2 6 算法在凸函数条件下全局收敛 另外 如果再满足 3 4 那么在适 当 的 条 件 下 算 法 满 足 局 部 超 线 性 收 敛 换 句 话 说 方 法 的 收 敛 性 依 赖 于 的 选 取 因此 选取适当的仇圣 使得 2 6 3 4 成立是非常重要的 下面的定理表明 几 o 乳1 肖 其中0 p l 是 一个合适的 取法 定 理3 5假设 水平 集 是 有 界的 乓 是由 修正 的 拟牛 顿 方 法 产 生 的 凡是 由bf gs迭 代 公 式 产 生 的 如 果 参 数几 凡 跳丫 0 p 0 对 于 所 有 的 k 有11 跳 之 r 又 因 为 迎 二儡 彝 丛 氏 雕 久 1二 ilu ec q 所以 可 以 选 取 充 分 大 的 风 使 得 仇 几 气 及 ll ao 尸 从 而 我 们 前 面 的 取 为 产 不 等 式 2 6 成 立 根 据 定 理2 5 得 到 1 乱 1 0 即 得 矛 盾 所 以 全 局 收 敛 性 满 足 另 外 如果 假设 a 中的 1 一 3 成立 我们从 36 得到 对 于充分 大的 k yk t 凡 一 4 r 护 xx十 成 么 m 凡 112 因 二 兰书 瓮 鲁 丛 裔 0cx 动 油 3 11 知 道 籽 针 灿 lq 是 有 上 界 的 且 由 j 2 z h a n g an d c x x u 因 的 引 理 3 3 知 道 ck 卜 0 凡 1 凡 卜 11 一 1 一 x 卜 11 一 x 1 z llx 一 x l 同 一 怀一 丫 m 卜 一 x lln k 而 所以 从而 适 当 地 选 取 风 可 以 使 得 久 耘 r 十 oct 之 0 就 有 叭 十 几 之 m 可以取 m 使得 2 6 成立 p 门 由 于艺 乓 一 艺 久 及 一 扩 n 户 艺 一 x 0 使 口 ij d 1 3一8 rlesesesl 任 一 v f x 卜 6 max llxk 十1一 lj 1 一 x 11 1 11 11 证明 根据范数的性质可知 11 一 v f x 氏 11 一 v f x 凡 1 1 o q 凡 凡 1 3 3 8 3 3 9 其中 q 易 十 易 r 氏 一 2 人 一 人 么 2 根据函数的泰勒展式 我们可以得到 一 十 一 一 t汽 一 告 t 一 一 一 二 it 一 合 一 爪 r g 一 其 中乓 古 xk 十 l 一 约 l 专 乓 十 l 一 的 孔 l 寸 刀 0 1 把上面两等式相加 我们可以得到 一 人 一 人 十 及 十 g l r 凡 根据假设 3 和q的定义 可以 得到 合 科g xj 一 xc 凡 11 11 警 ig 一 g 111 1 号 11 一 1 一 1 max ilxl 一 f 1 xt 一 1 11o 11 3 4 0 根据假设 3 可知 一 v f x 么 1 一 g 一 g x 氏 1 从 inax 11 一 平 11 t 一 lr 11 丁 3 4 1 把 3 4 0 3 4 1 式 代入 3 3 9 式 可 得 3 3 8 式 26 硕士论文墓于新拟牛顿方程的一类强迫正定算法的收敛性分析 弓 理 为 拟 牛 顿 算 法 产 生 的 点 列 那 么 当 凡 yk 时 存 在 仪 粤 1 l j 使得 iimc一 m 一 刚 ll m 一 刚 3 4 2 成立 证明 当 凡时 让m 1 显然 3 4 2 成立 当 j k 让 m 一 g x 万 那 么 根 据 的 定 义 由 假 设 3 和 范 数 的 性 质 可 知 mc一 m 一 城 卜 ilarllll 万一 m 一 几 11 一 llm llll 一 g x 凡 眠 乓 凡 1 11 11 工 g 氏 凡 d 一 g 卜 11二 rk 氏 11 llm lljj 11 工 jjg xk 一 g j 11 11 1 llm 111乓 1 上 1 一 1 川 ljm llf 11阵工 ixx 一 小 一 11 一 lj 11 jj 1 m j 凡 1 峡几 oc 几 1 因 为 一 0 llc 小 0 r 斗 所 以 存 在 常 数 八 卜 赫 无充 分 不等式 fl崛 一 m 一 火 0 八 ilar 1酬 成立 因 为 恤 卜 回卜 一lekll 因 此 存 在 0 川 使 得 11 一 m 一 乓 1 刀 m 一 凡 11 定理3 11 如果 存 在正常数产 之 0 使得 lfw一 m 一刚 iim ilv 到 成 立 其中 mo r 为 非 奇 异 对 称 矩 阵 那 么由 拟 牛 顿 算 法 产 生 的 点 列 凡 超 线 性 收 敛到x 证明 根据文献阅 定理5 3 存在x 的 某邻域n 使得 llm 万 根 据乓的 定 义 显然 ll4llv 二 ilxk 一 11 llxk 一 11 卜 硕士论文墓子新拟牛顿方程的一类强迫正定算法的收敏性分析 定义且 一 bk 习 b 一 凡 a g x 根据引理 3 8 3 9 可以得到 一 x 孤 价 一 昌 2 一 g 二 公 al 一 g 匕 二 a 询 m m 3 4 3 其中儿 i m 一 g x g x 公 1 m 一 凡 一 一 声 2 一 一 2 0 2 而 风 lim ji im 卜 下面对 3 4 3 进行讨论 如 果 凡 有 一 子 列 收 敛 到 g x 根 据 超 线 性 收 敛 条 件 那 么 点 列 超 线 性 收 敛 到 如 到 凡 一 可 x llu 不 收 敛 到 零 那 么 对 于 任 意 的 存 在 正 数 使 得 1凡 一 g x 匕 5 3 4 4 因 为 v 0 扼 万 一 号 44 式 可 写 成 晶 2 11 一 g 肠 ij 一 g x 1公 一 j 1 一 g 公 十 al l bk 一 g x 11 2 1 2 询ii m ll ii m ll二 根 据 引 理3 2 的 3 9 式 以 及 艺rk ll 凡一 g x 场 上 有 界 我 们 能 得 到 熟恤 一 x 七 根据 3 44 式可知 由八的定义可知 k 峥 时 儿呻0 1 凡 一 g x 凡 1 一 凡 一 g x 几 1 2 片 六 一 二一宁 云了尸 份 已二 ii m一 11 入 11么 1 m 一 11 一 im 一 凡 1 从而我们得到 1 凡 一 x 么 11 一气 七一二 一 斗 0 1 入1 所 以 点 列 超 线 性 收 敛 到 x 从上面的叙述可以 看出 基于该族拟牛顿方程的dfp 方法是局部超线性收敛的 硕士论文墓于新拟牛顿方程的一类强迫正定算法的收敛性分析 第四章数值验证 下面数值验证中的修正方程是建立在张建中新方程的基础上的 即我们取夕 3 同 时 我 们 取 一 月 那 么 算 法 要 满 足 一 个 重 要 的 条 件 是 3ck十 引 酬 在 文 中 我 们 仅证 得ok 是存 在的 而 且是 有界的 但是 具体取多少却 没 有给出 文中 称休为 调 整 值 因 此要 在 程 序 中 加 入 一 个 判 断 准 则 当 ack十 引 川 卢 1 00声 了 印 下面首先对于一般性的一致凸函数进行试验 l 函 数 f x 2 x0 2 扩一 4 x0 2 0 初 始点 2 1 初 始值 3 最优点 1 0 最优值 0 新算法下经过9 次迭代 最 优 点 1 0 0 0 0 3 0 1 0 6 5 2 3 o l o 6 s 2 3 o 5 9 5 e 一 0 0 5 最优值 2 7 1 92621 4 8 7 9e一 0 0 9 迭代次数9 计算函 数值次数50 计算梯度次数25 最终调整值0 0 01 李氏 算法在调整值为0 0 01下经过9 次迭代 最优点 0 9 9 9 1 3 2 1 6 7 6 64 0 0 1 948 6 2 1 2 9 5 04 最优值 0 0 0 0 3 8 1 2 1 8 7 6 1 0 7 6 迭代次数9 函数值计算次数35 梯度值计算次数24 相比 之下 同 样迭代次数 新算法的精度在大幅提高 z 函 数 x0 2 2 气 2 硕士论文墓于新拟牛顿方程的一类强迫正定算法的收纹性分析 初始点 最优点 2 1 0 0 函数值 6 最优值 0 新的算法下经过8 次迭代 最优点 0 0 0 0 9 1 4 4 947 4 1 6 5 6 一 0 0 0 0 4 5 7 2 4 7 3 7 0 8 2 7 最优值 1 2 5 4 4 5 0 948 7 7 e 0 0 6 迭代次数8 计算函 数值次数44 计算梯度次数22 最终调整值 刀 李氏 算法在调整值为0 0 01下经过8 次 迭代 最优点 0 0 5 9 1 2 1 5 1 2 0 6 4 4 一 0 0 1 2 2 4 9 3 8 2 7 1 9 8 最优值 0 0 0 3 7 9 5 447 9 4 2 8 1 迭代次数为 8 函数值计算次数30 梯度值计算次数22 相比之下 迭代次数相同 但是新算法的精度在提高 3 函 数xo 十 才一 xo xl 一 l o xo一 4 xl 60 初始点 2 1 初始值 39 最优点 8 6 最优值 8 新算法下经过n次迭代 最优点 7 9 5 7 9 7 0 6 0 印9 5 9 0 1 0 3 9 3 3 227 最优值 8 00740 0 4 2 6 82 迭代次数为 11 函数值计算次数39 梯度值计算次数26 最终调整值欣 0 01 李氏算法在调整值为0 0 01下的效果跟新的方法相同 下面 来看文献 56 中函 数 2 6 2 7 32 2 6 trig o n d m e tri c 丘 盯 c t i o n 函 数 f 3 一 s in xo 一 z co s xo 一 co s 凡 4 一 co s xo 一 3 co s 气 一 如气 z 初始点 最优点 05 住 5 初始值 0 0 最优值 00 1 2 6 8 7 7 7 6 1 6 1 4 o 在新算法下经过n次迭代 最优点 3 3 2 3 6 4 1 6 5 7 5 l e 0 1 2 一9 9 2 0 024 1 1 4 e 一 0 1 3 最优值 1 1 2 9 6 0 1 4 1 8 4 9 e 一 0 2 3 计算函 数值次数59 计算梯度次数28 最终调整值10 李氏 算法在调整值取0 001 进行 11次迭代 最优点 0 3 0 双0 3 0 5 0 9 0 1 0 0 02 8 2 049 1 5 1 0 5 3 最优值 0 0 446 5 0 1 9 9 1 4 7 6 迭代次数为 11 函数值计算次数49 梯度值计算次数18 3 0 硕士论文墓于新拟牛顿方程的一类强迫正定算法的收故性分析 李氏算法在调整值为10时经过n次迭代 最优点 0 1 7 6 1 6 5 5 0 5 2 3 9 一 0 8 9 3 5 2 8 2 6 6 7 3 2 最优值 3 7 2 2 2 9 6 5 3 1 02 迭代次数为 n函 数值计算次数46梯度值计算次数21 相比较而言 新算法高效 但是李氏算法失效 2 7 b rownal m o st l inear九 n c t l 呱 f x 2 x0 气 一 3 2 xo 石 一 1 2 初 始点 0 5 0 5 初 始值 2 8 1 2 5 最优点 1 1 最优值 0 在新算法下经过15次迭代 最优点 1 027 1 1 5 1 0 8 6 3 0 9 5 7 4 9 3 4 6 2 8 5 最优值 0 0 0 041 1 1 4 8 5 4 1 646 迭代次数 巧 计算函数值次数86 计算梯度次数43 最终调整值0 01 李氏 算法在调整值取0 0 01进行巧次迭代 最优点 1 1 0 3 2 4 729 9 9 9 0 8 3 7 8 1 6 6 2 3 3 2 4 最优值 0 0 0 7 6 9 1 1 0 9 2 3 4 8 5 迭代次数为 15 函数值计算次数57 梯度值计算次数42 李氏算法在调整值取0 0 01和0 01时效果相同 相比之下 两者效果差不多 3 2 l i n e ar丘 m c t l on一 丘 n r a nk 函 数 f 皓 xo一 子 气 一 1 2十 卜 子 xo 寺 气 一 1 子 xo 一 子 凡 一 1 2 初始点 1 最优点 一 1 1 初始值 9 一 1 最优值 次迭代 1 1 在新算法下进行1 最优点 最优值是 1 一 1 迭代次数1 计算函数值次数6 计算梯度次数4 最终调整值0 0 01 李氏 算法在调整值取住 0 01时 效果与新算法一样 接下来看 57 文献中的函 数 2 01 2 0 句 2 4 0 3 0 9 2 01 函 数 f 初始点 4 xo一 5 2 气 一 6 2 8 3 初始值 4 5 硕士论文墓于新拟牛顿方程的一类强迫正定算法的收敛性分析 最优点 5 6 最优值 0 在新的 算法下进行了8 次迭代 最优点 是 4 9 9 9 8 1 1 8 1 4 3 2 5 9 9 6 9 8 9 0 2 9 1 2 最优值是 9 2 0 7 6 0 1 021 0 5 e 一 0 0 6 迭代次 数8 计算函 数值次数科计算梯度次 数22最终调整值0 0 01 李氏 算法在调整值取0 0 01时经过8 次迭代 最优点 5 0 1 2 7 9 7 5 6 6 0 7 5 5 0 3 邓4 1 3 9 6 5 最优值 0 0 3 9 1 8 7 2 0 6 2 9 5 迭代次数为 8 函数值计算次数31梯度值计算次数21 很明显 新算法的精度比李氏算法高了很多 2 0 6 函 数 f 二 认一 亏 2 l00 i 一 xo z 初始点 最优点 一 1 2 l 1 初始值 4 84 1 94 1 最优值 0 在新的算法下进行了4 次迭代 最优点 是 1 0 0 0 0 3 6 1 1 似 1 0 0 1 5 7 5 6 0 6 1 5 最优值 3 3 9 3 4 1 9 5 2 2 8 5 e 一 0 0 6 迭代次数4 计算函数值次数20 计算梯度次数10 最终调整值0 1 李氏算法在调整值取0 0 01和0 1 进行了4 次迭代 最终点 1 0 0 0 5 5 5 7 0 4 6 5 1 0 0 3 5 3 1