（应用数学专业论文）非单调数值算法及其应用.pdf

同济大学博士后研究工作报告 中文摘要 本文我们考虑了几类新的非单调数值算法及其在优化与互补问题中的应用 主要内 容包括以下几部分 第一章t 给出了一类新的非单调统一线搜索技术 在一定条件下 可以证明几种常 用的非单调技术都是该技术的特例 将其应用到无约束优化问题可以在较弱条件下获得 算法的强收敛结果 通过n e w t o n 和拟n e w t o n 方法进行了数值检验 第二章 通常的线搜索算法中 关于步长参数的选取是任意给定的而与当前的迭代 点无关 本节我们给出一类可以调节的非单调算法 其中的参数可以根据当前点的信息 进行调节 将该技术应用到记忆梯度法 数值结果表明了算法的有效性 第三章 谱梯度法是求解大规模问题的一类有效算法 但由于谱梯度方向可能不是 下降方向 所以需要借助非单调线搜索来执行 本部分考虑了无约束优化非单调的谱共 轭梯度法 并分析了其收敛性和数值效果 第四章 本章将第一章提出的非单调线搜索技术推广到边界约束优化问题 并将之 与谱投影梯度法进行结合提出了一种边界约束优化问题的新算法 并在不需要算法产生 的点列事先存在一个极限点的条件下获得了算法的全局收敛性 利用数值实例进行了验 证和比较 第五章 本部分考虑扩展线性互补问题的解法 首先 我们利用光滑技术 将扩展 线性互补同题转化为一个光滑方程组 分析了该等价转化的一些性质 透一步的 我们 给出了求解该光滑方程组的非单调n e w t o n 算法并分析了其全局与局部收敛性 第六章 本部分考虑等式约束优化问题的一类非单调信赖域方法 在一定条件下 不仅获得了算法的全局收敛性 而且获得了局部超线性收敛性 关键词 非单谓算法 收敛 无约束优化 约束优化 共轭梯度 谱梯度 扩展互补问 题 价值函数 信赖域 同济大学博士后研究工作报告 a b s t r a c t t h i st h e s i sw ec o n s i d e rs o m ec l a s s e so fn o n m o n o t o n en u m e r i c a lm e t h o d sa n dt h e i r a p p l i c a t i o n si no p t i m i z a t i o na n dc o m p l e m e n t a r i t yp r o b l e m s t h et h e s i si n c l u d e ss i xp a r t s c h a p t e r1 i nt h i sc h a p t e r w eg i v ean e wc a l s so fn o n m o n o t o n el i n es e a r c ht e c h n i q u e u n d e rc e r t a i nc o n d i t i o n s w ep r o v et h a ts o m ew e l lk n o w nn o n m o n o t o n el i n es e a r c hs u n 8a s n o n m o n o t o n ea r i m i j ol i n es e a r c h g o l d s t e i nl i n es e a r c ha n dw o l f el i n es e a r c ha r es p e c i a l c a s eo ft h en e wm e t h o d w ea p p l yt h i sm e t h o dt os o l v i n gt h eu n c o n s t r a i n e do p t i m i z a t i o n a n do b t a i nt h eg l o b a lc o n v e r g n c eu n d e rw e a ka s s u m p t i o n s n u m e r i c a lt e s t sw i t hn e w t o n a n dm e m o r y l e s sq u a s i n e w t o nm e t h o d ss h o wt h ee f f i c i e n c yo ft h ep r o p o s e dm e t h o d c h a p t e r2 i nt h et r a d i t i o n a ll i n es e a r c ha l g o r i t h m t h ep a r a m e t e ra s s o c i a t e dw i t h t h es t e p s i z ei sg i v e nr a n d o m l yw h i l ei n d e p e n d e 1o nt h ec u r r e n ti t e r a t i o np o i n t i nt h i s c h a p e r w ep r o p o s ea na d a p t i v en o n m o n o t o n el i n es e a r c ht e c h n i q u ew h e r et h ep a r a m e t e r c a l lb ea d j u s t e da c c o r d i n gt ot h ea l g o r i t h m f u r t h e r m o r e w ec o m b i n et h em e t h o dw i t h m e m o r yg r a d i e n tm e t h o dt os o l v et h eu n c o n s t r a i n e do p t i m i z a t i o na n dn u m e r i c a lt e s t sa r e g i v e n c h a p t e r3 s p e c t r a lg r a d i e n tm e t h o da n dc o n j u g a t eg r a d i e n tm e t h o da r ev e r ye i f e c t i v em e t h o d sf o rl a r g es c a l ep r o b l e m b u ts i n c et h es p e c t r a lg r a d i e n td i r e c t i o nm a yn o tb e 8d e s c r e a s ed i r e c t i o n o n es h o u l de m p l o yt h eu o n m o n o t o n el i n es e a r c ht oe x e c u t e i nt h i s c h a p t e r w ec o n s i d e rac l a s so fm o d i f i e dn o n m o n o t o n es p e c t r a lc o n j u g a t eg r a d i e n tm e t h o d f o ru n c o n s t r a i n e do p t i m i z a t i o na n da n a l y z ei t sg l o b a lc o n v e r g e n c e c h a p t e r4 b ye x t e n d i n gt h en o n m o n o t o n el i n es e a r c ht e c h n i q u ei nc h a p t e ro n ea n d c o m b i n i n gi tw i t ht h es p e c t r a lp r o j e c t e dg r a d i e n tm e t h o d w ep r o p o s eas o l u t i o nm e t h o d f o rs o l v i n gt h eb o u n dc 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 s u n d e rm i l dc o n d i t i o n s w e o b t a i nt h eg l o b a lc o n v e r g e n c ee v e nw i t h o u tr e q u i r i n gap r i o ro ft h ee x i s t e n c eo fal i m i t p o i n t n u m e r i c a lt e s t sa r ea l s og i v e nt os h o wt h ee f f i c i e n c yo ft h ep r o p o s e dm e t h o d c h a p t e r5 i nt h i sc h a p t e r w ec o n s i d e ras o l u t i o nm e t h o df o rt h ee x t e n d e dl i n e a r c o m p l e m e n t a r i t yp r o b l e m b yu s i n gt h es m o o t h i n gt e c h n i q u e w ef i r s tr e f o r m u l a t et h e p r o b l e ma 8as m o o t he q u a t i o n sa n da n a l y z es o m ep r o p e h i e so ft h eq e q u a l i v e n tr e f o r m u l a t i o n a n dt h e n w ep r o p o s ea nu o n m o n o t o n ei n e x a c tn e w t o nm e t h o dt os o l v et h i s e q u a t i o n u n d e rc e r t a i nc o n d i t i o n s w eo b t a i nt h eg l o b a la n dl o c a lc o n v e r g e n c eo ft h e p r o p o s e da l g o r i t h m c h a p t e r6 t h i sc h a p t e r w ep r o p o s ean e wn o n m o n o t o n et r u s tr e g i o na l g o r i t h m f o rt h ee q u a l i t yc o n s t r a i n e do p t i m i z a t i o n u n d e rc e r t a i nc o n d i t i o n s t h eg l o b a la n dl o c a l 同济大学博士后研究工作报告 s u p e r t i n e a rc o n v e r g n e c ea r ee s t a b l i s h e d n u r m e r i c a lt e s t sa r ea l s og i v e nt os h o wt h e e f f i c i e n c yo ft h en e wa l g o r i t h m k e yw 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 n o n m o n o t o n el i n es e a r c h c o n v e r g e n c e c o n j u g a t eg r a d i e n tm e t h o d s p e c t r a g r a d i e n tm e t h o d e x t e n d e dl i n ec o m p l e m e n t a r i t yp r o b l e m m e r i tf u n c t i o n t r u s tr e g i o n 同济大学博士后研究工作报告 前言 最优化问题是在多种 有限或无限种 决策中挑选最好决策的问题 它广泛应用于农 业 国防 交通 金融 能源 通信等许多领域 如在资源利用 结构优化 调度管理 后勤 供应等许多问题中产生了巨大的经济效益和社会效应 优化在结构力学 生命科学 环 境科学等其他科学研究领域和方向也有广泛应用 如果说 模拟 深刻地改变着人们认识世界的能力 那么 优化 则深刻地改变着 人们改造世界的方法和途径 美国工程科学院院士 哈佛大学何毓琦教授在国际自控联 合会1 9 9 9 年世界大会上以 优化一光彩夺目的领域 为题的报告中提到 优化是人类文 明发展的柱石 许多急需解决的对国民经济有重大影响的大规模复杂科学和工程问题本质上都是优 化问题 它们有的规模十分巨大 维数达上百万 如大气科学中的四维同化问题 有的规 模并不十分巨大但却是非常复杂的优化问题 如化工工业中的多相流计算问题 因此 研究高效的优化计算方法不仅具有重要的科学意义 而且有着很大的应用前景 它对促 进优化方法在国民生产等方面的应用将起到重大作用 考虑如下形式的优化问题 m i n f x s t z q 1 在过去的几十年中 求解问题 1 的主要数值计算方法是线搜索方法和信赖域方法 传 统线搜索方法的基本思想是在当前迭代点z 定义一个搜索方向d k 然后沿此方向寻找 一个合适的步长 下一迭代点取为凯 1 x k 吼d k 获取步长a t 的方法称为线搜索 规则 耳前常见的规则有g o l d s t e i n 规则 w 0 1 f e 规则 a r i m 站 规则 其定义如下 g o l d s t e i n 准则 求讯满足 扛女 n d k x 女 触g d k z k q t d z k 1 一p a g d k 其中0 p 0 是信赖 域半径 当获得信赖域子问题的解靠后 定义一个预测下降量 p r e d k 奴 d 一奴 呔 以及实际下降量 a r e d k 孤 一 扛t 也 再定义预测下降和实际下降的比率为 如2 p r e d k a r e d k 根据这一比率来决定是否接受试验步以及如何调节信赖域半径 可以看出 上述提到的传统线搜索和信赖域方法都属于单调型算法 即在每次迭代 过程中会要求目标函数的值单调下降 但最近的研究表明 单调的算法可能会有一些缺 陷 特别的 强制目标函数单调下降可能会降低收敛的速度 例如当迭代点落入一个很窄 的大峡谷时 因此 允许目标函数偶尔上升可能会克服此缺陷 g r i p p o l a m p a f i e l l o 与 l u c i d i 是首次对非单调算法进行研究的学者 他们针对无约束优化问题引入了a r i m i j o 型 非单调线搜索技术 数值试验表明非单调的技术是非常有效和具有竞争力的 1 9 9 3 年 d e n gn a i y a n g 等人将这一技术推广到信赖域领域 提出了非单调的信赖域算法 尽管此 后该技术得到了广泛的推广和应用 但相对来说 目前该技术还不够成熟 有待于进一 步的研究 为此 本文我们将对非单调的方法作进一步的研究 主要讨论几类非单调线 搜索和信赖域技术在无约束优化 约束优化和互补问题中的应用和其数值表现 2 同济大学博士后研究工作报告 第一章一个新的统一非单调线搜索技术 本章我们给出一类新的非单调统一线搜索技术 在一定条件下 可以证明几种常用 的非单调技术都是该技术的特例 并通过n e w t o n 和拟n e w t o n 方法进行了数值检验 1 1 引言 考虑下面的无约束优化问题 r a i ny x s tz 舻 1 1 其中 z j p r 为连续可微的实值函数 在当前迭代点矾 如果g k v f x k 0 线搜索方法的基本思想是定义一个搜索方 向呶 然后沿此方向寻找一个合适的步长o c k 常用的线搜索规则 3 6 4 5 1 1 2 有 a r i m i j o g o l d s t e i n 准则 求吼满足 0 c t k d i s z t p q k g t d k 1 2 z i a d k 2f x t c 1 一p 口i 螽f 也 1 3 其中0 p 0 条件 1 8 与 1 9 在目前非单调线搜索算法中起着非常重要的作用 但是正如t o i n t 8 所指出的 当梯度很小时 条件 l 9 将会阻止大的步长的产生 例如当迭代点在鞍点附 近或在峡谷的底部时 虽然我们可以选择一个大的c 来克服这一点 但这个策略表明条 件 1 9 是不必要的 最近 d a if 3 0 对非单调的a r i m i j o 线搜索进行了分析 如果v z l i p s c h i t z 连 续 条件 1 9 可被放松为 h 噍i 芦 7 意 k l 2 1 1 0 其中卢 1 为两个正常数 利用条件 1 1 0 及充分下将条件 露d k 一c 2 陬酽 其中c 2 o d a i 获得了如下的收敛结果 一l i m i n f 恢0 0 1 1 2 n r w 在本文中 我们将给出一类新的非单调f 规则 该规则是受m u l b r i c h1 1 0 5 的非单 调信赖域方法的启发两给出的 利用此新规财 我识去捧了限翩条件 1 9 并建立了强的 全局收敛性 1 i m 阢 o 1 1 3 r w 另外 9 9 中对迭代序列紧致性要求以及 3 0 中v z 的l i p s c h i t z 连续性也不再需要 4 同济大学博士后研究工作报告 1 2 新的非单调f 规则 定义水平集c 如 r n t f z z o 本文我们假设下列条件成立 假设hf z 在水平集c 上有下界 v f z 在包含水平集c 的一个开凸集中一致连续 下面我们来回顾以下几种常见的g l l 非单调线搜索规则 非单调a r i m i j o 规则 设q 0 y 0 1 卢 0 1 m 为一非负整数 对每一个 k 定义m k 满足 m o 0 0 s m m i n m k 一1 1 嘲 对于南2 1 1 1 4 令k 伊 口 其中m 是满足下式的最小非负整数 伊口g k 9 m a x f x k 叫 7 矿n 卵以 1 1 5 类似的 非单调g o l d s t e i n 规则定义如下 f x k a k d k 一 g m a x 埘 f x k 一 j 触a 露以 1 1 7 其中0 p t 地 1 最后 我们定义非单调w o l f e 规贝4 如下 f x k k d 七 一 g m s a 列x m i j m 九靠血 1 1 8 g x k a 女呶 也芝他靠血 1 1 9 其中0 饥 他 0 则如下定义的映射 ji n f x y l i l l b x 一g y l i2 z 0 可 l i m 口一j t q 5 同济大学博士后研究工作报告 称为梯度连续的反模 接下来我们给出文 9 9 1 所定义的非单调f 规则 给定正整数m 在每次迭代时 定义m k 满足 m o 0 0 m k s m i n r n k 一1 m 对于k 1 设 0 有上界且满足 巩 m 出 一 j m s a x 耐 f x k j 一盯 1 2 1 其中仃为强迫函数 i d 改 1 1 下一迭代点为 z 15 t k 毗如 s u n 等人证明了前面提到的一些非单调线搜索技术都满足上述非单调f 规则 为了 完整起见 我们引入其证明内容 定理l 1 1 非单调a r i m i j o 规则 1 1 5 满足非单调f 规则 1 2 1 其中o t r f j t 5 1 y t 2 非单调g o l d s t e i n 规则 1 1 6 一 1 1 7 满足非单调f 规则 1 2 1 其中 a t p l t j 1 一脚 t 2 非单调g o l d s t e i n 规则 1 1 8 一 1 1 9 满足非单调f 规则 1 2 1 其中 a t 7 l t 6 1 一他 t 证明 仅证明情况 2 1 3 类似可证 记 l 埘 2 g m a x 埘 f z k l 这里 后一m k t k 七 根据 1 1 7 利用中值定理有 于是有 f z k a k d k z p a a k g r d k2 k 2 a 鳍也 g x o k a d k r d k 舰9 蚕呶 o k 0 1 脚一1 9 t 如d k j 1 一舰 ij g 以暑d i k 1 2 2 因此 根据 1 1 7 和 1 2 2 有 z 女 a k d k 5 l f 女 z l a 女9 手d 女 m 舭 p l a k 一黼 刚姐u 咱 一编以 1 刊需 m 酗 巾薪 其中o t m t 6 1 一r e t t 0 这说明非单调规则 1 1 6 1 1 7 满足非单调f 规则 1 2 1 下面我们给出新的非单调f 规则 取ae 0 1 1 m 1 为一正整数 定义m k m i n k 1 卅 选取 r e k 1 a h a r o 1 2 m 老 一1 a h 1 求o t k 0 有上界且满足 r e k 1 f z k a k d k m a x f x k a h m 卜盯 1 2 3 r o 令 x k l z i q k d k 1 2 4 类似于定理1 1 的证明 我们可以证明我们的非单调f 规则可以包含上述几类经典的非 单调规则 1 墨全局收敛性 在本节 我们讨论在新的非单调f 规则下求解无约束优化问题的全局收敛性 7 同济大学博士后研究工作报告 引理1 1 设 由 1 2 3 1 2 4 产生 则有 一2 k 一1 曼他o 一a o t 一o t k 1 f x o 一a 口 o 1 2 5 r 0r 0 证明 用数学归纳法 若k 1 由 1 2 3 1 2 4 并根据a 墨1 我们有 f x 1 f x o 一口 t o s z o 一a a t o 假设 1 2 5 对1 2 k 成立 考虑两种情况 m 一1 情况1 m a x f z t a h f x k 一 f x k 由 1 2 3 1 2 4 可得 r 0 f x k 1 f x k 毗d k z 一a t k k 1 曼f x o 一a o t r 一叮 t t r 0 i f z o 一a 盯 o r 0 r n k 一1m 忙 一1 情况2 m a x f x k k r f x k 一 l k f x l t 一 设q m i n k m 一1 再次利 r 0r 0 用 1 2 3 1 2 4 可得 口 m 川 他i q 也 a k p f z 呻 一盯 p 0 由 0 1 2 q 0 1 2 k q 一2 c r o p g 0sr k q 一2 8 盯一 一 p k 盯 一 00 盯 十 脚 一霸 如 a 舢 一 同济大学博士后研究工作报告 口 1 a 我们有 f z r k 十 粕 一a a m o t 一 a 却仃o k p 1 一仃 r o p 0 l o 0 k q 2 k 1 跏 一a 盯 o 一a 盯 o 一盯 t t r 0 r k q 1 k 1 f x o 一a 盯 o 一仃 y r o k 知 一a 盯 o 证明完毕 定理1 2 若假设1 成立 血满足条件 1 8 则 且 l i r af i g k l i 0 1 2 5 i c o o 证明 由引理1 1 易知钆 c 对所有的k 由于f x 在c 上有下界 所以由引理 1 1 可 得 a 盯 t r f x o 一 f x k t 设七 4 o o 则有 a o t o o 因此 1 i m 盯 0 有定义1 可知 舰 熙需 o 利用条件 1 8 可知 1 i mo 1 l g k l l 0 即 1 2 5 成立 证明完毕 作为应用 下面我们考虑将新的非单调技术与无记忆拟牛顿方法的结合 z 七 i 卫七 a d k 9 同济大学博士后研究工作报告 其中弧由非单调f r u l e 1 2 1 产生 如 一 1 9 k d o g o 鼠由下面的p e r r y 与s h a n n o 公式进行校正 bk 1辫 磊ykyt一藕ilyk丽1128k w 雏蚝s s 弧 s 酽 s 七 x k l 一瓢 y k 玑 l g k 如果我们利用鼠的逆王k 那么可以得到g k 的公式如下 h k 1 砰y t s k 2 如s k s 蓝一赤 纨s 蚕恤i f 那么下一个迭代点可以表示为 出 1 一日0 l g k 1 一日 l 鲰 1 豁蛐 c y 丽 g k l z 瓮m 咎弧 1 2 6 1 2 7 1 2 8 该方法最初由p e r r y 7 9 和s h a n n o 9 4 9 5 提出 后来许多学者也对其进行过研究 1 6 1 6 j 最近 l i u 与j i n g 6 5 分析了该方法在非单调w j l f e 准则下的全局收敛性 下面 我们分析在新的非单调f 规则下无记忆拟牛顿法的全局收敛性 与f 6 5 j 相比较 我们获 得了强全局收敛结果 为此 我们首先给出如下假设 假设2 z 为二次连续可微函数 存在正常数c a q 使得 这里g z v 2 x c 3 1 2 z t g x z c l l z l l 2 引理1 2 1 s 2 1 设 z i 由算法1 1 产生 如假设2 成立 则存在正常数c 5使得下式成立 辫 忍 定理1 3 设 满足假设1 和2 巩 为无记忆拟牛顿算法在非单调规则 1 2 3 下产 生的无穷点列 则 1 1 3 成立 证明 根据引理1 1 我们有 一1 z o 一a 盯 r o 1 0 同济大学博士后研究工作报告 令k o 根据假设1 我们有 趣i m a t k 0 因此根据定义1 1 我们有 舰哿 舰讧 1 2 9 根据凤和三k 的校正公式 可得 打 风 t n 磊i l y k l l 2 1 3 打 风 t 仃一 y t s k i 21 靠1 8 k 乳1 1 2 1 3 1 根据假设2 有 t 订s s g t s d t 之c 3 t l s e i l 2 j o 因此根据c a u c h y s c h w a r t z 不等式 我们得 而y t s k 掣 三 i l 姚1 1 22 谨钆3 c 3 再根据引理1 2 1 3 0 1 3 1 得到 打 晚 1 0 c 6 0 饥 0 1 仃 0 1 m o l k 0 s t e p1 计算肌 如果f i g k l i s 停 否则计算 的h e s s i a n 矩阵王k 如果风奇异 令d o g k m k 1 转s t e p4 s t e p2 计算如 一日f 1 鲰 如果j 靠d k i 0 令d k 一d o s t e p4 令n 1 s t e p5 计算厶 z 女 a d k 取a 0 1 选取 r e k 1 k a r 1 2 r e k 一1 且 a k 1 r 0 i f m k 一1 o m a x f x k a h m h 饥碗d 膏 r 0 8 e t 1 厂口 x k l z k a d 七 k 1 m k m i n k 1 卅 转s t e p l s t e p6 令口 o o t 转s t e p 5 接下来我们给出在新的非单调线搜索下的p e r r y 与s h a n n o 算法模型 见 6 5 算法模型2 s t e p1 给定跏 形 正整数m 常数 0 岛 0 y 1 0 1 仃 0 1 d o g o m 0 1 七 0 s t e p2 令a 0 1 选取 m 一1 k a r l 2 r e k 一1 且 a t 1 r 0 令口 1 m k m m k 1 m 如果 m k i a d o m a x y z k a h 址 7 c r g t d k r o 不成立 令n 仃a 同济大学博士后研究工作报告 s t e p3 令2 7 k 1 孤 吼出 计算乳 2 7 k l z 鲰 鲰 l g k s t e p4 如果i 鲰0 s 停 s t e p5 利用p e r r y 与s h a n n o 公式修正王k k 1 砑y s k 2 型y s k 一赤 乳西 弧s 令七 愚 1 计算比 h k g k 如果f 卵以i 0 为步长 对于搜索方向出 共轭梯度法 c g 是其中著名方法之一 d k 一 8 k d k 一1 反 r 以的选择不同可得到不同的共轭梯度法 比较著名的公式是f l e t c h e r r e e v e s f r 公式 p o l a k r i b i e r e p o l y a k p r p 公式 h e s t e n e s s t i e f e l 公式 关于这些方法的全局 收敛性已经有许多学者进行了研究 其中包括a l b a a l i 1 d a i v u a n 2 9 g r i p p oa n d l u c i d if 4 9 g i l b e r ta n dn o c e d a l 5 1 a n dz o u t e n d i j k 1 1 9 共轭梯度法的优势之一在于它 可以避免和储存矩阵 因此可以用来求解大规模的问题 记忆梯度法具有与共轭梯度法一样的性质 但与共轭梯度法相比较 记忆剃度法的主 要不同在于它可以更充分地利用以前迭代点的信息 因此有助于设计快速有效的算法 最初的记忆梯度法是由g r a g ga n dl e r y 2 7 以及m i e l ea n dc a n t r e l l 7 3 提出的 但 他们没有证明其全局收敛性 最近 关于记忆梯度法的全局收敛性已经由许多学者进行 了研究 7 6 9 6 9 7 文 7 6 9 6 9 7 1 主要讨论了在单调线搜索下记忆梯度法的全局收敛性 正如在上一章 提到的 单调线搜索方法有可能大大降低收敛的速率 特别是当迭代陷入一个 很狭窄 的峡谷时 可能会导致很短的步长或出现之子型现象 而非单调的线搜索技术有可能克 服此缺陷 在上一章中 我们提出了一类新的非单调线搜索技术 从数值测试看 具有 良好的效果 但一般的线搜索中 初始的步长都是任意给定的 而没有充分利用当前点的信息 我们认为这在一定程度上有可能影响算法的效果 为此 在本章我们给出一类调节非单 1 7 l 2 3 但 q 同济大学博士后研究工作报告 调线搜索技术 在这里 我们的初始步长可以根据算法本身进行调节 通过将此步长选 取的技术与上一章的非单调技术相结合 我们给出了一类调节非单调线搜索技术 进一 步的 我们利用此技术与记忆梯度法对无约束优化问题进行了求解 在适当条件下获得 了算法的全局收敛性 最后利用数值例子进行了验证 2 2 算法模型与全局收敛性 首先我们定义搜索方向如下 7 6 d t 2 一g t 去e 銎1 风d t 晶 这里m 表示以前要记忆的迭代数目 风 r 1 2 m 的计算公式为 风 i i g t 1 2 怯 其中 口 一谴翁 0 2 4 2 5 妒k 的计算公式为 蠢也一t i g k l l l l d k 一 l i p l o 1 m o 啦 0 1 0 0 令他 i 靠d t i i d t t l 2 选取 a t h m 计算o i m a x o j a t j 1 2 使得 仇 一1 z i a t d t sr r t a x f x t ea t r f 2 i r 叩l a t g t d t 一 7 2 口 l l 呶1 1 2 2 8 r 0 调节非单调记忆梯度法 a n m g 数据 正整数m m 常数 0 p 2 p l 0 口 0 1 啦 0 七 0 s t e pl 计算鲰 如果l i 弧0 停止 同济大学博士后研究工作报告 s t e p2 计算t f k 风l 使其满足 2 5 2 6 计算以b y 2 4 s t e p3 计算a 0 使得 2 8 成立 s t e p4 令z i 1 z 弧d k 七 k 1 转s t e p1 注 在算法a n m g 中如果我们选择m i 则算法即为单调算法 为获得算法的全局收敛性 我们给出如下的假设条件 h 1 f x 在水平集c 扛i 卫 s z o 上有下界 h 2 v f x 在包含水平集c xj f x f x o 的一个开凸集上l i p s c h i t z 连续 引理2 1 在第k 次迭代中 假如l 陕0 0 则存在有限值血使得步长o e k 驰 满足 2 8 证明 利用反证法 假如存在一个j 的无限集合 使得 2 8 不成立 那么对于每一个 j j 我们有 f n 一1 f x k 0 j a k d k m a x f x k a 打f x k 洲 t h a k g 吾d k 一 2 硎训2 r o 2 z 量 r h a k g t d k 一 2 q i d 8 2 即 f x k 0 1 a a 鬲k d k f 一 x k 1 9 d k 一 7 2 0 j a i i d k l l 2 2 9 伊 一1 1 5 取极限j zj 可得 靠d k 叩1 卵畋 这与 2 7 矛盾 因此结论成立 为了方便起见 下面我们记一 7 l 瓯舞以 啦 i i d k l l 2 a t k 引理2 2 设 乳 为算法a n m g 产生的无穷点列 则存在常数k o 0 使得 f x k 一a 釜m f x o 一a k o 薹祥 2 10 r 0 0 m o 一a 盯 o 一 警 2 r i l j 1 9 同济大学博士后研究工作报告 证明 根据 女的定义 对所有的j 我们有 a 巧 一目l q 醪由 啦嵋 i 奶 2 2 一 7 t p l 巧怕 7 2 西哼i d j0 2 三篡躲铲 7 l p l 7 2 店 爵 碍l m 现店 下面我们用反证法证明 2 1 0 如果 1 根据 2 8 及a s l 我们有 f x 1 sf x o 一盯 如 s z o 一a a t o sf x o 一a 反 d o 假设 2 1 0 对于1 2 七成立 我们考虑两种情况 m 一1 情况1 m a x f a k a k r f x k 一 f x k 根据 2 8 我们有 r o f x k 1 2f z k 1 k d k sf x t g 一口 如 f x o 一a 盯 t r 一盯 f x o 一a 仃 洲小a 霎祥 f n 一l 1 情况2 m a x a 打f x 一 k z t 一 令q m i n 睛 m 一1 利用 2 8 r or o 可得 口 f x k t f x k 口t 出 s a k p f x k 一口 t p o qk p 2 s a k p f x o 一a 盯 o 一盯 t i 呻一t 一盯 t f or o 由于 0 1 2 q 0 1 2 k q 一2 c 扫 r 0 p q 0sr 七一q 一2 2 0 同济大学博士后研究工作报告 q a 印 1 a 卸芝a 我有 如 1 一a x k p a t 一 o t k p 1 一o t r op o p o f x o 一a 仃 t r 一a o t j 一盯 r o r k q 1 z o 一a o t 一仃 f x o 一a 仃 o m 一a o 盟i i d j 业l 证毕 定理2 1 设假设h 1 一h 2 成立 巩 为算法产生的无穷点列 则有 1 1 i r a i i m i i 0 证明 令七 则根据假设h l 和引理2 2 有 砉c 需艮o o 厶 7 u 根据 2 5 和 2 6 我们可知 一 手d k 击犁m 引1 2 懈 圭娄 蜘媳 1 黔 将 2 4 重写为 d k g t 去 风 上式两边取平方可得 i i 呶 1 2 j l 去 凤t d k t i l 2 2 9 d k o 瓤忾 2 1 2 1 1 2 1 2 2 1 3 同济大学博士后研究工作报告 因为 所以 因此有 由此可得 因此 这意味着 攫d 开k 2 因此根据 2 1 2 我们有 这说明 2 1 1 成立 风 饥t 一靠呶 雕 l g k l l l l d k 一 叭 nm m 仇t 一菇血 i i g i i 凤 o d 女一t f l扛 i 2 3 数值测试 下面我们利用数值例子对我们的调节非单调算法进行验证 我们利用m a t l a b 语 言进行了编程 在m a t l a b 7 0 下进行了运算 首先我们给出参数的选取 妒研o l 2 m 取为 可k i f g i i i l d i i 0 靠d k i t l 其他参数为p l 0 2 5 如 0 7 5 斗l 0 2 t 2 0 8 f 0 5 k 而1 1 0 丽 三础 胛 i 一一 一 i i一 蓑磐羟 鱼 蚴艘 拙雨 一而 一蝌 删丽 尸 照 脚 0 为迭代步长 共轭梯度法 c g 是求解问题 3 1 的著名方法之一 其中搜索方向血定义如下 反 腓1 甚1 c s s l 一鲰 像呶一 七 风 r 关于其可选择的公式有 俨 砑l l g 1 1 2 4 6 鲜胩 器 8 0 i s 8 1 酽 箍 5 6 卵y 薄 f 3 2 1 黠8 箍 1 6 6 1 这里弧一1 g k 一玑一1 一般来说 在精确线搜索或强w o l f e 线搜索下 共轭梯度法都具有良好的收敛性质 可见文献f 1 9 2 9 4 9 5 5 6 8 1 1 9 然而 当利用a r i m i j o 线搜索或w o l f e 线搜索时 下 降性质一般就不能保证了 为了保证c g 方法的下降性质 d i x o n 3 5 与a i b a a l if 1 建 设当d 不县下降青向时 估用帚谏下隆肯向一o 而不县一以 诵对汶样一种混合籍赂 同济大学博士后研究工作报告 d i x o n 3 s 与a i b a a l i 1 获得了共轭梯度法在一些非精确线搜索下的全局收敛性结论 最近 z h a n g 等人 1 1 3 给出了一个改进的p r p 下降方法 并在几类a r m i j o 线搜索下 获得了算法的全局收敛性 1 9 8 8 年 b a r z i l a i 与b o r w e i n 提出了求解二次函数的谱梯度方法 也称为b b 方 法 与经典的最速下降法相比较 b b 方法要求更少的计算量并大大加快了收敛的速 度 1 9 9 7 年 r a y d a n 将该方法扩展到一般的光滑无约束优化问题中 并借助非单调线 搜索技术获得了算法的收敛性 最近 b i r g i n 与m a r t i n e z 1 1 将共轭梯度法与谱梯度步 长 3 9 2 相结合给出了一类谱共轭梯度法 其中的搜索方向定义如下 d k 一e k g k 瓯d k 一1 其中巩为一个参数 反 o k y l k r 1 k 1 一t g k a i 一l 珊一1 而乳一1 2t k z 一1 文f 1 1 的数值检验表明当以取如下的谱步长时具有良好的数值效果 氏 1 8 1 8 k 1 3 4 罩七一l y k l 不幸的是 谱共轭梯度方法不能保证d 七为下降方向 在文 3 1 中 利用b f g s 拟 n e w t o n 校正公式 a n d r e i 提出了一个尺度共轭梯度法 使得在w o l f e 线搜索下该方法 为下降方法 但不知道在a r i m i j o 线搜索下是否下降 为此 z h a n g 在文f 1 1 4 中给出了 一个改进的f r 共轭梯度法 该方法可以保证在a r i m i j o 线搜索下为下降方法 收敛结 果为 1 i r a i n f 鲰i l 0 3 5 本章的目的是对文 1 l 的谱共轭梯度法从另一个方面进行改进 在这里我们将谱梯 度步长应用到整个共轭梯度方向而不仅在负梯度方向 进一步的我们借助非单调a r i m i j o 型线搜索进行迭代 在适当条件下获得了算法的全局收敛性 3 2 算法模型与收敛性 在本部分 我们将给出非单调谱共轭梯度法的算法模型并分析其收敛性 首先 我 们给出共轭梯度方向 其中段的选择取自y a s u s h in a r u s h i m a 与h i r o s h iy a b e 7 6 令d 2 定义为 d 一鲰 反巍一1 这里 硝日 勘 罢孟 露呔 l 0 同济大学博士后研究工作报告 而我们的谱共轭梯度方向定义为 也 以d 3 6 关于艮的定义我们将在下面的算法中给出 算法3 1 s t e p0 给出正整数m 和一些常数e 0 l 0 2 盯1 0 7 0 1 6 0 靠m 讥 0 选取 n 如 0 s t e p1 计算鲰 如果i i g k l i e 停止 s t e p2 根据 3 6 式计算噍 s t e p3 1 令沁 器 s t e p3 2 令霉 魄 a 故 s t e p3 3 计算最大指标t k 使得 嗣 女一j i f m a l x g 垫f x j 卧悟f ziik2 f z4 以及 铲掣 3 s 令 m m a x p l k 0 2 3 9 如果p k 7 令孤 l 8 k z t l 一以 批 g z 1 一9 转s t e p4 如果p k 2 不成立 定义k p l k 仃2 a 1 令k a 转s t e p3 2 s t e p4 计算靠 靠 蛳 i f 玩 0 令以 l 岛 否则计算 口i 8 k 8 k a n d o k l r a i n 目 m m a x a i l b t s t e p5 令奄 1 转s t e p1 七 髁 酬 同济大学博士后研究工作报告 为获得算法的收敛性 我们给出如下假设条件 假设3 1 a i f x 在水平集c x l f x z o 上有下界 a 2 梯度函数在包含水平集c 的一个开凸集n 上l i p s c h i t z 连续 即存在一个常数己使 得对所有的z y q 有 i i g x 一g v lj l 0 z 一 引理3 1 设出由算法3 1 产生 则有 露也 一竽l l g k 胆 3 1 0 证明 如果反 0 则靠 一以鲰 由于艮 毋嘲 所以 羹也 一巩l m o s 一生竽o g k l l z 如果反 0 则根据以的定义有 靠也 靠 一l i 玑1 1 2 侠甄t 也一1 坼 2 挂羹 一譬l l g k l l 2 一警 2 引理3 2 设 孤 为算法3 1 产生的无穷点列 如假设3 1 成立 则存在一个正常数p 使得 k