（应用数学专业论文）求解无约束最优化问题的一类修改broyden非凸族.pdf

求解无约束最优化问题的一类修改b r o y d e n 非凸族 摘要 本文主要研究一类根据新拟牛顿方程得到的修改b r o y d e n 非凸族在无约 束最优化中的应用 本文结构如下 第一章 回顾了b r o y d e n 族算法的基本思想及研究概况 根据韦增欣等 2 0 0 4 年 提出的新的拟牛顿方程b k l s k 珐 y k a k s k 其中 为一矩阵 给出了两种类型的修改b r o y d e n 族 m b c l m b c 2 并分析了相关性质 第二章 将两种修改b r o y d e n 非凸族与a r n l i j o 线搜索相结合 得到了求 解无约束最优化问题两种算法 在适当的条件下 证明了这些算法具有全局 收敛性和超线性收敛性 第三章 给出了用来求解无约束最优化问题两种新的拟牛顿信赖域算法 这些算法将第一章给出的两种修改b r o y d e n 非凸族与信赖域算法有效结合起 来 它们具有全局收敛性和超线性收敛速度 关键词 无约束最优化b r o y d e n 非凸族信赖域算法全局收敛超 线性收敛 苎矍叁兰丝圭兰堡篁兰 曼 皇型 一圭竺墨丝查苎丝丝里矍竺三叁竺竺 型竺 鱼童 n ac l a s so ft h ep r e c o n v e xp a r t0 f m o d i f i e db r o y d e n sf l a m i l yf o rs o l v i n g u n c o n s t r a i n e do p t i m i z a t i o np r o b l e m a b s t r a c t w b m a i n l yr e a r c ht h ea p p l i c a t i o no fac l a 够0 ft h ep r e c o n v e xp a r to fm o d i 乱db r o y d e n 8f 枷l y w h i c h 盯eg e a n e r a t e d 矗o ma 蜊q u a s i w t o ne q 怵i o n s t ou n c o n s t r a i n e d o p t i m i z a t i o n t h et h e s i si 8o r g a n i z e d 勰f b u o w 昌 hc h a p t e r1 w er e v i e wt h eb a 8 i ct h o u g h ta n dr e s e 蛳ho ft h eb r o y d e n sf a n l i l y a 1 学0 r i t h n 蜩 w 苟a t8 1 2 0 0 4 p r o p e dac k 嘲o f t h en e wq u 鹪i n e w t o ne q u a t i o 瑚鼠 1 乳 吮 讥 a 乳 w h e r ea i s m em a t 血 b 蠲e do nt h i 8w eg i v et w o 锣p eo fm o d m e d b r o y d e n 8f 轴1 n y m b c l m b c 2 吼da n 蚯y t h ec 0 盯唧e n d i n gp r o p e r t i e s i nc h a p t e r 2 c o 血b i n i l 培t w oq p 鹤o ft h ep r o n v 坯p a 砒o fm o d i f i e db r o y d e n s y 丽t h 删ol i n e8 e a r c h w eg e tt w o8 l g o r i t h r 啮f b r8 0 l r i 唱1 1 n c 0 璐t r a i n e do p t i m i z a t i o n p r o b l e 瑚 锄dp r o v et h e 8 ea l g o r i t h m 8a g l o b a la n ds u p e r l i n e a r 面n v e r g e n c e1 1 n d 盯8 0 m e 8 u i 乜a b l ec o n d j t i o n s i nc h p t e r3 w ep r o p o 即幻mn e wq u 黯i n e w t o nt p et r l l s tr e 舀o nm e t h o 凼f o rs 0 1 v i n gu n c 鼬r a h e d0 p t i m i z a t i o np r o b l 锄 t h e 阮a l g o r i t h m 8 n l b i n et w ot y p 鹤o ft h e p 砌 c 旺m xp a r to fm o d j 丘e db r o y d e n sf 眦n yp r o p 0 8 e di n 出a p t e r1 丽t ht r l l 吕tr e g i 乩 g o r i t h me 丘e c 咖电l y t h e yh a v e9 1 0 b mc o n v e r g 朗c ep r o p e r t ya n d8 u p e r l i n e a rc o n v e 增e n c e r a 乞e k e y w o r d s u n c o n s t r 8 i n e d 印t i m i z a t i o np r o b l e 衄 p r e c o n v 驭p a r to fb r o y d e n s f 砌1 y t r i l s tr e 西o nm e t h o d 9 1 0 b a lc o n v e r g e n c e 8 u p e r h n e a rc o n v e r g e n c e 呈坠兰塑兰 兰丝圭 耋2 垒堡垂丝查墨丝丝望矍竺三叁竺竺皇丝 皇兰i v 符号说明 除了特别说明外 全文的向量均指列向量 n 维 实 欧氏向量空间 全体实数 兄上的全体n m 矩阵 除了特别说明外 全文指的是e u c l i n d e 缸范数 舻空间上的实值函数 可导函数 0 的梯度向量函数 二次可微函数 的h e 鼹i 雠矩阵 z 在迭代点巩的函数值 可导函数 p 的梯度向量在瓢的函数值 v 2 瓢 或者是它的近似 表示 任意 的意思 单位矩阵 鑫 r一 m嘶啡 苦 鼠玑刀 皇叁兰堡圭兰丝竺圭f 兰2 垒堡墨丝查苎丝丝堡塞竺三耋竺竺呈丝 鱼童1 1 1b r o y d e n 族算法概况 第 章引言 对于求解无约束最优化问题 m i n z i 8 p 1 1 其中厂 z 渺一乳是连续可微函数 拟牛顿是目前应用最广泛 理论上也最为成熟的 方法之一 其一般迭代形式为t b i 霉i d i 也 1 2 其中a 是步长 也是搜索方向 由线性方程组鲰 风以 0 决定 鼠是h e 鹤i a n 阵 g 刃 的近似 满足拟牛顿方程 轧 l 巩 挑 1 3 其中乳 v z k 巩 l 一巩 批 鲰 l 一矶 记点k 为鼠的逆 其中拟牛顿方程 1 3 在拟牛顿算法中扮演着至关重要的角色 不同的风将构成不同的拟牛顿方法 而 b r o y d e n 族是其中最著名的方法 它由以下迭代形式产生 风一鬻 糕地碱 1 a 其中批2 s 看鼠靠 枯一霉 九是常数 鲰t 风 舞一警 吼诚 其中讥2 孵风讥 赣一菇 以为常数 且有关系 以 矗 b 其中m 鲢铲 1 5 1 6 当机 0 1 帆 o 1 时 称其为b r o 刚e n 凸族 特别地机 1 帆 o 和 以 o 帆 1 时 即分别为著名的d f p 公式与b f g s 公式 而当机 懒 蚝兰去 苎皇苎兰堡圭兰竺丝塞 丝 量2圭竺垄竺叁苎垡些堡垒丝三叁丝苎 至里 竺 兰童 2 则所有的目k 都将保持正定 反之亦成立 7 0 年代以来b r o y d e n 族算法的收敛性质一直是无约束最优化算法理论研究的一个 热点 1 9 7 1 年酬 1 和1 9 7 2 年d i x o n f 2 j 首先成功地解决了在精确线搜索条件下的拟 牛顿算法的全局收敛性问题 1 9 7 3 年和1 9 7 4 年 b r o y d e n d e n n i 8 和m o 硝 2 t q 则迸一步 的研究了拟牛顿算法的全局收敛性和超线性收敛的特征 给出了著名的d e n n i 8 一m o 拍条 件 2 3 4 并指出 对于由拟牛顿算法得到的序列巩若收敛于矿 且满足d e n n i s m o 矩条 件 2 3 4 则 超线性收敛于矿的充要条件是步长口 一l 一 o 而对于带非精确线 搜索的拟牛顿算法的研究则是从1 9 7 6 年的p o w e u 的工作开始的 他在文献 3 1 中证明了 带w j e 搜索的b f g s 算法的全局收敛性和超线性收敛性 而后b y r d n o c e d 和y h a n 闭 将结果推广到限制的b r o y d e n 凸族 机 o 1 1 9 8 8 年 y i nz h a n g 和t e 啪勰o n 9 得 到了w d 瞻搜索下b r 呵d 既非凸族具有全局收敛性和超线性收敛速度的结论 并且数值 实验结果表明 在函数值计算的次数和算法迭代的次数的意义上讲 b r o y d e n 非凸族比 b f g s 算法更为有效 1 9 8 9 年n o c e d a l 等恻引入了一种新的分析技巧 在一致凸的 情况下 证明了带回追搜索的b f g s 算法的全局收敛性和超线性速度 利用这一技巧 柯小伍 1 7 j 证明了带回追线搜索的b 研d e n 非凸族的收敛性 对b r o y d e n 族算法收敛性 质的研究 韩继业等做了大量的工作 并取得了不步成果1 1 3 一l 正如我们前面所指出 b m y d 印族算法的收敛性已经取得很多成果 但主要都是针对目标函数为一致凸或者凸 的前提而言的 而当目标函数为非凸的收敛性 直到2 0 0 2 年y d a i 在文献 l l 中给出了 一个反例说明了目标函数为非凸函数的时候b f g s 算法不具有全局收敛性才得以解决 因此当前的 个研究热点问题 是如何构造一个新的算法 使得对于非凸函数亦有好的 收敛性质 对于这方面研究 l i n l c l l 8 h i m 闭一嘲和w e i 一 3 2 取得了一定的成果 而 对于b r r d e n 族算法的另一个研究热点则始于2 0 世纪8 0 年代 l a n 和b y r d 矧的 工作 即构造一个既具有好的收敛性质且在数值表现上优于b f g s 算法的方法 对后两 个研究方向上的一个重要方法就是修改所谓的拟牛顿方程 1 3 因为拟牛顿方程在算法 中处于至关重要的地位 他决定着凤的迭代形式 1 2 修改b r o y d 明族及其性质 遵照上述思路 最近韦增欣等在文献 3 0 中利用目标函数 z 的蛐展式z 回盘 钆 t v o t 缸一巩 一 t t v 2 z k 扣一巩 1 耋皇叁兰丝圭兰竺堕圭鲤 兰2垒丝垄丝查苎丝竺望矍丝三叁丝丝 至望堡竺 量童 3 其中取z z k 即得 8 五v 2 m s k22 矿 z 一 瓢 1 2 v m m t 乳 f 1 7 2 l z i 一 z k 1 l 阢z k 1 9 z 严s 8 蚕弧 从而据此 给出了一类新的拟牛顿方程 其中 b k l 瓤 虻 弧 a t s k 小数出纽糊挚嶝 1 8 1 9 修改拟牛顿方程 1 8 较之拟牛顿方程 1 3 有更高的精确度 这点可以从以下结论中不 难得出 定理1 2 1 着凡满足 1 8 和 1 9 则有 z b 1 v z 1 r z i z k 1 z a 1 t 吼 l 一 1 1 1 0 定理1 2 2 p l l 着函数 p 是光滑的 血满足 1 8 和 1 9 则当l l s 0 充分小的时 候 有 g k t s 一s 皖 s 蚕 死 s 轧 o s t l 4 和 s g 钵 靠一霹玑 c 瓦 s t s t d o s t 其中以 讥 也 1 钆 死 1 是 在 1 点的张量 满足 s 死 t s t s t 吐 j 女 l 1 1 1 1 1 2 下面给出基于新拟牛顿方程 1 8 的修改b r o y d 髓族 m b c l 的迭代形式t m b c l 风一鬻 簇蝴碱 1 1 3 其中t t t s 看风 1 s t a 羲一拣 氓 珊 a s 以上校正公式中若取特例 当机 0 即为修改b f g s m b f g s l 迭代公式 取以 l 则为修改d f p m d f p l 公式 对于修改b r o y d e n 族 类似 4 2 中定理5 矗2 的证明 我们有 皇苎兰塑圭竺竺竺塞 耋2塞丝垄丝查苎丝丝塑竺竺三叁竺兰 型竺 矍兰 4 定理1 2 3 设风正定 对于修改b r o y d e n 族 m b c l 校正公式 11 3 b 保持 正定的充要条件是 s i 靠 o 1 1 4 目 机 织去川 丝铲 1 1 5 如果厂 g n 一驼为二阶连续可微函数 利用以的定义和t a y l o r 展开式 有 8 看靠 s 看讥 2 l 厂 巩 一 1 函 z 1 g 巩 r 乳 三 譬芝嚣 嘉蚤等2 一砒 r 既 埘 2 卜g 巩 1 t 钆 s f g z 口 巩 1 一瓢 s d 幻0 b 1 r 既 s 看g z k 口 z 1 一 s 口 o 1 结合定理1 2 3 我们不难发现若存在m o 使得目标函数 z 满足t g z 弦 m 2 如 d 舻 1 1 7 总有8 看城 o 从而有结论t 定理1 2 4 若目标函数 动满足 1 1 7 初始矩阵风为对称正定矩阵 则对于修 改b r o y d e n 族 m b c l 校正公式 1 1 3 风 1 将保持正定性 而当条件 1 1 7 得不到满足对 其正定的遗传性将可能被破坏 或者说奴将不一定 能保持其下降方向 为此 我们将采用由l i n k 岫h i m a 给出的c a u t i o i l 8u p d a t e 技术 2 8 i 来克服这一缺点 为方便起见我们先定义指标集k 省邛 黼划排 1 1 8 其中n 口均为一正常数 从而得到以下的修改b r 呵d e n 族 m b c 2 的迭代形式 肌 i 风一瓣 瓣 觚嵋 鲋 1 1 9 i 风 i f 詹聋爿 其中叫k s 蚕风 1 s k 惫一撇 畦 批 a 蹰当其中九取 时 为m b f g s 2 校正公式 这样 当后 k 时 总成立s 靠 圳乳 j 鲰驴 o 如此 不难利用数学归 纳法得出m b c 2 校正公式中韵风总具有正定的遗传性 故有 定理1 2 5 若取初始矩阵岛为对称正定矩阵 则对于修改b r o y d 忸族 m b c 2 校 正公式 1 1 9 6 讧1 总保持正定性 皇苎兰堡圭兰竺丝圭 丝 2 童丝垄丝圭苎堡丝堡垒竺三叁竺鳘里 兰塑 垦童 5 本文主要讨论m b c 2 m b c l 校正公式 当机满足 1 一口 妒 o o 1 1 2 0 时的情形 即修改b r o y d e n m b c 2 m b c l 非凸族在无约束最优化中的应用 以下将 分两部分讨论 第一部分我们将m b c 2 m b c l 公式分别与a n n o 线搜索相结合 并 分析其收敛性 第二部分将之与信赖域相结合 得到两个新的拟牛顿信赖域算法 并证 明在适当的条件下它们具有全局收敛性和超线性收敛性 第二章修改b r o y d e n 非凸族在a r m i j o 搜索下的收敛性 2 1 算法 文献1 2 9 3 0 中作者将m b f g s l 公式与w j l f e 线搜索相结合 文献1 3 1 将m b f g s 2 公式与w j 蜘线搜索相结合 在适当的条件 证明了m b f g s l 算法与m b f g s 2 算法均 具有全局收敛性和超线性收敛性 并且数值计算结果显示两种修改b f g s 算法均明显优 于b f g s 算法 文献 3 3 中作者研究了修改b r o y d e n m b c l 非凸族的有关收敛性 其 中采用了广义w j 线搜索即g w 搜索模型 文献 3 4 则结合一类w j f e 类线搜索模 型的l s 搜索模型l 堋 证明了当机 1 一w 1 o 1 时的m b c l 算法具有全 局收敛性 从而进一步推广了有关结论 在本章中我们利用a r m i j o 线搜索h 即 取步长口 矽 其中a 是满足下式的最小非负整数j z 丸 瓢 叮 露如 2 1 其中霸p o 1 将之分别与m b c 2 m b c l 公式相结合 得到以下算法 m b c 2 算法 步1 给出初始点如 9 妒和初始对称正定距阵风 舻 0 e o 使得 j g z 一g i j l i z p 0 d 由于 单调下降 故由算法m b c 2 产生的序列 z 在水平集q 内 而且存在 常数 使得 戳l k 2 l 2 2 同时根据 瓢 有界这一事实 利用假设a 2 可以知道存在常数 o 使得的k 足够大的时候有 i l 鲰0 朋j 2 3 为方便起见 本文引入以下符号 c o s 靠 斋 一斋赫 吼 等m 靠凰 2 a 其中以用以表示乳和风靠之间的夹角 下面我们先给出几个引理 引理2 2 1 设 砜 由m b c 2 算法产生 其中九满足 1 2 0 则 一靠8 k 甑 2 5 0 证明 由 2 2 有 鄞 孤 一m 洲2 舰三 一他 2 舰 一他洲 一 故 矾 一 瓤 1 均满足 鬟 m 糕蛳 2 s 贝4 对于任意的p o 1 存在常数伍 尾 岛 o 使得对任一七 在 捌中至少有 扫叫个i 满足不等式 0 0 8 也 尻 岛慨1 1 2 巧鼠s t 岛 s 忾 岛 o 反8 o 譬慨限 2 9 其中 m i n 似 1 i 女 n 为集合 引 耳 i b 吣中元素的个数 证明 我们先引入妒函数 8 n 妒 a n a 一l d e t a 丸一h 2 1 0 其中入l a 2 k 为a 的特征根 当七 时 对 1 1 9 两边同时求迹 再利用九 o 有 n 风 1 n 风 烂一餐爱芒 奴怕川2 苎皇叁兰丝圭耋竺兰塞 丝兰2圭堡叁竺查苎丝丝塑翼丝 耋丝竺曼 塑 垒童 9 妨c 剐 糕一糕 再根据引理2 2 2 2 8 及妒函数的定义 2 1 0 可知对于惫 k 有 蜗 1 纠剐一彘 糕一 学仙弛仙移 刊 燃一 乩窑 l n 卅 1 s 2 氏 一彘曲彘 妒 鼠 m 一1 岫m 乩 i n c s 2 以 l 一彘仙彘 而当k 芒k 时 因为玩 1 风 故 妒 玩 1 妒 玩 所以对于任意的 有 妒 风 妒 m 一1 砘m 地 扫占 耳 1 n c 2 吼 1 一彘拙彘 2 1 1 定义 眈 乩耐以一f l 一去仙巍 2 1 2 显然有哺 0 由妒 鼠 1 0 可得 捂点 耳讯 掣删一o m 地址 令 为叼1 伽 中切以个最小值对应的下标集 7 m a 厶讯 则 知磊 k 琅 去 一酬 1 一p 因此对于任意的 厶 存在岛使得 哺 协 一1 n c 0 8 2 巩 v 蕾 厶 即c o s 巩 唧 一 三芦l 成立 由 2 1 2 和 2 1 3 易知 1 一磊 1 n 磊 一岛 厶 而函数t z 一1 一z l n z o 在z 1 处达到最大值 且霉 i 时 t l 功 一o 一o o 时 u z 一一 o 因此存在正常数瓦风 使得历 蠢嘧 风 厶 即 岛兰隗2 两 案爷 岛 厶 而且有岛s 唯铲 爱 厶 将 1 k 中使得不等式 2 9 成立的下标自小到大依次记为ti 1 2 缸 并记 氏 1 2 乱 皇叁兰塑圭兰竺丝圭f 兰 耋 圭竺垄塑塞苎丝丝塑望竺三耋竺竺里 兰墅 量童 1 0 和 a u 凰 l 如 k 1 下面我们分两种情况来考虑 1 当k 为有限集时 经过有限步以后 巩将恒相等 故 2 9 对充分大的k 都成 立 因此集合a 中有无数个元素 2 当k 为无限集时 此时当七一o o 时 有n o o 又则在 o 叫中至少有p m l 个i 满足 2 9 因而此种情况下集合a 中亦有无数个元素 因此有 推论2 2 1 设 张 由m b c 2 算法产生 其中机满足 1 2 0 且 2 8 成立 则存在 一无限下标集a i l 如 乱 o 使得成立 口女 证明 由m b f g s 算法的第三步 易知当n 1 时 有 z p 一1 q 知d 詹 一 z c 7 p 一1 口k 9 d k 2 1 4 根据均值公式 存在靠 o 1 使得 知 p 一1 a k d k 一 z 七 p 一1 q g z 靠p 一1 n k d 知 t 以 p 一1 口k g z t d i 1 a k b z 知 靠p 一1 0 七d 一g h 1 t d 七 1 a k 9 钆 r 也 矿1 a k 怕 靠p 一1 a 如 一g k 洲靠 p 一1 0 g k r 蟊 l p 一2 口2 j 如l 2 靠 p 1 g t 以 l p 2 0 以一 将 2 1 4 和 2 9 可以得到 尘铲 紫 譬学 所以 有a m i n l 毕 兰瓦 引理2 2 5 设 由m b c 2 算法产生 其中机满足 1 2 0 如果 1 妊擎 l o 窒圣塞丝圭兰竺丝塞 丝型 圭竺墨丝圭塞丝丝塑矍竺三叁丝苎皇丝 鱼兰1 1 则存在常数 1 1 o a 1 0 使得对于任意的 a 有 糕s 舰 证明 由于h m i i 峨一 i i 乳 0 即存在常数 o 使得 f 鲰0 e o 一1 2 再根据指标集k 的定义 1 1 8 知对于任意的 a 有 等却忙胪 另一方面 根据虻定义 假设a 1 和均值定理 有 剑挑i 幽止如罐护幽 崆也卑静出 l o 乳9 且 趔血蛙七型墼 锰昔牛咀照二虹删 l 0 乳0 l 1 6 i 扣k i i z 也i i s l 2 l i l 瓤n o 1 再结合 2 1 7 即知结论得证 其中m l p h 舴 下面我们给出本节的主要结论 2 1 5 2 1 6 2 1 7 2 1 8 定理2 2 1 若假设a l a 2 成立 巩 由m b c 2 算法产生 其中机满足 1 2 0 则 有 唔擎 o 证明 我们利用反证法来证明定理成立 否则存在常数s o 使得 慨0 g o 七 1 2 2 1 9 则 当k 为有限集时 由以上讨论可知 2 9 对充分大的k 都成立 而当k 为有限集 时 根据引理2 2 5 知此时满足推论2 2 1 的前提 所以无论何种情况 均存在一个无限 下标集a i 1 屯 如 一露s 露s 0 七 a 副川龆器 ir 一 以一乳 堕霹 兰生兰 墼窒塞竺兰丝 童 圭丝垄竺叁苎垡丝塑翼竺三叁竺竺皇丝 垦童1 2 于是 得到矛盾 从而结论成立 如果增加 个假设t a 3 是强凸的 即存在正数c l 使得 尹g z z c 10 z f l 2 白 d z 妒 注意到以下事实 根据 1 1 6 我们有 坑 s 看g 钆 口 z 1 一巩 乳 c l l l 8 k f l 2 o 同时 2 1 8 亦成立 所以有 慨0 2 4 l 2 城1 船一c 1 类似与m b c 2 算法全局收敛性的证明 我们不难得到m b c l 算法爵全局收敛性 定理2 2 2 若假设a 1 a 2 a 3 成立 t 由m b c l 算法产生 其中九满足 1 2 0 则有 唔掣 ji o 2 3 算法的超线性收敛性 接下来我们将讨论m b c 2 算法的超线性收敛性 为此还需要如下假设 a 4 j 矿一r 为二阶连续可微函数 a 5 在 的局部最小点矿满足g 矿 正定 a 6 存在矿的 个领域 矿 j 使得g 在该领域内h d l d e r 连续 即存在常数 口 0 1 和朋i 使得成立t 0 g 0 一g 矿 0 尬i i z 一矿旷 v z 矿 由以上假设 我们可以推得 存在a l 0 使得存在一个正整数后l 使得当七 时成立不等式 1 1 9 z 0 8 9 i 一9 矿 0 a l i l 巩一霉 0 2 2 0 和 矿g d 圳训2 w 铲 2 2 1 以下结论都是在假设a 1 a 2 a 4 a 5 a 6 成立的前提下进行 引理2 3 1 设 茹k 由m b c 2 算法产生 其中机满足 1 2 0 则存在一个正整数 对任意 时 均有 爵划娜 o 2 2 2 证明 由 1 1 6 和 2 2 1 可知当 h 时 有 等 煎号产孙 z s 慨胪慨扩 一 1 7 而这意味着当k 足够大时 2 2 2 将成立 因为 巩 一矿 故有m o z 钏z 十l 一 矿 i l 一矿忖一 和l l 鲰0 一怕 矿 l o 引理2 3 1 说明当k 充分大的时候 恒有七 因此不失一般性 在这节当中 我 们总认为对于所有的k 均有南 k 同时 当 七l 时 由 2 1 8 和 2 2 3 可知成立 器孔 糕曼等恢酽一一 孵 乳 a 1 类似引理2 2 3 的证明 有结论 推论2 3 1 设 瓢 由m b c 2 算法产生 其中机满足 1 2 0 则对于任意的p o 1 使得对任一磨 后l 在吼 明中至少有加叫一七1 个i 满足不等式 2 9 并记其中下标集 为a k 5 l 理2 3 2 设 z 由m b c 2 算法产生 其中机满足 1 2 0 对于u o 1 则存在 r 0 1 卢 o 使得当奄足够大时成立 1 一二 历 一 o 口 0 瓢一霉 旷 七罱l 而且 若记m m z 钏瓢一矿 0 l 一矿扩 则亦有 m 0 0 k l 有 2 2 4 2 2 5 2 2 6 证明 首先 由m b c 2 算法第三步 再根据推论2 2 2 和引理2 2 4 可知对于 a 地 训 一吣以 吲一1 赫 揣 2 西口譬蚓 2 c 1 0 吼0 2 2 2 7 其中c 研玺 再由 2 2 1 容易推出 掣 l a l c l2o 因为a i n 陋l 明至少有囟明一h 个i 故 当k 充分大时 成立 l 一 卢一忻一 其中p r 争 即结论 2 2 4 成立 再由 2 2 8 可得 nn o z t 一霉 o 善 氏一 i 归菩 一 r l 1 因为1 l a 1 c l 0 所以 争磊 川 猫 o o 由次可推知 2 2 5 成立 同时亦有 慨一矿0 o o k 1 2 2 9 再注意到msij z 1 一矿旷 i i 孤一矿n 所以可直接由 2 2 5 得到 2 2 6 成立 引理2 3 3 设 巩 由m b c 2 算法产生 其中机满足 1 2 0 则 垄罂0 a 1 8 o 2 3 0 月 和 胆 0 0 0 2 3 1 和 证明 根据 i a y l o r 展式 有 靠巩 鲰 l 一鲰 t g 饥 靠 孤 一 o 一最 乳 掘g 瓴 轧 其中 k 锄介于孤和z 之间 将以上两式代入a 自的表达式 根据假设a 4 有 jj 幽铲o 0 g 已 一g 6 i l 0 g 2 k 一g 矿 0 i i g 0 一g c 1 0 l 川 2 一z i i 1 1 6 女一z i i 故 2 3 0 成立 同时 有 悄 i i 0 g 婚 一g 锄 0 1 l g e 一g z 6 l i g z 一g 屯e 1 1 工i i f l k z i r l i i 如 一z i r 引理2 3 4 设t 孤 由m b c 2 算法产生 其中九满足 1 2 0 则则存在 使得 监掣鲰 2 3 2 愀0 7 而且 满足 靠 1 w 2 3 7 及存在铂 锯 使得k 足够大时 成寺 不妨假设c b 则 糕外 1 n 1 一岛g 一2 c b 2 3 8 2 3 9 苎皇叁耋垄圭兰竺竺塞 丝丝童 查竺垒竺查墨丝丝堡垒丝三叁竺垒里 丝呈 鱼童1 7 将 23 7 一 2 3 9 及九 1 一仉 西 0 代入 2 3 6 得 邶 鲥鼠 3 岫时卜彘铀磊 妒 百1 3 匈日一l n 饥一风 其中n 磊耋z l l n 磊 一1 一l i l 磊 o 再由条件 e 一杏 故 o o 为步长界 信赖域半径 每次迭代时根据鲰 d z 矾 靠d i 矿鼠d 在矾的领域内关于 的近似程度对 进行调节 由于 圳悯l 所以无论风在迭代过程中是否保持正定性 子问题 3 1 总是有解 但若玩非正 定 从数值计算的角度去看 将很难求解 3 1 而且其收敛速度可能只为线性收敛 若 玩为正定 则 3 1 将有唯一的解 实际上 以上中的鼠可以通过拟牛顿方法迭代产 生 文献 3 7 和 3 8 中分别提出了一类修改b f g s 信赖域方法 并且证明其全局收敛性 和超线性收敛速度 本章主要讨论修改b r o y d e n 非凸族 m b c 2 m b c l 和信赖域方 法相结合的收敛性 定义 z 一 钆 以 n 2 莉矿专獗厂 有算法如下t m b c 2 t r 算法 步1 给出初始点知 咿和初始正定距阵疡 舻 0 岛r o 令 七 o 步2 设 咖 步3 解子问题 3 1 求得搜索方向以 步4 若 p 令 7 转步3 步5 令矾 l z 以 步6 分别利用 1 9 和 1 1 9 计算a 和风 1 其中碱由 1 8 给出 令膏 后 1 转步2 m b c l 一t r 算法 将m b c 2 算法中的步6 替换成 分别利用 1 9 和 1 1 3 计算凡和占饵l 其中城 皇叁兰塑圭兰竺丝圭 型查竺垒丝查塞丝丝塑矍竺三耋竺竺呈 坚丝 量童 2 0 由 1 8 给出 令 1 转步2 3 2 算法的全局收敛性 下面我们将在假设a l a 2 前提下讨论m b c 2 t r 算法的全局收敛性 g i 理3 2 1 设 由m b c 2 t r 算法产生 其中机满足 1 2 0 则 一靠如 o o 耀b 以 o 3 2 00 证明t 由于风为正定 所以解子问题 3 1 有唯 解也 并且存在一个乘数a 满 足下列等式嘲 搿i 篙二 慨s l 毗 i 以0 一 o 由上式可知 a 一訾 3 t 即 9 蚕以 耀鼠如 一a t 0 如n 故有 吼 呶 菇也 耀风也 9 血 一 耀风丸 o 3 5 根据m b c 2 t r 算法的步3 有 瓢 一 鳍以 曰k 毗如 靠也p 一 霹j e k 以p 3 6 再由 2 2 得 耀风丸 一鳍也 巩 一 瓢 1 坦乳 一 r e p r 一 一 1 7 川 毒墨翼 跏 一 口 2 黝 一m 结论得证 引理3 2 2 设 k 由m b c 2 算法产生 其中机满足 12 0 且不等式 29 对无限 多的i 成立 则 u 翌蝉怏0 o 3 7 p 证明 记a 为使得不等式 2 9 成立的下标集 我们首先证明存在常数c l c 2 c 3 c 1 c 2 使得对任意的 a 若i l 比0 m 则有 c 1 1 1 9 z l i i 也 l c 2 0 9 k l i o 七 c 3 3 8 事实上 1 若0 也0 由 3 3 知 a t o 和风如 一9 结合 1 2 0 有 岛0 丸0 2 一d 知 巩 i i 也 g z k 9 和 m 瓢 i l o 风以 主譬慨吡 即有c 1 基 吻 壶 臼 o 使得 3 3 成立 2 若i l 以i i i 设瓦 m i n 椭 r 4 并设瓦为下列的解 竺 掣i r 剐 3 9 s t i 刮 瓦 7 因为 k 显然有吼 巩 弧 也 所以有 如k 蓼b 矗k s 蟊氐 寥b k d k l 结合 2 9 和 3 1 0 有 一靠也 耀风也一卵瓦 岛 宇笔 8 以1 1 2 再利用 2 9 和 3 3 不难证明存在c 3 使得m c 3 成立 而且 我们有 岛i i 也1 1 2 露风如 考一1 9 t 如 耄 1 愀巩 洲以玑 兰皇叁兰丝兰兰竺竺塞 童2垒竺垄丝查塞堡丝塑耋竺三耋丝竺星 兰塑 里竺 2 2 故 有 l d kj lsc 2 j 1 9 z k i i 其中c 2 壶 暑 1 由 2 9 和 3 1 可得 剧 l 风训l 蚓 f 冬 鲁 c l 川吼 综上 有 3 8 成立 由引理3 2 1 有任意的k 均有 舰9 t 也 熙d 著鼠以 o 结合 2 9 有 是罂 慨 j o 3 1 1 3 1 2 再根据 3 8 即可知命题成立 下面给出本节的结论 定理3 2 1 若假设a 1 a 2 成立 茹 由m b c 2 t r 算法产生 其中机满足 1 2 0 则有 3 7 成立 证明 利用反证法 即假设结论不成立 则有 2 1 9 成立 当k 为有限集的时候 由于在有限步以后占k 为常数矩阵 易知引理3 2 2 的前提 成立 而当k 为无限集的时候 根据引理2 2 5 知引理3 2 2 的前提成立 所以无论哪种 情况总有 3 7 成立 从而与 2 1 9 矛盾 故结论成立 即m b c 2 t r 算法具有全局收 敛性 对于m b c l t r 算法 在假设a l a 2 和a 3 下 亦有全局收敛性 即 定理3 2 2 若假设a 1 a 2 a 3 成立 z k 由m b c l t r 算法产生 其中机满足 1 2 0 剐有 3 7 成立 3 3 超线性收敛性 与第二章类似 因为引理2 3 1 我们不妨假设 对于一切的k 均有后 k 引理3 31 设 由m b c 2 一t r 算法产生 其中机满足 12 0 对于任意的 o 1 有 2 2 9 成立 证明 显然推论2 2 1 仍然成立 再根据 3 6 可知对于v 詹 a 有 z k 一 k 1 解玩d 一 p 鳍也 盎 踹怕州2 p 劫9 玉 类似于引理2 3 2 的证明 可得命题成立 据此 与第二章引理2 3 3 引理2 3 5 相仿 有结论 引理3 3 2 设 巩 由m b c 2 t r 算法产生 其中机满足机 1 一 西l c 0 1 其中 仇 e 一古 对于任意的t o 1 有 2 3 4 成立 而且序列钏风i i 和圳嚣 盼均有界 下面我们给出本节的结论t 定理3 3 1 若假设a l a 2 a 4 a 5 a 6 成立伽k 由m b c 2 t r 算法产生 其中机满 足饥 1 一仇 鳍 o 其中巩 e 一由 则瓢超线性收敛于矿 证明 考虑五 一占i 1 鲰 由引理3 3 2 知 2 4 2 成立 即 l l 五0 i l z 石1 鲰0 i i j 石1 洲弧8 一o 首先 利用7 r a y l a o r 展式和 2 3 4 可以得到以下等式 t 也 一 z t 一靠也一 凤以 一 d 最一g 以 o 0 出 其中 介于戤与矾 比之间 再次当l l 五0 时 有也 五 其中矗表示子问题 3 1 的解 所以有 瓠 o 一吼慨 亨靠也一去 风也 b k d k r d 知一 d b 缸d k 去露风血 去h 0 靠忆 其中k 为风的最小特征根 皇叁兰丝圭耋竺竺圭 量竺 兰 圭堡垒丝垒苎丝竺塑塞竺三耋丝竺呈 塑 矍童 2 4 当 f 五1 t 时 由 3 3 和巩的含义 知 似o 咱 畎0 咄 志 一 念五风五 尚 风驴五 赢 风驴五 a 丸 k o 蟊一 因此 有 仉 甜 器乩 由此可知 当k 充分大时有 k l 因此当k 足够大时z 1 z 一日蕾1 鲰在信赖 域吼 伽川g 一 0 k 内为可行的 而且m b c 2 t r 算法实际上变为单位步长的 m b c 2 算法 由第二章可知结论成立 类似的 若满足假设a 1 a 6 则有结论 定理3 3 2 若假设a 1 a 2 a 3 a 4 a 5 a 6 成立 k 由m b c l t r 算法产生 其中九 满足机 1 一 咖 c 0 其中地 e 一古 则瓢超线性收敛于矿 里叁兰 丝圭兰竺丝圭 丝 兰2童竺垒竺查苎丝丝堡垒竺 耋竺竺里 至塑 垦苎 2 5 参考文献 1 m j d p c l w e u o nt h ec o r e r g e n c eo ft h ev a r i a b l em e t r i ca l l 扣r i t h m 8 j i 璐t m a t h a p p l 1 9 7 1 7 2 l 3 6 2 l c w d i x o n v 啦a b l em e t r i ca l g o r i t h r 璐 n e c e 踊a r ya n ds u f l i d e n tc o n d i t i o 册f o r i d e n t i c a ib e h a v i o ro nn o n q u a d r a t i cf u n c t i o 聃 j o p t t h e o r ya p p l 1 9 7 2 1 0 3 4 4 0 3 m j d p a w e u s o m eg l o b a lc o n v e r g e n c ep r o p e r t i 髑o fav a r i a b l em e t r i ca l g o r i t h m s f o rm i n i i z a t i o nw i t h o u t 眈a c tl i n e8 e a r c h i nn o n l i n e a rp r o g r a m m i n 舀s i a m a m s p r o c e 她 a m e r d a nm a t h e m a t i c a ls o c i e t y p 砌d d e n c e 砌 1 9 7 6 9 4 c g b r 刚吼 j e d e 如i s j j m o 吒o nt h el o c a la n ds u p e r l i n e a rc o n v e r g e n c eo f q u 柏 n e w t o nm 或h o d 8 j i n 8 t m a t h a p p l 1 9 7 3 1 2 2 2 3 2 4 6 5 j e d e n n i s j j m o 硝 a c h a r a c t e r i z a t i o no fs u p e r l i n e a rc o n v e r g e n c ea n di t s 印p l i c 舢 t i o nt oq 嘲i n e w t m e t h o 出 m a t h c o m p 1 9 7 4 2 8 5 4 9 5 6 0 6 a g r i e 啪n l p h l t o n i n t l o c a l n v e f g e n 髓a b 两sf o rp a r t i 七i o n e dq u 船i n e w t o u p d 8 t 鸽 n 岫e r m a t h 1 9 8 2 3 9 4 2 9 4 4 8 7 r b y r d j n o c e d a l y m g 1 0 b a lc o n 删g e n c eo fad a 鹤o fq l l a s i n e w t o nn l e t h o d s o nc o n v e xp r o b k m 8 s i a mj o u m a lo nn u i 唧i c 8 王a n a l y 西8 1 9 8 7 2 4 1 1 7 1 1 1 8 9 8 r b d j n o c e d a l at o o lf o rt h e 蝴b 8 i so fq u 捌一n 鲫t o nm e t h o 凼w i t ha p p l i c a t i o n t ou n e 0 璐t r 豳耐m i n i i n i z a t i o n s i a mj o 啪a lo nn 啪e r i c a la n 胡y 凼 1 9 8 9 2 6 7 2 7 7 3 9 9 y z h a n g r p i h m n q u 舾i n e w t o na 1 9 0 r i t h 瑚硒t hu p d a t e s 厅o mt h ep r e c o n v 既 p a r to fb r o y d e n 8f 砌l y i a mj o 啪a lo fn u m e r i c a la i 越y s i s 1 9 8 8 8 4 8 7 5 0 9 1 0 j n o c e d a l t h r yo fa l g o r i t h i n 8f b r 邶 瑚t r a i n e do p t i i n i z a t i o n a c t an 岫e r i c a 1 9 9 1 1 1 9 9 2 4 2 1 l y d a i c 0 n v e r g e 姗p r o p e r t i e 8o ft h eb f g sa i g o r i t h m s i a mj o p t i m 2 0 0 2 1 3 6 9 3 7 0 1 12 y y h 缸 c o n v e r g e n c e0 fd f pa i g o r i t h m s c i e n i nc h i n a s e r i e sa 1 9 9 5 1 1 1 2 8 1 1 2 9 4 13 j h 锄 g l i u g l o b a lc o n v e r g e n c e 她a l y s i so fan e wn 0 衄o n o t o n eb f g s 啦o r i t h m o nc o n v e o b j e c t i v ef i l n c t i o n c o m p u t a t i o n a l0 p t i m i z a t i o n 吼da p p l i c a t i o n 1 9 9 7 7 2 7 7 2 8 9 1 4 g l i u j h a n z x u g l o b 以c o n v e r g e n o eo ft h e 训a b l em e t r i ca l g o r i t h 脚吡ha 矍叁兰塑圭兰竺童圭f 量墼兰 垒丝垄竺查苎丝丝塑篓竺三叁竺竺里 型竺 垒童 2 6 g e n e r a h z 酣w o l f el i n e s e a r c h j o u m a lo fm a t h e m a t i c a l 舶s e a r c ha n de x p o s i t i o n 1 9 9 5 4 4 9 9 5 0 1 5 韩继业 刘光辉 无约柬最优化线搜索一般模型及b f g s 方法的整体收敛性 应用 数学学报 1 9 9 5 1 1 1 2 1 2 2 1 q 刘光辉 韩继业 带一类非精确搜索的b r o y d e n 族的全局收敛性 计算数学 1 9 9 6 3 2 3 譬2 4 0 1 7 1 柯小伍 b r o y d e n 非凸族的收敛性 北京师范大学学报 1 9 9 5 3 l 1 6 9 1 8 柯小伍 带非精确线搜索的