（应用数学专业论文）求解大规模优化问题的几种方法.pdf

求解大规模优化同题的几种方法 摘要 本论文研究求解大规模无约束优化问题和有界约束优化问题的算法建立算 法的收敛性理论，并通过大量的数值试验验证算法的有效性 第2 章，我们在w e i ，l i ，和q i 提出的一种修正b f g s 算法基础上提出一种 求解大规模无约束问题的有限记忆b f g s 方法该算法的一个重要特点是充分利 用了目标函数值和梯度的信息我们证明该算法用于求解一致凸函数极小化问题 时具有全局收敛性数值试验表明，该算法比传统的有限记忆b f g s 方法数值结 果要好 第3 章，在d a i - l i a o 以及l i - t a a g - w e i 提出的非线性共轭梯度法的基础上， 我们分别提出两种改进的共轭梯度法所提出算法的一个非常好的性质是算法总 能产生下降的方向，该性质与算法所用的线搜索无关我们证明本章算法用于求 解非凸函数极小化问题时也具有全局收敛性并通过大量的数值试验验证算法的 数值效果，结果表明，本章所提出的算法比已有的被认为数值效果最好的标准的 p r p 方法数值结果要好 第垂5 章，利用f a c c h i n e i ，j 讧d i c e 和s o a r e s 提出的积极集估计技术，结合有 限记忆b f g s 方法提出求解大规模有界约束问题的两种算法第4 章提出的算法 充分利用了严格互补条件的特征，采用回溯策略保持算法产生的迭代点可行第 5 章的算法使用了梯度投影技术所提出的算法每次迭代可同时删除或增加多个 约束在一定条件下，我们建立算法的全局收敛性定理我们还对这两种方法进 行数值试验 第6 章，对n i 和y u a n 提出的子空间有限记忆拟牛顿法进行改进改进后的 算法更多地使用b f g s 迭代步数值试验表明改进后的算法提高了效率 第7 章，基于f a c c h i n e i ，j f i d i c e 和s o a r e s 提出的积极集判别技术，提出一 种求解大规模有界约束问题的积极集b a m i l a i - b r o w e i n 梯度方法在一定的条件 下，我们建立算法的全局收敛性本章的数值试验表明，该算法能与p r o j b f g s 和谱投影梯度算法s p g 相媲美 第8 章，我们在f a c c h i n e i ，f i s c h e r ，和k a n z o w 提出的积极集估计技术基础 上，、结合b a m i l a i - b r o w e i n 梯度方法，提出一种可用于求解退化的有界约束问题 的投影b a r z i l a i - b r o w e i n 算法我们建立该算法使用非单调搜索技术时的全局收 敛性数值试验表明，此算法比s p g 数值结果要好 本博士论文得到了国家自然科学基金的资助( 1 0 4 7 1 0 3 6 ) 关键词；大规模优化；无约束优化；共轭梯度法；有限记忆b f g s 法；投影梯度； b a r z i l a i b r o w e i n 梯度方法；全局收敛性 1 i 博士学位论文 a b s t r a c t t h ep u r p o s eo ft h et h e s i si st os t u d yn u m e r i c a lm e t h o d sf o rl a r g e - s c a l eu 1 1 - c o n s t r a i n e do p t i m i z a t i o na n db o u n dc o n s t r a i n e do p t i m i z a t i o n w ee s t a b l i s ht h e g l o b a lc o n v e r g e n c eo ft h e s em e t h o d s w ea l s ot e s tt h ep r o p o s e dm e t h o d st h r o u g h as e to fl a r g e - s c a l ep r o b l e m s i nc h a p t e r 2 ，b a s e do nt h em o d i f i e db f g sm e t h o db yw e i ，l ia n dq i ，w ep r o - p o s eal i m i t e dm e m o r yb f g sm e t h o df o r 。l a r g e - s c a l 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 g o o df e a t u r eo ft h ep r o p o s e dm e t h o di st h a tu p d a t ef o r m l l l au s et h ei n f o r m a t i o n o ft h eg r a d i e n t sa n df u n c t i o n s w ep r o v et h a tt h em e t h o di sg l o b a l l yc o n v e r g e n t i ft h eo b j e c t i v ef u n c t i o ni su n i f o r m l yc o n v e x n u m e r i c a le x p e r i m e n t si n d i c a t et h a t o u rp r o p o s e dm e t h o do u tp e r f o r m st h es t a n d a r dl i m i t e dm e m o r yb f g sa l g o r i t h m 一 i nc h a p t e r3 ，b a s e do i lt h en o n l i n e a rc o n j u g a t eg r a d i e n tm e t h o d sp r o p o s e db y d a i - l i a oa n dl i - t a n g - w e i ，r e s p e c t i v e l y , w ep r e s e n tt w on o n l i n e a rc o n j u g a t eg r a d i - e n tm e t h o d s a na t t r a c t i v ep r o p e r 锣o ft h ep r o p o s e dm e t h o d si st h a tt h ed i r e c t i o n s g e n e r a t e db yt h em e t h o d sa r ea l w a y sd e s c e n t t h i sp r o p e r t yi si n d e p e n d e n tw i t h t h el i n es e a r c hu s e d w es h o wt h a tb o t hm e t h o d sa r eg l o b a l l yc o n v e r g e n te v e n f o rn o n c o n v e xp r o b l e m s t h er e p o r t e dn u m e r i c a le x p e r i m e n t si n d i c a t et h ep e f f o r - m a n c eo ft h ep r o p o s e dm e t h o d si s 嬲w e l la st h a to ft h es t a n d a r dp r pm e t h o d i nc h a p t e r4 - 5 ，b yt h eu s eo ft h ea c t i v es e ti d e n t i f i c a t i o nt e c h n i q u ep r o - p o s e db yf a c c h i n e i ，j f i d i c e ，a n ds o a r e s ，w ep r o p o s et w oa l g o r i t h m sf o rl a r g e - s c a l e b o u n dc o n s t r a i n e do p t i m i z a t i o n t h em e t h o di nc h a p t e r4t a k e sf u l la d v a n t a g eo f t h es t r i c tc o m p l e m e n t a r ya s s u m p t i o n b yt h eu 8 eo fb a c k t r a c k i n gt e c h n i q u e t h e m e t h o dg e n e r a t e sas e q u e n c eo ff e a s i b l ei t e r a t e s t h em e t h o dg i v ei nc h a p t e r5 u s e dt h eg r a d i e n tp r o j e c t i o nt e c h n i q u e i tw a ss h o w nt h a t ，b o t ht h ep r o p o s e da l g o - r i t h m sc a na d dt oo rd r o pf r o mt h ec u r r e n te s t i m a t e da c t i v es e tm a n yc o n s t r a i n t s a te a c hs t e p u n d e rs u i t a b l ec o n d i t i o n s ，w ee s t a b l i s ht h eg l o b a lc o n v e r g e n c et h e - o r e m w ea l s ot e s tt h ep r o p o s e dm e t h o d st h r o u g has e to fb o u n dc o n s t r a i n e d o p t i m i z a t i o np r o b l e m s i nc h a p t e r6 ，t h ed e v e l o p e dm e t h o di st h em o d i f i c a t i o n so ft h es u b s p a c e l i m i t e dm e m o r yq u a s i n e w t o nm e t h o db yn ia n dy u a n a ni m p o r t a n tp r o p e r t yo f t h en e wa p p r o a c hi st h a tm o r el i m i t e dm e m o r yb f g su p d a t ea r eu s e d e x t e n s i v e n u m e r i c a lr e s u l t si n d i c a t et h em o d i f i c a t i o n sa r eb e n e l i c i a lt ot h ep e r f o r m a n c eo f t h ea l g o r i t h m i nc h a p t e r7 ，b a s e do nt h ea c t i v es e ti d e n t i f i c a t i o nt e c h n i q u eg i v e nb yf a c c h i n e i i i i 求解大规模优化问题的几种方法 j f i d i c e ，a n ds o a r e s ，w ep r o p o s e da na c t i v es e ts u b s p a c eb a r z i l a i b r o w e i ng r a d i e n t a l g o r i t h mf o rl a r g e - s c a l 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 n ，a n do b t a i ni t sg l o b a l c o n v e r g e n c e w ea l s op r e s e n ts o m en u m e r i c a le x p e r i m e n t st os h o wt h ee f f e c t i v e - n e s so ft h ep r o p o s e dm e t h o d i nc h a p t e r8 ，b a s e do nt h ea c t i v es e ti d e n t i f i c a t i o nt e c h n i q u eg i v e nb yf a c c h i n e i ， f i s c h e r ，a n dk a n z o w ，w ed e v e l o pap r o j e c t e db a r z i l a l - b r o w e i ng r a d i e n ta l g o r i t h m f o rs o l v i n gl a r g e - s c a l eb o u n dc o n s t r a i n e dd e g e n e r a t eo p t i m i z a t i o np r o b l e m s w j s h o wt h a tt h ep r o p o s e dm e t h o dw i t han o n m o n o t o n el i n es e a r c hi s 舒o b a l l yc o i l - v e r g e n t n u m e r i c a le x p e r i m e n t si n d i c a t et h a tt h ep r o p o s e dm e t h o do u tp e r f o r m e d b e t t e rt h a nt h ew e u - k n o ws p gm e t h o dd i d t h i st h e s i sw a ss u p p o r t e db yc h i n e s en s f g r a n t ( 1 0 4 7 1 0 3 6 ) k e yw o r d s ：l a r g e - s c a l eo p t i m i z a t i o n ；u n c o n s t r a i n e do p t i m i z a t i o n ；c o n - j u g a t eg r a d i e n tm e t h o d ；l i m i t e dm e m o r yb f g sm e t h o d ；p r o j e c t i o n g r a d i e n t ；b a r z i l a i - b r o w e i ng r a d i e n tm e t h o d ；g l o b a lc o n v e r g e n c e 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究 所取得的研究成果除了文中特别加以标注引用的内容外，本论文不包 含任何其他个人或集体已经发表或撰写的成果作品对本文的研究做出 重要贡献的个人和集体，均已在文中以明确方式标明本人完全意识到 本声明的法律后果由本人承担 名t 甫 d 匈日期：切1 年月日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同 意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许 论文被查阅和借阅本人授权湖南大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段 保存和汇编本学位论文 。 本学位论文属于 1 、保密口，在年解密后适用本授权书 2 、不保密彤 ( 请在以上相应方框内打”，) 作者签 导师签 日期：1 年月中日 魄秒铀乒日 博士学位论文 第1 章绪论 1 1 课题的研究意义与发展概况 本论文主要考虑用数值方法求解如下大规模非线性优化问题， m i “m ) ( 1 1 ) s t 善n 咿 、 其中，是定义在舻上的实值函数，我们称函数，为问题( 1 1 ) 的目标函数， 集合n 为问题的可行域，可行域中的点为可行点 在石油勘探、大气模拟、航空航天，数据挖掘、经济计划、工程设计、生产管理 等以及许多高尖端的科技领域经常出现未知变量越来越多。目标函数的结构异常 复杂而且约束条件数量也十分庞大的优化问题，这类问题称为。大规模问题4 ， 随着计算机的发展，有关大规模问题的观点也在与时俱进目前，一般认为维数 超过5 0 0 0 的优化问题都可以称做大规模问题 1 1 下面的图1 1 描述了对大规模问题定义随时问变化的情况【2 】t h 图1 1 大规模优化问题发展趋向图 研究求解大规模问题的具有计算简便存储需求量小的高效率的算法具有十 分重要的理论和实际意义计算机领域的发展，以及国际互联网络的出现，对求 豁拭奁vi器嚣自目目薯 求解大规模优化问题的几种方怯 饵大规模优化问题提供了方便进入2 1 世纪以来，求解大规模优化问题的算法设 计以及理论创新已经受到数学家们的广泛关注 1 1 1 大规模无约束优化 在问题( 1 1 ) 中，如果令q = 舻，则问题就变为如下的无约束优化问题， m i n ，( z ) ，z 咿( 1 2 ) 求解无约束优化问题的方法很多若，连续可微，可采取利用导数的方法，常用 的算法有牛顿法，拟牛顿类型法和共轭梯度类型法等 牛顿法是求解上述优化问题( 1 2 ) 的古老而有效的方法，相对于其它的求解 无约束问题的方法，该方法在找到最优点时需要较少的迭代次数和函数值计算次 数牛顿法的基本思想是在矿附近用二次模型做，的近似t 1 ，( z + u ) 型，( z ) + 9 ( z 七) 了1 u 4 - = i “，t g ( z ) u ，( 1 3 ) 其中9 ( z ) = v ( x ) 和g ( 一) = v 2 ( x ) 分别表示函数，在点矿的梯度和海赛 矩阵古典牛顿法具有如下的迭代形式 z + 1 = z - 4 - d ，k = 0 ，1 ，( 1 4 ) 其中d 是( 1 3 ) 右端二次函数极小值点古典牛顿法的一个显著优点是其局部二 次收敛性，而且借助于线搜索或信赖域技术，可使其具有全局收敛性当c ( x ) 正定或半正定时，驴是下面的关于d 的线性方程组的解 g ( x ) d = 一9 ( z ) ，( 1 5 ) 当g ( x ) 稀疏时，牛顿法需要较少的存储量，因而，牛顿法可用于求解当g ( z ) 稀疏时的大规模优化问题【3 】然而，牛顿法要求计算目标函数的二阶导数，并且 当迭代点远离问题( 1 2 ) 的解时，的海赛矩阵可能不正定甚至奇异，此时，方 程组( 1 3 ) 可能无解，从而导致牛顿法失败p 拟牛顿法利用目标函数值和一阶导数的信息，具有收敛速度快的优点1 3 一拟 牛顿方法用某个( 对称正定) 矩阵鼠做为v 2 f ( x ) 的近似，以避免二阶导数的计 算玩称为拟牛顿矩阵，它满足下面的拟牛顿方程 玩+ l 矿= 矿，( 1 6 ) 其中，s = t k + 1 一妒，矿= 9 + 1 一g 取+ 1 一般由对取进行低秩修正产生 b r o y d e n 族秩二修正公式是常用的一类修正公式，其形式如下； b k + l = 风一s k 万s k s 瓦k t f b k + y k y 可k r + 机h 堙 2 ( 1 7 ) 博士学位论文 其中，机是参数，收= 、s 万鼠s t ( 一i ) 当机= 0 或机= 1 时候， 上述公式分别变为著名的b f g s 或d f p 公式 拟牛顿法在求解无约束优化问题的局部收敛性和全局收敛性方面都取得了丰 硕的成果p o w e l l s 和d i x o n 7 证明了b r o y d e n 族方法在精确线搜索下的全局收 敛性b y r d i s 等证明了除d f p 方法外的b r o y d e n 凸族方法( 即机 0 ，1 ) ) 在 w o l f e 线搜索下求解凸极小化优化问题的全局收敛性 b y r d 和n o d e d a l 9 证明 了b f g s 方法在a r m i j o 线搜索下求解凸极小化优化问题的全局收敛性当目标 函数是非凸函数时，m a r e a r e n h a s t l 0 】构造反例说明b f g s 方法以及b r o y d e n 族 中某些方法在精确线搜索下对非凸极小化问题不具有全局收敛性d a i 1 1 】构造了 一个反例说明采用非精确搜索的b f g s 方法对非凸函数不具有全局收敛性近年 来，探求求解非凸问题时具有全局收敛性的拟牛顿法引起了人们的关注 l i 和 f u k u s h i m a n j a 修正了标准的b f g s 公式，提出了c b f g s 方法和m b f g s 方法 并且证明了这两种方法在a r m i j o 和w o l f e 线性搜索下对非凸极小化问题全局收 敛 拟牛顿法在每次迭代需要存储个n n 矩阵，当问题的维数非常大的时候， 需要非常大的存储空间为了克服拟牛顿法每次迭代需要存储矩阵的缺点，同时还 能保持较快的收敛速度，n o c e d a l 1 q 提出了限记忆b f g s 方法l i u 和n o e e d a l 1 目 建立了有限记忆b f g s 方法用于求一致凸函数极小化问题时的全局收敛性，并做 了大量的试验，结果表明此算法非常适合求解大规模无约束问题有限记忆b f g s 法的思想和标准的b f g s 法类似，但是因为该方法不需要存储矩阵且有较快的线 性收敛速度1 1 6 】，更适合求解大规模优化问题，其具体过程如下在每迭代步，求 解搜索方向， d = 一伊g ( x ) ， 其中日是目标函数海赛矩阵的逆近似在标准的b f g s 方法中，矩阵日是由 如下迭代形式产生 日k + l ；v 1 h k v k + p k 8 s “ 其中，v = i 一矿f 驴1 ，矿= ：忑1 在有限记忆b f g s 方法里，不存储矩阵 日，而是存储m ( 事先设定) 个向量对 s ，矿 因此在开始的前m 次迭代里与标 准的b f g s 方法等价，但是当k m 时，有限记忆b f g s 方法利用最近m 步的 信息来修正一个给定的初始正定矩阵f 一来得到矩阵日1 我们将在下一章对有 限记忆b f g s 算法做详细的介绍文献【1 7 ，1 目中的大量的数值试验表明有限记忆 b f g s 法比已有求解大规模无约束优化问题的算法需要较少的迭代和函数值计算 次数，其中包括p r p + 等b y r d ，n o c e d a l ，s c h i l a b e l 【1 q 对有限记忆b f g s 方法 的计算复杂度进行了分析，并对拟牛顿矩阵的形式进行了研究，使其更容易用来 求解约束优化问题和非线性方程组 3 求解大规模优化问题的几种方法 共轭梯度法最早是由h e s t e n e s 1 q 和s t i e f e l 2 0 l 在2 0 世纪5 0 年代初为求解线 性方程组独立提出的1 9 6 4 年，f l e t c h e r 和r e e v e s 2 1 】将此方法推广到求解非线 性极小化问题，提出求解非凸函数极小值的共轭梯度法非线性共轭梯度法的迭 代形式如下 十1 = z 。+ n 七d k ，k = 0 ，1 ，( 1 8 ) 其中，口由某种线搜索得到，搜索方向d 由下式确定 也= 博+ 矿。，葚 ( 1 r 9 ) 其中，仇是一个参数不同的凤对应不同的非线性共轭梯度方法著名的有1 9 5 2 年的h e s t e n e s 和s t i e f e l 2 提出的h s 方法，1 9 6 4 年由f l e t c h e r 和r e e v e s 【2 3 1 提 出的f r 方法，1 9 6 9 年p o l a k ，r i b i r e 和p o l y a k t m 提出的p r p 方法，1 9 8 7 年 f l e t c h e r 【2 5 1 提出的c d 方法，1 9 9 1 年l i u 和s t o r e y 2 6 1 提出的l s 方法，1 9 9 9 年 d a i 和y h a n 鲫提出的d y 方法这些算法中，参数胪的形式如下： 胪= 辫，藤丽g k t y k - 1 ，1 3 s = 等， 船7 = g 斋，露。一鬈，酽一等， 非线性共轭梯度法的表达形式简单，易于编程，且只需要计算和存储目标函数的 梯度值，因而非常适合求解大规模优化问题 非线性共轭梯度法的收敛j 陛分析的早期工作由f l e t c h e r ，p o w e u ，b e a l e 等人完 成，这段时期的工作主要集中在精确线搜索下目标函数是凸函数的全局收敛性的 分析上【2 8 】近年来，由于许多大规模问题的出现，特别是g i l b e r t 和n o c e d m l 2 9 1 给出p r p + 方法对非凸函数的全局收敛性结果，以及p r p + 方法良好的数值表 现，使得非线性共轭梯度法的研究再次受到了关注【2 75 叫其中比较成功的是有 g r i p p o 和l u c i d i s s 基于标准的p r p 公式结合新的a m i j o 型线搜索给出p r p 方 法的全局收敛性，d a i 和y i l a n 【3 1 1 提出的杂交共轭梯度法上述算法产生方向的 下降性依赖于所采用的线搜索技术最近，h a g e r 和z h a n g 4 2 , 删提出提出一种下 降的共轭梯度法，该算法总产生充分下降方向，该下降方向与所采用的线搜索无 关 z h a n g ，z h o u 和l i 呻，4 提出了一种新的三项共轭梯度法，也具有下降性 关于共轭梯度法的其它方面的工作，如t 预条件共轭梯度法，基于剖线方程的共 轭梯度法，杂交共轭梯度法等，见文献h a g e r ，z h a n g1 5 l 】，g i l l ，m u r r y , w r i g h t 【5 2 】， f l e t c h e r 嘲以及戴蜮虹和袁亚湘的专著【2 8 】 除上面的有限记忆b f g s 法，非线性共轭梯度法可求解大规模无约束同题 外，b a r z i l a i 和b o n l r 咖酬在1 9 8 8 年提出一种求解大规模无约束优化问题的梯 4 博士学位论文 度型方法该方法迭代形式为 z + 1 = z 一a k g ( z ) ，( 1 1 0 ) 其中参数”有如下两种选择 a = 万s k - 丽1 ) t q 产k - 1 ，a ；= 酽( , k - 硬1 ) t y 芦k - 1 ，( 1 1 1 ) b a r z i l a i - b o r w e i n “ 方法结构非常简单，存储量与共轭梯度法相当，而且不需要线 搜索来决定步长b b 方法形式上可认为与最速下降法一致，但参数舻的意义 与线搜索产生步长的最速下降法有重大差异 由于不进行线搜索，因此b b 梯度方法并不能保证目标函数单调下降，但在 一定的条件下该算法具有很好的收敛性对二维严格凸二次函数，b a r z i l a i 和 b o r w e i n l “ 证明了该方法具有r 一超线性收敛性，p 。a y d a n l 5 5 建立了在此情况 下的全局收敛性对于3 维的严格凸二次函数，d a i 和f l e t c h e r ”l 建立了b b 方 法的r 一超线性收敛性对于n 维的严格凸二次函数，d a i 和l i a o ：5 7 证明了b b 方法的线性收敛性，r a y d a n s s 得到了在此情况下的全局收敛性结果借助于非 单调线搜索例，r a y d a n l a o 把b b 方法应用到求解非凸极小化问题中文献刚中 的大量数值试验表明，使用非单调线搜索的b b 方法的数值表现可以与p r p + 共 轭梯度方法相媲美有关b b 方法的在求解无约束优化问题方面的收敛性研究和 算法的改进等工作可以参见文献 o l - 叫 有关求解大规模无约束优化问题其它算法的研究参见r o m a 【1 1 ，g o u l d ，o r b a n ， t o i n t ，n o c e d a l 【邸】等 1 1 2 大规模有界约束优化 在问题( 1 1 ) 中，如果取q 是一个矩形区域，那么问题就变为如下简单的有 界约束问题t i n i “，( 。) ( 1 1 2 、 s t i z t 1 工程和科学计算中许多的问题可以转化成问题( 1 1 2 ) 的形式 5 z , 0 7 , 删此外，有界 约束优化算法经常做为求解一般约束优化问题的增广l a g r a n g i a n 方法和罚函数方 法的子算法眇_ 7 ”因此研究求解有界约束问题( 1 1 2 ) 的实用算法具有重要的实 际意义 称点虿是问题( 1 1 2 ) 的稳定点，若其满足 i l = 夏净v 0 ， k m 时，矩阵h k + 1 由标准的b f g s 修 正利用当前点前m 次的信息修正初始矩阵凰m 次得到，即 m + l = 昭风k - i - p k s s = 曙【v 。, t l i l k l k l + m l s 一1 s 一1 7 】k - pp k s s r = 【曙幢。】风一m 陬一+ 1 吲 b p k m + l 【v h , t 吧。+ 2 矽一+ 1 ( s “卅1 ) f k 一。+ 2 k 一1 】 上 + p k s k s ”f 2 1 0 ) 1 2 博士学位论文 其中k 一。+ 1 = b 有限记忆b f g s 方法因其不需要存储矩阵更适合求解大规模优化问题在一 定条件下，有限记忆b f g s 方法用于求解凸函数极小化问题时具有全局收敛性【 本节的主要目的就是结合【1 4 】和【8 8 】的工作提出一种求解大规模无约束问题的有 限记忆b f g s 方法 用9 ：来代替( 2 1 0 ) 中的玑得到如下的有限记忆b f g s 校正公式， h k + l = f 嵋t k 乙+ 1 h k m + l 【略1 w 】 + 虞一m + l i v , t 1 睢2 t 8 一”1 ( s 胁+ 1 ) t 【睡。+ 2 睢1 】 上 + 壤s s ， ( 2 1 1 ) 其中虞= ；两1 ，嵋= ，一成口：s p ，h k 一卅l = 曰0 结合w o l f e - p o w e l l 线搜索，下面给出本文有限记忆b f g s ( n - l b f g s - t ) 算法 的步骤 算法2 3 1 步0 取初始点护g p 和一个对称正定矩阵风给定常数0 j 0 令= 0 步1 若1 1 9 0 = 0 ，算法终止 步2 由d = 一h k g 计算搜索方向以 步3 确定口k 满足下面的w o l f e - p o w e l l 条件 f ( x + a k d ) f ( x 。) + 缸女g 1 驴 ( 2 1 2 ) 和 g k + l r d k2a g k t d k ( 2 1 3 ) 令z 1 = 一+ 口k d 步4 设m k = m i n k + 1 ，m ) ，利用 ，：，九 叁一。+ 1 ，通过式( 2 1 1 ) 校正凰 ”k 次得矩阵f k + 1 步5 令k = + 1 转步1 上面的有限记忆b f g s 算法与标准的有限记忆b f g s 算法的主要区别在于 对f k 的修正公式 2 4收敛性分析 本节，我们证明算法2 3 1 对一致凸函数的全局收敛性，并且证明收敛速度是 r - 线性的 1 3 求解大规模优化问题的几种方法 令b k = 正誓1 ，则算法2 3 1 可等价地写成如下的算法t 算法2 4 1 步0 取初始点z o g 妒和一个对称正定矩阵岛给定常数0 j 0 令k = 0 步1 若1 1 9 0 = 0 ，算法终止 步2 由d = 一目i l g 来计算搜索方向扩 步3 确定帆满足 和 ，0 + 口d k ) f ( x ) + 6 a k g k t d k g k + 1 7 d k 盯9 k t d k ( 2 1 4 ) ( 2 1 5 ) 令i + 1 = z + q k d k 步4 设m k = m i a k + 1 ，m 利用 s ，以，九) 坠i 一。+ 1 ，由下式校正初始b om k 次得到矩阵风+ 1 。b 。c l + 1 ) 趔一搿+ 筹8 ， ( 2 1 6 ) s d i s ： 其中s i = 一十1 一一，越= 暑，+ s 。，对所有的k 有b 一“+ 1 ) = 岛 步5 设k = k + 1 转步1 为了建立算法2 4 1 ( 或等价地算法2 3 1 ) 的收敛性，我们做如下假设 假设2 4 1 水平集n = 扛i f ( x ) ，( z o ) ) 包含在闭凸集d 内 假设2 4 2 目标函数，( z ) 在d 上一致凸，即，存在正常数尬和m 2 使得 m 11 1 z t 2 z t c ( x ) z m 2l l z l l 2 ( 2 1 7 ) 对所有的z g p 和z d 成立 由于目标函数，( z ) 在凸集d 上二次连续可微，因此存在常数l 使得 1 1 9 ( z ) 一g ( y ) l i l 0 z 一引f ，v 墨y d ( 2 1 8 ) 在本章的余下部分，若无特别说明，我们总设假设条件2 4 1 2 4 2 成立 定理2 4 1 算法2 4 1 产生的点列 。k ) 收敛于问题( 2 1 ) 的极值点矿且存在常 数0 1 0 使得 ，( z h l ) 一，( z + ) s ( 1 一c c o s 2 以) ( ，0 ) 一，( z 。) ) 由式( 2 2 6 ) 可知( 2 1 9 ) 成立 又由( 2 1 7 ) 可得 去 n i i z 一z + 1 1 2 一， 上式结合( 2 1 9 ) 得到i i 铲一矿i i 1 a 2 ( f o 一广) m 】”，故迭代序列 扩 收敛于 聚点矿的速度是r - 线性的证毕 定理2 4 1 表明序列 扩) 收敛于矿，而且收敛速度是线性的 2 5 迭代矩阵的表示 本节，我们描述拟牛顿矩阵巩和风的重新表示，这种表示方法可以使得 有限记忆方法在求解大规模约束优化问题中被方便地应用首先注意到有限记忆 b f g s 迭代( 2 i i ) 可重新写为 严扎t 龇一卅时扛s 。g 妻- + 。唿t 苦踽， ( 2 z ，) =m 十i 一 其中 v i , k = f i ( 卜鲤蛘) ( 2 2 8 ) 设nxk 矩阵鼠和k & = 【8 k - “+ 1 ，s 】，k = 破一”“，确，( 2 2 9 ) 用札表示” x m k 对角矩阵 a k = d i a g a k m k + l ，a k 】( 2 3 0 ) 我们首先给出如下关于投影矩阵而且在后面的部分经常使用的一个引理 1 6 博士学位论文 引理2 5 1 式( 2 2 7 ) 中的k 个投影矩阵的乘积可以写成如下的形式 u 一。州，k = 卜圪何1 算 ( 2 3 1 ) 其中w = k + s k a k ，凡是翊r 足义的m k ”k 矩阵 c 砒。= 8 乙。髻一押篡冀 仁s z ， 证明使用数学归纳法首先对k m k + 1 式子( 2 3 1 ) 显然是成立，因为这时