（应用数学专业论文）几类变分不等式与互补问题的算法研究.pdf

几类变分不等式与互补问题的算法研究 摘要 变分不等式与互补问题广泛应用于阐述与研究机械，工程，物理，金融，最优 控制数学模型以及交通运输中出现的各种平衡模型等因此，研究其快速数值解 法是十分有意义的近几十年来，变分不等式与互补问题在数值解法方面取得了 巨大的进展，这方面的研究成果层出不穷本文讨论了求解几类变分不等式与互 补问题的有效算法 实际中出现的科学问题往往计算规模大，而且精度要求高这就要求我们能 够设计出新的更有效的算法来解决这些问题随着并行计算机的出现，并行计算 成为解决这类问题的一种很重要的手段多重分裂方法是并行求解线性或非线性 方程组的重要数值计算方法之一其特点是将原问题转化为几个子问题进行并行 求解本文将这类方法推广到求解对称仿射二阶锥互补问题( s o c c p ) 我们在进 行矩阵分裂时考虑了矩阵的特殊结构，诸如稀疏性，块结构性在每一次迭代过程 中，每个处理器分别处理一个由分裂得到的子问题，然后再将每个处理器得到的结 果加权相加作为下一次迭代的初始值在子问题的求解中，我们使用了似m a o r 方法数值结果表明多重分裂方法用于求解对称仿射s o c c p 是十分有效的 区域分解法是上世纪八十年代崛起的新算法其思想是将计算区域分为若干 子区域，将原问题的求解转化为相应子区域上子问题的求解它是求解变分不等 式与互补问题的一类重要算法本文探讨了求解带m 一函数的非线性互补问题的 两水平加性s c h w a r z 算法这种方法基于某种判断准则，将计算区域分为两个子 区域一个子区域上含有障碍子问题，而在另一个子区域上仅需求解非线性方程 组我们得到算法的有限步收敛性结论数值实验表明该算法是十分有效的 根据不同的解的等价最优性条件，对于一般t 一单调算子的单边及双边障碍 问题，我们提出了不同的有效集算法这两种算法的本质都是基于某种策略，将区 域分解为有效和非有效的两个部分然后在非有效集上求解一个简化的非线性方 程组和p s o r 及s c h w a r z 算法不同的是，有效集算法不需要求解额外的线性或 非线性子问题我们将这类算法和p s o r 及s c h w a x z 算法做了比较，算例表明有 效集算法是非常高效的 近年来，变分不等式已经开始向各个方向推广，出现了诸如广义变分不等式， 混合变分不等式，广义似变分不等式等其中很重要的一类推广是变分不等式系 统我们考虑了一类广义似变分不等式系统( s g v l i p ) 的数值解，提出和s g v l i p 相关的逼近问题，证明了逼近问题解的存在性基于这些逼近问题，构造了求解 s g v l i p 的算法，证明了s g v l i p 解的存在唯一性以及算法的收敛性针对一类 非线性变分不等式系统( s n v i ) ，我们研究了其相关辅助问题，建立了辅助问题解 的存在性定理基于这些辅助问题，构造了求解s n v i 的算法，证明了s n v i 解的 i i 博士学位论文 存在性以及算法的收敛性最后，我们讨论了b a n a c h 空间中混合非线性变分不 等式系统( s m n v i ) 的数值算法我们先引入适定次可微泛函的叼一逼近映射的 概念，利用叩一逼近映射的性质，提出了求解s m n v i 的一些迭代算法，并证明了 算法的收敛性 关键词：变分不等式；互补问题；多重分裂；区域分解：逼近问题；辅助问题 i i i 几类变分不等式与可：补问题的算法研究 a b s t r a c t v a r i a t i o n a li n e q u a l i t y a n dc o m p l e m e n t a r i t yp r o b l e m sh a v e al o to fa p p l i c a - t i o n si nm a n yf i e l d s ，s u c ha sm e c h a n i s m ，e n g i n e e r i n g ，p h y s i c s ，f i n a n c e ，o p t i m a l c o n t r o lt h e o r ym a t h e m a t i c a lm o d e l sa n de q u i l i b r i u mm o d e l sa r i s e df r o mt r a f f i c t r a n s p o r t a t i o n h e n c e ，i t i sm e a n i n g f u lt os t u d yt h ee f f i c i e n tn u m e r i c a lm e t h o d sf o r s o l v i n gv a r i a t i o n a li n e q u a l i t ya n dc o m p l e m e n t a r i t yp r o b l e m i nt h ep a s td e c a d e s ， g r e a tp r o g r e s sh a sb e e nm a d ei nt h es t u d yo fn u m e r i c a la l g o r i t h m sa n dt h i sk i n d o fr e s e a r c he m e r g e si ne n d l e s s l y i nt h i st h e s i s ，w ec o n s t r u c ta n da n a l y z es o m e e f f i c i e n tn u m e r i c a lm e t h o d sf o rs o l v i n gv a r i a t i o n a li n e q u a l i t ya n dc o m p l e m e n t a r i t y p r o b l e m m a n yp r o b l e m sa r i s e di ns c i e n c ea n de n g i n e e r i n ga r eo f t e nl a r g es c a l e ，a n d r e q u i r eh i g hp r e c i s i o n h e n c e ，w en e e dt od e s i g ns o m en e wa n dm o r ee f f i c i e n t a l g o r i t h m sf o rs u c hp r o b l e m s w i t ht h eu s eo fp a r a l l e lc o m p u t e r ，i ti sav e r y i m p o r t a n tw a y t os o l v et h o s ep r o b l e m si np a r a l l e l m u l t i s p l i t t i n gm e t h o di sa n i m p o r t a n tt h e o r e t i c a lt o o lf o rs o l v i n gl i n e a ro rn o n l i n e a re q u a t i o n si np a r a l l e l i t sf e a t u r ei st od e c o m p o s eal a r g es c a l ep r o b l e mi n t os e v e r a ls u b p r o b l e m sa n d s o l v et h o s es u b p r o b l e m si np a r a l l e l i nc h a p t e r2 ，w ee x t e n dt h i sm e t h o df o r s o l v i n gs y m m e t r i c a la f f i n es e c o n do r d e rc o n ec o m p l e m e n t a r i t yp r o b l e m ( s o c c p ) t h em u l t i s p l i t t i n gm e t h o dw ec o n s t r u c t e df o rs o c c p e x p l o i t sp a r t i c u l a rf e a t u r e s o fm a t r i c e ss u c ha st h es p a r s i t ya n dt h eb l o c ks t r u c t u r e i ne a c hi t e r a t i o no ft h e m e t h o d ，e a c hp r o c e s s o rd e a l sw i t has u b p r o b l e mo b t a i n e df r o mo n em a t r i xs p l i t t i n g r e s p e c t i v e l y a f t e rt h a t ，t h er e s u l t sf r o me a c hp r o c e s s o ra r es u m m e dw i t hw e i g h t a 8t h ei n i t i a lv a l u ef o rt h en e x ti t e r a t i o n m o r e o v e r w ec o n s i d e ra nm a o r l i k e m e t h o dt os o l v et h es u b p r o b l e m s n u m e r i c a lr e s u l t ss h o w e dt h a tm u l t i s p l i t t i n gi s e f f e c t i v ef o rs o l v i n gs y m m e t r i c a la f f i n es o c c p d o m a i nd e c o m p o s i t i o nm e t h o dw a sd e v e l o p e di n1 9 8 0 s i t sm a i np o i n ti st o d i v i d et h ed o m a i ni n t os e v e r a ls m a l ls u b d o m a i n s ，a n dt os o l v et h es u b p r o b l e m s i nr e l a t e ds u b d o m a i n s i ti sav e r yi m p o r t a n tn u m e r i c a lm e t h o df o rs o l v i n gv a r i - a t i o n a li n e q u a l i t ya n dc o m p l e m e n t a r i t yp r o b l e m i nc h a p t e r3 ，w ed e v e l o pa n d a n a l y z ea t w o - l e v e la d d i t i v es c h w a r zm e t h o df o rn o n l i n e a rc o m p l e m e n t a r i t yp r o b - l e m ( n c p ) w i t ha nm f u n c t i o n b a s e do nc e r t a i nc r i t e r i o n ，t h i sm e t h o dd i v i d e s t h ed o m a i ni n t ot w os u b d o m a i n 8w h i c hc o n t a i no b s t a c l es u b p r o b l e ma n dn o n l i n e a r e q u a t i o n ss u b p r o b l e m ，r e s p e c t i v e l y t h ea d v a n t a g eo ft h i sm e t h o di st h a ti to f f e r s t h ep o s s i b i l i t yo fm a k i n gu s eo ff a s tn o n l i n e a rs o l v e r sf o rt h eg e n u i n e l yn o n l i n e a r i v 博上学付论文 o b s t a c l ep r o b l e m s w ep r o v et h a tt h i sm e t h o dc o n v e r g e si nf i n i t en u m b e ro f i t e r a t i o n s n u m e r i c a lr e s u l t ss h o wt h a tt h em e t h o di se f f i c i e n t a c c o r d i n gt od i f f e r e n to p t i m a l i t yc o n d i t i o n so ft h es o l u t i o n ，w es t u d yd i f f e r - e n ta c t i v es e ts t r a t e g i e sf o ru n i l a t e r a la n db i l a t e r a lo b s t a c l ep r o b l e m sw i t hat - m o n o t o n eo p e r a t o ri nc h a p t e r4 b a s e do nc e r t a i nc r i t e r i o n s a c t i v es e ts t r a t e g i e s c a nd e c o m p o s et h ei n d e xs e ti n t oa c t i v es e ta n di n a c t i v es e t ，t h e ns o l v ear e d u c e d n o n l i n e a rs y s t e mi ni n a c t i v es e t c o n t r a r yt ot h ep s o ra n ds c h w a r zm e t h o d s n oa d d i t i o n a ll i n e a ro rn o n l i n e a rs u b p r o b l e ms o l v e r sa r en e e d e d i nn u m e r i c a le x - p e r i m e n t s ，w ec o m p a r ea c t i v es e ts t r a t e g i e sw i t hp s o ra n ds c h w a r zm e t h o d ，a n d n u m e r i c a lr e s u l t si n d i c a t et h a ta c t i v es e ts t r a t e g i e sa r ev a h d i nr e c e n ty e a r s ，v a r i a t i o n a li n e q u a l i t yh a sb e e ne x t e n d e dt ov a r i o u sd i r e c t i o n s ， s u c ha sg e n e r a l i z e dv a r i a t i o n a li n e q u a l i t y ，m i x e dv a r i a t i o n a li n e q u a l i t y , g e n e r a l i z e d v a r i a t i o n a l - l i k ei n e q u a l i t ya n ds oo n o n eo ft h em o s ti m p o r t a n te x t e n s i o ni s s y s t e mo fv a r i a t i o n a li n e q u a l i t i e s i nc h a p t e r5 ，w ec o n s i d e ras y s t e mo fg e n e r - a l i z e dv a r i a t i o n a l - l i k ei n e q u a l i t i e sp r o b l e m s ( s g v l i p ) f i r s t l y , s o m ea p p r o x i m a t e p r o b l e m sr e l a t e dt os g v l i pa r ep r o p o s e d t h ee x i s t e n c et h e o r e mo fs o l u t i o no f a p p r o x i m a t ep r o b l e m si so b t a i n e d t h e na l g o r i t h m sb a s e do nt h e s ea p p r o x i m a t e p r o b l e m sa r ec o n s t r u c t e df o rt h es g v l i pa n dt h ec o n v e r g e n c eo ft h ea l g o r i t h m s a r ea l s od i s c u s s e d i nc h a p t e r6 ，w es t u d yak i n do fs y s t e mo fn o n h n e a rv a r i a t i o n a l i n e q u a l i t i e s ( s n ) a n di t sr e l a t e da u x i l i a r yp r o b l e m si nr e a lh i l b e r ts p a c e e x i s - t e n c et h e o r e m sf o rs n v ia n dt h ea u x i l i a r yp r o b l e m sa r ee s t a b l i s h e d f u r t h e r m o r e b ye x p l o i t i n ge x i s t e n c et h e o r e m a l g o r i t h m sf o rs n v ia r ec o n s t r u c t e da n dt h ec o n - v e r g e n c eo ft h ea l g o r i t h mi sd i s c u s s e d i nc h a p t e r7 ，w ec o n s i d e rt h en u m e r i c a l s o l u t i o no fs y s t e mo fm i x e dn o n l i n e a rv a r i a t i o n a li n e q u a l i t i e s ( s m n v i ) i nb a n a c h s p a c e t h ed e f i n i t i o no fr - p r o x i m a lm a p p i n gf o rap r o p e rs u b d i f f e r e n t i a b l ef u n c - t i o n a li si n t r o d u c e d u s i n gt h ep r o p e r t i e so fy - p r o x i m a lm a p p i n g ，s o m ei t e r a t i v e a l g o r i t h m sf o rs o l v i n gs m n v ia r ec o n s t r u c t e da n dc o n v e r g e n c et h e o r e mi sa l s o e s t a b l i s h e d k e yw o r d s ：v a r i a t i o n a li n e q u a l i t y ； d o m a i nd e c o m p o s i t i o n ；a p p r o x i m a t e c o m p l e m e n t a r i t yp r o b l e m ；m u l t i s p l i t t i n g ； p r o b l e m ；a u x i l i a r yp r o b l e m v 几类变分不等式与耳补问题的算法研究 附表索引 表2 1 针对s o c c p ( 2 1 ) 的不同规模，算法2 2 1 的运行结果1 8 表2 2 针对s o c c p ( 2 1 ) 中矩阵不同的稀疏度，算法2 2 1 的运行结果1 8 表2 3 针对s o c c p ( 2 1 ) 中不同的权矩阵组合，算法2 2 1 的运行结果1 9 表2 4 针对s o c c p ( 2 1 ) 中不同日的笛卡儿结构，算法2 2 1 的运行结果1 9 表3 1p s o r 算法中松弛因子u 的影响3 2 表3 2 迭代次数的比较3 3 表3 3 执行时间的比较3 3 表4 1p s 0 冗算法中松弛因子u 的影响4 7 表4 2 迭代次数的比较4 7 表4 3 执行时间的比较4 8 表4 4p s o 冗算法中松弛因子u 的影响4 8 表4 5 迭代次数的比较4 9 表4 6 执行时间的比较4 9 v i 博上学位论文 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的 成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体 已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均己在 文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。 作者签名：许湖儒日期：细7 年，月z 了日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保 留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。 本人授权湖南大学可以将本学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后试用本授权书。 2 、不保密匹 ( 请在以上相应方框内打“”) 作者签名：许】裙谲 刷醛轹砧 、 1 日期：力钟7 年y 月哆日 日期：阳7 年厂月乃日 博上学位论文 1 1概述 第1 章绪论 人们对变分不等式的兴趣始于一些力学问题的研究1 】，如在1 9 3 3 年s i g n o r i n i 2 】研究一个线性弹性体与刚性体的无摩擦接触问题时导出了一个变分不等式，称 为s i g n o r i n i 问题然而变分不等式作为一门数学学科则始于上世纪6 0 年代当 时，关于s i g n o r i n i 问题的变分不等式的第一个严格的分析是由f i c h e r a 3 1 给出 的与此同时，s t a m p a c c h i a 作出了变分不等式这一数学学科的奠基性贡献在 l i o n s 和s t a m p a c c h i a 【4 】这篇著名的论文中给出了变分不等式的一些数学理论 1 9 6 4 年，l e m k e 和h o w s o nf 5 1 证明了n a s h 均衡问题可转化为线性互补问题。 c o o t l e 6 】在其博士论文中首次提出了非线性互补问题自此，人们开始重视互补 问题的研究线性与非线性互补问题和变分不等式有着密切联系，它可看成是变 分不等式的特例 变分不等式作为变分原理的推广，是一类非常重要的非线性问题，它已经广泛 应用于机械，工程，物理，金融，最优控制等领域对这些看似毫不相干的实际问题， 变分不等式理论提供了一个自然、直接、简单、统一而且有效的框架这使得我们可 以在这一统一框架中讨论这些问题解的存在性，唯一性等变分不等式理论的另一 个十分重要且有趣的问题是如何构造有效的迭代算法来求解变分不等式的近似解 实际应用中的变分不等式涉及到了偏微分方程许多学者在将此类变分不等式离 散成为有限维问题做了大量工作，可参见【7 ，8 ，9 ，1 0 ，1 1 ，1 2 ，1 3 ，1 4 ，1 5 ，1 6 1 近几十年来， 随着对变分不等式的近似解的深入研究，已经出现了许多有效的算法如投影法及 其变形，w i e n n e r - h o p f 方程技巧，线性逼近法，下降法，牛顿法等投影法是求解 变分不等式数值解的一种重要方法这种方法用于求解变分不等式和互补问题最 早可见于g o l d s t e i n 1 7 ，l e v i t i n 和p o l y a kf 1 8 在上世纪1 9 7 0 s 年代，a u s l e n d e r 【1 9 1 ，b a k u s i n s k i i ，p o l y a k 2 0 1 以及b r u c k 【2 1 】，s i b o n y 【2 2 】等对这类方法作了深 入研究然而投影法需要计算投影，这是十分困难的而且投影法需要算子是强 单调且l i p s c h i t z 连续的，这样的条件在许多实际应用中并不具备于是许多学者 对其提出了各种各样的改进k o r p e l e v i c h 2 3 】首次提出了投影算法的一种改进方 法，即e x t r a g r a d i e n t 法，这种算法的收敛性仅要求解的存在性以及单调算子的 l i p s h c i t z 连续性此后，许多学者( 【2 4 ，2 5 ，2 6 ，2 7 ，2 8 ，2 9 1 ) 提出了各种进一步改进的 算法，数值结果表明改进后的算法比原来算法更加有效i u s e m ，s v a i t e rf 3 0 1 在求 解伪单调变分不等式时首次提出了一类变种的e x t r a g r a d i e n t 法，这种算法每一步 需要两次投影，故称之为双投影算法s o l o d o v ，s v a i t e r 【3 1 】对上述算法进行改进 并应用于求解非光滑变分不等式改进后的算法在理论和数值实验上都具有优越 一1 一 几类变分不等式与瓦补问题的算法研究 性m a r t i n e t ( 3 2 1 于1 9 7 0 年首次提出了逼近点算法，该算法属于一种隐投影算法 关于逼近点算法后续研究成果层出不穷，可参见f 3 3 ，3 4 ，3 5 ，3 6 ，3 7 ，3 8 ，3 9 ，4 0 ，4 1 ，4 2 ，4 3 1 作为投影算法的进一步研究成果，t s e n gf 4 4 提出了一种求解线性变分不等式的 矩阵分裂算法，该算法也属于隐投影算法同一年，m a c h i d a 等f 4 5 1 采用多重分裂 算法求解线性互补问题，数值结果表明该算法是十分有效的h a y a s h i 等4 6 1 推 广了矩阵分裂算法，用于求解二阶锥互补问题在本文中，我们将推广多重分裂算 法到求解对称仿射二阶锥互补问题，并证明算法的收敛性数值例子表明多重分 裂算法用于求解对称仿射二阶锥互补问题是十分有效的 区域分解法是求解变分不等式问题的一类很重要的方法第一个区域分解法 由s c h w a r z 在1 8 6 9 年提出的他首次用交替法论证了相互重叠区域上l a p l a c e 方 程d i r i c h l e t 初值问题解的存在性l i o n s 4 7 最早将此算法应用于求解变分不等 式之后，这类方法得到了很大的发展，可参见f 4 8 ，4 9 ，5 0 ，5 1 ，5 2 ，5 3 ，5 4 z e n g ，z h o u 【5 5 】讨论了双边障碍问题的单调收敛性，首次证明了区域分解法应用于求解变分 不等式问题也具有与剖分网格h 无关的收敛速度z h o u ，d i n gf 5 6 1 讨论了求解变 分不等式的一类并行s c h w a r z 算法；z e n g ，w a n gf 5 v 讨论了求解障碍变分不等 式的一类非重叠区域分解法；b a d e a ，w a n g 【5 8 】讨论了求解变分不等式的一类加 性s c h w a r z 算法随着对s c h w a r z 算法研究的深入，该算法得到进一步发展，开 始出现广义s c h w a r z 算法t a n gf 5 9 1 提出了广义s c h w a r z 分裂；d o u g l a s ，h u a n g 【6 0 ，6 l 】研究了基于r o b i n 传输条件的加速区域分解法；z h o u 等f 6 2 1 提出了求 解一类障碍问题的广义s c h w a r z 算法；“等6 3 1 研究了求解带t 单调算子的障 碍问题的广义s c h w a r z 算法的收敛性数值实验表明广义s c h w a r z 算法效果比一 般s c h w a r z 算法好t a r v a i n e n 【6 4 1 提出了s c h w a r z 法的一种新的变种，即两水平 s c h w a r z 法这种方法并不是盲目的将区域进行分解，而是基于某种方式，将原来 的问题有效的分成线性或非线性子问题在本文中，针对带m 一函数的非线性互 补问题，我们将两水平s c h w a r z 法加以改进和推广，提出了两水平加性s c h w a r z 算 法，建立了算法的收敛性定理数值实验表明，两水平加性s c h w a r z 算法较p s o r 及经典的s c h w a r z 算法效果要好的多 有效集策略( 【6 5 ，6 6 ，6 7 ，6 8 ，6 9 ，7 0 ，7 1 ，7 2 ，7 3 】) 是另一种有效的求解离散障碍问题 的方法在求解单边双边障碍问题时，k u n i s c h 等| 6 5 1 对原先已有的一些有效集 算法做了推广其思想是基于某种判断准则，将集合分解为有效集和非有效集两 个部分在非有效集里，只需求解一个线性或非线性方程组，而在有效集里，解和 障碍贴合和p s o r 及s c h w a r z 算法不同的是，这类算法不需要额外地求解线性 或非线性子问题e r d m a n n 等【7 1 提出的有效集算法将离散障碍问题减化为一系 列的线性或非线性问题，进而采用有效的算法求解这些减化后的问题在本文中， 我们将有效集策略推广到求解带t 一单调算子障碍问题算例表明有效集策略可 2 一 博上学位论文 以以较快的收敛率和较短的c p u 时间得到问题的解 在过去的几十年里，伴随着对其数值解法的研究，变分不等式也已经开始向 各个方向推广，参见f 7 4 1 7 5 ，7 6 ，7 7 ，7 8 ，7 9 ，s o h u a n g 等7 4 1 介绍并研究了广义非线 性集值混合拟变分不等式( g n s m q v i ) 的数值解通过使用极大单调映射的预解 式算子，h u a n g 等构造了求解g n s m q v i 的算法，并证明了解的存在性和算法的 收敛性n o o r 7 5 】基于辅助原则技巧，提出了一类新的求解多值变分不等式的预 估校正算法其收敛性仅要求算子是偏松弛单调即可n o o r 【7 6 1 使用辅助原则技 巧提出并分析了一些求解混合拟变分不等式的算法h u a n g 和d e n g 【7 7 推广辅 助原则技巧并研究了一类广义集值强非线性混合似变分不等式 变分不等式的另外一个重要推广是变分不等式系统( s v i ) 最近，其解的存在 性及数值解法吸引了众多学者的兴趣，可参见 7 8 ，7 9 ，8 0 ，8 1 ，8 2 ，8 3 ，8 4 ，8 5 ，8 6 】对于 s v i 的求解，现在的数值算法并不多绝大多数的算法都是直接推广投影算法李 克俊【8 7 】引入和研究了一类新的集值混合拟变分不等式系统利用预解式算子与 投影算子技巧，作者给出了求解此类变分不等式系统近似解的迭代算法并证明了 由算法生成的迭代序列的强收敛性刘江蓉【8 8 】利用投影方法研究了一类集值映 象变分不等式系统，给出了其解的迭代算法，并证明了由迭代算法生成的迭代序列 的收敛性k o n n o v 【8 9 】使用联合松弛和分裂方法求解一类带多值映射的s ，这 类s v i 可以看成是带约束的原始对偶变分不等式的扩展h u a n g 和n o o r 9 0 讨 论了h i l b e r t 空间中，在一定条件下，求解一类变分不等式系统的投影算法的收敛 性v e r m a 9 1 1 研究了h i l b e r t 空间中，一类非线性变分不等式系统的数值算法， 提出了一系列的投影算法并讨论了算法的收敛性a n s a r i 等f 9 2 1 介绍了广义隐变 分不等式系统，证明了解的存在性作为应用，建立了一些包括n a s h 均衡问题在 内的优化问题解的存在性n o o r 【9 3 】介绍并考虑一类新的包含4 个不同算子的广 义变分不等式系统使用投影技巧，提出并分析一些新的隐式迭代方法，在某些弱 的条件下给出了算法的收敛性分析所讨论的变分不等式系统包含了许多特殊情 况，如变分不等式，相关优化问题等n o o rf 9 4 】使用投影技巧和w i e n e r - h o p f 方 程，提出并分析了和拟变分不等式相关的隐式投影动态系统证明了仅需算子是伪 单调的，动态系统具有全局渐进稳定性并分析了一些特殊的情况在本文中，我们 研究b a n a c h 空间中，一类混合非线性变分不等式系统( s m n v i ) 的数值解由于 投影算法难以直接推广，我们将s m n v i 转化为不动点问题，提出了求解s m n 的一些迭代算法，并证明了算法的收敛性 除了投影算法外，构造辅助问题及逼近问题也是求解变分不等式系统的常用 方法这类方法通常通过构造辅助问题等方式，将原问题进行适当地变换，再用 投影算法求解，可参见 9 5 ，9 6 k a z m i 和k h a n 【9 6 】通过考虑相关辅助问题来求 解广义似变分不等式系统( s g v l i p ) 他们证明了s g v l i p 解的存在唯一性在 一3 一 几类变分不等式与互补问题的算法研究 本文中，我们进一步讨论了s g v l i p 的数值解，构造了一系列求解s g v l i p 的算 法，证明了s g v l i p 解的存在唯一性以及算法的收敛性 1 2 创新点及主要内容 在本文中，我们讨论了求解几类变分不等式和互补问题的有效的算法主要 包括下面内容 1 针对对称仿射二阶锥互补问题，我们通过引入日一q 分裂的概念，建立了 相应的多重分裂算法，并得到了算法的收敛性定理数值实验表明多重分裂方法 是有效的这是迄今为止我们所见到的关于求解对称仿射二阶锥互补问题的第一 个多重分裂方法 2 针对带m 一函数的非线性互补问题，我们提出了两子域两水平加性s c h w a r z 算法，建立了算法的收敛性定理进一步地，我们讨论了多子域两水平加性s c h w a r z 算法，并得到了类似的收敛性定理与经典的s c h w a r z 算法不同，在我们的算法中 充分考虑了区域的特征分解，提高了s c h w a r z 算法的有效性数值实验表明，两 水平加性s c h w a r z 算法较p s o r 及经典的s c h w a r z 算法效果要好得多 3 针对带t 一单调算子单边及双边障碍问题，我们提出了两种不同的有效集 策略对于单边障碍问题，每个迭代步包括两个子步在第一个阶段，按照某种判 断准则，指标集分解成有效集和非有效集两个部分在第二个阶段，求解一个和非 有效集相关的减化的非线性系统对于双边障碍问题，在每步迭代中，我们做三个 测试来更新问题的解并确定有效集和非有效集和p s o r 及s c h w a r z 算法不同的 是，有效集策略不需要求解额外的线性或非线性子问题 4 针对一类广义变分不等式系统( s g v l i p ) ，我们提出与其相关的逼近问题， 证明了逼近问题解的存在性基于这些逼近问题，构造了一系列求解s g v l i p 的 算法，证明了s g v l i p 解的存在唯一性以及算法的收敛性另外，我们通过构造 辅助问题求解了一类非线性变分不等式系统 5 我们讨论了b a n a c h 空间中，一类混合非线性变分不等式系统( s m n v i ) 的数值解由于标准的投影算法依赖于h i l b e r t 空间中的内积，这使得这一技巧无 法推广到b a n a c h 空间中的变分不等式问题此外，对于混合变分不等式，投影算 法并不适用，因为难以找到投影针对这些闲难，我们引入次可微泛函的刀一逼近 映射的概念，利用叼一逼近映射的性质，提出了求解s m n v i 的些迭代算法，并 证明了算法的收敛性 上述研究成果具有如下创新点 1 在多重分裂概念的基础上，引入了h q 分裂的概念 2 我们采用似m a o r 方法求解仿射s o c c p ，从而使计算更加有效 一4 一 博士学位论文 3 在求解带m 一函数的非线性互补问题时，我们考虑了并行求解子问题，所 提出的算法可以有效的在多处理器上运行，缩短算法的执行时间 4 和【6 4 】相比，我们提出的两水平加性s c h w a r z 算法可以任意选取初始值， 并且很容易推广到多子域两水平加性s c h w a r z 算法 5 带t 一单调算子单边及双边障碍问题，根据不同的解的最优性条件，我们 提出了两种不同的有效集策略和p s o r 及s c h w a r z 算法不同的是，我们所提出 的有效集策略不需要求解额外的线性或非线性子问题，因而可以以较快的速度得 到问题的解 6 在讨论s g v l i p 的过程中，我们提出了对称线性有界映射的概念通过选 择适当的对称线性有界映射，算法中的参数可以取不同的范围，这使我们在计算 的过程中有更大的选择空间 7 和 9 1 】相比，我们在算法收敛性的证明过程中，不需要算子是强单调的 8 在讨论b a n a c h 空间中一类混合非线性变分不等式系统( s m n ) 的数值 解过程中，通过引入次可微泛函的叼一逼近映射的概念，巧妙地处理了投影算法 不适用这一难题 整篇论文的安排如下：第二章讨论了求解对称仿射二阶锥互补问题的多重分 裂算法及其收敛性，并给出了数值算例第三章研究了带m 一函数的非线性互 补问题的两水平加性s c h w a r z 算法，给出了相应的算法收敛性结果，并在数值算 例中与p s o r 算法及经典s c h w a r z 算法做了比较第四章讨论了带t 一单调算 子的单边及双边障碍问题的有效集算法，证明了算法的收敛性，并给出了数值算 例第五章考虑了一类广义似变分不等式系统( s g v l i p ) 的数值解，构造了求解 s g v l i p 的算法，证明了s g v l i p 解的存在唯一性以及算法的收敛性第六章针 对一类非线性变分不等式系统( s n v i ) 及其相关辅助问题，构造了求解s n v i 的 算法，证明了s n v i 解的存在性以及算法的收敛性第七章讨论了b a n a c h 空间 中混合非线性变分不等式系统( s m n v i ) 的数值算法，提出了求解s m n v i 的一 些迭代算法，并证明了算法的收敛性在最后，我们对论文进行了总结，并讨论了 今后所要做的工作 1 3记号及基本概念 在这一节里，我们给出在整篇文章中所要用到的记号和概念 一5 一 几类变分不等式与瓦补问题的算法研究 1 3 1记号 研 n 维欧氏空间 形竹佗佗阶矩阵集 n = 1 ，2 ，礼指标集 a = ( a i j ) 舒肌元素为。订的n 阶矩阵 a 一1矩阵a 的逆矩阵 矩阵a 的转置 a i j 表示a 的子矩阵，其元素为a o ( i ，j j ) 川i a i = ( i n , j 1 ) 钆舻向量u u 向量u 的第i 个分量 u f表示分量为u t ( i i ) 的子向量 a _ ba 到b 的单值映射 0空集 ”l | 范数 还有一些特殊的记号将在文中用到时再具体说明 1 3 2 基本模型 在这一部分我们给出本文所考虑的一些基本变分不等式与互补问题模型 二阶锥互补问题： 蓑得三茎；h m z 球h ，z t ( m z + q m 0 m 1 ， 使得z ， + g ，+ )