（计算数学专业论文）大型稀疏极大极小问题的数值方法.pdf

大连理工大学博士学位论文 摘要 本文研究求解大型稀疏极大极小问题的对称相容分组修正n e w t o n 型方法、不精确 牛顿法和不精确对称相容分组修正n e w t o n 型方法取得的主要结果可概括如下： 1 在第2 章，我们先从光滑问题入手，对大型稀疏光滑无约束优化问题的几种对称相 容分组修正n e w t o n 型法和对称相容分组修正c h o l e s k y 因子算法作了一些改进，并给 出不精确的分组修正n e w t o n 型方法，证明了它们的g 超线性收敛性和全局收敛性 并给出r 一敛速估计 2 在第3 章，我们研究稀疏的极大极小问题的对称相容分组修正算法由于极大极小 问题涉及多个函数，每个函数的h e s s e 矩阵的稀疏结构不一定相同，每个函数需要采 用不同的分组策略，因而有不同的换元周期，我们在不假设严格互补的条件下证明了 分组修正算法的g - 超线性收敛性和全局收敛性，并给出，- 敛速估计此外，还基于 修改的c h o l e s k y 因子分解提出了非凸极大极小问题的有效算法 3 在第4 章，我们研究求解极大极小问题的不精确n e w t o n 法在求解极大极小问题的 不精确n e w t o n 法中，每步迭代需要近似求解一个二次极大极小问题，而求解二次极 大极小问题则需要近似求解一系列特殊的线性方程组我们给出二次极大极小子问 题和线性方程组求解精度的控制准则，在保持n e w t o n 法的超线性收敛性的前提下尽 可能减少子问题求解的计算量在不假设严格互补的条件下，证明了算法的局部超线 性收敛性和全局收敛性，并给出q 收敛阶 4 在第5 章，我们给出求解大型稀疏的极大极小问题的不精确对称相容分组修正算法 我们给出二次极大极小子问题和线性方程组求解精度的控制准则，在保持分组修正 算法的超线性收敛性的前提下尽可能减少子问题求解的计算量在不假设严格互补 的条件下，证明了算法的局部超线性收敛性和全局收敛性，并给出其收敛阶 对所给出的算法，都用c c + + 或m a t l a b 语言编程实现，并通过数值实验与已有的 算法进行了比较数值结果表明这些方法足有效的 关键词：极大极小问题；稀疏；分组修正算法；相容分组；不精确n e w t o n 型法 a b s t r a c t i nt h et h e s i s ，s y m m e t r i c a l l yc o n s i s t e n tg r o u p - w i s eu p d a t i n gn e w t o n 1 i k em e t h o d s ，i n e x a c t n e w t o nm e t h o d sa n di n e x a c ts y m m e t r i c a l l yc o n s i s t e n tg r o u p - w i s eu p d a t i n gn e w t o n l i k em e t h - o d sf o rl a r g es c a l es p a r s em i n i m a xp r o b l e m sa r es t u d i e d m a i nr e s u l t so b t a i n e da r es k e t c h e da s f o l l o w s ： 1 i nc h a p t e r2 ，w eb e g i nw i t hs m o o t hp r o b l e m sa n ds t u d ys o m ei m p r o v e dv e r s i o n so fs y m m e t - r i c a l l yc o n s i s t e n tg r o u p - w i s eu p d a t i n gn e w t o n l i k em e t h o d sa n ds y m m e t r i c a l l yc o n s i s t e n t g r o u p - w i s eu p d a t i n gc h o l e s k yf a c t o rt e c h n i q u e s a n da ni n e x a c ts y m m e t r i c a l l yc o n s i s t e n t g r o u p - w i s eu p d a t i n gn e w t o n - l i k em e t h o di sp r e s e n t e d l o c a lq - s u p e r l i n e a rc o n v e r g e n c ea n d g l o b a lc o n v e r g e n c ea r ep r o v e na n dr - c o n v e r g e n c er a t e so ft h e ma r ee s t i m a t e d 2 i nc h a p t e r3 ，as y m m e t r i c a l l yc o n s i s t e n tg r o u p - w i s eu p d a t i n gm e t h o df o rs p a r s em i n i m a x p r o b l e m si sg i v e n b e c a u s et h eo b j e c t i v ec o n c e r n smf u n c t i o n sw i t hh e s s i a n si nd i f f e r e n t s p a r s es t r u c t u r e s ，d i f f e r e n tg r o u p i a gs t r a t e g i e sf o rt h eh e s s i a n sm u s tb et a k e n ，a n dh e n c e p e r i o d so ft h eh e s s i a n su p d a t i n gm a yb ed i f f e r e n t w i t h o u ts t r i c tc o m p l e m e n t a r i t y , q s u p e r l i n e a rl o c a lc o n v e r g e n c ea n dg l o b a lc o n v e r g e n c ea r ep r o v e n ，a n da nr c o n v e r g e n c er a t e i se s t i m a t e d i na d d i t i o n e f f i c i e n tm e t h o d sb a s e do i lt h em o d i f i e dc h o l e s k yf a c t o r i z a t i o n a r eg i v e nt os o l v et h en o n c o n v e xm i n i m a xp r o b l e m s 3 i nc h a p t e r4 ，i n e x a c tn e w t o nm e t h o d sf o rt h em i n i m a xp r o b l e m sa r es t u d i e d i ne a c h i t e r a t i o n ，aq u a d r a t i cm i n i m a xp r o b l e mn e e d st ob ea p p r o x i m a t e l ys o l v e di n e x a c t l yb y s o l v i n gas e q u e n c eo fs p e c i a ll i n e a re q u a t i o ns y s t e m s p r e c i s i o nc o n t r o l l i n gc r i t e r i o n sf o r t h eb o t hs t a g e sa r eg i v e nt op r e s e r v et h es u p e r l i n e a rc o n v e r g e n c ea n dt o 同9 , y ec o m p u t a t i o n o f s o l v i n gt h es u b p r o b l e m s w i t h o u ts t r i c tc o m p l e m e n t a r i t y , l o c a lq - s u p e r l i n e a rc o n v e r g e n c e a n dg l o b a lc o n v e r g e n c ea r ep r o v e na n dt h eq - c o n v e r g e n c er a t ei se s t i m a t e d 4 i nc h a p t e r5 ，i n e x a c ts y m m e t r i c a l l yc o n s i s t e n tg r o u p - w i s eu p d a t i n gm e t h o d sf o rl a r g es c a l e s p a r s em i n i m a xp r o b l e m sa r es t u d i e d p r e c i s i o nc o n t r o l l i n gc r i t e r i o n sf o rt h eb o t hs t a g e s a r eg i v e nt op r e s e r v et h es u p e r l i n e a rc o n v e r g e n c ea n dt os a v ec o m p u t a t i o no fs o l v i n gt h e s u b p r o b l e m s w i t h o u ts t r i c tc o m p l e m e n t a r i t y , l o c a lq - s u p e r l i n e a rc o n v e r g e n c ea n dg l o b a l c o n v e r g e n c ea r ep r o v e na n dt h ec o n v e r g e n c er a t ei se s t i m a t e d a l la l g o r i t h m sp r o p o s e di nt h i sp a p e ra r ei m p l e m e n t e di nc c + + o rm a t l a bs y s t e m sa n d n u m e r i c a lt e s t sa r ed o n e n u m e r i c a lr e s u l t ss h o w st h a tt h e s em e t h o d sa r ee f f i c i e n t k e y w o r d s ：m i n i m a xp r o b l e m s ；s p a r s i t y ；g r o u p - w i s eu p d a t i n ga l g o r i t h m ；c o n s i s t e n tg r o u p i n g ； i n e x a c tn e w t o n l i k em e t h o d i i 独创性说明 作者郑重声明：本博士学位论文是我个人在导师指导下进行的研究工作 及取得研究成果尽我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理工大学 或者其他单位的学位或证书所使用过的材料与我一同工作的同志对本研究 所做的贡献均已在论文中做了明确的说明并表示了谢意 作者签名：日期： 伊艿, i t 大连理工大学博士学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解。大连理工大学硕士、博士学位论文版权使用 规定”，同意大连理工大学保留并向国家有关部门或机构送交学位论文的复印件和电子 版，允许论文被查阅和借阅本人授权大连理工大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇编学位论 文 保密口，在年解密后适用本授权书 本学位论文属于 不保密口 ( 请在以上方框内打”，) 作者签名t 导师签名t 硷& 年! 月巴日 1 0 5 大连理工大学博士学位论文 1 绪论 本章对求解大型稀疏极大极小问题的几种方法进行扼要的综述，给出本文的一些预 备知识及记号说明，并介绍一下本文的主要工作 1 1 大型稀疏极大极小问题 最优化问题足现代应用数学和计算数学研究的热点之一，它讨论决策问题的最佳选 择之特征，构造寻求最佳解的计算方法，研究这些计算方法的理论性质及实际计算表现 数学上就足研究在一定条件下函数的最大或最小值是否存在、最大值或最小值点集合的性 质以及如何求解它们等问题最优化方法起源于十分古老的极值问题，在d a n t z i g ( 1 9 4 7 ) 9 】 提出求解一般线性规划问题的单纯形法之后，最优化方法开始成为一门独立的学科，并 得到了飞速的发展现在，求解线性规划、非线性规划、非光滑规划、随机规划、多目标 规划、几何规划以及整数规划等各种最优化问题的理论的研究发展迅速，新方法不断涌 现，实际应用e t 益广泛伴随着计算机的高速发展和优化计算方法的进步，产生了规模 越来越大的优化问题，即大型( 稀疏) 问题，并且不断要求又准又快地得到解决因为最 优化问题广泛见于经济计划、工程设计、生产过程的自动化、人才管理，交通运输、国 防、军事、投资决策等重要领域，它已受到政府部门、科研机构和产业部门的高度重视 最优化在决策科学和物理系统分析中也是一个重要工具为了使用它，我们必须首先确 定某个目标，这个目标可能是利润、时间、势能或用一个数代表的量或量的组合这个 目标依赖于系统的某些性质，称之为变量或未知量我们的目的就足要找优化这个目标 的变量的值常常这些变量足有约束的，例如，在贷款中的利息率不能为负 最优化问题的一般形式为： 。r a ，i 。n 。f ( z ) s t 笔 三；薹：。i e z c , ( 1 - ) 这里和z 分别为等式约束的指标集和不等式约束的指标集，色是约束函数问题( 1 1 1 ) 可以按照目标函数和约束的属性分为线性、非线性和凸性；按变量数分为大型和小型； 按函数的光滑性( 可微或不可微) 分为光滑和非光滑等等，当然还可以按照有无约束分为 无约束优化和约束优化无约束优化问题直接出现在许多实际应用中，约束优化问题来 自包括变量有明显约束的模型无约束优化问题也来自约束优化问题的转换，即约束部 分用罚项代替放在目标函数中以妨碍违反约束 求解光滑无约束优化问题的常用方法有牛顿法、共轭梯度法、拟牛顿法等；而求解光 滑约束优化问题的常用方法罚函数法，可行方向法、序列二次规划法、信赖域法等等 大型稀疏极大极小问题的数值方法 在拟牛顿法和n e w t o n 型法的研究中一个重要的课题是对于大型问题的适用性，解决这 一问题的关键是寻找保持稀疏性的算法，拟牛顿法以各种修正矩阵去近似代替h e s s e 阵 或其逆阵，但这些修正算法往往并无原稀疏结构的传递性，需要对修正矩阵作较为复杂 的改造，冯果忱、李光烨等人( 【1 4 ，1 5 ，1 6 ，2 9 ，3 0 】) 给出了一些保持对称性和稀疏性的行列 修正拟n e w t o n 法和换元修正n e w t o n 型算法，具有超线性收敛性，并且有介于1 和2 之 间收敛阶，算法简单易行，是解具有稀疏性的光滑无约束优化问题的一类有效方法 非光滑函数是指不作可微要求的函数，所以也称为不可微函数在优化问题( 1 1 1 ) 中，i ( x ) 和q 中有至少一个足变量z 的非线性函数时，问题( 1 1 1 ) 称为非线性规划； 又若在非线性规划问题( 1 1 1 ) 中，( x ) 和q 中有一个是变量z 的非光滑函数时，问题 ( 1 1 1 ) 称为非光滑优化由于带约束条件的非光滑优化问题可以通过添加一个罚项代替 约束函数到目标函数上将其变为无约束非光滑优化问题，故无约束非光滑优化问题的理 论和算法是最基本的问题现考虑无约束非光滑优化问题( 1 1 1 ) ，即= 毋( 空集) 和z = 毋 且，( z ) 是定义在b a n a c h 空间的不可微函数假定函数f ( x ) 满足l i p s c h i t z 条件易知矿 是问题( 1 1 1 ) 的解则必有 0 o f ( x + ) ，( 1 1 2 ) 其中次梯度o ( x ) 的定义见第二节( 1 2 1 ) 式称满足0 o ( x ) 的点z 为问题( 1 1 1 ) 的 稳定点非光滑优化问题( 1 1 1 ) 的求解，如果利用解可微问题的方法( 假定在每个迭代 点上f ( x ) 都可微) 有两个很大的难点第一是算法的终止条件不易给出可知，当z 充 分靠近一连续可微函数f ( x ) 的极小点时，i i v f ( x ) l i 一定非常小，所以光滑的无约束优化 方法的终止判别条件常常是 j i v f ( x ) l l ( 1 1 3 ) 但对于非光滑函数，( z ) ，并没有类似的结果另一个难点是由w o l f e ( 1 9 7 5 ) 6 5 l 指出的“折 线收敛于非解”现象，也就是说，当f ( x ) 是不可微函数时，用精确搜索下的最速下降法 求解( 1 1 1 ) 可能产生一收敛于非稳定点的点列 z 由于这些困难，通常的求解光滑优 化问题的方法在非光滑情形不再适用了解非光滑优化的常用方法有次梯度法、割平面 法、捆集法、信赖域法等【7 0 】 本文研究如下的无约束极大极小问题； m 胛i n 妒( x ) ， 而 妒( z ) = 1 罂擎，( z ) ，岛= 1 ，2 ，m ) ， ，t ” 其中tf j ：舻一r 是舻上的二次连续可微函数 ( 1 1 4 ) ( 1 1 5 ) 极大极小问题是数学规划中的一类典型非光滑优化问题，在工程优化设计、电子线 路优化设计、计算机辅助设计、最优控制及对策论中有着广泛的应用，很多实际问题都 可以建成极大极小问题的数学模氆，例如菲线性l o o 、l l 拟合问题、解不等式组、应用 不可微罚函数法解非线性规划问题、内点法解非线性规划问题的初始可行解的确定以及 出现在求解半无限极大极小问题的算法中的子问题等，某些特殊类型的互补问题及变分 不等式问题也能转化成等价的极大极小问题，通过求解转化后的极大极小问题而得到原 2 大连理工大学博士学位论文 问题的解，另外多目标规划的求解方法如极大极小法和增量系数法，也屉通过将多目标 转化为单目标的极大极小问题的方法来求解，因此研究极大极小问题的有效解法，具有 十分重要的意义 可以用解非光滑优化的一般方法，如次梯度法、割平面法、捆集法、信赖域法等，来 求解极大极小问题，但针对该问题设计特殊方法足更好的选择目前，有许多方法求解极 大极小问题( 1 1 4 ) ，一般说来，下面这三类方法较为常见第一类方法是把问题( 1 1 4 ) 转化为约束光滑优化问题； m i n 口，s t p ( x ) 一 0 ，j k ， ( 1 1 6 ) 从而按大家所熟悉的方法如可行方向法【4 9 】、序列线性规划方法 2 2 】、序列二次规划方 法 2 5 ，4 1 】、内点法【6 0 】、非光滑方程 1 8 ，3 7 】等求解比如，v a r d i 6 1 】使用某些松弛变 量去处理( 1 1 6 ) 的不等式约束，然后利用信赖域策略只去求解等式约束最小化问题；文 【3 8 】则采用可行原内点法处理( 1 1 6 ) 来求解大型稀疏极大极小问题；文【2 2 】足对( 1 1 6 ) 采用序列线性规划方法求解虽然这些方法克服了由于妒( z ) 的非光滑性造成的困难，但 一般难以获得较高的效率，比如可行方向法仅为线性收敛的，而序列二次规划方法也可 能会产生m a r o t o s 效应从而破坏超线性收敛性；第二类方法足使用参数光滑函数 1 f 一 1 f p ( z ) = 言i n e x p p f j ( x ) 】 l j kj 作为目标函数变成一个简单易行的光滑无约束优化问题求解因为 0 昂( z ) 一，( z ) ( x p ) i n m ， 故昂( z ) 一，( z ) ，p 一。o ( 【3 3 ，3 4 ，5 0 ，6 7 】) 但随着p 的增大，耳( z ) 的h e s s e 阵变得接近奇 异，这为找到最优解带来困难，因此，一般需把该方法与其它方法结合使用；第三类方法 足一种搜索方向算法，也就是把问题( 1 1 4 ) 直接看成无约束非光滑优化问题( 由于t f ，( z ) 非光滑) 【4 6 ，4 7 ，4 8 】，文【4 5 ，叫提出了一种直接求解极大极小问题的p p p 算法，但这种 方法仅为线性收敛的；文【4 8 】给出了直接求解极大极小问题的二阶收敛的n e w t o n 法， 但是为获得二阶收敛速度要求在d a n s k i n 点【4 8 】处满足严格互补条件，这个条件太强， 很多实际问题尤其是半无限极大极小问题的离散化不满足该条件；文 4 7 】给出另外一种 n e w t o n 法，在不假设严格互补的条件下，证明了它的超线性( 3 2 阶) 收敛性张淑婷等 人【6 8 ，6 9 ，7 1 ，7 2 ，7 3 】给出使用拟n e w t o n 法或换元修正n e w t o n 型法等来精确或不精确求 解( 1 1 4 ) 其中拟n e w t o n 法继承了光滑优化问题的拟n e w t o n 法不需要计算目标函数的 h e s s e 阵的优点，并且在不假设严格互补的条件下证明了算法具有局部超线性收敛速度及 全局收敛性由于算法在每步迭代中需要求解一个二次函数极大极小子问题，不能象光 滑情形的拟n e w t o n 方程那样利用秩2 修正性质用较少的计算量求解，因此不能完全体 现拟n e w t o n 法的优越性为了提高拟n e w t o n 法的计算效率，又给出一种有限极大极小 问题的不精确拟n e w t o n 法，并给出子问题求解精度的控制准则，证明在这样的准则下， 不精确拟n e w t o n 法同样可以具有局部超线性收敛性和全局收敛性对于她给出的有限 极大极小问题的行列修正法和换元修正n e w t o n 型法，在不假设严格互补的条件下她证 明了这些算法的局部超线性收敛性( 丁阶，其中丁为2 俨+ 1 2 t “一1 = 0 的唯一正根) 以及 3 大型稀疏极大极小问题的数值方法 全局收敛性此时，要求修正矩阵满足的条件是自然可以满足的与光滑情形一样，换 元修正n e w t o n 型法具有可以保持迭代矩阵的稀疏性和对称性的优点，因此更适用于大 型稀疏问题 既然换元修正n e w t o n 型算法具有这样好的特性，怎样有效利用迭代矩阵的稀疏性 和对称性来计算这些h e s s e 阵呢? 那些好的收敛性质足否还能保持呢? 收敛阶又足怎样 的呢? 另外，对于第三类方法来说，当远离最优点时，若某些h e s s e 阵不正定的话，搜索 方向可能不是下降方向，那又应该使用哪种方法才能保证下降? 对不精确n e w t o n 法， d e m b oe t a 1 i 0 ，1 1 】在用到光滑无约束优化中时证明了这种方法通过适当选择强迫序列能 达到超线性收敛性，甚至能达到二次收敛性，同时节省了求解的计算量但当使用这种 方法求解极大极小问题时，因为解n e w t o n 型方程组之后还要求解一个二次子f 训嚣，那么 怎样选择强迫序列通过有效控制子问题的精度在保持一个比较好的收敛性质的同时尽量 减少求解子问题的计算量呢? 本文着重就这些问题进行研究 下面先来介绍一下第三类方法：令是f j ( x ) 在点z 的二阶导数h j ( x ) 的某个正定 近似，令 矽( z ，s ) = 罂擎 ，( z ) + ( 9 j ( z ) ，s ) + ( 1 2 ) ( s ，矽s ) ) ， ( 1 1 7 ) j 亡j m 其中。矿( z ) 是户在z 的梯度，( ) 足内积，则 妒( z + ) 一妒( z ) 巴孕x 厂( z ) + ( 矿( z ) ，z + 一z ) + ( 1 2 ) ( x + 一z ，b j ( x + 一z ) ) ) j t i m = 1 ；f ，( z ，z + 一z ) 一妒( z ) ， ( 1 1 8 ) 其中f j ( z ) = f j ( x ) 一矽( z ) 如同光滑函数的n e w t o n 法，对最小化t f ，( z ) 的搜索方向司由 ( 1 1 8 ) 右边关于z + 极小化得到，即解 眯r a i 舻n 妒圹帅卜玳m i o i 筹觏卅 + 丢 ， c 9 ， 其中 = p r ”：薹= 1 ，。，助k ) ， 这是因为一组标量的最大值等于它们凸包的最大值求解搜索方向问题的其中一种方法 是应用投影梯度法或约束n e w t o n 法到它的对偶上现定义最优性函数p ( ) 和搜索方向 = 耀魏痧( z ， ) 一妒( z ) 2 m i nj m m a x f j ( z ) + ( z ) ， ) + ( 1 2 ) ( ，b j ) ) 2 蜒m 俨i nm p a 乞x ( # , h ) ， 4 ( 1 1 1 0 ) ( 1 1 1 1 ) 大连理工大学博士学位论文 ( z ) 2 a r g ，啦妒( z ， ) 一妒( z ) - a r g 删, m ! n 。m 脚a x 咖( # ， ) - ( 1 1 1 2 ) 其中 cp，=萎三户cz，+三1 c t 3 ， ( p ， ) = 户( z ) + ( 矿( z ) ， ) + 互( ，) ( 1 1 1 3 ) lt 而且由 4 6 】的推论5 5 3 ( 见本章第二节的定理1 4 ) ，我们有 耀恐搿咖( p ， ) = m p a 占xn m 刨i n 。妒( p , h ) = 一m p i n 一耀器( p ， ) ) ( 1 1 1 4 ) 故这个问题的对偶是： r a “i nt ，( p ) ， ( 1 1 1 5 ) ，似，= 一薹户c z ，+ 丢 当然，( i i 1 5 ) 足一个带线性等式和非负约束的非线性光滑约束优化问题尽管前面已介 绍了求解的多种方法，但解( 1 1 1 5 ) 最常用且非常有效的方法是转化为序列二次规划方 法( s q p ) ，即给定初始点x 0 后，通过在第七( 1 ) 次外迭代并给定胀，0 作为初始内迭代之 后，多次从当前内迭代点胀i 解二次规划 啦 ( v j ( 胀，t ) ，p p 七，t ) + ( i 2 ) 似一p 七再( 纵，t ) 一鲰，t ) ) ( 1 1 1 6 ) 得到下一个迭代点p 七，件1 ，最后得到最小值点p 七，。作为新的外迭代点p 七+ 1 从而得到h 及x k ，如此循环迭代，直到收敛，这里v j ( u ，i ) 和j 五( u k ，t ) 分别指j ( u k ，t ) 的梯度和h e s s e 阵 注意；如果( z ) 能够一个分量一个分量地估计，那么磁可以按逐元素有限差分法 得到使用这种方法，磁由下式给出： ( 磋k = 垫耸 趔， 其逐元素有限差分法可以利用稀疏性去减少梯度赋值次数不幸的足，对大多数问题， 特别对大规模问题，调用梯度向量分量远比按向量整体调用困难所以要求使用能利用 h e s s e 阵的稀疏性的有限差分法去减少梯度赋值的次数， c u r t i s 、p o w e l l 和r e i d 8 提出 的一种计算非对称的稀疏j a c o b i 矩阵方法，实际上足有限差分算法，但它利用了j a c o b i 矩阵的稀疏性使得其函数赋值次数比一般的有限差分算法小后来，人们又利用自动微 分法去估计稀疏j a c o b i 矩阵【7 】及有效利用j a c o b i 阵的稀疏性的因子修正算法( 1 ，2 】) 为 了更有效地计算稀疏h e s s e 阵，p o w e l l 和t o i n t 5 3 】把c p r 算法【8 】的思想引入对称的情 况，提出了两种实际有效的算法( 直接法和间接下三角形替换法) 以获得h e s s e 阵的一 个好的廉价近似，这使得不得不计算的梯度赋值的次数变小了直接法是基于h e s s e 阵 的对称相容分组间接下三角形替换法是基于h e s s e 阵的下三角部分的列的相容分组 c o l e m a n 和m o r 6 6 把分组问题同图着色联系起来，给出了某些分组算法，这些算法使得 5 大型稀疏极大极小问题的数值方法 梯度赋值的次数优化或接近优化本文假定按逐个的计算梯度的各个元素不便，也即梯 度只作为一个整体去赋值而不是逐元素的赋值在这种情况下，这种方法能维持一个好 的收敛性质且差分梯度所需要的梯度赋值次数当h e s s e 阵稀疏时相对于问题的维数而言 通常足小的 在以上提到的p o w e l l 和t o i n t 的直接法中，在用有限差分近似来计算h e s s e 阵的所 有元素时，在每次迭代中足以计算额外的p 个梯度值为代价的，而通常此时的p 比n 小 得多而比1 大，这里p 为分组组数，n 为问题的维数这可能在每次迭代中进一步减少 计算梯度值的次数足有好处的但当p 比1 大很多时，这种好处在逐渐减弱解决的一 个办法就是按冯果忱 1 4 】建议的不修正矩阵所有的元素其中一种是行列修正法，讲的 是在每次迭代中伊的一列元素按照由差分梯度9 j ( z ) 所得到的向量被修正，而印的相 应的行由这列的转置被修正，这种修正逐次地周期地连续进行下去直到找到最优解，这 种方法最先用于求解光滑无约束优化问题【1 6 1 ，之后李光烨阳】考虑了利用稀疏性提出 逐元素修正算法( s e c ) 求解大型稀疏光滑无约束优化问题，它足行列修正算法的稀疏推 广尽管这种方法有一个好的局部收敛性质，但是对某些问题存在一些不足就像在李 光烨【2 8 】中提到的，假定h e s s e 阵h ( x ) 有一个带形结构且带宽至少足3 的话，这种由 逐次元素修正算法产生的近似阵b 七( k p ) 在每p 步迭代其非对角元素至少修正了两 次而对角元素却只修正了一次，换句话说，对于那些对角占优势的矩阵来说，这种方法 在每p 步迭代花费了大量的时间用在修正非对角元上，这显然足不可取的鉴于这个原 因，李光烨【2 8 】提出了对角割线校正算法( d s e c ) 再次在每次迭代修正对角元素这似 乎弥补了以上的这种不足，但却增加了每次迭代的矩阵的计算量而于波和张淑婷等人 6 9 ，7 3 】已将行列修正算法引入求解极大极小问题另一种足换元修正n e w t o n 型法( 参见 冯果忱【1 4 1 或冯果忱和亢正刚【1 5 1 ) ，说的是事先把的元素分成几组在每次迭代中按 照某种方法计算的某一组中的元素，比如伊的某一组中的元素由梯度的有限差分近 似的方法得到，其余元素保持不变，这种修正逐次地周期进行下去直到找到最优解这种 方法最先用于求解非线性方程组【1 4 ，1 5 】，后来张淑婷等人【6 9 ，7 3 】又将这种方法引入求 解极大极小问题本文在第二章第二、三节、第三章和第五章把换元修正n e w t o n 型方法 和c o l e m a n 和m o r 6 1 6 1 的矩阵的稀疏分组算法结合起来提出了对称相容分组修正算法来 求解稀疏光滑无约束优化问题和稀疏极大极小问题还有一种换元方法就是王宇和冯果 忱【6 3 】提出的求解光滑无约束优化的直接列校正c h o l e s k y 因子算法，此算法就足在一步 步迭代中逐列校正其c h o l e s k y 因子的算法以节省每次分解的时间，提高算法的效率本 文作者在 3 1 ，3 2 】中把这种思想结合c o l e m a n 和m o r 6 ( 1 9 8 3 ) 5 】的分组思想引入求解稀疏 光滑无约束优化问题；由于分组方法没有考虑对称性，也没有考虑到分划组的合并，尽 管节省了每步的c h o l e s k y 分解，但效果并不太明显；为此本文又把此思想结合c o l e m a n 和m o r 6 ( 1 9 8 4 ) 6 】的分组算法引入求解稀疏光滑无约束优化问题( 见第二章第一节) ，进一 步又推广到稀疏极大极小问题( 第三章) ，并证明了这种算法能保持一个好的局部和全局 收敛性质，特别在极大极小问题的收敛性分析中没有限制严格互补条件成立，最后通过 数值实验验证了算法的效率 再者，当远离最优点时，无论是光滑无约束优化问题还足极大极小问题，若某个h e s s e 阵不正定的话，搜索方向可能不是下降方向，因此需要对h e s s e 阵进行正定修正，为此， 6 大连理工大学博士学位论文 人们提出了若干修正h e s s e 阵h j ( z 七) 的正定措施( 见 4 2 ，4 8 ，7 0 】) ，其中大部分足通过显 式的或隐式的选择砭修正h e s s e 阵h j ( x k ) 以便矩阵魂= h j ( 巩) + 磁充分正定当然， 除需要的修正矩阵是良条件的外，仍希望修正尽可能得少但要在h e s s e 矩阵或其近似中 的二阶信息尽可能得被保存对基于h j ( x k ) 的特征值分解的特征值修正策略来说，尽管 它很有效，但是由于它一般计算代价太大，所以一般不执行这种修正方法用来修正一 个不正定的h e s s e 阵的数值比较稳定、比较有效且常用方法是执行它的c h o l e s k y 分解， 即g i l l 和m u r r a y 等( 1 9 7 4 ) ( 1 9 ，2 0 ) 提出的修改的c h o l e s k y 因子分解( m o d i f i e dc h o l e s k y f a c t o r i z a t i o n ) 方法，这种方法在分解期间必要时增加对角元素以保证它们充分正这种 修改的c h o l e s k y 方法不仅保证了相对于实际h e s s e 阵的修改的c h o l e s k y 因子存在而且有 界，而且如果h e s s e 阵充分正定，则不去修正本文采用修改的c h o l e s k y 因子正定措施 以及对称相容分组修正修改的c h o l e s k y 因子正定措施来保证近似h e s s e 阵正定，从而保 证得到的搜索方向足一个下降方向( 见第二章第二节、第三章) 但遗憾的是，在用这种方 法求解极大极小问题时，由于求解的线性方程组为多个h e s s e 阵的组合，如何有效地利 用所得到的c h o l e s k y 分解来快速求解线性方程组有待进一步研究又当远离最优点时， 不精确n e w t o n 法起到一个节省计算量从而能快速接近最优点的作用，本文把对称相容 分组修正算法同不精确n e w t o n 法结合起来求解大型稀疏光滑无约柬优化问题( 第二章第 三节) ，这样既解决了繁琐的计算h e s s e 阵的困难，又解决了远离最优点时过多的不必要 的运算量，从而保证了算法的高效进展但是当不精确n e w t o n 方法用到求解极大极小问 题时，却遇到了解n e w t o n 型方程组之后并非直接得到一个下降方向，还要求解一个二次 子问题，怎样控制住这两个子问题呢? 我们通过认真研究，终于找到了一个控制强迫序 列的方法，在所给控制序列下即控制了不精确解n e w t o n 型方程组又对近似求解二次子 问题起到了很好的监控作用，从而节省了求解的计算量，并在不假设严格互补的条件下 证明了它能达到一个比较好的收敛性质( 见第四章) ，最后把这种方法与对称相容分组修 正n e w t o n 型法结合起来求解大型稀疏极大极小问题( 见第五章) ，而张 7 3 1 提出的各种 不精确极大极小算法仅足针对二次子问题的求解精度进行的控制 1 2 预备知识和记号说明 先介绍一些常用的定义( 见【4 ，4 6 】) 定义1 1 称函数，于z 舻关于常数口 0 是局部l i p s c h i t z 连续的，如果存在某个 g 0 使得 l f ( y ) 一，( z ) i q | i y z l f ，v y ，z s ( z ，) 定义1 2 函数f ：舻一r 在z 舻处沿着方向h 舻的方向导数定义为 d f ( x ；h ) = 珊塑等型 定义1 3 假设比，h r n ，：舻一r 在z 处沿方向h 的方向导数彤( z ； ) 存在，定义 l ( x ) 在z 的次梯度o f ( x ) c 形如下； o f ( x ) = f r ”：d ( z ；h ) f ， ) ，v h r n ) ( 1 2 1 ) 7 大型稀疏极大极小问题的数值方法 极大值函数( 1 1 5 ) 在最优化问题中具有重要的作用下面介绍极大值函数的一些重 要性质，为研究以极大值函数为目标的极大极小问题提供有效的工具 定理1 1 ( 【4 6 】定理5 4 5 ) 函数砂( z ) 如( 1 1 5 ) 式定义，对歹k ，如果f j ：舻一r 是局 部l i p s c h i t z 连续的，并且v z ，h 彤1 ，方向导数矿( z ；h ) 存在，有 ( 1 ) 妒( z ) 为局部l i p s c h i t z 连续函数 ( 2 ) 比，h 舻，妒( z ) 在点z 处沿方向h 的方向导数d e ( x ；h ) 存在，且 d 砂( z ；h ) = m a xd ( z ；九) ，( 1 2 2 ) j e l m ( x ) 其中五。( z ) = j 厶。：f ( x ) = 妒( z ) ， 定理1 2 ( 1 4 6 】推论5 4 6 ) 函数妒( z ) 如( 1 1 5 ) 式定义，对j k ，如果f j ：舻_ r 是连 续可微的，那么v x ，h r ，l ，方向导数却( z ；h ) 存在，且 d 妒( 。；h ) = m a x ( v f j ( z ) ，九) j l n ( 功 而砂( z ) 在z r n 的次梯度a 妒( z ) 为 鲫( z ) = c o n v j 厶( 。) v ，( z ) ) ， 以及 却( z ； ) 2 锤m 鲫a x ( z 产 ) 定理1 3 ( 1 4 6 】命题5 2 1 6 ) 对j k ，如果户：r n r 是凸的， 凸的；如果户是严格凸的，则1 1 f ，( z ) 也是严格凸的 ( 1 2 3 ) ( 1 2 4 ) ( 1 2 5 ) 则极大值函数( 1 1 5 ) 是 下面给出本文中用到的两个极大极小定理 定理1 4 ( 离散极大极小对偶定理) ( 4 6 】推论5 5 3 ) 考虑极大极小问题( 1 1 4 ) ，假设对j k 函数户：舻_ _ r 凸并且至少存在一个j k ，r a i n r ，if ( x ) 存在，那么 柏m i nj m a k x ，2 删m i