（运筹学与控制论专业论文）非光滑方程的光滑化换元修正牛顿型方法.pdf

大连理上人学硕士学位论文 摘要 非光滑方程的数值求解是计算数学和数学规划中的重要研究课题，它为数学规划中 许多问题的研究提供了一个统一的理论框架，非线性互补问题、变分不等式问题及各类 优化问题，都可转化为非光滑方程的求解问题。近年来，关于非光滑方程，特别是互补 问题、变分不等式问题的数值解法的研究得到了国际国内学者的极大重视，在投影类方 法、广义牛顿法、光滑化牛顿法和拟牛顿法等方面取得了丰富的研究成果，奠定了非光 滑方程解法的理论基础并为非光滑方程的求解提供了很多有效、实用的方法。 实际中经常遇到稀疏非光滑方程，即非光滑映射的j a c o b i 矩阵或广义j a c o b i 矩阵是 稀疏矩阵的非光滑方程。如何利用稀疏性更有效的求解这类问题是需要进一步考虑的问 题。 对光滑非线性方程组和光滑无约束优化问题，换元修正牛顿型法是一类能够有效利 用稀疏性的迭代法。它可以尽可能少的计算近似j a c o b i 矩阵或h e s s e 矩阵，并具有介于 1 和2 之间的收敛速度，因而适用于求解大规模稀疏问题。 本文考虑稀疏非光滑方程的换元修正牛顿型算法。首先给出了光滑化的换元修正牛 顿型算法及理论分析，然后将牛顿法和换元修正牛顿型方法相结合，给出了光滑化的牛 顿一换元修正算法，在较弱的条件下证明了该方法的超线性收敛性。最后应用该算法求 解一类具体的非光滑方程箱约束变分不等式问题。初步的数值试验结果表明，该方法 是行之有效的。 关键词：非光滑方程；换元修正牛顿型法；光滑化牛顿法 非光滑方程的光滑化换元修正牛顿型方法 s m o o t h i n ge n t r i e su p d a t i n gn e w t o n l i k em e t h o d s f o rn o n s m o o t he q u a t i o n s a b s t r a c t t h en u m e r i c a ls o l u t i o no fn o n s m o o t he q u a t i o ni sa l li m p o r t a n tr e s e a r c ht o p i ci n c o m p u t a t i o n a lm a t h e m a t i c sa n dm a t h e m a t i c a lp r o g r a m m i n g ，w h i mp r o v i d e sau n i f i e d f r a m e w o r kf o rs t u d y i n gm a n yp r o b l e m si nm a t h e m a t i c a lp r o g r a m m i n g n es y s t e mo f n o n s m o o t he q u a t i o n sa r i s e sf r o mm a n ya p p l i c a t i o n s p a n gj o n g s l l ia n dq il i q u nr e v i e w e d e i g h tp r o b l e m si nt h es t u d yo fc o m p l e m e n t a r i t yp r o b l e m s ，v a r i a t i o n a li n e q u a l i t yp r o b l e m sa n d o p t i m i z a t i o np r o b l e m s w h i c hc a nb er e f o r m u l a t e d 嬲s y s t e m so fn o n s m o o t he q u a t i o n s i n r e c e n ty e a r s ，t h ei n t e r n a t i o n a la n dd o m e s t i cs c h o l a r sp a yg r e a ta t t e n t i o nt on u m e r i c a ls o l u t i o n o fn o n s m o o t he q u a t i o n , e s p e c i a l l yo nc o m p l e m e n t a r i t yp r o b l e m sa n dv a r i a t i o n a li n e q u a l i t y p r o b l e m s 1 1 1 ep l e n t i f u lr e s e a r c hr e s u l t sa b o u tp r o j e c t i o n ，g e n e r a l i z e dn e w t o nm e t h o da n d s m o o t h i n gn e w t o nm e t h o dl a i dat h e o r e t i c a lf o u n d a t i o na n dp r o v i d eal o to fe f f e c t i v ea n d p r a c t i c a lm e t h o d sf o rn u m e r i c a ls o l u t i o no fn o n s m o o t he q u a t i o n i nf a c t ，w eo f t e ne n c o u n t e rs p a r s en o n s m o o t he q u a t i o n s ，t h a ti s ，t h ej a c o b im a t r i xo r g e n e r a l i z e dj o c o b im a t r i xo fn o n s m o o t hm a p p i n gi ss p a r s e h o wt os o l v es u c hp r o b l e m s e f f e c t i v e l yu s eo fs p a r i t yi saw o r t h yo ff u r t h e rc o n s i d e r a t i o ni s s u e t h ee n t r i e su p d a t en e w t o n 1 i k em e t h o d sa r ee f f e c t i v ei t e r a t i v em e t h o d sf o rs m o o t h n o n l i n e a re q u a t i o n sa n ds m o o t hu 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 t h e yc a nc a l c u l a t e a p p r o x i m a t ej a c o b im a t r i x e so rh e s s em a t r i x e sa sf e w 鹤p o s s i b l ea n dh a v ec o n v e r g e n c er a t e b e t w e e no n ea n dt w o t h e r e f o r et h e ya l ea p p l i c a b l ef o rs o l v i n gs p a r s el a r g e - s c a l ep r o b l e m s w ec o n s i d e rt h e s em e t h o d st os o l v es p a r s en o n s m o o t he q u a t i o nh e r e f i r s t ，w eg i v et h e s m o o t h i n ge n t r i e su p d a t en e w t o n - l i k em e t h o d sa l g o r i t h ma n dt h e o r e t i c a la n a l y s i s ，a n dt h e n w ew e a k e nt h et h e o r e mc o n d i t i o n s ，g i v et h em i x e dn e w t o na n de n t r i e su p d a t en e w t o n 1 i k e m e t h o d s l o c a l l ys u p e r l i n e a rr e s u l ti sp r e s e n t e du n d e r l ea s s u m p t i o no fw e a k e rc o n d i t i o n w ei l l u s t r a t et h es m o o t h i n gm e t h o do nb o xc o n s t r a i n e dv a r i a t i o n a li n e q u a l i t i e sp r o b l e m p r e l i m i n a r yn u m e r i c a lt e s t ss h o wt h e s em e t h o d sa r ee 伍c i e n t k e yw o r d s ：n o n s m o o t he q u a t i o n ；e n t r i e su p d a t en e w t o n l i k em e t h o d s ；s m o o t h i n gn e w t o n m e t h o d s - i i - 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理 工大学或者其他单位的学位或证书所使用过的材料。与我一同工作的同志 对本研究所做的贡献均已在论文中做了明确的说明并表示了谢意。 作者签名： 主! j 起日期：忍五，笸上 大连理工大学硕士研究生学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位 论文版权使用规定 ，同意大连理工大学保留并向国家有关部门或机构送 交学位论文的复印件和电子版，允许论文被查阅和借阅。本人授权大连理 工大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，也 可采用影印、缩印或扫描等复制手段保存和汇编学位论文。 作者签名：刻起 r 导师签名： h 年月上e t 大连理工大学硕士学位论文 1绪论 1 1 研究求解非光滑方程的目的及意义 考虑方程： f ( x ) = 0 ，( 1 1 ) 其中f ：r ”一足”是非光滑映射。 非光滑方程的数值求解是计算数学和数学规划中的重要研究课题，它起源于现实问题并 在许多方面有着广泛的应用，为研究数学规划中许多重要问题提供了一个统一框架。 p a n gj o n g s h i 和q il i q u n 1 】在研究互补问题、变分不等式问题和各种优化问题时，总结 了以下八大类可以转化为求解非光滑方程( 1 1 ) 的原问题模型。 1 非线性互补问题 非光滑方程的主要来源之一是非线性互补问题。令f ：d r ”是一给定映射，其中 开集d r ”是包含非负向量群的集合。相应的非线性互补问题，记为n c p ( f ) 是：求向 量x r ”满足 x 0 ；厂( 功o ，x 7 八力= 0 有两种方法将n c p ( f ) 转换为非光滑方程。其一是定义映射f ：dj r ”为 ，( x ) = m i n ( x ，厂( x ) ) ， 其中m i n ( ) 是分段光滑算子。z 是n c p ( f ) 的解当且仅当x 是f ( ) 的零点。其二是定义映 射f ：r ”一r “为 f 0 ) = f ( z + ) 一z 一， 其中2 + = 扛足”i z 0 ) ，z 一= z 尺“l z o ) 如果z 是f 的零点，则z + 是n c p ( f ) 的解。 反之，如果x 是n c p ( f ) 的解，则z = x f ( x ) 是，的零点。上面定义的两映射，和f 都 不是，可微，但均是方向可微。 2 带有上界的n c p 在数学规划或均衡规划中，所研究的n c p 中的变量带有边界条件的约束是很普遍 的。其定义如下：令口r ”为一正向量，f ：d 寸r ”是定义在开集d 上的一阶连续可微 函数。该问题是：求向量对( x ，y ) r ”r ”满足 非光滑方程的光滑化换元修正牛顿型方法 ”= 厂( x ) + y 0 ， u = a - x 0 ， x 0 ，u t x = o y 0 ，u r y = 0 我们注意到该问题是关于向量x 和y 的2 n 阶n c p ，同样有两种方法将其转换为n 阶 非光滑方程。较为常用的一种方法是定义映射f ：d r ”为 f ( x ) = r a i n ( f ( x ) + ，x ) + r a i n ( f ( x ) 一，a - x ) ， 工是带有上界的n c p 的解当且仅当x 是约束方程f ( x ) = 0 ，x o ，a 】的解。 3 定义在凸集上的变分不等式问题 前两个例子是定义在闭凸集上的变分不等式问题的特例。令k 是r ”中的闭凸子集， 厂：d _ r ”是定义在包含k 的开集d 天”的一阶连续可微函数，相应的变分不等式问 题，记为v i ( k ，) 是：求向量x k ，满足 ( y x ) r f ( x ) 0v y k 当厂是泛函少：r ”一r 的梯度算子时，v i ( k ，) 等价于下述问题的稳定点。 r a i n f ，( 功 s jx k 由此我们可以得到两个非光滑方程： f ( x ) = x 一兀k ( x - 厂( x ) )f ( z ) = f ( h k ( z ) ) + ( z - i - i ( z ) ) 其中兀ro ) 为y 到k 的投影算子，定义为兀置( y ) = a r g r a i n i x - y i ix k ) ，f 和f 的非光 滑性来源于投影算子兀k ( ) 。需要注意的是k 的凸性是保证v i ( k ，f ) 并f lf ，f 等价的前 提。 4 k a r u s h k u h n t u c k 9 1 系统 考虑v i ( k ，f ) ，k 是由下面的等式及不等式确定的集合，即 k = x r ”：g ( x ) 0 ，办( x ) = 0 ， 其中g ：r ”一r p 和h ：r ”一r q 均是二阶连续可微映射。 足的非凸性使得我们无法得到3 中由投影算子确定的f 和f ，但在标准的约束规格之 下，比如k 是一多面体或满足m a n g a s a x i a n f r o m o v i t z 条件，我们可以得到v i ( k ，f ) 的 k k t 系统。而该k k t 系统等价于由映射f ：r ”r 尸r q r ”r p r q 确定的非光滑 方程组： 一2 一 大连理工大学硕士学位论文 厂( x ) + 圭五v g i ( z ) + 圭竹v 勺( x ) i = l j - i f ( x ，五，) = lr a i n ( 2 ，- g ( x ) ) 办 ) 其中五r ，z r 4 分别是对应的等式和不等式约束的l a g r a n g e 乘子。 5 特殊结构的分片光滑方程 考虑如下非光滑方程： f ( x ) = n l i n c 五( x ) 9 o9 ( x ) ) ， 其中每个六：尺”寸r ”是一阶连续可微函数。，的零点是下述互补问题的解： f j c x ) 0 ，j = 1 ，n n 石( x ) = o ，z = 1 ， - 1 其中兀( x ) 是兀( z ) 的第f 个分量函数。 6 不等式可行性问题 该问题是数学或均衡规划中的基本问题。其定义为：求向量x r ”，满足 g ( x ) 0 ，x k 其中g ：g “一r “是局部l i p s c h i t i z 连续函数，k 是r ”中的多面体集。该问题可以转化为 求解非光滑方程，( 工) = m i n ( o ，g ( x ) ) ，x k 的零点。 7 极大单调算子 令t ：r ”jg r 为一集值极大单调算子。相应的问题是：求向量x r ”满足0 丁( x ) 由相关理论知该问题等价于求解非光滑方程y ( x ) = 0 ， 其中y ( x ) = x - - 只( 功，只= ( ，+ 五r ) 一，i 为单位算子，力为一正数。 8 三c 1 优化问题 l c l 函数是指导数是局部l i p s c h i t z 连续但非f 一可微的泛函。l c l 优化问题是指目标 函数为l c l 函数的一类优化问题，其常见于随机规划和最优控制领域。求解无约束l c l 优化问题的稳定点等价于求解非光滑方程，o ) = 0 ，其中f 是目标函数的梯度算子。对于 有约束条件的l c l 优化问题其k k t 系统仍为非光滑方程组。 本文讨论形如( 1 1 ) 的一类方程的求解问题，其中，( ) 是局部l i p s c h i t z 连续函数。 非光滑方程的光滑化换元修正牛顿型方法 1 2 非光滑方程求解的研究现状 r o b i n s o n 2 】提出的b 导数概念将求解非线性问题的牛顿法和拟牛顿法推广到非光滑 领域。许多研究工作 3 - 8 1 都是针对某一具体的非光滑方程应用上述方法或其变形开展的。 q il i q u n 和s u nd e f e n g 9 提出了求解( 1 1 ) 的广义牛顿法，他们采用了如下的迭代格 式： x + 1 = x i y f l f ( x ) ，圪a f ( x ) ， 其中8 f ( x ) 是f 在x 的c l a r k e 意义下的广义j a e o b i 矩阵，圪是其任意一个元素。 在半光滑性的假设下证明了广义牛顿法的超线性收敛性。但是这种方法在实际计算中遇 到了某些困难。一方面是计算j a e o b i 矩阵的复杂性，另一方面当选取的初始点远离解点 时并不能保证算法的下降。 拟牛顿法由于无需计算，的导数在非线性领域受到广泛重视。对于非光滑方程， 很多情况下其广义j a c o b i 很难计算，因此无需计算广义j a c o b i 的拟牛顿法的研究越来 越受到重视。i p 和k y p a r i s i s 1 0 】将条件f 在点x li p s c h i t z 连续放松至f 在工的方向导 数径向l i p s c h i t z 连续，这说明f 在x 是强可微的。q il i q u n t l l 】进一步减弱强可微性至 2 阶方向可微性。但是只得到了关于拟牛顿法线性收敛的结果。为了得到超线性收敛性， 人们开始了拟牛顿法变体的研究。其中的分裂拟n e w t o n 法是通过引入光滑逼近函数来 处理非光滑问题。k r a s n o s e l s k i i 和z i n e e n k o t l 2 】提出了如下形式的迭代公式： x “1 = 一( x ) - 1 f ( x ) ， 一 ， 其中矽：r ”专科是光滑函数且s u p i i f ( x ) 一( x ) i l ，x e r ”) 相对很小。因非光滑函数f 被分 成光滑部分和非光滑部分f 一，所以该方法叫做分裂法。分裂法还可以利用当前迭 代点的信息扩展成如下形式： 矿+ 1 = ，一无( ，) - 1 f ( 矿) ， 其中吮：r ”一r ”是光滑函数且s u p i f ( x ) 一九o ) 0 ，z r ) 相对很小。分裂法在b a n a n c h 空间或有限维欧氏空间掣的局部及全部收敛性可参考 1 3 ，1 4 ，1 5 】。此外，基于对非光滑 函数，的各种不同结构，人们提出了许多不同组合形式的拟牛顿法。k o j i m a 和s h i n d o 1 6 给出了求解分片光滑方程的具有超线性收敛的拟牛顿型方法。在每步迭代中，如果x 和 ，+ 1 位于同一曲面上，皿+ 。用拟牛顿公式修正，否则用f 在x “1 的广义j a c o b i 近似去修 正。s u n 和h a n 1 7 】针对方程缈( 工，厅o ) ) = 0 提出了混合牛顿拟牛顿法，其中h ：r 4 一r ” 连续可微函数，y ：j j c “r “_ r ”局部l i p s e h i t z 连续函数。在【1 4 】中，首先通过 大连理工大学硕士学位论文 h , c x ) = h ( x 2 ) + 毋 一矿) 线性化h ，然后使用n e w t o n 迭代法 x + 1 - x 。一吁1 沙( z ，( x 。) ) ， 其中反满足厅o 。) 一| i l ( x ) = 岛( 矿一x k - i ) ，圪是y ( ，惋( ) ) 在的广义j a e o b i 由于采用 线性化h 使得圪相对容易计算。文献 1 7 在非光滑的前提下，证明了混合牛顿拟牛顿 法的线性及超线性收敛。q i 和j i a n g 1 8 1 研究了来源于数学规划中k k t 条件的非光滑方程 的混合牛顿一拟牛顿法。其中 一( 掰 p ：r ”一r 7 ( 0 ， 0 是待定的步长，方向d 通常称为光滑牛顿方向，光滑牛顿法便由此而来。 对于局部l i p s c h i t z 连续函数f ( x ) 的带参数的光滑逼近函数f ( x ，s ) 可以通过卷积实 现，并能够保证逼近的精确度。但是一般来说，要通过卷积得到这类函数的光滑逼近函 数要涉及多变量的积分，在实际中并不是总能得到的，只有对某些具有特殊结构的函数 能够实现。比如极大值函数、绝对值函数、某些互补函数等。此外光滑技术还用来求解 带有均衡约束的数学规划问题。 2 3 2 光滑逼近函数基本理论嘲1 定义2 1 令f ：r “一r ”是局部l i p s c h i t z 连续函数，我们称f ：r ”r + + 一r ”是，的光 滑逼近函数，如果厂满足下面的性质： ( 1 ) 存在正常数，使得任何( x ，占) r “r + + 都有忙( x ) 一厂( x ，g ) i i o 使得对跏s ，f o o ) 非奇异且0 尸 ) 。1 忙m 。 2 存在m m 和占 0 ，使得对跏s ，s ( o ，占) ，石o ，f ) 非奇异忻。，f ) 10 - m 。 例2 1 考虑非光滑函数f ( x ) = l 卅，工r ，定义 则 石“占) = f ( x ，f ) = 一x + 三x 一三 一x + 一z s 一一 22 x 一2 x 2 一三 x u 二 x 一一 x 占2 x工0 1x 一三 2 1 一4 x 一三 0 ， 1 令州= x 一q 何1 f ( x ) ，q 为迭代参数； 2 用下式修正毋； b k + i = b i - i - p i e t ( a - b k ) e j p t ， ( 1 ，) e q - m i = ( k + 1 ) m o d l ，a i z o ，吼) ，为换元周期。 3 如果i i f ( ，+ 1 ) i i 幻，终止；否贝l jk - - k + l ，转步1 。 注意：光滑化换元修正算法和第2 节中叙述的经典换元修正方法的差别在于这里使用了 光滑逼近函数修正色 3 2 光滑化换元修正牛顿型算法局部收敛性 用q ：表示q = ( f ，刊f ，j = 1 ，2 ，甩) 的子集： ，- 1 q j f = q ，h u q ，= 1 ，2 ，一l ，q ：= q 艉， ，i - - o 显然q ：nq = 矽，j 且uq ：= q = u 因而我们有 b k = q e r a k 一脚p p 歹，当七， m = o ( i , j ) g f 2 ：| e ，e r a h p j p 歹+ z e e e j a o e j e 歹， 当七 ， r a - - - o0 ) q ： ( i ，) 五： 。k i 式中五：= 叫u q 怕 ，i - - - 0 引理3 1 【2 1 】令f ：r ”一r ”在开凸集dc _ r ”局部l i p s e h i t z 连续，( ，占) 是f ( ) 的光滑逼 近函数，(