（运筹学与控制论专业论文）求解非线性无约束优化问题的修正bfgs方法.pdf

硕 ：论文 求解1 r 线性无约束优化问题的修证b f g s 方法 摘要 本文以a i p i n gl i a 0 1 6 提出的修正b f g s 公式为基础，着重研究了参数( 瓯，儿) ，给出 了一系列的参数选择。本文的日i 半部分介绍了b f g s 算法的历史和修正b f g s 算法的研 究现状。 本文的后半部分首先参照a i p i n gl i a o l 6 构造参数的方式，提出了一类新的参数 ( 坑，九) ，从而给出了新的修正b f g s 公式，并给出了算法全局收敛性、局部超线性收敛 性以及数值实验结果；紧接着，为了得到一般修j 下b f g s 算法的全局收敛性和局部超线 性收敛性，本文提出了参数( 坑，儿) 所需要满足的一般性条件，在数值实验部分，给定了 一个参数f 坑，儿) ，并给出了数值实验结果；最后，本文将新拟牛顿方程引入修正b f g s 公式，参数( 坑，以) 使用其一般性条件，同样有算法的全局收敛性和局部超线性收敛性， 作为这个算法的一个推论，本文会给出另外一个参数( 坑，以) 的一般性条件。 关键词：b f g s ，参数选择，全局收敛性，局部超线性收敛性，新拟牛顿方程 a b s t r a c t t h i sp a p e ri sb a s e do nt h em o d i f i e db f g sf o r m u l ap r o p o s e db ya i p i n gl i a o 6 i t d i s c u s s e sa b o u tt h ec h o i c eo ft h ep a r a m e t e r ( 瓯，儿) a n dp r o p o s e sas e r i e so fp a r a m e t e r c h o i c e s t h ef i r s tp a r to ft h i sp a p e rm a i n l yi n t r o d u c e st h eh i s t o r yo fb f g sa l g o r i t h ma n dt h e p r e s e n ts i t u a t i o no fm o d i f i e db f g sa l g o r i t h m t h es e c o n dp a r to ft h i sp a p e rf i r s t l yp r o p o s e sac l a s so f p a r a m e t e r ( 瓯，以) b yi m i t a t i n g l i a o sm e t h o d ，s ot h a tan e wb f g sf o r m u l ai so b t a i n e d t h eg l o b a lc o n v e r g e n c e 、l o c a l s u p e r l i n e a rc o n v e r g e n c ea n dn u m e r i c a le x p e r i m e n ta r eg i v e ni ns u c c e s s i o n t h e n ，i no r d e rt o o b t a i nt h eg l o b a l c o n v e r g e n c ea n dl o c a ls u p e r l i n e a rc o n v e r g e n c eo ft h eg e n e r a lm o d i f i e d b f g sa l g o r i t h m ，ag e n e r a la t t r i b u t eo f p a r a m e t e r ( 皖，以) i sg i v e n i nt h ep a r to fn u m e r i c a l e x p e r i m e n t ，as p e c i f i cp a r a m e t e ri sg i v e nt op a r a m e t e r ( d k ，儿) a tl a s t ，n e wq u a s i - n e w t o n e q u a t i o n sa r ei n t r o d u c e di n t o t h em o d i f i e db f g sf o r m u l a , s oan e wm o d i f i e db f g s a l g o r i t h mw i t ht h eg e n e r a lc o n d i t i o no fp a r a m e t e r ( 皖，以) w h i c hi sg l o b a lc o n v e r g e n ta n d l o c a ls u p e r l i n e a rc o n v e r g e n ti so b t a i n e d a sac o r o l l a r yo ft h i s a l g o r i t h m ，a n o t h e rg e n e r a l c o n d i t i o no fp a r a m e t e r ( 瓯，儿) i so b t a i n e d k e yw o r d ：b f g s ，p a r a m e t e rc h o i c e ，g l o b a lc o n v e r g e n c e ，l o c a ls u p e r l i n e a rc o n v e r g e n c e ， n e w q u a s i - n e w t o ne q u a t i o n l i 声明 本学位论文是我在导师的指导下取得的研究成果，尽我所知，在 本学位论文中，除了加以标注和致谢的部分外，不包含其他人已经发 表或公布过的研究成果，也不包含我为获得任何教育机构的学位或学 历而使用过的材料。与我一同工作的同事对本学位论文做出的贡献均 己在论文中作了明确的说明。 力j p 年占月z 岁日 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅 或上网公布本学位论文的部分或全部内容，可以向有关部门或机构送 交并授权其保存、借阅或上网公布本学位论文的部分或全部内容。对 于保密论文，按保密的有关规定和程序处理。 刎9 年b 。月可日刎9 ，年月巧口 硕l ：论文求解1 r 线件无约束优化问题的修正b f g s 方法 1 绪论 考虑下面的无约束优化问题 要势厂( x ) ( 1 1 ) 拟牛顿法被认为是求解中低维无约束优化问题的最有效算法之一，拟牛顿法一般采 用下面的迭代格式： 昧+ l = 坼+ 矾 ( 1 2 ) 其中听 0 是迭代步长，它满足某种线搜索条件，矾是迭代方向，一般满足 矾= 一何1 9 k ( 1 3 ) 其中g 。全夥( ) ，b 一般满足拟牛顿方程 境+ l s 女= y k ( 1 4 ) 其中s k 全以= x k + 1 - x k ，y k 垒g k + l - - g k 。 ， 著名的b r o y d e n 族拟牛顿校正公式满足式( 1 4 ) 且保持对称性，即 耻反一等+ 筹t + ( 色& ) 比嵋 其中2 石y k 一磊b h s k 。 当= 0 时， 孵= 暖一鬻+ 筹 ( 1 5 ) s 1b i ? s l ?s j ? v i ? 即得b f g s 公式； 当矽= 1 时， 群= b k + ( 1 + s 眺 b k s k ，筹一一 6 ， 即得d f p 公式。 p o w e l l 、b y r d 和n o c e d a l 等人对拟牛顿算法的收敛性做出了很大的贡献，如r i c h a r d h b y r d 、j o r g en o c e d a l 和y a x i a n gy u a n 1 9 1 证明了对二阶连续可微且有下界的凸函数，线 搜索采用w o l f e 准则的布鲁丹族算法( 除d f p 算法以外) 的全局收敛性和f ( x ) 是一致 凸函数且其h e s s i o n 矩阵为h o l d e r 连续条件下的局部超线性收敛性。 大量的数值实验表明b f g s 公式的数值稳定性要优于其他b r o y d e n 族公式，而且它 与非精确线性搜索方法结合使用能收到较好的计算效果，所以在实际计算中大多采用 b f g s 方法。 1 1 修正b f g s 方法 i i 1 对拟牛顿方程的修正 由于经典的拟牛顿方程( 1 4 ) 中只用到了两步的梯度信息“g k ，忽略了函数 值信息，所以很多学者都将函数值信息加入拟牛顿方程，以期得到更好的结果。 2 0 0 1 年，j i a n z h o n gz h a n g 和c h e n g x i a n x u u 利用张量技术，将厂( ) 和繇在+ l 点 展开 其中石 五= 石+ t 一颤t + 。+ 去v 2 厂( 吒+ 。) & 一刍( 瓦+ ，& ) s k + 0 ( 恢1 1 4 ) 。繇一v 2 厂( + 。) & + 击( 瓦+ 。瓯) 靠+ o ( i r s 。1 1 4 ) 全厂( ) ，瓦+ 。r ”是厂( x ) 在点+ 。处的张量，且 j ( 五+ ，s k ) s k 3 f ( x k + 。) i 融l 瓠ja x s 。i k c 。j k 。“l t 将上述两式消去张量部分，得 v 2 厂( + ，) 唧= ( 繇+ ，一) r & + 6 ( 五- a + ；) + 3 ( 繇+ + ，) r & + o ( 1 l s , 1 1 4 ) 由于需要s , b k + ，& 逼近v 2 ( + ，) & ，所以 b “s k2s t y + 9 k 其中皖= 6 ( 石一六+ 1 ) + 3 ( + g k + 1 ) 7 s k 。基于此式，j i a n z h o n gz h a n g 【u 提出了下面修正的 b 洲s k 。：多：，；7 。：y ：+ 牟m us k 其中u k r ”，u 。t 唧0 。 ( 1 7 ) 如果f ( x ) 充分光滑，那么有下面的结论成立： 4 ( v 2 f ( x k + 。s k y k ) = o ( f l s k 4 ( v 2 厂( 坼+ 。s k 一或) = d “& 1 1 4 ) 由上述两式可知，由式( 1 7 ) 捌s r b k + ，& 逼近v 2 厂( x ： + 。) 比由式( 1 4 ) 决定的瓯r b 川& 有更高的精度。 由式( 1 7 ) 得到的类b f g s 公式为 绞+ l _ 反一警孥+ 婆 j i a n z h o n gz h a n g 等证明了采用此峨校正公式的拟牛顿算法的全局收敛性和局部超线性 当= s k 时，式( 1 7 ) 退化为j z z h a n g ，n y d e n g 和l h c h e n 【2 】在1 9 9 9 年利用二次插值，提出的带函数值信息的修正拟牛顿方程 2 。小 硕i 二论文 求解1 | 线性无约束优化问题的修正b f g s 方法 b k + l s k - = 死蜘y k + 蠢s t 2 0 0 1 年，c h e n x i a nx u 和j i a n z h o n gz h a n g 3 1 用二次函数逼近厂( x ) 在+ 1 附近的值 饥，( s ) = 五+ 1 + 也s + s 若令v 吼+ 。( - - s k ) = g 。，便可得经典的拟牛顿方程( 1 4 ) ，若令吼+ 。( - - s k ) = 五，可得 忍+ ，s k = 2 ( 五- a 卅+ t 既+ 。t 儿+ e , 3 c h e n x i a nx u 等得到下面的拟牛顿方程 色以：y k , y k ：儿+ 掣甜 u s k 其中u k 月”，t 瓯0 。 当u 。= y k 时，式( 1 8 ) 退化为 b k + l s k - = ( 1 + 去卜磊所 得到下面的类b f g s 公式 这罩的磊 嘶镣+ 磊筹 ：1 + 旦：坐二墨芸型墨! s k y ks k y k ( 1 8 ) 。事实上，这里的上式就是1 9 9 1 年y a x i a n g y u a n 4 】所提出的修正的b f g s 公式。 2 0 0 6 年z e n g x i nw e i ，g u o y i nl i 和l i q u nq i t 5 】提出了一种拟牛顿方程的新形式： 鼠+ 1 s 女= y k + 4 & 全或( 1 9 ) 其中a k 是简单的对称矩阵。z e n g x i nw e i0 5 1 给出了a k 的一些选择： 1 1 2 对色校正公式的修正 钟) 2 爵， 觯) 2 南眦7 1 9 9 9 年焦宝聪【2 7 】基于目标函数的局部二次模型近似，取最+ ，如式 = 坑一鬻ss k 筹；b ks ；y k ( 1 1 0 ) 其中气一2 0 j 。- 肌a ) ( 五一无+ 。+ + 。7 1 & ) + 见秒 。，1 】。焦宝聪在文中参考r h b y r d 和j n o c e d a l l 7 】中的证明方法，得到算法全局收敛性和局部超线性收敛性。 1 9 9 7 年a i p i n gl i a o 6 1 出了一种双参数修j 下的拟牛顿法，其b 的校正公式如下： 3 l 绪论 硕i j 论文 = 色一瓯鬻+ 以爱 其中0 0 。 a i p i n gl i a o 6 1 给出了皖，以的取值： 若 ()：i(sl鼠sk一丽7-户焘+skyk+s；yk t f 婶k ，y k 、) = ! s k 巧k s k + s k y k1u 文b k s k 1 。 【( r ，1 ) e l s e 且0 f 1 ，在目标函数厂f x l 二阶连续可微和一致凸的条件下可得算法的全局收敛性； 武b k sk武y k s i 色s k + s j k y k ! s 7 ：b k s k 七s ：ykp 意气 ( 气，1 ) e l s e _ ro t k 1 ，一l nr k 0 的一些性质， 在适当的条件下，得到算法的全局收敛性和局部超线性收敛性，并进行数值验证。 本文可以分为以下4 个部分： 第1 章主要介绍了b f g s 算法的历史和修正b f g s 算法的研究现状； 第2 章 参照a i p i n gl i a o l 6 中的参数( 瓯，扎) ，模仿给出了一个新的参数选择 ( 皖，儿) ，从而给出新的算法，并给出了全局收敛性和局部超线性收敛性，最后给出了算 法的数值结果； 第3 章通过对a i p i n g “a o 【6 j 和第2 章的研究，为了得到一般的双参数修正b f g s 算法的全局收敛性和局部超线性收敛性，第3 章给出了参数( 坑，九) 的一般条件，最后给 出了一个参数( 瓯，以) 的具体选择以及它的数值结果； 第4 章将新拟牛顿方程引入双参数修正b f g s 公式，并利用第3 章中的参数 ( 皖，以) 的一般条件，得到第4 章算法的全局收敛性和局部超线性收敛性；最后作为第4 章一个推论，本文将给出一个稍弱的参数( 瓯，儿) 一般条件。 4 硕l ：论文求解1 f 线性无约束优化问题的修证b f g s 方法 2 一类修正的b f g s 算法 2 1 算法的一些准备工作 最的迭代公式： 嘶瓯鬻+ 缁 ( 2 1 ) 考察a i p i n gl i a o 【6 1 中的参数( 哦，圪) ，显然，在开关准则的第一条中满足坑+ 段= 1 ， 然而在b f g s 公式中，有( 反，儿) = ( 1 ，1 ) ，瓯+ 以= 2 ，所以有理由让我们在第2 章中取 暖+ 以= 1 + 旯，0 五1 。 参数选择1 ： 给定常数0 a 1 ，常数0 旯f 1 。，：(糍yk，糍7yk 若鲁鬻h( 皖，以) = s ；+ s ；b 瓯1+ s ；毋& j s ：以+ s ：色一 i( f ，1 ) 其他 显然，有下面的关系式成立： f 皖1 ( 2 2 ) 五以1 + 允一f 1 ( 2 3 ) 线搜索采用w o l f e 准则： 给定0 0 - 0 2 1 ，0 0 ；令k ：= 1 ； 步2 如果0g k i i 占，迭代停止；求解方程组或矾= 一g t 得到搜索方向巩； 步3 利用w o l f e 准则求吼； 步4由式( 1 2 ) 计算得到+ l ，通过参数选择1 计算出参数( 瓯，所) ，进而由式( 2 1 ) 计算得到反“； 步5 令k ：= k + 1 ，转入步2 。 2 2 全局收敛性 假设a ： ( a ) f ( x ) 二阶连续可微； ( b ) f ( x ) - - 致凸，即存在 掰 0 使得 聊2 z 7 g ( x ) z ，v x ，z r ” 此时，水平集( ) = x i f ( x ) 厂( ) 是有界闭凸集，存在o o ，境的迭代公式如式( 2 1 ) ，吼由w o l f e 准则确定， 那么当0 反1 ，以 0 时，毋+ l 0 。 证明：妥b o ，则由c a u c h y s c h w a r z 不等式有( x 7 砂) 2 o 若0 皖 o ，由于z 7 玩z 0 ，最 0 ，故z t n k + l z o ；若瓯= 1 ，儿 o g z 与唧 平行，显然有z7 反+ ，z o ；若瓯= 1 ，以 og z 与& 不平行，也显然有z i b k + l z 0 。 故引理得证。 显然，对于算法1 而言，由式( 2 2 ) 、式( 2 3 ) 和引理2 1 知，b 将保持正定性。 引理2 2 若厂( x ) 满足假设a ，则有 墼聊，单s m s ；s k y i s k 证明：以= g k + l - - = f g ( + o s k ) s k d o 令瓦= fg ( 稚+ 0 & ) d p y k = g k s k 那么有下面的不等式成立 6 ( 2 4 ) 硕i j 论文求解1 r 线性无约束优化问题的修正b f g s 方法 y ：y k y l k s k 孥t ：掣s tu 朋 s l &s is k m 其中z = 硪2 s t 引理2 3 若b 0 ，则有x r b x y 7 b 一1 j ，x r y ) ，协，y r ”，且当且仅当出与 y 线性相关时，等号成立。 证明：因为b 0 ，所以b 一1 2 存在。对“= b v 2 x 和v = b i ，2 y 应用c a u c h y s c h w a r z 不 等式，即 x r y ) 2 = ( b i 2 x ) 7 b q 2 y ) 2 = ( ) 2 “r 甜v 7 ， ( b l 2 x ) r ( b 1 2 x ) ( b l 2 y ) 7 1b l 2 y ) x t b x y7 1 b 一1 y 当且仅当“和v 线性相关，即凰与y 线性相关时，等号成立。 引理2 4 若最的迭代公式如式( 2 1 ) ，参数( 玩，以) 如参数选择1 ，则 其中 ，r ( 反+ 一) 护( 剐一互c o s 址20 。+ 鸩 d e t ( 反+ t ) d e t ( 壤) 詈 ( 2 5 ) ( 2 6 ) = 鲁，鸭= 等地= 警，c o s 皖= 瓜s l 最翮s , ，皖为& 和鼽的夹觥i 巩和 一的夹角。 证明：由式( 2 1 ) 得 帆一( 聃瓯燃+ 以咎 鲰( 聃反赢+ 警 甜( 聃器+ 地 由s h e r m a n m o r r i s o n - w o o d b u r y 定理以及引理2 3 可得 7 学瓣 2 一类修萨的b f g s 算法颂i ：论文 a e t ( 钆) _ d e t ( 色) h + ( 1 刮以訾蝴盎 批t c 色，h + 儿箍) = a e t c 最，卜+ 九号) 当 当 丸s t l yk + s7 i bk s i s t k yk + 誊k b k s | 1 一瞑 a s f y 。七0 k bk s t s t k yk + 武8 k s i f 时，参数( 瓯，以) 满足参数选择1 ， 帆in吼k=1一徽sks l l s k s kq k y k + 1 一墨丝丝! + m , q 女+ 1 ：盟 吼 0 ，则函数( b ) = 护( b ) 一i n ( d e tb ) 的最小值为n 。 证明：设b 的特征值为乃五 0 ，则 ( 口) = ( 4 - i n 见, ) _ 1 令h ( t ) = l - t + i n t ，f 0 ，显然有办( f ) 0 ，那么y ( b ) - - z ( 以- l na i ) _ n 0 。 = l 引理2 6 若( x ) 满足假设a ，由w o l f e 准则确定， 三0 一矗0 2 五一工土lg ,iim2m 2 一l i x 。一】已s ，。一，s 。 。 。 石一五+ ， q ( 1 - o 2 ) ( g 翘) 2 证明：由于厂( x ) 满足假设a ，那么 a - f , = ( 一五) + f ( 1 一目) ( 致一兄) 7 g ( 坼+ 矽( 一五) ) ( 一x ) c l o 刎一溉1 1 2 这里的矗是( x ) 的唯一最小值点，z 全厂( 五) ，毋= ag ( 矗) 。 8 ( 2 7 ) ( 2 8 ) ( 2 9 ) ( 2 1 0 ) 糍 硕i ：论文求解1 r 线性无约束优化问题的修j 下b f g s 方法 五一石g f ( 一矗) 0 i i i x k 一矗0 ( 2 1 1 ) = 繇一昏= fg ( 矗+ ，( 一五) ) ( 一矗) 力 令色= fg ( 五+ ，( 一矗) ) 斫，贝 j jg k = 磊( 一五) 所以有 m x k x 1 1 2 ( 一矗) 7 8 k ( x k 一五) = ( 一五) 7 所- - i l x 。- x 1lg 。0 将上式带入式( 2 1 1 ) ，可得 f t - f 判繇1 1 2 这样就得到式( 2 9 ) 。 出于吼满足w o l f e 准则，可得 【g k + ，- g k 7 巩( 吒一1 ) 颤t 以 0 繇卅一反0 = 0 五( + 。一砟) i f m 0 以0 联系上面两式，有 等爵 亿 将式( 2 1 2 ) 带入w o l f e 准则的第一个不等式，即可得式( 2 1 0 ) 。 引理2 7g 发f ( x ) 满足假设a ， 以) 是由算法1 生成的迭代数列，那么对任意的 pe ( o ，1 ) ，都存在常数届，厦，屈，使得对任意自然数七l ，在区间【1 ，k 】中至少有 p 尼】个 i 满足 c o s o , 屈 ( 2 1 3 ) 殷q j 屈 ( 2 1 4 ) 左皆会 亿柳 证明：仿照r h b y r d 和j n o c e d a l t 7 1 中的定理2 1 。由引理2 2 得，m k 册，坂m 由引理2 5 和引理2 4 得， 9 2 一类修币的b f g s 算法硕1 ：论文 0 y 【饩+ 1j 2 驴【饩+ 1 ) 一i n i d e t 版+ ij 护( 色) 一耄箩茛+ 一1 n ( d e t 色) 一l n + 1 1 1 吼 酬讣( 坂乩叫山跏( 卜“n 器) + i n c o s 2 幺 酬讣( m - l n m - l - l n r ) + ( 卜器地器 + i n c o s 2 皖 训咖m 瓤一器地器卜毋叫 令旬= 一( ，一函地) - i n c o s 2 够，显然纠，将上式重写为 三k 圭旬 型k + q ( 2 1 6 ) 智列 一1 p 令以为卣，乞，色中 p 后】个最小值所对应的指标集，缸= m a x 乞i _ ，以) 妻和去卜纠划唧， 由式( 2 1 6 ) 和式( 2 17 ) ，对于任蒽的j 以，有 乞 而1 ( y ( 岛) + q ) 记屁2 f l - ( ( 且) + q ) ，故乞 一属 那么存在常数度，孱，使得o o ，使得对任意自然 数| 1 ，在区间【l ，k 】中至少有【p 忌】个f 满足 c o s a , ( 2 1 8 ) 那么 以 一x ，且芝0 k x 1 l ，存在常数o ， 1 ，使得五+ - 一工r ( 石一工) 。 证明：仿照r h b y r d 和j n o c e d a l 7 1 中的定理3 1 。令j 为使得式( 2 1 8 ) 成立的指标 集，考虑对于任意的j j ，k l ：l 式( 2 9 ) 椭掣臀7 2 = 掣c o s 钝1 1 ，1 1 2 掣o , f l ( 1 - c r , l l g 川2 = w ol l g ，l | 2 其中w o = q ) 6 ( 1 - o r ：) m 。 由式( 2 9 ) 以及上式，对于任意的j j l - + f - 乃| 2 r 工乃一工一w ol l g 胛 ( 1 一，z ) ( 乃一z ) = r v p ( 乃一工) 其中，v p = 1 一w o m 。 由于j n 【1 ，克】至少有【础】个元素，以及序列 五) 是一个下降序列，有 五+ ，- s r ( 乃一工) 由式( 2 9 ) ， 勤- - x , 1 1 - ( 2 m ) v 2 艺( 五一工) v 2 2 ( 石一工) 垅 啦砉( ) 。 定理2 9 若( x ) 满足假设a ，那么由算法1 所产生的迭代数列 以) 收敛到厂( x ) 的 2 一类修于的b f g s 算法 硕i ：论文 最小值点溉， 且i i - - x , i i ，存在常数o 厂 1 ，使得石卅- f r 。( 石一工) 。 k = l 证明： 由引理2 7 知，对任意的p ( o ，1 ) ，都存在常数届，使得对任意自然数k 1 ， 在区间【1 ，k 】中至少有【肚 个f 满足 c o s p 届 那么由定理2 8 可得， 坼) 专五，且i i x , - x ij 0 0 ，存在常数o r 1 ，使得 五q 一石，( 石一工) 。 2 3 局部超线性收敛 给定常数o 五1 和数列 巩) 满足o r k 1 ，一l i l 佃 。，：( 糍，撩 若筹鬻t 靠婶k ，y k 、) = n 武y k + b k s k ! s ：y k + 畦b k s k ) 乍y k + s t b k sx q 【( 靠，1 ) 其他 显然，有下面的关系式成立： 皖1 ，l i r n 气= l 存在充分大的自然数，使得v k k o ，有 五以1 + 名一气1 线搜索采用试验步长为= l 的w 6 l f e 准则，即 给定0 q 0 2 1 ，0 q 0 ；令k ：= 1 ； 步2 如果| i 繇0 s ，迭代停止；求解方程组鼠矾= 一g k 得到搜索方向矾； 步3 利用试验步长为吼= l 的w b l f e 准则求吼； 步4 由式( 1 2 ) 计算得到以+ ，通过参数选择2 计算出参数( 瓯，儿) ，进而由式( 2 1 ) 计算得到色； 硕l ：论义 求解1 f 线性无约束优化问题的修币b f g s 方法 步5 令k ：= k + 1 ，转入步2 。 假设b ： ( c )g - , = 0 ，g 正定。 ( d ) f ( x ) 的h e s s i a n 矩阵g ( x ) 在矗处l i p s c h i t z 连续，即 i i o ( x ) - c i i 0 对五的某个邻域内的所有x 都成立。 参照r h b y r d 和j n o c e d a l t 7 】给出下面的一些记号： 记五= d 2 唧，觅= g f 啦y k ，磊= g i v 2 最g f l 2 ：攀，c 。s 反： s ls k 显黼s 1 kb k s k = 吾k k ，s t ky i = 蓉：多ko s - 1 茂蓉( = 百y ks k ，皿：罂 s ks ky ；s k 由( 2 1 ) 及上述等式可得 b k + l = 吾k 一瓯鬻+ 儿赣 ( 2 2 1 ) 引理2 1 0 由式( 2 2 1 ) ，参数( 坑，以) 如参数选择2 ，当k k o ，有下面的不等式成立 驴( 训外( 反) 一盟c o s 2 # k d e t ( 训独t ( 怠) 詈 + m t 少( 磊卅) ( 摩) + ( 亿一l n 历。一l 一1 n ) 鲫( 反) 一瞑+ 见 拙( 讣融( 摩) h + ( 1 训以案 冰t ( 磊) 卜+ 磅) t k 时，( 瓯，以) = 九文y k + 武b k s k 文y k + b k s k + l n c o s 2 反 + 6 y s t ky k + 九b k sk s k t y k + s7 ：b k s t ( 2 2 2 ) ( 2 2 3 ) ( 2 2 4 ) 1 3 l - 颤堂鹈 揣 当 2 一类修正的b f g s 算法硕l ：论文 1 一瓯+ 以孕 q k ：1 一鸳丝睾t 垒盘 s ：y k + s ：b k s k ：1 一墨篓亟美璺墨 s - - k 1 萝k + s - k 7b k i k s ：y k + 2 s ：b k s k 汤k s k 7y k + s ：b k s k 辱k i ：萝k + 兔：b k k 藏k ：多k + ：b k k 每k ：】一墨亟纽! + 亟纽塑堕 而k 每k + 1而k q , + 1 每k ：盟 每k 3 a ：v 2 1 1 2 ，存在自然数如 - - k o ， v k 以，有 a 以1 + 咆，i n ，魂一瓴 ， ， 其中气= m a x i x 。+ ，- - x , i 一溉吣 证明：仿照r h b y r d 和j n o c e d a l t 7 】中的定理3 2 。由式( 2 4 ) 多k i k = g ：气2y k 一k = g ：。己k g 心意k 一k = g v 2 ( 五一g ) g v 2 五 其中吼= m a x i x , - x i l 那么有下面的不等式成立 其中万= i g ：v 2 肚。 1 4 五一g 训i l g 啦0 2 三恢恢 万&( 2 2 5 ) 揣 当 啦 g = n ” 划吨 兑恢 硕i j 论义求解1 r 线性无约束优化问题的修丁fb f g s 方法 由式( 2 2 5 ) 0 或i i 一0 五0 万i i 瓦i l ，0 五i l 一0 或l 确0 瓦0 将上式重写为下式 ( 1 一砚) 0 瓦4 - 3 万，存在充分大的自然数 毛k o ，v 足k l ，有 见半箜_ l + 孕当幺 l + 瓴 “ 1 一醅。l 一万占。 “ “ 由于 办( 击) _ 三一- n ( - 叫o 以及。1 i m + 。& = o ，则存在充分大的自然数后2 毛，v 尼砭，有石气 一；。& 定理2 1 2 若f ( x ) 满足假设a 和假设b ， 坼) 是由算法2 生成的迭代数列，那么迭 代序列 砟 超线性收敛到x 。 证明：若参数( 皖，儿) 如参数选择2 ，则由式( 2 1 9 ) ，对于常数r 旯，存在充 分大的自然数岛，使得v 七岛，有f 暖1 ，五以1 ，这时可由第2 2 节证得全局收敛 性，且有恢一x i i 。 由引理2 1 0 和引理2 1 1 ，当k k ，时 2 一类修正的b f g s 算法硕l ：论文 o ( 反+ ，) ( 鼠) + ( n 砚- l - i n z k ) + 1 _ 籍扎箍j + i n c o s 2 反 ( 反) 弓。c k - i n r k + ( ，一器心蕊 + i n c o s 2 反 蛳) + 弦勺一孙k r 2 r 2 + 射一函扎器卜矗巨1 ， j =j = 七2i v v o v ， v v o v ， 由e 矧i i x k x 0 o 。，得k = k 2 。 外丽1 一 一器儿 ( 廖：) + 羹。一妻h 。j = k 得 j 羔= k 2l - n 丽1 一( 1 _ 盏地器肛 酹h 南巩一 一器地器卜得 炒丽1 一o ，小基伯 _ 0 可得l i m c o s o j = 1 ，l i m s j q j = 1 ，- - - 0 9，- - o o 。 e h 式( 2 1 9 ) ，得l i m s j = 1 1 6 故 l i m c o s o j = 1 ，l i m 季f = 1 l|-oo 。 = 随等丛2 = j c o s l 2o k 一2 玩+ 1 _ 。 蚓( 统一q ) & 删阱壤一酬忡t 忙网1 缈i & 故 ( 2 2 9 ) 佃 以 h 。树 一口 羽 k 2 ，数列 ( 摩) 有界。 设矩阵磊的特征值为o 臂霉露，则( 摩) = ( 臂一l n 臂) 。由于数列 ( 鼠) 有界，那么v f _ l ，厅，1s 髫一l n 零丁，存在常数 o 巧 i t 2 ，使得 互 影 疋；而矩阵露t 的特征值为o 去了1 f ，且对于每一个特征值，有 砉 毒 扣乩m 由上述分析可知 1 1 反1 1 ) 和 i l 露1 i i 有界，由等式色= g y 2 摩础2 ，那么有 0 d 7 2 l i _ 2l i 反忙0 色| l i i 础2 | 1 2 | i 反0 和0 g v 2 i l - 2l 露1 | l i i 所1 忙0 g v 2 1 1 2 i i 露1 l i ，所以 l l 最l l 和钏巧1 l l 有界。 由徐成贤、陈志平和李乃成2 3 1 中的定理3 3 3 5 知 ) 超线性收敛到最优解x 。 注：参数( 瓯，以) 满足参数选择2 的选择有很多： 注2 1 若五= 1 ，则b 的迭代公式( 2 1 ) 退化为经典的b f g s 公式，即r h b y r da n d j n o c e d a l 在文献【7 】中的工作； 注2 2 若力= 0 ，则毋的迭代公式( 1 ) 即为l i a o 6 1 中的公式，即l i a o 在文献 6 中 2 4 数值实验 针对( 反，几) 的些不同取法，我们通过数值实验，去考察它们的数值表现。我们用 v c + + 语言编写了程序源代码。在源程序中，w o l f e 准则的参数选择为： q = 0 0 0 0 1 ，= 0 9 ，初始步长设为1 ；初始矩阵且取为单位矩阵i ；算法的终止准则是 0 9 女i l 1 0 。5 或者迭代次数超过1 0 0 0 次。 考察( 4 ，) 满足参数选择2 的算法2 ，其中= e x p ( 一l o o 足1 0 0 0 5 ) 。注2 1 中的算法 即为经典的b f g s ，记为b f g s ，注2 2 中的算法记为l b f g s ，当0 五 0 5 ，则 m b f g s ，彳与l b f g s 相比，结果并不是很好；若0 五o 5 ，与l b f g s 相比，m b f g s ，名 的数值表现是不错的。 从表2 7 和表2 8 可以看出，对于解决8 0 维和1 0 0 维这样中等维数的问题，与l b f g s 相比，m b f g s ，五，五= 0 2 ，0 4 ，0 5 ，0 6 ，0 8 总体的表现并不令人满意。 硕l ：论文求解1 f 线性无约束优化问题的修正b f g s 方法 3 双参数修正b f g s 公式的一般性结论 3 1 问题的提出 a i p i n gl i a o l 6 1 中提出的双参数b f g s 公式，即式( 2 1 ) = 色一皖等s k + 儿爱y ks ；a k s o 且参数( 瓯，儿) 满足参数选择2 给定数列 ，满足o 气1e l - l n r , o o ( 哦，以)= f 吱bk s 文y k + 8 k sc! s ：y k + b k s l ( 气，1 ) ) 若焘现 其他 a i p i n gl i a 0 1 6 】给出了该算法的全局收敛性和局部超线性收敛性。 a i p i n gl i a o l 6 】中的超线性收敛证明，主要参考r h b y r d 和j n o c e d a l 7 】中的结论， 我们可以还原整个证明过程，发现厨百s l y ks lt ；k s k 丢。下面借助本文第2 3 节的一些 。 ” +z 符号说明这一点： 。 塞垒墨：篓堡墨刽墨虻： 吒t 儿+ s ；峨s ：几l 陬0 2 + s ；反蚧1 五1 1 2 m k + q k 利用本文第2 章的一些结论，有 卟嚣冰碥! 鳃驴1 亟 r n k + q k 吼 1 一乏s k 七圣i 这样删 就可以的得到两燕丢。 有了上面的结果，我们不难看出参数( 瓯，儿) 的定义中，j1 ，故( 坑，g k ) 只会取 到开关准则的第二条，即( 坑，y k ) = ( 气，1 ) ，而完全不会取到第一条。由此看来，算法的 局部超线性收敛主要归功于( 瓯，儿) 定义的第二条。那么像a i p i n gl i a o 6 1 的用开关准则去 定义参数( 瞑，苁) 就显得没有那么必要了。 下面本文将给出参数( 瓯，儿) 的一般性条件。 3 2 算法的条件 3 双参数修j 下b f g s 公r l ：的一般性结论 硕j ：论文 参数选择3 ： 给定常数0 0 ；令k ：= l ； 步2 如果0g k 忙，迭代停止；求解方程组b 矾= 一g k 得到搜索方向吨； 步3 利用w o l f e 准则求； 步4由式( 1 2 ) 计算得到+ 1 ，通过参数选择3 计算出参数( 瓯，儿) ，进而由式( 2 1 ) 计算得到玩+ ； 步5 令k ：= k + l ，转入步2 。 3 3 全局收敛性 引理3 1 若鼠的迭代公式如( 2 1 ) ，参数( 瓯，以) 如参数选择3 ，则 护( 最+ ，) 驴( 反) 一夏6 k q 百k + 届m d e t ( b k + 。) 风d e t ( 壤) 争 其中m pm k 、q 和o k 的定义如前。 证明：由( 2 1 ) 得 蛾砂( 耻瓯嵘+ 以咎 似t ( 色) 舞 聃t ( 色) 鲁 ( 3 1 ) ( 3 2 ) 引理3 2 设( x ) 满足假设a ， ) 是由算法3 生成的迭代数列，那么对任意的 p ( o ，1 ) ，都存在常数屏，以，孱，使得对任意自然数七 1 ，在区间【1 ，k 】中至少有【础】个 i 满足 c o s o , 群 压q j 孱 硕i ：论文 求解非线性无约束优化问题的修正b f g s 方法 属皆鲁 0 ( 玩+ 。) = 护( b + ) 一i n ( d e t b k + 。) 驴( 剐一器+ 岛峨乩( d e t 毋) 山山p 儿吼 叫讣( 矾乩- 1 - i n p 0 - i n 咖( 卜器地器) + i n c o s 2 皖 酬讣( 一膨- l n m - l - l n p o - i n t o ) + ( 卜器“蕊j + i n c o s 2 皖 酬跏咖册一函札普卜毋叫 其中c 2 = p i m - i n m - l - l n p o 1 1 1 。 仿照引理2 7 ，即可得引理的结论。 定理3 3 若厂( x ) 满足假设a ， 坼) 为由算法3 生成的迭代数列，则 k 收敛到( z ) 的最小值点矗，且喜l l 坼一溉| | o 。，存在常数o r