（应用数学专业论文）一般变分不等式的算法研究.pdfVIP

中文摘要 一般变分不等式是经典变分不等式的一种极其重要的推广，它为我们研究数 学、物理、经济学和工程科学中的许多问题提供了简单的统一框架，也是目前应 用数学领域中备受关注的热点之一。 本文较为系统地研究了一般变分不等式问题的算法，其中包括一般单调变分 不等式般强单调变分不等式，一般伪单调变分不等式和一般集值混合拟交分 不等式等，这些一般变分不等式统一和推广了许多已有的变分不等式问题。具体 内容如下： 给出了一种解一般变分不等式的改进投影算法。此算法运用白适应过程，产 生了一种高效的步长选取策略，提高了投影算法的效率。在算子f 为g 一强单调的 条件下，证明了算法的全局收敛性，并给出了其数值实验结果。 提出了一种新的解一般单调变分不等式的预估一校正投影算法，建立了算法的 收敛性定理。该算法采用了非常有效的预估和校正步长准则，大大减少了计算量， 并给出了其数值试验结果。 基于算子的分裂技巧，给出了解一般变分不等式的几种新的投影算法，包括 三步和k 步迭代算法。在算子丁是g 一伪单调和g l i p s c h i t z 连续的条件下，证明了新 算法的收敛性。值得指出的是，这个新算法不同于已有的投影算法，且其收敛性 的证明相对其他方法而言更为简单。 利用辅助原理和预解算子技巧，提出了解一般混合集值拟变分不等式的预估一 校正算法和三步迭代算法。如果混合集值拟变分不等式中的双函数是斜对称的， 则预估一校正算法的收敛性只要求映射是g 局部放松强单调的即可，这是一个比 g 强制性更弱的条件。而且，改正了n o o r 的一些错误：在适当的条件下，证明了 三步选代算法是强收敛的。 利用c h e n ，h a r k e r - k a n z o w s m a l e 光滑函数提出了一种解箱约束变分不等式的 光滑牛顿法。此算法在每一步迭代中只需处理一个光滑函数，不需考虑伎近似参 数下降的过程，当满足适当条件时算法是全局收敛的。 关键词：一般变分不等式预估一校正算法投影算法光滑函数收敛性 a b s t r a c t g e n e r a lv a r i a t i o n a li n e q u a l i t i e s a r ea n i m p o r t a n t a n du s e f u l g e n e r a l i z a t i o n o f v a r i a t i o n a li n e q u a l i t i e s i th a sb e e ns h o w nt h a tg e n e r a lv a r i a t i o n a li n e q u a l i t i e sp r o v i d e u sw i t hau n i f i e d ，s i m p l e ，a n dn a t u r a lf r a m e w o r kt os t u d yaw i d ec l a s so fp r o b l e m s i n c l u d i n gu n i l a t e r a l ，m o v i n g ，o b s t a c l e ，f r e e ，e q u i l i b r i u m ，a n d e c o n o m i c sa r i s i n gi n v a r i o u sa r e a so fp u r ea n da p p l i e ds c i e n c e s i ti sa l s oo n eo ff o c a lp o i n tp r o b l e m sp a i d c l o s ea t t e n t i o nb ys c h o l a r si nt h ef i e l do fa p p l i e dm a t h e m a t i c s t h i s p a p e r i sd e v o t e dt o s t u d y i n gs y s t e m a t i c a l l y t h e a l g o r i t h m s o f g e n e r a l v a r i a t i o n a l i n e q u a l i t yp r o b l e m s ，i n c l u d i n gg e n e r a ls t r o n g l y m o n o t o n ev a r i a t i o n a l i n e q u a l i t y , g e n e r a lm o n o t o n e v 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 lp s e u d o m o n o t o n ev a r i a t i o n a l i n e q u a l i t y , a n dm u l t i v a l u e dg e n e r a lm i x e dq u a s i v a r i a t i o n a li n e q u a l i t y , w h i c h a r et h e u n i t ya n de x t e n s i o no fal a r g en u m b e ro fk n o w nv a r i a t i o n a li n e q u a l i t i e s a n dm i x e d v a r i a t i o n a li n e q u a l i t i e s am o d i f i e d p r o j e c t i o n m e t h o df o r s o l v i n g g e n e r a l v a r i a t i o n a l i n e q u a l i t i e s i s p r e s e n t e d ap r a c t i c a l a n dr o b u s t s t e p s i z e c h o i c e s t r a t e g y ，t e r m e ds e l f - a d a p t i v e p r o c e d u r e ，i sd e v e l o p e d t h er e s u l t i n ga l g o r i t h m i s g l o b a l l yc o n v e r g e n tf o rs t r o n g l y m o n o t o n e o p e r a t o r n u m e r i c a l r e s u l t sa n d c o m p a r i s o n w i t hs o m e e x i s t i n g p r o j e c t i o n - t y p em e t h o d sa r e a l s o g i v e n t oi l l u s t r a t et h ee f f i c i e n c yo ft h ep r o p o s e d m e t h o d am o d i f i e d p r e d i c t i o n c o r r e c t i o n m e t h o di s p r o p o s e d f o r g e n e r a l m o n o t o n e v a r i a t i o n a l i n e q u a l i t i e sb yu s i n g t h eb e t t e r p r e d i c t i o n a n dc o r r e c t i o n s t e p s i z e s p r e l i m i n a r y 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 ei m p r o v e m e n t sa r e s i g n i f i c a n t s o m en e wp r o j e c t i o nm e t h o d sa r e p r e s e n t e d f o r s o l v i n gg e n e r a l v a r i a t i o n a l i n e q u a l i t i e sb a s e do n t h eo p e r a t o rs p l i t t i n gt e c h n i q u e ，i n c l u d i n gt h r e e - s t e p sa n dk - s t e p s i t e r a t i v e a l g o r i t h m s t h e m o d i f i e dm e t h o d s c o n v e r g e f o r g - p s e u d o m o n o t o n e a n d g - l i p s c h i t zc o n t i n u o u so p e r a t o r s ，w h i c h i sm u c hw e a k e rt h a n g - m o n o t o n i c i t y i t i s w o r t h w h i l et op o i n to u tt h a tt h en e wi t e r a t i v em e t h o d sa r ed i f f e r e n tf r o mt h ee x i s t i n g p r o j e c t i o nm e t h o d s ，a n do u rp r o o f o fc o n v e r g e n c ei sv e r ys i m p l ec o m p a r e dw i t ho t h e r m e t h o d s s o m en e wp r e d i c t o r - c o r r e c t o rm e t h o d sa n d t h r e e s t e p s i t e r a t i v e a l g o r i t h m s f o r s o l v i n gm u l t i v a l u e dg e n e r a lm i x e dq u a s i v a r i a t i o n a li n e q u a l i t i e si sp r e s e n t e db yu s i n g t h ea u x i l i a r yp r i n c i p l ea n dr e s o l v e n to p e r a t o rt e c h n i q u e ，r e s p e c t i v e l y i ft h eb i f u n c t i o n i n v o l v i n g t h em u l t i v a l u e d g e n e r a l m i x e d q u a s i - v a r i a t i o n a li n e q u a l i t i e s i ss k e w s y m m e t r i c t h e nt h en e wp r e d i c t o rm e t h o d s i ss h o w nt h a tt h ec o n v e r g e n c eo ft h en e w m e t h o dr e q u i r e st h ep a n i c a l l yr e l a x e ds t r o n gm o n o t o n i c i t yp r o p e r t yo ft h eo p e r a t o r , w h i c hi saw e a k e rc o n d i t i o nt h a nc o c o e c i v i t y m o r e o v e r ，w ec o r r e c ts o m em i s t a k e so f n o o r t h e t h r e e s t e p si t e r a t i v ea l g o r i t h m sc o n v e r g es t r o n g l y u n d e rs u i t a b l e c o n d i t i o n s an e ws m o o t h i n gn e w t o n a l g o r i t h m f o r s l o v i n g b o x c o n s t r a i n e d v a r i a t i o n a l i n e q u a l i t yi sp r o p o s e db yu s i n gc h e n - h a r k e r - k a n z o w s m a l es m o o t h i n gf u n c t i o n t h i s m e t h o dh a st h ea d v a n t a g et h a ti th a so n l yt od e a lw i t has m o o t hf u n c t i o na ta n yi t e r a t i o n a n di tn e v e rr e q u i r e sap r o c e d u r et od e c r e a s ea na p p r o x i m a t e p a r a m e t e r u n d e rs u i t a b l e c o n d i t i o n s ，i t sg l o b a l l yc o n v e r g e n t k e y w o r d s ：g e n e r a lv a r i a t i o n a li n e q u a l i t i e s p r e d i c t i o n c o r r e c t i o nm e t h o d p r o j e c t i o nm e t h o d+ s m o o t h i n gf u n c t i o nc o n v e r g e n c e 创新性声明 y $ 8 3 4 5 9 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均己在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担切相关责任。 本人签名：盘塞刍 日期：如0 3 d 增 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生 在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕业 离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。学校 有权保留送交论文的复印件，允许盎阅和借阅论文；学校可以公布论文的全部或 部分内容，可以允许采用影印、缩印或其他复制手段保存论文。( 保密的论文在解 密后遵守此规定) 本人签名：童墨盔 。 导师签名 日期：塑i ：! ：盛 日期：渤多j ，2 5 牡 第一章绪论 第二_ 章绪论 1 1 一般变分不等式的背景和研究现状 2 0 世纪6 0 年代，l i o n s ，b r o w d e r ，s t a m p a c c h i a ，k yf a n ，l e m k ，c a t t e ，d a n t i z i n g 等提出和创立了变分不等式和互补问题的基本理论。经过许多学者的努力，变分 不等式理论及应用的研究已取得重大的进展。到目前为止，变分不等式己成为一 个内容十分丰富的交叉性研究领域，并有广阔的应用前景。 变分不等式的数值解法一直是一个备受关注的热点问题，下面我们概述与本 文密切相关的一些算法方面的研究现状。 针对单调变分不等式，g o l d s t e i n l e v i t i n p o l y a k i 卜2 】利用“+ 是经典变分不等式 的解等价于“一尼一p f ( “) ) ”，提出了显式投影方法，迭代格式为： “- 矗阻一卢i f ( ) 】 其中圪( ) 是c 上的正交投影，成，0 是选定的任一步长。但为了证明算法的收敛 性，单值映射f 必须是l i p s c h i t z 连续且强单调。1 9 9 9 年，n o o r l 3 】和z h a o l 4 】就单调 变分不等式问题分别提出了改进的投影算法。 之后，k o r p e l e v i c h l 5 i 提出改进方法，即著名的外梯度法，迭代格式为： 一足阻一f l j , f ( u ) 1 ， “”一晶阻一只f ( 矿) 】，( i - 1 ) 其中成是选定的任一步长。当单值映射f 是u p s c h i t z 连续时，此算法收敛。但如 果f 不是l i p s c h i t z 连续或l i p s c h i t z 常数不确定时，为了得到新步长，在每一试验 点都需要进行a r m i j o 线性搜索，这就大大增加了计算量。因此人们对外梯度算法 进行大量的改进：i u s e m 和s v a i t e r i 6 】的算法只需一个投影就可得到步长成，而且全 局收敛的条件没有增加；s o l o d o v 和s v a i t e r 7 1 使用相同的搜索方向，通过修改投影 区域得到了更好的步长规则：2 0 0 1 年，王宜举i8 】改进了外梯度算法的搜索方向， 同时在【9 】中提出了一种外梯度算法的统一框架；2 0 0 2 年，何炳生等【1 0 i 将外梯度算 法( 1 1 ) 的步长成做了改进，大大提高了算法效率。 此后，针对单调变分不等式，学者们又提出了各种解法。八十年代，g a b a y l “】 引入一个罚参数并提出交错方向法，但如果罚参数选择不当，求解时间就会大大 增加。为此，可变的罚参序列被用来代替固定的罚参数。但是选择合适的初始罚 2一般变分不等式的算法研究 参数也很难，h ee ta 1 吲通过使用自适应法则来调整罚序列，得到了较好的结果。 t e n g l l 3 】基于线性约束的凸可分规划的内点法，提出了路径跟踪法来解单调变 分不等式。其主要思想是在每一个迭代步，用一个n e w m n 法不精确地解一个原始 问题的参量化光滑逼近，并且以几何速率使参数逼近零点。这个算法可从任何一 个内点开始，而且全局收敛。c h e n 和h a r k e r l l 4 】也将互补问题的路径跟踪法推广到 了变分不等式，并加以改进，得到的算法可在任意一个初始点开始，而且不要求 中间点一定为可行点。1 9 9 8 年，k c h r i s t i a n 和j i a n g i j 提出一种类内点连续算法。 单调变分不等式的自由导数法，没有用到映射的j a c o b i a n 矩阵，而是利用各 种价值函数来解决，所以这种方法适合解大规模的变分不等式。p e n g l l 6 j 平u 用一个 所谓的d 一间断函数，可看作是隐式l a g r a n g e 算子从互补问题到变分不等式的一种 推广，将变分不等式转化为无约束的价值函数极小化问题。可参看文献 1 7 1 8 1 。 对于一些带有可分结构的大规模变分不等式问题，可用分解法将原始问题分 解为一系列低维数的子问题。引入一个l a g r a n g e 乘子( 向量) 后，通过一定的规 则进行迭代。它是增广l a g ：r a n g e 算子方法的推广，可参看文献 1 9 1 。 对于伪单调变分不等式，w a n g i9 】将文【6 7 中的投影残量和改进的外梯度方向 相结合，得到了新的搜索方向，此时步长的选择使得新的迭代点更加接近解集， 而且在伪单调的情况下，算法收敛：n o o r i 捌在每一迭代步中使用了一个附加的预 捌步和投影，大大提高了外梯度算法的收敛速度：2 0 0 0 年，a r n i 2 1 】利用推广的k v f a n 极小不等式得到了广义伪单调拟变分不等式的解的存在性定理。 对于带有约束集的变分不等式，如果约束集由一些不等式定义，而且一些标 准的约束限定成立，那么问题可转化为一个k k t 系统：利用f i s c h e r 函数【2 2 1 可将 k k t 系统转化为一个非光滑方程组或者是极小化问题，可参看文献 1 8 ，2 3 1 。除 了可将变分不等式转化为无约束优化问题外，一些学者还考虑将它转化为约束优 化问题，可参看文献 2 4 1 。这种转化的一个原因就是变分不等式中的函数可能仅定 义在一个约束集上。在多数情况下，要找一个优化问题的全局最小解是很困难的， 并且许多优化技巧只局限于价值函数的一个平稳点。虽然给出了保证价值函数的 一个平稳点是变分不等式或互补问题的解的条件。但是仍存在不是原始问题解的 平稳点，这样会增加计算量。 特别地，对于箱约束交分不等式，q i ，s u n 和z h o u l 2 5 l 引入额外人工变量，将 变分不等式问题化为非线性互补问题来研究，而后利用光滑牛顿法得出其迭代算 法，但从计算角度讲显然是不经济的。2 0 0 2 年，陈国庆，曹兵【2 6 l 引入一种新的间 断函数并提出了广义牛顿法；同年，陈国庆，刘水霞 2 7 】针对不可微箱约束变分不 等式提出了下降算法。 近年来，许多数学工作者根据所研究变分不等式的特点，提出了各种各样行 之有效的算法。限于篇幅，这里就不一一罗列，有兴趣的读者可参阅f 1 5 2 1 。 第一章绪论 但是对于一般变分不等式的算法研究相对较少。近年来，许多学者利用不同 的技巧( 如投影算法、辅助原理、w i e n e r h o p f 方程等) 提出了解一般变分不等式 的一些算法。n o o r 2 8 】首先建立了一个不动点方程；p a n g 和y a o l 2 9 给出了解的存在 性的一些充分条件，并研究了其的稳定性：h e 【3 0 】提出了一个非精确的稳定投影方 法：2 0 0 0 年，n o o r 3 1 】应用分裂技巧，提出了三步分裂迭代解法；2 0 0 2 年，n o o r 3 2 j 利用新的搜索方向，在解集非空和映射为单调的情况下提出一种修正投影算法。 包含非线性双函数的一般混合集值拟变分不等式是变分不等式的一种重要推 广，但由于非线性双函数的存在，投影法、w i e n e r - h o p f 方程法和它们的各种变形 都不能用于解这类变分不等式。当非线性双函数是真凸下半连续泛函时，它的次 微分映射是一个极大单调集值映射，此时一般混合集值拟变分不等式等价于不动 点问题，于是学者们利用集值映射的预解算子来代替投影算子，利用不动点格式 提出了一些新的迭代算法。这一方法最早是由m a r t i n e t 3 3 1 和b r e z i s t 3 4 1 提出的，随后 h a s s o u n i 和m o u d a f i 3 5 l 将之加以改进和完善。n o o r f 3 6 】在预解算子的基础上又提出 了预解方程，并建立了它与混合变分不等式的等价关系。之后，利用预解算予和 预解方程将针对变分不等式问题的许多研究成果推广到了混合变分不等式问题 上。但是这种方法要求我们计算( 估计) 出映射的预解算子，这本身就是一个很 难解决的问题；另一方面这种技巧不能用于不可微的双函数。于是，学者们又提 出了辅助原理法，或称辅助变分不等式法，针对各种变分不等式提出了许多迭代 方法。这一方法最早是由l i o n s 和s t a m p a c c h i a l 3 7 1 提出的。近十年来，这两种方法 被广泛的用来构造各种迭代算法，研究混合变分不等式问题解的存在性、参数解 的灵敏性，读者可参看文献 3 6 4 1 ，4 7 4 8 1 。 1 2 一般变分不等式问题的数学模型 设h 为一个实h i l b e r t 空间，( ，) 和洲分别表示日的内积和范数，k 为h 的一 非空闭凸集，c ( 月) 是h 的所有非空紧子集集合。当h r ”时，h 为e u c l i d e a n 空 间，它是一个n 维欧氏空间，q 是彤的一非空闭凸集。f ，g ：r ”一彤是非线性映 射，且g 可逆。丁，v ：一c ( h ) 是集值映射，妒( 。，：h x h - - r u + 畸为一不可微 的非线性双函数。给定非线性映射( ，) ：h h 日，g ：h 一日，本文考虑的一般 变分不等式问题和一般混合集值拟变分不等式问题分别为： 求工r “，gx ) q ，使得 !二塑奎坌至箜茎鳖篓鎏婴壅一 f ( z ) ( g ( y ) 一g ( x ) ) o , v g ( y ) e f 2 。 ( 1 2 ) 求“日，x e t ( u ) ，y e v ( u ) 使得 ( u ( x ，_ ) ，) ，g ( v ) 一g ( “) ) + 妒( 占( v ) ，g ( “) ) 一妒( 占( h ) g ( “) ) 2 0 , v g ( v ) e h a ( 1 - 3 ) 适当地选择g ，n ，仍t ，y 和空问h ，这两类问题可繁衍出许多已有的( 混合) ( 拟) 变分不等式问题，本节只列举一部分： ( 1 ) 如果占0 ) 一x ，问题( 1 - 2 ) 等价于求z q 使得 f ( x ) 7 ( y x ) 2o ，y y q ， 这类问题就是经典变分不等式问题。 ( 2 ) 如果q ”一 x e 8 “j ( z ，y ) = o ，v y e a i 是r “中凸锥k 的一个极锥，问题( 1 - 2 ) 等价于求x g r 8 使得 g o ) q ，f ( x ) e a ”，( g ) ，f o ) ) 一0 ， ( 1 4 ) 这类问题被称为一般非线性互补问题。如果g o ) - x m o ) ，其中m 是点到集映射， 腮称问题( 1 - 4 ) 为拟( 隐式) 互补问题。如果9 0 ) 一x ，称问题( 1 - 4 ) 为广义互 补问题。 ( 3 ) 如果z y - v ，妒：h r u + 。) ，则问题( 1 3 ) 等价于求“h ，v z ( “) 使 得 ( n ( v ，v ) ，g ( v ) 一g ( “) ) + 妒( g ( v ) ) 一伊( g ( “) ) z 0 , v g ( v ) 日， ( 1 5 ) 这类问题被称为一般集值混合变分不等式1 3 8 】。 ( 4 ) 如果妒：h r u + 畸是一个真凸下半连续函数，则问题( 1 5 ) 等价于求 日，v e t ( u ) 使得 o n ( v ，v ) 十a 妒( g m ) ) ，( 1 - 6 ) 其中0 妒是尹的次微分，且是一极大单调映射。问题( 1 6 ) 也就是求( 极大) 单调映射 之和的零点。读者可参看文献 3 9 4 1 。 ( 5 ) 如果t ：h 一日是一个单值映射，则问题( 1 5 ) 等价于求“打使得 第一章绪论5 ( ，“) ，g ( o g ( “) ) 十妒( 9 0 ) ) 一妒皓 ) ) o , v g ( v ) h ，( 1 - 7 ) 这类问题被称为一般混合变分不等式。 ( 6 ) 如果( “，h ) 一丁( “) ，t ：h 一日，c p 是日中一个闭凸集k 的指标函数，则问 题( 1 - 7 ) 等价于求“，g ( u ) e k 使得 ( t u ，g ( v ) - g ( u ) ) 0 , v g ( 0 e k ，( 1 - 8 ) 这类问题被称为一般拟变分不等式。1 9 8 8 年n b o r i 刎对此类问题做了详细的介绍。 可以证明一类拟变分不等式和非凸规划问题可以通过一般变分不等式来研究。可 参看文献【3 8 4 0 。 ( 7 ) 如果g ；j 为恒等映射，则问题( 1 5 ) 等价于求u h ，v t ( u ) 使得 ( n ( v ，v ) ，v 一“) + 妒( v ) 一妒( “) o , v ， ( 1 9 ) 这类问题被称为广义混合变分不等式。如果伊是日中一闭凸集k 的示性函数，则 问题( 1 5 ) 等价于求“日，g ( u ) e k ，v e t ( u ) 使得 ( n ( v ，v ) ，g ( v ) 一g ( h ) ) o , v g ( o e k ，( 1 - 1 0 ) 这类问题被称为集值变分不等式。近来，n o o r l 4 1 j 对此做了详细的研究。特别当g ；i 时，问题( 1 - 1 0 ) 就是广义变分不等式问题。读者可参看文献【4 2 】。 ( 8 ) 如果k - 恤h ：( “，v ) o ，v v k ) 是日中一凸锥k 的一个极锥，则问题 ( 1 - 1 0 ) 等价于求“h 使得 g ) k ，n ( v ，v ) k ，( ( v ，v ) ，g ( v ) ) 一0 ，( 1 1 1 ) 这类问题被称为集值互补问题。如果g ( u ) 一“一川( “) ，其中m 是一个点到点映射， 则问题( 1 - 1 1 ) 被称为集值拟( 隐式) 互补问题。当( “，u ) ；t u 时，问题被称为一般非 线性互补问题。 ( 9 ) 如果n ( u ，“) 一t u ，则问题( 1 - 3 ) 等价于求u 使得 ( t u ，g ( v ) 一g ( “) ) 十妒( g ( v ) ，占( “) ) 一妒( g ( “) g ( “) ) o ，v g ( v ) h ，( 1 1 2 ) 这类问题被称为一般混合拟变分不等式。 读者可参看文献 4 3 。 ( 1 0 ) 如果妒( ，。) 是关于第一变量的真凸下半连续函数，则问题( 1 1 2 ) 等价于求 6一般变分不等式的算法研究 “使得 0 e t u + a 妒( g ( “) ，g ( “) ) ，( 1 - 1 3 ) 其中a 伊( ，) 是双函数妒( ，) 的次微分，且是一极大单调映射。问题( 1 1 3 ) 也就是求两 个或更多极大单调映射之和的零点。 ( 1 1 ) 如果g ；，为单位映射，则问题( 1 1 2 ) 等价于求“h 使得 ( t u ，v - u ) + 日o ( v ，“) 一妒o ，“) o ，v v h ，( 1 1 4 ) 这类问题被称为混合拟变分不等式。 读者可参看文献 4 4 】。 ( 1 2 ) 如果妒( ，) 是日中一闭凸值集k ( “) 的示性函数，即 时帆”仁“嚣， i 则问题( 1 1 2 ) 等价于求h h ，g ( h ) k 使得 ( t u ，g ( v ) 一g ) ) a o ，妇( v ) k )( 1 a s ) 这类问题被称为一般拟变分不等式。 读者可参看文献 4 5 。当k ( “) 一k 时，它就 是问题( 1 - 8 ) 。 ( 1 3 ) 如果k 0 ) t 缸h ：( “，v ) o ，v v e k ) 是h 中一闭凸值集的一个极 锥，g k ，则问题( 1 1 2 ) 等价于求u h 使得 9 0 ) k ) ，n k 0 ) ，( r u ，9 0 ) ) 一0( 1 1 6 ) 这类问题被称为一般拟互补问题。如果9 0 ) t “一m ( u ) ，其中研是一个点到点映 射，则问题( 1 1 6 ) 被称为拟( 隐式) 互补问题。若占- ，问题( 1 1 6 ) 就是广义的互补 问题。 ( 1 4 ) 如果g ；j 为恒等映射，则问题( 1 1 5 ) 退化为求“e k ( u ) 使得 ( t u ，v 一“) 苫o ，v v k ( u ) ， 这类问题被称为经典拟变分不等式。 第一章绪论7 1 3 基本概念及基本引理 本节叵| 顾将在文中用到的一些基本概念。 定义1 3 1 1 5 1 】设h 是一实h i l b e r t 空间，丁是日上的极大单调算子，称映射： j ，( “) = ( j + p t ) 1 ( “) ，v u h 为预解算子其中p 0 为常数。 定义1 3 2 【5 l l 设h 是一实h i l b e r t 空间，c ( 日) 为日的所有紧子集组成的集合。 对于给定的r ，v ：h c ( h ) 为两个集值映射，( ，：hx h 一日为一单值映射， 令r r ( “) = i - j ，0 ) ，考虑以下问题：求z ，“e h ，w e t ( u ) ，y c v ( u ) ，使得 g ( w ，y ) + p r r z = 0 ， 称上述方程为预解方程其中，( “) 是预解算子，j 是h 上的恒等算子，p ，0 是 一个常数。 定义1 3 3 4 2 l 对于给定的“h ，g ( “) k ，求w h ，g ( w ) g k 满足 ( p t u + g ( w ) 一g ( “) ，占( v ) 一g ( p ) ) o ，v g ( v ) e k ， 称上式为辅助变分不等式问题其中p ，0 是常数。 定义1 3 4 【5 0 1 设h 是一实h i l b e r t 空间，k c h 是一非空闭凸集，“是一给定 的点。若存在z k 使得 1 1 2 - n i l = 曾陋一v j i ， 则称z 是“在k 上的投影，记做z = 足u ) 。 特别地，当h = f 时，上述定义即为e u c l i d e a n 空间的投影： 圪( v ) = a r g m i n t v - - uj fk q 。 引理1 3 1 【5 0 】设h 是实h i l b e r t 空问，k h 是一非空闭凸集，“是一给定 的点，则z 。最( h ) 是“日在k 上的投影，当且仅当z 是( z 一“，v z ) o ，v v k 的 解。 引理1 3 2 设k 是h i l b e r t 空i h j h 的一非空闭凸集，则y ；足0 ) 有下列性质： ( 1 ) s o l 投影算子是非扩张的，即对x ，x ，k ，下式成立 一般变分不等式的算法研究 l i 足( z ) 一足( z 8 i i x - - x 1 i ； ( 2 ) 5 0 1 ( x 一最( x ) ，r l 一只( z ) ) s 0 ，v 叮k ； ( 3 ) 5 2 1 ( x 一叩，足o ) 一& o ) ) ：最( x ) 一斥( 叩) n v r g h ： ( 4 ) 5 2 1 1 1 坟 ) 一硼2s 忙一“0 2 一忙一只 ) n v u e h 。 由于一般文献中没有给出详尽的证明，在这里我们给出其完整证明。 证明：( 1 ) ( 2 ) 证明可见文 5 0 。 ( 3 ) 要证。一1 ) 7 足( 工) 一足( 叩) ) z0 最( x ) 一& o ) n v r f i e h ， 即证g 一7 7 + 最( 叩) 一昂o ) ，最o ) 一斥0 ) ) t 0 ， g 一最o ) ，只0 ) 一只) ) + ( 只国) 一叩，最o ) 一足0 ) ) z 0 ， 即 ( x 一& ( 工) ，最) 一最o ) ) + ( 叩一最( 叩) ，最0 ) 一最) ) s 0 ， 由( 2 ) 可知，上式成立。 ( 4 ) 由于 j i x - - u 0 2 - l l x 一最o ) + 最0 ) 一“0 2 - i i x - p 。( x ) 1 1 2 + 0 最( 工) 一“1 1 2 + 2 ( x 一足o ) ，最 ) 一“) 一忙一最( z ) i | 2 + j | 最o ) 一“胪一2 ( x 一坟 ) ，“一足( z ) ) 老忙一p 。( x ) 1 1 2 + 恢 ) 一“n 引理1 3 3 【5 0 1 设丁：k 一日为一单值映射，则“e k 是变分不等式 ( t u ，v 一“) o ，v v u _ k 的解当且仅当“为最( ，一p t ) 的一不动点，即 “；最( h p r u ) 其中p ，0 为常数，斥是h 在k 上的投影算子。 引理1 3 4 【3 2 】“h ，g ) k 是一般变分不等式 ( t u ，g ( p ) 一g ( “) ) o ，v g ( v ) k 的一个解当日仅当 得证。 ( 1 1 7 ) ( 1 1 8 ) 第一章绪论 g ( u ) = 足拇m ) 一f i t , 】 ( 1 - 1 9 ) 其中) 0 为一常数： 证明：由引理1 3 1 知，z g k 是w 在k 上的投影，即 z = 足( w ) 当且仅当 ( z w ，v z ) o ，v v k 。 于是，当“k 是一般变分不等式( 1 - 1 8 ) 的解时，即当 ( t u ，g ( v ) 一占( “) ) o ，v g ( v ) k 时，有 ( g ( “) 一( g 以) 一p i k ) ，占( v ) 一g 以) ) = o v 奢( v ) k ，p ，0 ， 因而g ) t 最( 占 ) 一p t u ) ，即占“) 是最( 9 0 ) 一p t u ) 的一不动点。 反之，设9 0 ) = 最( 占0 ) 一p t u ) ，于是有 ( g ( “) 一( 占( “) 一p 办) ，g ( v ) 一占( “) ) 一( p 孔，g ( v ) 一g ( “) ) z o ，v g ( v ) g k ， 故 ( t u ，g ( v ) - g ( u ) ) 2 0 ，v g ( v ) e k ， 即“是( 1 - 1 8 ) 的解。 注：上述引理表明一般变分不等式等价于不动点方程( 1 1 9 ) 。这一等价关系 是以后各章中构造一般变分不等式的迭代算法的基础。n o o r l 3 2 】给出了这一结论， 但没有给出证明。 1 4 本文的主要研究内容 本文较为系统地研究了几类一般变分不等式问题的迭代算法，其中包括一般 单调变分不等式，一般强单调变分不等式，一般伪单调变分不等式和一般集值混 合拟变分不等式，它们统一和推广了许多已有的变分不等式问题和混合变分不等 式问题。研究分为两个方面：一是就一般混合集值拟变分不等式和一般单调变分 不等式分别提出了新的预估一校正算法。前者借助辅助原理，满足适当条件时，新 算法的收敛条件大大减弱，后者使用一个非常有效的预估和校正步长准则，大大 减少了计算量；二是就一般伪单调变分不等式和一般强单调变分不等式分别给出 了几种投影算法，前者基于算子的分裂技巧研究了三步和k 步迭代算法，后者运用 1 0股变分不等式的算法研究 自适应过程，产生了一种高效的步长选取策略，提高了投影算法的效率。具体内 容安排如下： 第一章简单介绍了啊二般变分不等式问题的背景、研究现状和数学模型以及本 文将要用到的一些基本概念和引理。 第二章针对一般强单调变分不等式问题，提出了一种改进的投影算法，它采 用自适应过程，产生高效的步长选取策略，并在算子f 为g 强单调的条件下，建 立了全局收敛定理，给出了算法的数值实验结果；针对一般单调变分不等式问题， 借助一个非常有效的预估和校正步长准则，提出了一种新的预估一校正投影算法， 并建立了算法的收敛性定理，给出了数值试验结果；针对一般伪单调变分不等式 给出了几种新的投影算法，此算法基于算子的分裂技巧研究了三步和k 步迭代算 法，在算子r 是g - 伪单调和g l i p s c h i t z 连续的条件下，证明了新算法的收敛性。 第三章利用辅助原理和预解算子技巧分别提出了解一般混合集值拟变分不等 式的预估一校正算法和三步迭代算法。如果混合集值拟变分不等式中的双函数是斜 对称的，则预估一校正算法的收敛性只要求映射是g 局部放松强单调的即可，这 是一个比窟强制性更弱的条件。 第四章利用c h e n h a r k e r k a n z o w s m a l e 光滑函数提出了一种新的解箱约束变 分不等式的光滑牛顿算法。此算法在每一步迭代中只需处理一个光滑函数，不需 考虑使近似参数下降的过程，当满足适当条件时算法是全局收敛的。 第二章一般变分不等式的数值算法 第二章一般变分不等式的数值算法 本章针对一般变分不等式问题，采用不同的技巧提出了一些全新的算法，这 些算法分别在映射为强单调、单调和伪单调的情况下全局收敛，所得结果是近期 一些文献中相应结果的改进与扩充。具体内容安排如下：在第2 1 节中介绍了将要 用到的概念和引理；在第2 2 节中考虑到算子的强单调性，我们引入新的步长选取 规则，即自适应过程，提出了一种新的全局收敛的投影算法；在第2 3 节中，采用 一个更好的预估和校正步长准则，在f 是譬单调且g - l i p s c h i t z 连续的条件下，给 出了解一般变分不等式的一种新方法；在第2 4 节中，利用分裂技巧和多步迭代技 巧，我们提出了解一般变分不等式的两个全新算法：三步和k 步迭代方法，并且 只要算子f 是p 一伪单调和g l i p s c h i t z 连续的，由算法产生的迭代序列就具有收敛 性，大大降低了对条件的严格要求。 2 1 概念与引理 设q 是e u c l i d e a n 空间中的一个非空