（应用数学专业论文）bfgs方法及其在求解约束优化问题中的应用.pdf

博士学位论文 摘要 本文研究求姆无约束非凸闻题的b f g s 方法以及求锵非线性约束问题的序列 二次规划( s q p ) 方法，既约h e s s i a ns q p 方法，序列二次约束= 次规划( s q c q p ) 方法我们首先在第1 章简单介绍将要研究的问题的背景和已有结果 在第2 章，我们磅究b f g s 方法在求解无约束非凸问题时的收敛问题众所 周知，b f g s 方法是求锯无约束优化问题的拟牛顿法中最有效的方法之一，它具 有很好的数值效果及快速的收敛性，然而采用精确线性搜索或非精确的w o f ，e 型 缗洼搜索或a r m 巧。绻陛搜索的b f g s 方法在求解非凸函数的极小化问题时并不 一定全局收敛本文通过在拟牛顿方程中使用扰动策略提出了一种扰动b f g s 方 法我们证明采用w o 骆型非精确线性搜索扰动b f g s 方法求解非凸函数的极小 化问越具有全局收敛性并且具有局部超线性收敛速度，而且保持b f g s 方法的仿 射不变性我们的数值实验表明扰动b f g s 方法比b f g s 方法及修正b f g s 方 法其有更好韵数馕效果 b f g s 方法中的较正公式经常被其它优化方法所使用并被弼来求解非线性方 程组，约束优化闯题，随机规鲻问题以及半无限规趔闯题等我们在第3 - 5 章里 研究通过b f g s 校正公式分别与s q p 方法，既约h e 鹊i m ls q e 方法，s q c q p 方法等的结台来求解一般的约束优化阔题 在第3 章，我们研究s q p 方法在较弱条件下的收敛闯题已有的关于s q p 算法的全局收敛性研究结果通常要求拟牛顿短阵序列一致正定和有界，然而是否 存在满足该条件的拟牛顿法尚不清楚利用扰动技术与b f g s 校正技术的有效结 合，我们提出了一种扰动s q p 方法，并证明所提出的扰动s q p 方法在较弱的约 束品性下保持全局收敛性，特别地，全局收敛性不要求拟牛顿矩阵的一致正定性 和有界性此外，我们也研究了没有使用扰动技术的s q p 方法的全局收敛问题， 提出了确保s q p 方法收敛的若干策略，其中包括一个新的拟牛顿矩阵校正公式和 一个关于罚参数的有效校正准_ 呱! 数值实验表明这些策略的使用使s q p 方法具有 更好的数值效果 s q p 方法通常被用来求解中小规模的约束问题，因此，我们在第4 章研究求 解较大规模问题的既约h e s s i a ns q p 方法融有的既约h e s s i a ns q p 方法通常只 能求解等式约束问题，而且它们的全局收敛分析要求约束函数的梯度向量是线性 无关的以及拉格朗匪涵数的既约h e s s i a n 矩阵序列是一致正定的使用前一条件 的主要原因在于已有盼拟牛顿校正公式灵能产生肄有霹定阶的拟牛顿矩阵序列， 面葡时这释校正公式对既皇尊h e s s i a ns q p 方法的全局收敛性起着重要的作舄因 i i b f c s 方法及其在求解约束优化问题中的应用 此，我们提出了一个产生的拟牛顿矩阵静阶可变化的校正公式，然后在戴基础上， 我们提出了求解一般等式约束问题f 可以是退化闻题) 的修正既约h e s s i a ns q p 方 法，并且在没有假定上述两个条件的情形下，我们证明修正既约h e s s i a ns q p 方 法是全局收敛的，而且将这种方法推广然后用来求解不等式约京闻题并获得了全 局收敛性结果，该方法的优点是可以求解既有等式约柬又有不等式约束的较大规 模问题，有效克服了已有的这类方法在求解含不等式约束问题时所遇到的困难与 限制 在第5 章，我们研究求解不等式约束问题的序列二次约束二次规划( s q c q p ) 方法众所周知，传统的s q p 方法通常会产生m a r a t o s 效应，阻碍了算法的快速 收敛性近年来，许多学者提出了使用约束函数的一阶和二阶信息的s q c q p 方 法，这类方法能有效地避免m a r a t o s 效应因而具有较快的收敛速度然而巴提出 的s q c q p 方法存在某些局限性，要么算法的全局收敛性条件太强，要么算法的 全局收敛性没有保证，要么只能求解凸规卿问题或约束函数是凸函数的问题利 甩扰动技术或b f g s 校正技术，我订挺出两个求锯一般不等约束问题的s q c q p 方法，并证织它们在较弱的条件下仍然全局收敛，丽且具有至少超线性收敛速度 在第6 章，我们针对前面各章提出静算法进行数值实验，数值结果表明所提 出的算法比已有的疑类算法更有效，有效地支持了本文的算法+ 关键词：b f g s 方法；非凸问题；约束问题；s q p 方法；既约h e s s i a u 阵方法； s q c q p 方法；全局收敛性 i i i 博士学位沦文 a b s t r a c t t h i st h e s i si sc o n c e r n e dw i t ht h eb f g sm e t h o df o ru n c o n s t r a i n e do p f i m i t - t i o na n di t sa p p l i c a t i o n st os e q u e n t 。i a lq u a ，d r a t i cp r o g r a m m i n g ( s q p ) m e t h o d ， r e d u c e dh e s s i a ns q p1 2 1 e t h o da n ds e q u e n t i a lq u a d r a t i c a l l yc o n s t r a i n e dq u a d r a t i c p r o g r a m m i n g ( s q c q p ) m e t h o df o rc o n s t r a i n e do p t i m i z a t i o n w ef i r s ti n t r o d u c et h ep r e v i o u sw o r k so nt h et h e s i si nc h a p t , ri i nc h a p t e r 2 ，w es t u d yt a l ee o i l v e r g e n c ep r o p e r t i e so fb f g sm e t h o df o rs o l v i n gn o n c o n v e x1 1 1 2 一 c o n s t r a i n e dp r o b l e m s i ti sw e l l k n o w mt h a tt h eb f g sm e t h o di so n eo ft h em o s t f a m o u sq u a s i n e w t o na l g o r i t h m sf o rs o l v i n gu 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 s b e c a u s eo f i t sf a v o r a b l en u m e r i c a le x p e r i m e n ta n df a s tc o n v e r g e n c ep r o p e r t y t t o w - e v e r ，t h eb f g sm e t h o dw i t he x a c tl i n es e a r c ho rw o l f e t y p ei n e x a c tl i n es e a r c ho r a r m i j oi n e x a c tl i n es e a r c hn e e dn o tc o i l v e r g ef o rs o l v i n gn o n c o n v e xm i n i m i z a t i o n p r o b l e m i nt h i sc h a p t e r ，w ei n t r o d u c eap e r t u r b a t i o ns t r a t e g yi nb f g sm e t h o d t od e v e l o pap e r t u x b e db f g sm e t h o d w ep t o v et h a tu n d e rm i l dc o n d i t i o n ，t h e p e r t u r b e db f g sm e t h o dw i t hw o l f el i n es e a r c hi sc o n v e r g e n tg l o b a l l ya n ds n p e r l i n e a r l ye v e ni ft h eo b j e c t i v ef u n c t i o ni sn o n c o n v e x m o r e o v e r ，t h ep r o p o s e d m e t h o dm a i n t a i n st h ea f f i n ei n v a r i a n e eo ft h eb f g sm e t h o da n de n j o y sm o r ef a - v o r a b l en u m e r i c a le x p e r i m e n t _ r e s u l t st h a nt h eb f g sm e t h o da n dt h em o d i f i e d b f g sm e t h o d s t h eb f g s u p d a t et e c h n i q u ei su s u a l l yu s e db yo t h e rm e t h o d sf o rs o l v i n gs o m e r e l a t e dp r b l e m ss u c ha sn o n l i n e a re q u a t i o n s ，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 s ， s t o e h a s t i cp r o g r a m m i n ga n ds e m i i n f i n i t ep r o g r a m m i n g i nn e x tt h r e ec h a p t e i r 。 w em a i n l ya n a l y z es q pm e t h o d ，r e d u c e dh e s s i a ns q pm e t h o d ，s q c q pm e t o df o r s o l v i n gc 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 sb ye m p l o y i n gb f g su p d a t et e c t m i q u e i nc h a p t e r3 ，w es t u d yt h ec c m v e r g e n cp r o p e r t i e so fs q pm e t h o d su n d e rm i l d c o n d i t i o n s t h eg l o b a lc o n v e r g e n c eo ft h ee x i s t e ds q pm e t h o d su s u a l l yr e q u i r e s t h a tt h eq u a s i n e w t o nm a t r i c e sa r eu n i f o r m l yp o s i t i v ed e f i n i t ea n db o u n d e d h o w e v e r ，i ti su n k n o w nw h e t h e rt h e r ee x i s t st h eq n s i n e w t o nm e t h o ds a t i s f y i n gt h e a b o v ec o n d i t i o n s b ye m p l o y i n gb f g su p d a t et e c h n i q u e ，w ep r o p o s e uap e r h l r b e d s q pm e t h o df o rs o l v i n gg e n e r a lc o n s t r a i n e dp r o b l e m s 1 1 叠p r o v et h a tt h ep r o p o s e dm e t h o dc o n v e r g e sg l o b a l l yu n d e rm i l dc o n d i t i o n i np a r t i c u l a r ，t h eg l o b a l c o n v e r g e n c ed o e sn o tr e q u i r et h eu n i f o r m l yp o s i t i v ed e f i n i t e n e s sa n dt h eb o u n d e d n e s so ft h eq u a s i n e w t o nm a t r i c e s ，w h i l ee x i s t e ds q pm e t h o su s u a l l yr e q u i r e b f g s 方法及其在求解约柬优化问题中的应用 t h e s ec o n d i t i o n s b e s i d e s ，w ep r o p o s es o m es t r a t e g i e sf a rg l o b a lc o n v e r g e n c ei n s q pm e t h o d s n u m e r i c a lr e s u l t ss h o wt h a tt h ep r o p o s e ds t r a t e g i e sa r ep r a c t i c a l l y e m c i e n t s q pm e t h o d s8 t eu s u a l l yu s e d s o l v es m a l la n dm e d i u m s c a l ep r o b l e m s i nc h a p t e r4 ，r es t u d yr e d u c e dh e s s i a ns q pm e t h o d sf o rs l o v i n gl a r g e - s c a l eo p t i m i z a t i o np r o b l e m s t h ee x i s t e dr e d u c e dh e s s i a nm e t h o d ss l o v eo n l ye q u a l i t y c o n s t r a i n e dp r o b l e m sa n dt h d rg l o b a lc o n v e r g e n c er e q u i r et h el i n e a ri n d e p e n d e n c e a n dt h eu n i f o r m t yp o s i t i v ed e f i n i t e n e s so ft h er e d u c e dh e s s i a no fl a g r a n g i a nt i m e t i o n t h er e & 8 0 nu s i n gt h er e q u i r e m e n to fl i n e a ri n d e p e n d e n c ei st h a tt h ee x i s t e d q u a s i n e w t o nu p d a t ef o r m u l a sg e n e r a “、o n l yq u a s i n e 吼o nm a t r i c e sw i 洫f i x e do r - d e r o nt h eo t - - h e rh a n d ，t h eu p d a t ef o r m u l a sp l a yi m p o r t a n t , r o l e si na n a l y z i n gt h e g l o b a lc o n v e r g e n c eo fr e d u c e dh e s s i a ns q p m e t h o d s # 昭p r o p o s ean e wq u a s i n e w t o nu p d a t ef o r m u l aw h i c hc a ng e n e r a t eq u a s i n e w t o nm a t r i c e sw i t hv a r i a b l e o r d e r ，a n dt h e np r o p o s ear e d u c e dh e s s i a ni n e t h o df o rs o l v i n gg e n e r a le q u a l i t y c o n s t r a i n e dp r o b l e m s ( i n c l u d i n gd e g n e r a t ep r o b l e m s ) a n dp r o v et h a tt h e p r o p o s e d m e t h o dg l o b a l l yc o n v e r g e sw i t h o u ta b o v et w or e q u i r e m e n t s m o r e o v e r ，b yu s i n g t h ep r o p o s e du p d a t ef o r m u l a we x t e n d st h er e d u c e dh e s s i a nm e t h o dt os o l v e c o n s t r a i n e dp r o b l e m sw i t hi n e q u a l i t yc o n s t r a i n t s i nc h a p t e r5 ，w es t u d yt h es e q u e n t i mq u a d r a t i c a l l yc o n s t r a i n e dq u a d r a t i c p r o g r a m m i n gm e t h o df o rs o l v i n gi n e q u a l i t yc o n s t r a i n e dp r o b l e m s i ti sw e l l k n o w n t h a tt r a d i t i o n a ls q pm e t h o d sm a yo c c u rm a r a t o se f f e c t s e v e r a la u t h o r sh a v e c o n s i d e r e ds q c q p t y p er f l e t h o d sw h i c hl l s p ；i n f o r m a t i o nu pt os e c o n d o r d e rf o r b o t ht h ec o n s t r a i n t sa n do b j e c t i v ef u n c t i o n s q c q pm e t h o d sa r ef r e eo ft h e m a r a t o se 髓c ta n dt h u se n j o yf a s tc o n v e r g e n c ep r o p e r t y h o w e v e r t h ee x i s t e d s q c q pm e t h o d ss o l v eo n l ys o m es p e c i a lp r o b l e m ss u c ha sc o n v e xp r o g r a m m i n g ， o rp r o b l e m sw i t hc o n v e xf e a s i b l es e 吐o rs o m ep r o b l e m sw i t hs t r o n gc o n d i t i o n s b ye m p o ： d n gt h ep e r t u r b e ds t r a t 9 3 o rb f g su p d a t et e c h n i q u ew ep r o p o s et w o s q c q pm e t b o d sf o rg e n e r a li n e 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 na n dp r o v et h a t t h ep r o p o s e ds q c q pm e t h o d sa r eg l o b a l l yc o n v e r g e n tu n d e xm i l dc o n d i t i o na n d a r eo fs u p e r l i n e a rr a t eo fc o n v e r g e n e ea tl e a s t i nc h a p t e r6 ，w er e p o r ts o m en u m e r i c a lr e s u l t sf o rt h ep r o p o s e dm e t h o d s t h en u m e r i c a lr d s u t ss h o wt h a tt h ep r o p o s e dm e t h o d sa r ep r a c t i c a l l ye f f i c i e n t a n dt h u ss u p p o r tt i l ep r o p o s e dm e t h o d s v 博士学位论文 k e yw o r d s ：b f g sm e t h o d ；n o n c o n v e xp r o b l e m ；c o n s t r a i n e dp r o b l e m ；s q p m e t h o d ；r e d u c e dh e s s i a nm e t h o d ；s q c q pm e t l h o d ；g l o b a lc o n v e r g e n c e v i 湖南大学 学位论文原仓性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究 所取得的研究成果除了文中特别加以标注引用的内容外，本论文不包 含任何其他个人或集体已经发表或撰写的成果作品对本文的研究做出 重要贡献的个人和集体，均已l 在文中以明确方式标明本人完全意识到 本声明的法律后果由本人承担 作者签名：誊1 诎丸 日期：办，占年 月善日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同 意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许 论文被查阅和借阗本人授权湖南大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段 保存和汇编本学位论文 本学位论文属于 l 、保密口，在年解密后适用本授权书。 2 、不保密团 ( 请在以上相应方框内打v ) 、 作者签名： 硝豇 导师签名铅奉 日期：西。占年2 月f 日 日期： 口年f 己月6 日 博士学位论文 1 1 预备知识 第1 章绪论 1 1 1无约束问题及其最优性条件 无约束优化问题的基本形式为； m i n ，( z ) ，z 酽，( 1 1 1 ) 其中f ：j p _ r 称为目标函数( 1 1 1 ) 的最优解定义如下 定义1 1 1 如果存在6 0 ，使得对所有满足忙一矿1 | 厂( 矿) ，则称矿为( 1 1 1 ) 的严格局部最优解 定义1 1 2 如果对所有。舒，( z ) ，( 矿) ，则称矿为( 1 1 1 ) 的总体 最优解如果对所有z 印，( o ) ，( 矿) ，则称矿为( 1 1 1 ) 的严格总体最 优解 判断舻是否是( 1 1 1 ) 的最优解的条件有如下三种形式 一阶必要条件设函数，连续可微，若z 是( 1 1 1 ) 的局部最优解，则 v y ( x 4 ) = 0 其中v ，表示，的梯度 二阶必要条件设函数，二阶连续可微，若，是( 1 1 1 ) 的局部最优解，则 v f ( x + ) = 0 且u t v 2 ，( z + ) 让0 ，v “舻 二阶充分条件设函数，二阶连续可微，则矿是( 1 1 1 ) 的严格局部最优解 的充分条件是 v f ( x ) = 0 且“t v 2 ，( z + ) “ 0 ，v0 u 彤 其中v 2 ，表示，的h e s s i a n 阵 b f g s 方法及其在求解约束优化问题中的应用 1 1 2约束问题及其最优性条件 约束优化问题的一般形式为： r a i n ，( z ) s t g ( z ) = 0 ，i = i ，2 ，m 。 ( 1 1 2 ) 岛( z ) 0 ，t = m e - f i ，m 。+ 2 ，m 其中，：舻_ + r 称为目标函数，c = ( c 1 ，仍，) 丁：形- + r m 称为约束函 数当m 。= m 时，( 1 1 2 ) 称为等式约束问题，而当m 。= 0 时，则( 1 1 2 ) 称为 不等式约束问题 可行解与可行域如果z 彤满足( 1 1 2 ) 中所有约束条件，则z 称为约束 问题( 1 1 2 ) 的可行解；所有可行解的集合称为可行域，记为x ，即 x = 卜形蔓三等。嚣棚) 定义1 2 1 设矿x ，如果 ( x ) ( x 。) ，v z x 成立，则称矿是问题( 1 1 2 ) 的总体最优解如果对一切z x 且$ 矿有 f ( x ) f ( x + ) 成立，则称矿是问题( 1 1 2 ) 的总体严格最优解 定义1 2 2 设矿x ，如果存在z 的某一邻域n ( x ，使得 f ( x ) f ( x 。) ，v 霉x n 0 + ，6 ) 成立，则称矿是问题( 1 1 2 ) 的局部最优解如果对一切f xn ( 矿，6 ) 且 z 矿有 ( x ) ( x + ) 成立，则称矿是伺题( 1 1 2 ) 的局部严格最优解 我们丹| 入记号 e = 1 ，2 ，m e ) i = 仉- i - 1 ，批+ 2 ，m ) 博士学位论文 i ( x ) = a ：岛( z ) = 0 ，t n 定义1 2 3 对任何z 舻，我们称集合 4 ( z ) = f u l ( x ) 为在z 点处的有效集合，称g ( z ) ( i 4 ( z ) ) 为在z 点处的有效约束 与( 1 1 2 ) 有着密切联系的一个函数是 m l ( x ，a ) = m ) + a 7 c ( 砷= m ) + 九c l ( z ) ， 口1 这一函数被称为拉格盯日函数，其中a = ( a 1 ，k ，k ) t 尼”被称为拉格朗日 乘子 设矿x ，我们定义集合 l f d ( x * , x ) = 冠“：v c | i ( z + ) r 钍= o ，i e ；v c 。( z + ) 7 u 0 ，i i ( x 。) ) s f d ( x + ，x ) = u 彤：j _ + ，如_ o i e z + - 4 - g k u k x ) 跗= r n v c ( x * ) t u = o i e e m 。， 纠嚣黧嚣 n 坞， 条件( 1 1 3 ) 称为k k t 条件，它由k u h n 和t u c k e r 【1 】以及k a r u s h 【2 】给出， ( 1 1 3 ) 也可以写成 p 矿h 巴6 鼎i 耋荔 m ， 【 a ；o ，j ( $ + ) 。 3 _ b f g $ 方法及其在求解约柬优化问题中的应用 满足k k t 条件的点x x 或( 矿，”) 被称为k k t 点当k k t 点满足某种约 束品性时，它一定是最优解i s ，4 ，5 】 二阶充分条件设矿是问题( 1 1 2 ) 的一个k k t 点，”是相应的拉格朗日 乘子如果 “r v ：。l ( z ，a + ) 牡 0 ，y o 乱s ( z + ，a + ) 成立，则矿是问题( 1 1 - 2 ) 的局部严格最优解其中 l v l ( 矿，”) = v 2 ( z ) + n v 2 c l ( 矿) l = 1 是l ( x ，a ) 在0 ，”) 处关于。的h e s s i a n 矩阵 1 2 研究背景及进展 1 2 1 b f g s 方法及其研究进展 b f g s 方法求是解无约束问题的拟牛顿方法中的最有效的方法之一，它由 b r o y d e n 【6 】，f l e t c h e r 3 】，g o l d f a r b 【7 】和s h a n n o 8 】所提出求解问题( 1 1 1 ) 的 b f g s 方法的算法步骤如下t b f g s 方法 步0 选择初始点z l p ，初始对称且正定矩阵b 1 p “计算梯度 v ，( z 1 ) 令k = 1 步1 如果v ，( z ) = 0 ，则算法终止，否则，令呶= 一点1 1 v ，( ) 步2 对函数，0 ) 在点瓢处沿着方向以进行某种线性搜索获得步长觎，然 后令z k + 1 = 孤+ o d k 计算v ( z k + 1 ) 步3 由下列公式计算鼠+ 1 b k + l = b a 一鬻+ 舞， 其中8 k = z + 1 一z k ，y k = v ( z k + 1 ) 一v f ( x k ) 步4 令k = k + 1 ，转步1 b f g s 方法中矩阵岛+ l 满足拟牛顿条件y k = 风+ 1 8 众所周知，如果玩是正 定的，则也是，在孤处的一个下降方向计算步长q 女所使用的线性搜索包括 精确搜索，非精确的w o f ，e 型搜索、a r m o o 搜索以及满足g o l d s t e i n 条件的非精 确搜索等 4 博士学位论文 由于b f g s 方法具有较好的数值效果和快速的收敛性，它已成为工程师和数 学家解决最优化问题的一类受欢迎的方法b f g s 方法已有较完善的局部收敛理 论h ，对其全局收敛性的研究也取得了重要成果特别是对于凸函数的极小化 问题，采用精确线性搜索或某些特殊非精确线性搜索，b f g s 方法具有全局收敛 性 u - 堋 对于求解一致凸目标函数的极小化问题，p o w e l l 【1 6 】证明了b r o y d e n 族( 包含 b f g s 方法) 中的d f p 方法( 参见文献【7 】) 当采用精确线性搜索时会终止于唯一 的极小值点或者其迭代序列收敛于极值点d i x o n 【1 q 进一步发现在求解一般函 数的最优化问题时，b r o y d e n 族中的所有算法如果采用精确线性搜索会产生相同 的迭代序列p o w e l l 在文献 1 9 】中首先证明了采用w o 托型非精确线性搜索的 b f g s 方法在求解凸函数的极小化问题时是全局收敛的，b y r d ，n o d 出和y u a n 【1 2 】将p o w e l l 的结论推广到参数日 0 ，1 ) 之间的b r o y d e n 族中的所有方法 许多优化研究工作者一直致力于研究b f g s 方法在求解无约束非凸问题时 的全局收敛性问题，现在已取得不少的成果在假定x k - - + 牙的条件下，p o w e l l 1 9 】 考虑了二维的目标函数的极小化问题，并证明了采用精确线性搜索的b f g s 方法 来求解该问题时是全局收敛的，即牙满足v 厂( 牙) = 0 p u 和y h 将这一结果 推广到多维的情形y u a n ” 通过修改近似目标函数的二次模型的匹配条件提出 了一个改正的b f g s 算法，并证明了它的全局收敛性与局部超线性收敛性 l i 和f u k u s h i m a 在文献 2 2 和【2 3 】中通过修正b f g s 校正公式分别提出了修正的 b f g s ( m b f g s ) 方法和保守的b f g s ( c b f g s ) 方法，并且证明了这两种方法在使 用非精确的w o 雅型线性搜索或a r m i j o 线性搜索时即使求解无约束非凸最优化 问题也是全局地收敛的但前者破坏了b f g s 算法的仿射不变性质，而后者仅部 分地保持这一性质阻1 p o w e l li 衢】提出，如果目标函数在有界水平集上是二次连 续可微的，并且在每次迭代所使用的非精确线性搜索总是找到效益函数的第一个 局部极小点，那么b f g s 方法全局地收敛在一个较长时间内，人们试图使用较 强的附加条件或修正b f g s 方法的结构等手段来研究b f g s 方法在求解非凸问 题时的全局收敛性，但没有从根本上解决b f g s 方法是否全局收敛的问题直到 最近，d a i 在文献【2 6 】中给出了一个二维函数的例子说明采用w o 骆型非精确 线性搜索的b f g s 方法在求解无约束非凸问题时不一定收敛 m a s c a r e n h a s 【2 1 中进步给出了一个三维函数的例子说明采用精确线性搜索的b f g s 方法在求解 无约束非凸问题时也不一定收敛，而且在给出的例子中，b f g s 方法产生的迭代 满足a r m i j o 搜索条件，这意味着使用a r m i 3 0 线性搜索的b f g s 方法也可能不 收敛w e i ，y u 和y u a n 等【3 8 】通过修改拟牛顿条件提出了一个修正的b f g s 方 法，并在一定条件下证明了它的超线性收敛性y u ，w e i 和g u a n 3 0 提出了一个 b f g s 方法及其在求解约柬优化问题中的应用 信赖域b f g s 方法，在每次迭代求解一个与原问题的凸性无关的严格凸规划子问 题，并证明了所提出的方法是全局和超线性收敛的由已有的关于b f g s 方法的 研究成果可知，为确保b f g s 算法的全局收敛性，b f g s 方法通常需要作某一些 修正本文将进一步研究在保持b f g s 方法仿射不变性的前提下b f g s 方法的修 正形式 b f g s 方法的核心内容是b f s 校正公式，利用这一公式产生h e s s i a n 矩阵 的近似，避免了直接计算h e s s i a n 矩阵因此，这一校正公式现在已被广泛使用 在其它优化方法中，例如，它已经被用在求解非线性方程组【3 ”，约束优化问题 【3 2 ，3 3 ，3 4 ，3 5 1 ，半无限规划问题m ，3 1 以及随机规划问题嗍等的数值方法中 1 2 2 s q p 方法的研究进展 在求解约束优化问题的方法中，s q p 类方法是颇受欢迎的算法类之一s q p 方法是求解中小规模的约束优化问题的最有效的方法之一s q p 方法是一种迭 代方法，其核心工作是在每次迭代求解一个二次规划( q p ) 子问题如何构造q p 子问题，对s q p 方法的收敛性起着重要的作用除非直接计算拉格朗日函数的 h e s s i a n 矩阵，这类方法通常需要生成拟牛顿矩阵来近似h e s s i a n 矩阵，然后构造 子问题的目标函数因此如何生成拟牛顿矩阵对s q p 方法的收敛性起着重要的作 用 与s q p 方法的最初研究相关的工作是w i l s o n 于1 9 6 3 年提出的l a g r a n g e - n e w t o n 方法这种方法通过直接计算拉格朗日函数的h e s s i a n 矩阵来构造q p 子 问题或关于原来问题的k k t 条件的拟牛顿方程，然后通过求解q p 子问题或拟 牛顿方程产生一个搜索方向，由此构造一个序列来近似原问题的k k t 点这种方 法的全局收敛性要求h e 龉i a n 矩阵是正定且一致有界，但这种条件通常很难被满 足，而且这种方法的计算量太大p o w d l 【蚰】在1 9 7 7 年对这一方法进行了修改在 上一世纪6 0 年代末和7 0 年代初，随着拟牛顿技术的发展，s q p 方法吸引了许多 学者的注意，其中有代表性的工作是h a nh 1 】于1 9 7 6 年对l a g r a n g e - n e w t o n 方法 的修改，其主要的修改是在每次迭代用拟牛顿矩阵来代替拉格朗日函数的h e 龉i a n 矩阵在h a n 【4 1 的基础上，s q p 方法的研究工作已取得丰硕的成果，箱，4 2 5 5 1 关于s q p 方法研究工作的一个重要方面的是生成拟牛顿矩阵序列生成拟牛 顿矩阵序列的一个有效方法是利用b f g s 校正公式，由这一公式生成的拟牛顿矩 阵是对称的然而s q p 方法通常需进行某种使效益函数单调下降的线性搜索， 这要求所使用的搜索方向是效益函数在给定点处的下降方向，进而要求拟牛顿矩 阵是正定的同时为确保s q p 方法产生的迭代序列收敛，要求拟牛顿矩阵是有界 的因此，s q p 方法全局收敛分析通常要求拟牛顿矩阵序列一致正定且有界， 博士学位论文 然而，至今为止，尚不清楚是否有满足该条件的拟牛顿法存在许多作者通过对 b f g s 校正公式作适当的修改确保拟牛顿矩阵序列的正定性一捌但拟牛顿矩阵 的一致正定性和有界性仍然是没有保证的 关于s q p 方法研究工作的另一个重要方面是如何确保其中的二次子问题的 可行性f 3 4 ，5 1 ，5 4 ，删二次子问题的可行性完全取决于其线性约束的相容性，当线 性约束不相容时，二次子问题是无解的p a n t o j a 和m a y n em 通过在线性约束 中添加松弛变量使得二次子问题是有解的，然后提出一个修正的s q p 方法，在正 的线性无关性，二次子问题解的有界性和拟牛顿矩阵的一致正定有界性的假设条 件下，他们证明了所提出盼s q p 方法的全局收敛性w r i g h t 嗍则提出了一个 稳定的s q p 方法，即使有效约束的雅可比矩阵是非满秩的，w r i g h t 证明了所提 出的方法具有局部超线性收敛性w r i g h t 【5 5 】则提出了另外一种s q p 算法，并 证明了这一算法在较弱的约束品性性具有局部超线性收敛性，l i 和q im 利用 求解线性方程组提出了个稳定的s q p 算法，并且在没有假定线性无关性的条件 下证明了这一算法具有局部二次收敛性当线性约束不相容时，z h a n g 和z h a n g 阳】使用效益函数的负梯度的某个近似作为搜索方向来修正s q p 方法，在所有 可行点处具有广义的 扎叼口n n m m m d 协约束品性和在不可行点处具有线性无 关性的假定条件下，作者证明了所提出的方法是全局收敛的 除上面两个重要方面外，在大多数使用线性搜索的序列规划方法中，罚参数 的校正方法也是非常重要的文献【3 4 ，3 5 ，5 9 ，6 0 】研究了关于罚参数的校正方法 除了上面关于s q p 方法的传统的研究工作外，许多作者提出了不使用线性搜 索的过滤器s q p 方法【6 l 4 1 这类方法一般对拟牛顿矩阵的要求比传统的s q p 方法低，但其全局收敛分析也通常需假定拟牛顿矩阵是有界的由此可见，在对 拟牛顿矩阵没有任何假定的条件下研究s q p 方法的全局收敛性有着重要的理论 意义此外，对s q p 方法在较弱的约束品性下的全局收敛行为及罚函数中关于罚 参数的校正准则的研究也有一定的理论和现实意义本文将进步研究s q p 方 法中罚参数的校正方法以及拟牛顿矩阵的产生方法，并且研究s q p 方法在较弱 的假设条件下的全局收敛性 1 2 3 既约h e s s i a n 阵方法的研究进展 s q p 方法一般用来求解中小规模的优化问题，但实际中的许多问题通常具有 较大规模，因此，研究如何求解大规模问题具有非常重要的现实意义既约h e s s i a n 阵方法是求解较大规模问题的有效方法之；它的一个显著优点是在算法执行过 程中能节省大量的存储空间，这一点对求解大规模问题尤其重要+ 文献 6 5 】利用 拟牛顿校正技术提出了求解无约束优化问题的既约h e s s i a n 拟牛顿方法，但更多 b f g s 方法及其在求解约束优化问题中的应用 的研究工作者侧重于研究利用既约h e s s i a n 方法来求解约束问题【3 2 ，部- 6 9 1 在既约 h e s s i a n 方法中，每次迭代需构造一个q p 子问题，它的目标函数的h e s s i a n 矩阵 拟牛顿矩阵通常是拉格朗日函数的既约h e s s i a n 矩阵的近似，生成这种h e s s i a n 矩阵的有效方法是借用拟牛顿校正公式，其中b f g s 校正公