（运筹学与控制论专业论文）线性约束优化问题的可行mbfgs算法.pdf

af e a s i b l em b f g sm e t h o df o rl i n e a r l yc o n s t r a i n e d o p t i m i z a t i o n m azh e n g f a n g b s ( h u n a nu n i v e r s i t y ) 2 0 0 8 at h e s i ss u b m i t t e di np a r t i a ls a t i s f i a c t i o no ft h e r e q u i r e m e n t sf o rt h ed e g r e eo f m a s t e ro fs c i e n c e o p e r a t i o n sr e s e a r c ha n dc o n t r o lt h e o r y i nt h e g r a d u a t es c h o o l o f h u n a nu n i v e r s i t y s u p e r v i s o r p r o f e s s o rl id o n g h u i a p r i l ，2 0 1 1 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究 所取得的成果。除了文中特别加以标注引用的内容外，本论文不包含任 何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要 贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声 明的法律后果由本人承担。 作者签名：乃正劣 日期：“年厂月 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同 意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许 论文被查阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段 保存和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密讨。 ( 请在以上相应方框内打“ ) 作者签 导师签 日期：纠f 年莎月2 - 日 日期：圳年6 月2 日 l 硕：l ：学位论文 摘要 最优化问题广泛的存在于农业、国防、交通、金融、能源、通信等诸多领域 其中拟牛顿法是求解最优化问题的一类十分重要的算法，该类算法中拟牛顿矩阵 风的修正对算法的收敛性和收敛速度起着重要的作用b f g s 方法被认为是拟牛 顿法中最为有效的一种，它只需利用目标函数值和一阶导数的信息在一定的条件 下具有较快的收敛速度但在求解无约束最优化问题中，当目标函数非凸时，有例 子表明采用w o l f e - p o w e l l 型线性搜索的b f g s 算法不收敛为此l i f u k u s h i m a 在 2 0 0 1 年提出了一种b f g s 的修正形式一m b f g s 算法，该算法用于求解非凸函数 极小值问题时也具有全局收敛性而且，仇的对称止定性与算法的线性搜索以及 目标函数的凸性无关 本文将l i f u k u s h i m a 求解无约束最优化问题的m b f g s 算法加以改进，将其 应用到求解线性约束优化问题中，采用可行方向与m b f g s 修正相结合的方式建 立算法分别提出求解等式约束优化问题、非负约束优化问题和一般线性约束优化 问题的可行m b f g s 算法，并证明在一定条件下采用t r m i j o 线性搜索的m b f g s 算法具有全局收敛性和超线性收敛速度特别地，对于等式约束优化问题我们将 g r i p p o 等提出的非单调线性搜索技术引入到m b f g s 算法中这种技术可以减少 线性搜索试探步，获得较大步长最后，通过数值实验来验证以上算法，结果表明 本文的算法具有较好的数值效果 本文算法的优点在于算法产生的点列是可行点序列，且直接利用目标函数作 为效益函数，可以有效地避免m a r a t o s 效用 关键词：线性约束问题；m b f g s 算法；a r m i j o 线性搜索；非单调线性搜索；全局收 敛性；超线性收敛性 i i 硕士学位论文 a b s tr a c t o p t i m i z a t i o np r o b l e m sh a v eaw i d er a n g eo fp r a c t i c a lb a c k g r o u n di na g r i c u l t u r e ， n a t i o n a ld e f e n s e ，t r a n s p o r t a t i o n ，f i n a n c e ，e n e r g y , t e l e c o m m u n i c a t i o n sa n do t h e ra r e a s q u a s i - n e w t o nm e t h o d sa r ev e r yw e l c o m ei nt h es o l u t i o no fm i d d l es i z eo p t i m i z a t i o n p r o b l e m s i naq u a s i n e w t o nm e t h o d ，t h ep o s i t i v ed e f i n i t e n e s so ft h eq u a s i n e w t o n m a t r i xp l a y sa ni m p o r t a n tr o l ei nt h eg l o b a lc o n v e r g e n c eo ft h em e t h o d b f g sm e t h o d i sr e g a r d e da so n eo ft h em o s te f f i c i e n tq u a s i n e w t o nm e t h o d s u n d e ra p p r o p r i a t ec o n - d i t i o n s ，t h em e t h o di sg l o b a l l ya n ds u p e r l i n e a r l yc o n v e r g e n t h o w e v e r ，w h e na p p l i e d t os o l v ean o n c o n v e xm i n i m i z a t i o np r o b l e m ，t h es t a n d a r dm e t h o dm a yn o tb eg l o b a l l y c o n v e r g e n t r e c e n t l y , l ia n df u k u s h i m am a d eam o d i f i c a t i o nt ot h es t a n d a r db f g s m e t h o da n dp r o p o s e dam o d i f i e db f g sm e t h o d m b f g sm e t h o d i th a sb e e np r o v e d t h a tt h em b f g sm e t h o di sg l o b a l l ya n ds u p e r l i n e a r l yc o n v e r g e n te v e nw h e nt h eo b - j e c t i v ef u n c t i o ni sn o tc o n v e x a na t t r a c t i v ep r o p e r t yo ft h em b f g sm e t h o di st h a t t h eq u a s i n e w t o nm a t r i c e sg e n e r a t e db yt h em e t h o da r ea l w a y sp o s i t i v ed e f i n i t e t h i s p r o p e r t yd o e sn o tr e l yt h el i n es e a r c hu s e d i nt h i st h e s i s ，w ee x t e n dt h em b f g sm e t h o do fu n c o n s t r a i n e do p t i m i z a t i o nt o d e v e l o paf e a s i b l em b f g sm e t h o df o rs o l v i n gl i n e a r l yc 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 w ep r o p o s et h em e t h o db yt h eu s eo ft h ei d e ao ft h ef e a s i b l ed i r e c t i o nm e t h o d a n dt h em b f g sm e t h o d w ef i r s td e v e l o paf e a s i b l em b f g sm e t h o df o rs o l v i n gl i n e a r e q u a l i t yc o n s t r a i n e dp r o b l e m w et h e ne x t e n dt h ei d e at od e v e l o paf e a s i b l em b f g s m e t h o df o rs o l v i n gn o n - n e g a t i v ec o n s t r a i n e dp r o b l e ma n dg e n e r a ll i n e a r l yc o n s t r a i n e d p r o b l e m s w es h o wt h a tu n d e ra p p r o p r i a t ec o n d i t i o n s ，t h ep r o p o s e dm e t h o d i sg l o b a l l y a n ds u p e r l i n e a r l yc o n v e r g e n t w ea l s oa d o p tt 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 e i n t r o d u c e db yg r i p p oe t a 1 t od e v e l o pan o n m o n o t o n ef e a s i b l em b f g sm e t h o df o r s o l v i n gl i n e a re q u a l i t yc o n s t r a i n e dp r o b l e m s a tl a s t ，w ed os o m en u m e r i c a le x p e r i m e n t st ot e s tt h ep r o p o s e dm e t h o d t h er e s u l t ss h o wt h a tt h ep r o p o s e dm e t h o di s p r a c t i c a l l ye f f i c i e n t a st h ep r o p o s e dm e t h o dg e n e r a t e sf e a s i b l ep o i n t s ，w eu s et h eo b j e c t i v ef u n c t i o n a st h em e r i tf u n c t i o n c o n s e q u e n t l y , t h em e t h o dc a na v o i dt h em a r a t o se f f e c t k e yw o r d s ：l i n e a rc 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 ；m b f g sm e t h o d ；a r m i j o l i n e a rs e a r c h ；n o n m o n o t o n el i n e a rs e a r c h ；g l o b a lc o n v e r g e n c e ； s u p e r l i n e a rc o n v e r g e n c e i i i 硕士学位论文 目录 学位论文原创性声明和学位论文版权使用授权书i 摘要i i a b s t r a c t i i i 第1 章绪论1 1 1 引言1 1 2 求解无约束优化问题的b f g s 法和m b f g s 法2 1 3 线性搜索准则4 1 4 本文的主要贡献与章节安排6 第2 章求解等式约束优化问题的单调可行m b f g s 法8 2 2 算法8 2 3 全局收敛性1 0 2 4 超线性收敛性1 2 2 5 数值试验1 4 第3 章求解等式约束优化问题的非单调可行m b f g s 法1 6 3 2 算法1 6 3 3 全局收敛性1 7 3 4 数值试验1 9 第4 章求解非负约束优化问题的单调可行m b f g s 法2 2 4 2 算法2 2 4 3 全局收敛性2 4 4 4 数值试验2 5 第5 章求解线性约束优化问题的单调可行m b f g s 法2 7 5 2 算法2 7 5 3 全局收敛性2 9 5 4 数值试验3 0 结论3 2 参考文献3 5 致谢3 8 硕l ：学位论文 1 1 引言 第1 章绪论 本文考察如下线性约束优化问题： m i n f ( x ) s t a x = b ，( 1 1 ) z 0 其中目标函数f ：形一r 连续可微，矩阵a 黼，向量b 我们假设线性 约束a x = b 是相容的为方便起见，我们不妨假设a 是行满秩的 在求解约束最优化问题例如( 1 1 ) 的很多算法中，序列二次规划( s q p ) 算法是 一类有效的算法s q p 算法最早是由w i l s o n 于1 9 6 3 年在其博_ 上论文中提出，但 直到2 0 世纪7 0 年代中期才引起人们的重视并得到发展其中，h a n 分别在1 9 7 6 年和1 9 7 7 年证明了算法的伞局收敛性和超线性收敛性，p o w e l l 在1 9 7 7 年进一步 完善了这一算法，因此又称其为w i l s o n - h a n p o w e l l 方法【1 1 近年来经过许多研究 工作者的努力，s q p 方法的理论已刁、= 断完善 2 - 5 ，并且被广泛应用于实践中 6 - 1 1 s q p 算法是按下面的方式产生迭代点列 x k l ：设z 七是当前迭代点，新的迭代 点z 岛+ l 由z k + l = z 免+ a k d k 产生这里也是某一个二次规划( q p ) 子问题的解，设 二次规划子问题是( 1 1 ) 的某个二次近似，通常具有如下形式： m i n ；( z x k ) t b k ( x z 屉) + v f ( x k ) t ( z x k ) s t a x k = b ， z 七0 其中b 七称为拟牛顿矩阵问题( 1 1 ) 的l a g r a n g e 函数 l ( x ，a ，肛) = f ( x ) + a t ( a x b ) 一# t x 则风是函数l 在钆处的二阶导数h e s s i a n 阵的某种近似，或等价地，鼠是目标 函数是，在x k 处的h e s s i a n 阵的近似s q p 算法中，q 七是在z 詹处沿方向d k 进行 某种线性搜索确定的步长，其目的是使得某个效益函数在x 岛+ 1 处的值较z 南处的 值要小使用s q p 方法求解约束最优化问题时，为获得算法的全局收敛性通常需 要假定鼠具有某种有界性，而且在二次子问题中由于仅使用了约束函数的一阶 信息，通常会产生m a r a t o 效应，破坏其超线性收敛性因此，通常需要使用某种 校正步来避免m a r a t o 效应最近发展起来的q p f r e e 算法可以克服s q p 算法的某 些缺陷，但每次需要解多个线性方程组本文拟将可行点算法与拟n e w t o n 法相结 合，提出一种实用性好的算法 一1 一 线性约束优化问题的可行m b f g s 算法 在s q p 类算法中，矩阵风的性质对算法的收敛性有着非常重要的影响一 方面，风应为l a g r a n g e 函数的h e s s i a n 阵的近似；另一方面，矩阵风能够对称 正定若矩阵风对称正定，则二次规划子问题( q p ) 一个严格凸二次规划问题 此时，该问题有唯一解而且，其求解也相对容易( 见【1 】，1 1 2 ) 为保证b 南+ 1 的正 定性，p o w e l l ( 1 9 7 8 ) 提出了一个修正的b f g s 公式，称为截断b f g s 修正公式【1 3 1 ， 其修正公式如下： s k + l 风+ 蓑一鬻 其中 k = v z l ( x k + 1 ，a 知，詹) 一v 。l ( x k ，a 詹，p 岛) ， y k = 口七饥+ ( 1 一o k ) b k s k ，0 0 1 ， 以= 杀，驻t 麓t 嚣 这里的v 茁l 为l a g r a n g e 函数关于z 的一阶导数上而的修正方式可以保证琚8 k 0 因此只要鼠正定，则b + 1 正定数值计算结果表明采用该修正公式的s q p 算法的数值效果较好，但采用该修正方式的s q p 算法的收敛性尚不清楚 1 2 求解无约束优化问题的b f g s 法和m b f g s 法 由于s q p 算法是求解无约束问题的拟牛顿算法的一种推广，本节我们来回顾 关于求解无约束问题的拟牛顿笄法 对于无约束最优化问题 m i n ，( z ) ，z r n ， ( 1 2 ) 拟牛顿算法是一类非常有效的求解方法拟牛顿算法的步骤如下：设矩阵鼠是， 在x k 处的h e s s i a n 矩阵v 2 f ( x k ) 的某种近似，满足下面的割线方程： b k + l s k2y k 这里8 k = x k + 1 一z 奄，y k = v f ( x k + 1 ) 一v f ( x k ) ，v i ( x k ) 表示函数f ( x ) 在处的 梯度。算法按如下方式产生点列 z 七) ：给定初始点x 0 ，一般地，z 知由下面的格式确 定： x k + l = z 七+ a k d k ，k = 0 ，1 ， ( 1 3 ) 一2 一- 硕士学位论文 其中o l 七由线性搜索产生，以满足： 鼠也+ v f ( x k ) = 0 ( 1 4 ) 拟n e w t o n 算法中，矩阵风+ l 通常由对风进行低秩修正产生常用的修正 公式有对称秩1 修正公式( s r l ) ，b f g s 修正公式，d f p 修正公式，p s b 修正公式 等，公式分别如下： 。b 膏s + r 。1 = b 岛+ 鱼丝二暑尝唾掣， b b f g s 一鼠+ 糍一警， b p e p = b k 十虹型掣一紫y k y t ， 。b 七p + s 。b = b 知+ 鱼竺二塾兰立堡麦专孑州一鱼警s 七s 蚕 本文主要考察b f g s 算法，即b k + 1 由修正公式( 1 5 ) 确定该修正公式的一 个重要性质是若鼠对称正定，鼠+ 1 由b f g s 的修正公式( 1 5 ) 确定，则当且仅当 y t s t 0 时，鼠+ l 对称正定 自七十年代以来，关于b f g s 收敛性理论的研究也取得了重大的进展f 1 4 之o j p o w e l l ( 1 9 7 6 ) 证明了采片jw b l f e 线性搜索的b f g s 方法用于求解凸函数极小值问 题时的全局收敛性b y r d ，n o c e d a l ( 1 9 8 9 ) 证明了采用a r m i j o 线性搜索时，b f g s 法求解凸函数极小值问题时也具有全局收敛性然而当用于非凸函数极小值问题 求解时，b f g s 法不具有全局收敛性 2 1 - 2 3 为了改进b f g s 算法的收敛性，l i f u k u s h i m a 2 4 , 2 5 】对标准的b f g s 法进行了改进，提出了一种修正的b f g s 法 m b f g s 算法，并证明了算法用于求解非凸函数极小值问题时的全局收敛性文 献【2 5 】中的m b f g s 算法鼠的修正公式也是由( 1 5 ) 确定，但y k 的定义与( 1 5 ) 中不同在m b f g s 修正公式中 s 奄2x k + l z 知， y k = 饥+ v k s k = v f ( x k + 1 ) 一v f ( x k ) + v k ( x k + l x k ) ， 其中，魄由下式确定： ( 1 6 ) = c t k l v f ( x k ) p ， 牡1 + m 卟裔2 0 ) c 叫i v m 圳p ， 其中，p 0 和c 0 是常数这样坛t s 知 0 ，即若风对称正定，则b k + 1 对称正 定值得指出的是：该条件与算法所需的线性搜索无关 求解问题( 1 2 ) 的m b f g s 算法的步骤如下： 一3 一 线性约束优化问题的可行m b f g s 算法 算法1 1 ( m b f g s 算法) 步仇给定初始点z o 舻，初始对称正定矩阵b o 形肌给定精度 0 令 k ：= 0 步j ：若i v f ( x m ) l i ，则迭代终止，得到解z 知，否则，转步2 步2 ：求线性方程组n 得到d k 转步舅 步爱由线性搜索确定步长o t 七 步彳：令z k + 1 = z 知+ q k 也若i i v f ( x k ) l l u i n f ( x k + a d k ) 可见精确线性搜索实质上是一个特殊的一维优化问题，它确定的步长0 l 七满足： v f ( ：r k + a k d k ) 1 。也= 0 即z 七+ 1 满足条件v f ( z k + 1 ) t d k = 0 精确线性搜索的计算量比较大因此在求解无 约束优化问题中使用更多的是非精确线性搜索，它， i 要求目标函数在迭代的每一 步都有一定的下降量即可，在计算上容易实现 二、非精确线性搜索 1 、a r m i j o 型线性搜索：寻找满足下面不等式的最小非负整数歹： ，( z 七+ 矿d k ) f ( x k ) + t r p j v f ( x k ) 1d k( 1 7 ) 其中o r ，p ( 0 ，1 ) 是给定的常数，那么步长q 七= - 2 、w o l f e - p o w e l l 型线性搜索：即求q 七 0 使得下面两个不等式成立 r ，( z 七+ q 知d k ) ，( z 七) - i t r l a k v f ( z 南) t d k ， 、v f ( 巩+ q 础) 丁毗盯2 v f ( z 七) t d k ， 一4 一 硕士学位论文 其中，o r l ，0 2 是给定的常数，满足0 口1 1 2 ，盯l 0 2 0 ，满足 ， i ，( z 七+ o l k d k ) s ，( z 七) + 0 1 a k v f ( x k ) t d k ， l l v f ( x k + a k d k ) t 训0 2 v f ( x 七) t d k l ， 其巾，0 以 0 2 1 。若取眈= 0 ，则有v f ( x k + 1 ) t d k = 0 故强w b l f e 型线性搜索 可看成精确线性搜索的一种推广 三、非单调线性搜索 不难发现，前面的精确线性搜索和非精确线性搜索产生的点列要求目标函数 值在每一步都是下降的，即 f ( x k + 1 ) f ( x k ) ， 我们称满足上面条件的线性搜索为单调线性搜索所谓非单调搜索则不要求对每 个k 均有f ( x k + 1 ) f ( x k ) 成立，而是给出一个更宽松的迭代条件，以期获得较大 的步长非单调线性搜索准则最早由g r i p p o ，l a m p a r i e l l o 和l u c i d i ( 见 2 6 】) 在1 9 8 6 年提出该线性搜索的条件如下： 7 ，( z 七+ q 南d 七) 。s m j a 。x ，( 七) ，( z 七一歹) + 6 q 七v f ( z 詹) t d k ( 1 8 ) 其巾，6 ( 0 ，1 ) ，m ( 0 ) = 0 ，0 m ( k ) m i n m ( k 一1 ) + 1 ，m 】，m 是一正整数当 m = 0 时，上述非单调线性搜索变为标准的a r m i j o 型线性搜索在文献| 2 6 】和 文献【2 7 1 中，g r i p p o 等详细分析了采用非单调搜索的牛顿法和截断牛顿泫的收敛 性，并给出了非单调搜索的一些特殊性质，还通过大量数值试验说明了非单调搜 索降低了搜索次数和函数计算次数1 9 9 1 年p a n i e r 和t i t s 证明了非单调搜索能避 免m a r a t o s 效应【2 剐t o i n t 2 9 】在1 9 9 6 年对求解无约束优化问题的非单调搜索进行 了研究，表明了其数值结果较稳定于是很多研究者将非单调搜索应用到求解无 约束优化问题的其他方法中，例如非单调搜索的共轭梯度法【3 0 】等l i u 等【3 1 】提 出了一种非单调w o l f e 型线性搜索准则，寻找步长因子q 七满足： m 知+ a 七d ) 。m 娥a x 朋f ( 钆一j ) + e l a 七v m 七) t d 七， v f ( x k + o t k d k ) 丁d k m a x e 2 ，1 一( q 七l i d 七i i p ) v f ( x 七) t d 知，p ( - - o o ，1 ) 这里e 1 ( 0 ，1 ) ，e 2 ( 0 ，；) ，m 是非负整数并且证明了当用于求解凸函数极 小化问题时，采用上述非单调搜索的标准b f g s 方法具有全局收敛性显然当 一5 一 线性约束优化问题的可行m b f g s 算法 m = 0 ，p = 0 时就是前面所讲的w r o l f e 型线性搜索h a n 和l i u 3 2 1 又提出了如下 非单调强w o l f e 型线性搜索准则，寻找步长冈子q 七满足： m 七+ q 豇d k ) 。m 鄂a x 肘f ( z 知一j ) + e q 七v m 詹) t 毗， l d t v f ( x k + o r k d k ) l 盯耀v f ( x k ) ，0 e 盯 1 ， 尽管使用非单调线性搜索( 1 8 ) 的算法比较稳定，但也还有一定的不足嘲 d a i 删在2 0 0 2 年指出，即使某种迭代方法用于求解强凸函数极小化问题是r 线性 收敛，也不能保证该方法有满足( 1 8 ) 的足够大的k 存在为此z h a n g 和h a g e r 在2 0 0 4 提出了一种新的非单调线性搜索，格式如下： f ( x 知+ a k d 知) g + 6 q 七v f ( x k ) t d k ， v f ( x 七+ a k d 七) t d 七a v f ( x 詹) t d 知，0 6 1 ， 其中，伉+ 1 = ( r l k q k g4 - f ( x k + 1 ) ) q k + 1 ，讯【溉叩僦。】，0 竹s n z 1 ，q 知+ 1 = 讯q 詹+ 1 ，q o = 1 ，c o = f ( x o ) 显然g 是函数值f ( x o ) ，f ( x 1 ) ，f ( x k ) 的凸组合同时我们发现讯的选择决定了线性搜索的性质当v ，吼= 0 时，上 述线性搜索就变为标准的w b l f e 或者a r m i j o 型线性搜索当v 七，讯= 1 时，则 g = a k ，其中，a k = 丽1 ，( 兢) 是函数值的平均值该算法证明了非凸函数的 全局收敛性和强凸函数的r - 线性收敛性 此外s u n 等【删也提出了一种非单调线性搜索，将非单调的g o l d s t e i n ，w b l f e 和a r m i j o 型线性搜索都包含在内，并且证明了采用该线性搜索的一些迭代法的全 局收敛性2 0 0 9 年z h o u 等( 见【3 7 】) 证明了采用一种新的非单调线性搜索的非凸 函数的m b f g s 方法的全局收敛性非单调线性搜索可以减少线性搜索的试探步， 并可获得较大步长，具有一定的优势 1 4 本文的主要贡献与章节安排 本文将求解无约束最优化问题的m b f g s 算法加以改进，将其应用到求解线 性约束优化问题中，提出一种求解线性约束问题的可行m b f g s 算法，算法结合采 用可行方向法与m b f g s 修正方式我们分别对等式约束优化问题、非负约束优化 问题和一般线性约束优化问题建立算法对于等式约束优化问题分别使用a r m i j o 线性搜索和非单调线性搜索，并证明在较弱的条件下，单调算法具有全局收敛性 和超线性收敛速度，非单调算法具有全局收敛性对于非负约束问题和线性约束 问题( 1 1 ) 建立单调算法及其全局收敛性算法的最大优点在于算法产生的点列是 可行点序列，而且算法产生的方向是目标函数的下降方向，因而可以直接利用目 一6 一 硕卜学位论文 标函数作为效益函数，可以有效地避免m 盯a t o s 效用本文还对所提出的算法进行 了数值试验结果表明本文提出的算法是求解线性约束问题的一类有效算法 本文以后各章节安排如下： 在第二章，针对等式约束优化问题提出一种可行的m b f g s 算法，算法中采用 a r m i j o 线性搜索我们还在较弱的条件下证明算法具有全局收敛性和超线性收敛 性，最后通过数值实验来验证算法的数值效果 在第三章，提出一种求解线性等式约束优化问题的可行非单调m b f g s 算法， 证明一定条件下算法的伞局收敛性，最后用数值实验来验证算法的数值效果 第四章提出一种求解非负约束优化问题的可行m b f g s 算法，并证明在较弱的 条件下采用a r m i j o 线性搜索的算法具有全局收敛性，最后通过数值实验来验证算 法的数值效果 第五章提出一种求解一般线性约束问题( 1 1 ) 下的可行m b f g s 算法，并证明 在较弱的条件下算法具有全局收敛性，最后通过数值实验米验证算法的数值效果 一7 一 线性约束优化问题的可行m b f g s 算法 第2 章求解等式约束优化问题的单调可行 m b f g s 法 考察如下线性约束最优化问题， m l n s t f ( x ) a x = b ( 2 1 ) 其中f ：钟叶r 连续可微，a 矽n ，b 矽我们假设a 行满秩，或等价地，矩 阵a a r 可逆 前面一章我们已经知道序n - - 次规划算法( s q p ) 是求解上述问题的一类有效 的算法s q p 算法是按下面的方式产生迭代点列 z 知) ，设z 七是当前迭代点，由线 性搜索确定步长o l k ，令x k + 1 = z 七+ q 七以这里以是下面二次规划( q p ) 子问题的 解： m l n 墨d ：kb k d k + v m 七) t d k ( 2 2 ) s t a d 知+ a z 七一b = 0 ， 其中鼠是对称正定的矩阵，它是v 2 厂( 钆) 的某个近似当是可行点时，( 2 2 ) 的 约束条件简化为a d k = 0 2 1 算法 本节我们结合m b f g s 法和可行方向法提出一种求解( 2 1 ) 的算法 问题( 2 1 ) 的l a g r a n g e 函数为 l ( x ，a ) = ，( z ) 一入t ( a z 一6 ) ， 这里入矽是拉格朗日乘子，由此可得( 2 1 ) 的k k t 条件为 竺r 仁3 ， 相应地，子问题( 2 2 ) 的k k t 条件为：存在拉格朗口乘予k 满足 a b 毗k d k ：+ 。v ，( z 。一a 丁天蠡2 。 c 2 4 ， 下面的定理给出了问题( 2 1 ) 与子问题( 2 2 ) 的k k t 点之间的关系 定理2 1 1 设x k 是问题偿j ，j 的可行点，巩是似剀的解，并且鼠对称正 定，则 一8 硕士学位论文 以jx k 是偿j 夕的k - k - t 点的充要条件是d k = 0 例d k 0 时，也是可行下降方向 证g q ：( 1 ) 若d k = 0 ，由( 2 4 ) 可以得到 v f ( z k ) 一a t k = 0 但x k 是问题( 2 1 ) 的可行点，即a x k = b 因此x k 是( 2 1 ) 的k k t 点 反之，若x k 是( 2 1 ) 的k k t 点，有( 2 3 ) 成立，再由( 2 4 ) 中的第一式可以 得到风d k = 0 ，但是鼠对称正定，因此，d k = 0 得证 ( 2 ) 注意到a d k = 0 ，因此以是可行方向 又由于反对称正定，因此 v ，( z 七) t d k = 一耀鼠d 七 0 ， 即d 磨是下降方向，得证 令 日c 名，= 日c z ，入，= ( v a z l x ( - 。? ) = ( v ，冀：二入) ( 2 5 ) l 则z k = ( t k ，h ) 是( 2 1 ) 的k k t 点的充要条件是h ( ) = 0 值得注意的是s q p 算法中b k 的正定性是至关重要的我们将文献【2 5 】提出 的求解无约束问题的b f g s 的修正技术推广到约束问题 令 兔= ( a a 丁) a v f ( x 七) ， 入七= 妻：芸孟1 | 日( z 知，天七) l l 0 ，初始对称正定矩阵 b o p n 令k ：= 0 步j 二由偿钏及俾砂求得毗和入詹若0 以i i 0 ，满足 v f ( x ) 一v f ( y ) i i l l l x 一矽i i ，v x ，y ( 3 ) 水平集q = x l f ( x ) f ( x o ) ) 有界 如果假设a 的条件成立，我们容易验证i i h ( x k ，入七) | i 是有界的，即存在常数 凰 0 使得 h ( x k ，a k ) l i h o ，v k 引理2 2 1 若假设a 中的条件成立，并且存在常数 0 ，使得f i h ( x 膏，k ) i i ，v k ，那么存在常数m 0 和m 0 ，使得下面得条件成立， 警m ，磐m ，v k s 二s 后鳙飘 则进一步存在正数岛，j = 1 ，2 ，3 ，使得对任意充分大的k ，至少有后2 个指标i 满足下面的条件， 鼠s t l l p 1 i i s l l ，侥| l s 1 1 2 s t b t s t 风i i s 1 1 2 1 0 ( 2 8 ) 硕士学位论文 证由弧的定义知， mm 戤8 k = 8 k + 因此，我们得到 h ( x k ，a 奄) i i s 蚕s 七， 一驴ts 融 一磊鲰 如果谨8 k o ； + i h ( x k ，a 七) i i s ：s 七，否贝u 可吾s 七i i h ( x 七，a 知) i l | | s 七f 1 2 e i i s 知1 1 2 进一步由入七的定义及v ( x ) 的l i p s c h i t z 连续性，我们得到 弧| i i l 饥i i +h ( x 七，k i ii i s 七| i + 。7 t cs k 南i i s 五乳 0 v z l ( x k + 1 ，入知) 一v z l ( x k ，a 七) i i + i h ( x k ，入七) l i s 七+ l l l s k i ( 2 l + h 0 1 | | s 七i i 因此，我们有 挚e ，鐾( 2 l + h 0 ) 2 e ，讹 s 未s 七蚝s 奄 这样我们证明了引理的第一部分类似于文献 2 5 】中引理5 1 可以完成证明 i 为方便起见，我们定义指标集 瓦= 引( 2 8 ) 成立) 引理2 2 2 设假设条件a 成立，若存在常数e 0 ，使得i i h ( x k ，入七) | | e ，v k ， 则存在正数瓦，使得对所有i 一k ，叱西成立 证若啦l ，南线性搜索准则知a ：三叱j d 不满足( 2 7 ) ，即有 ( x i + o i d i ) ，( 甄) + o d , v ( = t ) r 也 再由中值定理和假设a 中的( 2 ) ，我们可以得到存在0 i ( 0 ，1 ) ，使得 ，( 以+ q ：也)= ( z t ) + q ：v ，( a ) 丁d i + q ：( v 厂( 觑+ 晚q ：哦) 一v ( x t ) ) t d i s ，( 孔) + q ：v ，( 兢) 丁d i + ( o ：) 2 n l l d , 1 1 2 再由( 2 8 ) 及( 2 9 ) 我们得到对于所有i 霄， , 1 , n l l d , 1 1 2 一( 1 一盯) v ，( 戤) t d i = ( 1 一盯) 巧最也( 1 一o ) z ：l l d , 1 1 2 ( 2 9 ) 由上式可知q ：l ( 1 一a ) z 2 l ，因此o t i = a ：p ( 1 一a ) & p n = - 5 ，对所有i 一k i 引理2 2 3 设假设条件a 成立， z 七) 由上面的算法2 j 产生，则 + - v ( z 七) r s 七 一v f ( x 七) 丁8 k = o t 七d ：k b k d k k = o k = 0 西耀风以西侥l i 比1 1 2