（计算数学专业论文）几个非线性问题的算法研究.pdf

摘要 在第四 章里， 我们讨论了一类广义变分不等式，传统定义中的变分 不等式是这种广义变分不等式的特例。我们这里的主要工作是， 在弱 协强制(w e a k c o- c o e rc iv ity )条件下证明了求解这类变分不等式的几种算法 的 收 敛 性。 我 们知 道， 协强 制(c o- c o e r c iv ity ) 性质出 现 在很多 求 解变 分 不 等式问 题的 算法的收敛条件当中，而杨庆之教授在2 0 0 5 年的两篇文章中 提出的弱协强制性条件在一般意义下弱于协强制性条件，故我们实际 上是减弱了算法的收敛性条件。然后，我们指出，求解定义在r 上的 算子 t 的零点问 题的一种f - b ( fo rw a r d - b a c k w a r d ) 分裂方法的收敛性条件中 所要求的协强制性也可减弱为弱协强制性。最后，我们通过在算法中 引入a r m ij 。 不精确一维搜索进一步改进了前述求解变分不等式问 题的算 法 。 最后在第五章里， 我们考察了带约束的最大单调算子零点包含问题 的 求 解 方 法。 我们 首先 在已 有的 无 约束问 题的逼 近点 算法(p p a ) 和 f -b 分 裂方法的 基础上提出相应的 投影方法。然后，我们利用p . t s e n g 改进f - b 分裂方法的思想，给出了一个新的算法并证明了算法的收敛性。此后， 我们进一步把算法中向一般闭凸集c任r 的正交投影改为向 半空间 c k 的 正交投影，得到相应的松弛化投影方法。由于向半空间的正交投影可以 通过简单的计算直接得到，从而使得改进后的算法更易于实现 ，与此同 时，我们也给出了松弛化投影方法的收敛性定理。最后，我们将收敛性 结 果 中 所 需 的 l ip s c h it z 连续 条 件 进一 步 减 弱为 次 l i p s c h it z 连 续(s u b - l ip s c h it z c o n t in u it y ) ， 并证明了前述算法在这个更弱的 条件下也是收敛的。 关键词: 不动点，k m 定理，广义k m 定理，非扩张，f - 非扩张，分裂 可行问 题，变分不等式， 最大单调， 协强制， 弱协强制 ab s t r a c t ab s t r a c t i n t h i s t h e s i s , w e s t u d y o n c o m p u t a t i o n a l me t h o d s f o r s e v e r a l r e l a t e d n o n l i n - e a r p r o b l e m s , w h i c h a r e fi x e d - p o i n t p r o b l e m; t h e s p l i t f e a s i b i l i t y p r o b l e m ( s f p ) v a r i a t io n a l i n e q u a l i t y p r o b l e m ( v l ) a n d m a x i m a l mo n o t o n e i n c l u s i o n p r o b l e m . a m o n g t h e m , t h e s f p c a n b e f o r m u l a t e d a s a s p e c i a l k i n d o f v i , a n d v i s c a n b e w r i t t e n a s m a x i m a l m o n o t o n e i n c l u s i o n p r o b l e m s , w h i l e a l l o f t h e s e t h r e e p r o b l e m s f a l l i n t o p r o b l e ms o f fi n d i n g fi x e d p o i n t s o # s o m e c e r t a i n o p e r a t o r s i n t h e fi r s t c h a p t e r , w e i n t r o d u c e s e v e r a l n o n l in e a r p r o b l e m s c o n c e r n e d i n t h i s t h e s i s , t h e i r r e l a t i o n s , a n d s o m e b a s i c n o t a t i o n s i n c h a p t e r 2 , w e i n v e s t i g a t e t h e c o n v e r g e n c e b e h a v i o r o f k r a s n o s e l s k i - ma n n ( k m ) i t e r a t i o n a n d i t s g e n e r a l i z a t i o n s , a i min g a t fi n d i n g fi x e d p o i n t s o f a n o p e r a - f o r n. a c t u a l l y , m a n y p r o b l e m s f r o m v a r i o u s fi e ld s c a n b e e x p r e s s e d as p r o b l e m s o f fi n d i n g fi x e d p o i n t s o f s o m e c e r t a i n o p e r a t o r . t h e e x is t i n g k m t h e o r e m s t a t e s t h e c o n v e r g e n c e o f t h e k m i t e r a t i o n w h e n t h e o p e r a t o r n i s n o n e x p a n s i v e a n d h as a fi x e d p o i n t . i n t h i s c h a p t e r , w e fi r s t e x t e n d t h e c o n v e r g e n c e r e s u l t t o t h e c a s e w h e n n i s fi r mly n o n e x p a n s i v e a n d r e l a x a t i o n p a r a me t e r s a r e n o w a ll o w e d t o b e in t h e in t e r v a l 0 , 2 , in st e a d o f 0 , 1 . t h e n , w e g iv e s o m e g e n e r a liz e d k m i t e r a t iv e s c h e me s a n d e s t a b l i s h t h e c o r r e s p o n d i n g c o n v e r g e n c e r e s u l t s u n d e r c e r - t a i n as s u m p t i o n f o r t h e s e g e n e r a l i z e d k m i t e r a t i o n s . mo r e o v e r , w e a l s o d i s c u s s o n t h e c a s e w h e n t h e o p e r a t o r n d o e s n o t h a v e a n y fi x e d p o i n t s . we p r o v e t h a t t h e s e q u e n c e s g e n e r a t e d f r o m t h e k m i t e r a t i o n a n d t h e g e n e r a l i z e d k m i t e r a t i o n s a r e u n b o u n d e d i f t h e o p e r a t o r s r e l a t e d t o t h e i t e r a t i o n s h a v e n o fi x e d p o i n t s . f o r i l l u s t r a t i o n , w e a p p l y t h e s e g e n e r a l iz a t io n s t o t h e c o n v e x f e as i b i li t y p r o b l e m a n d v a r i a t i o n a l i n e q u a l i t y p r o b l e m i n c h a p t e r 3 , w e p r o p o s e s e v e r a l s o l u t i o n m e t h o d s f o r t h e s p l i t f e as i b i li t y p ro b le m (s f p ) , w h ic h is t o fi n d x e c w i th a x e q , if su c h p o in ts e x is t , w h e r e c a n d q a r e n o n e m p t y c l o s e d c o n v e x s e t s in r a n d r , r e s p e c t i v e l y , a n d a i s a n m b y二r e a l ma t r i x . b y r n e p r o p o s e d t h e c q a l g o r i t h m t o s o lv e t h e 3 f p , as s u mi n g t h a t p c a n d p q , t h e o r t h o g o n a l p r o j e c t i o n s o n t o c a n d q , a r e , as i l y c a l c u l a t e d . h o w e v e r , i n s o m e c as e s , i t i s d i ff i c u l t o r e v e n i m p o s s i b l e t o : o m p u t e p c a n d p q e x a c t l y . n o t i n g t h i s , b ase d o n t h e c q a l g o r i t h m a c i d mo s c o i i i ab s t r a c t c o n v e r g e n c e , w e p r e s e n t a p e r t u r b e d p r o j e c t i o n a l g o r i t h m t o s o l v e t h e s f p b y a p p l y i n g g e n e r a l iz e d k m t h e o r e m s i n c h a p t e r 2 , b e s i d e s , i n v i e w o f p r o p e r t y o f t h e s f p , w e a l s o g i v e s o m e i n e x a c t a l g o r i t h m s t o s o l v e i t . c o m p a r i n g w i t h t h e c q a l g o r i t h m , o u r a l g o r it h m s a r e m o r e p r a c t i c a l a n d e a s i e r t o i mp l e m e n t . i n t h e e n d o f t h i s c h a p t e r , w e p r o p o s e a n e w c o n j u g a t e g r a d i e n t m e t h o d t o s o l v e t h e s f p in o r d e r t o s p e e d u p t h e c o n v e r g e n c e i n t h e c a s e w h e n b o t h p c a n d p q c a n b e e a s i l y c a l c u l a t e d . c h a p t e r 4 d e a l s w i t h a 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 it y , w h i c h i n c l u d e s t h e t r a - d i t i o n a l v a r i a t i o n a l i n e q u a l i t y a s a s p e c i a l c a s e . we p r o v e t h e c o n v e r g e n c e r e s u l t s o f s o m e g e n e r a l i t e r a t i v e s c h e m e s f o r s o l v i n g t h i s v i u n d e r w e a k c o - c o e r c i v i t y a s - s u m p t i o n , w h i c h is p r o p o s e d b y q . y a n g i n h i s r e c e n t w o r k . we c a n s e e t h a t w e a k c o- c o e r c i v i t y a s s u m p t i o n i s u s u a l l y m i l d e r t h a n c o - c o e r c i v i t y a s s u m p t i o n , a n d t h e l a t t e r h a s b e e n w i d e l y u s e d i n a n a l y z i n g c o n v e r g e n c e p r o p e r t y o f p r o j e c t i o n me t h - o d s f o r s o l v i n g v a r i a t i o n a l i n e q u a l i t i e s . t h e n , w e e s t a b l i s h t h e c o n v e r g e n c e r e s u l t o f a f o r w a r d - b a c k w a r d s p l i t t i n g m e t h o d f o r fi n d in g a z e r o o f t h e o p e r a t o r t o n r u n d e r t h e w e a k c o- c o e r c i v i t y a s s u m p t i o n . f i n a l l y i n t h i s c h a p t e r , w e f u r t h e r m o d i f y t h e i t e r a t i v e s c h e m e s f o r s o l v i n g v i 饰 a d o p t i n g a n a r m i j o- l i k e l i n e s e a r c h . a t l a s t , in c h a p t e r 5 w e c o n s i d e r t h e c o n s t r a i n e d m a x i ma l m o n o t o n e i n c l u - s i o n p r o b l e m; w h i c h c o v e r s n u me r o u s a p p l i c a t i o n s . we fi r s t p r e s e n t s o m e p r o j e c - t i o n m e t h o d s b a s e d o n t h e b a s i c p r o x i ma l p o i n t a l g o r i t h m a n d f o r w a r d - b a c k w a r d s p l i t t i n g m e t h o d , t h e n w e ma in ly e x t e n d p . t s e n g s m o d i fi e d f o r w a r d - b a c k w a r d s p l i t t i n g m e t h o d f o r s o l v i n g i t . a f t e r t h i s , w e p r o p o s e r e l a x e d p r o j e c t i o n s c h e m e s o f t h e s e a l g o r i t h m s a n d e s t a b l i s h t h e c o n v e r g e n c e r e s u l t s . i n t h e r e l a x e d p r o j e c - t i o n s c h e m e s , w e u s e o r t h o g o n a l p r o j e c t i o n s o n t o a h a lf s p a c e 久 i n s t e a d o f c a t t h e k t h i t e r a t i o n , w h i c h c a n b e d i r e c t l y c a l c u l a t e d , a n d t h i s ma k e s t h e a l g o r i t h m s m u c h m o r e e a s i l y e x e c u t e d . f i n a l l y , w e d e fi n e s u b - l ip s c h i t z c o n t i n u i t y a n d s h o w t h a t t h e a l g o r i t h m s d i s c u s s e d s t i ll c o n v e r g e u n d e r t h i s m i l d e r a s s u m p t i o n . ke y w o r d s : f ix e d p o i n t , k m t h e o r e m , g e n e r a l i z e d k m t h e o r e m , n o n e x p a n s i v e , fi r m l y n o n e x p a n s i v e , t h e s p l it f e a s i b i l i t y p r o b l e m , v a r i a t i o n a l i n e q u a l i t y , m a x i m a l m o n o t o n e , c o-c o e r c i v e , w e a k l y c o-c o e r c i v e . i v 南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、保存、使用学位论文的规定， 同意如下各项内容:按照学校要求提交学位论文的印刷本和电子版 本;学校有权保存学位论文的印 刷本和电 子版，并采用影印、 缩印、 扫描、 数字化或其它手段保存论文; 学校有权提供目 录检索以 及提供 本学位论文全文或者部分的阅览服务; 学校有权按有关规定向国家有 关部门 或者机构送交论文的复印 件和电 子版; 在不以 赢利为目 的的 前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学 位 论 文 作 者 签 名 :. 走r势 冷 ”7 年 少 月 3 v 日 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名:学位论文作者签名: 解密时间:年月日 各密级的最长保密年限及书写格式规定如下: 卜 一内 部 、s 年 一ha =ck 5 纸 一可 少 于 乡 年 ) 撼 显 秘密*i o 年仗 最长1 0 年抓 . 可少于t o 年) 汁手 际;n * 2 d 年 ( r -k 2 0 军 ,0,7 好2 o 该 南开大学学位论文原创性声明 本人郑重声明: 所呈交的学位论文， 是本人在导师指导下， 进行 研究工作所取得的成果。 除文中己经注明引用的内容外， 本学位论文 的研究成果不包含任何他人创作的、 已 公开发表或者没有公开发表的 作品的内 容。对本论文所涉及的研究工作做出贡献的其他个人和集 体， 均已在文中以明确方式标明。 本学位论文原创性声明的 法律责任 由本人承担。 学位论文作者签名: 炎备 冷 2 -,od 7年少 月 3 a 日 c h a p t e r 1 . i n t r o d u c t io n a n d p r e li mi n a r ie s c h a p t e r 1 i n t r o d u c t i o n a n d p r e l i mi n a r i e s 1 . 1 i n t r od uc t i o n ma n y r e c e n t a d v a n c e s i n s c i e n c e , e c o n o m i c s a n d e n g i n e e r i n g r e l y o n n u m e r - i c a l t e c h n i q u e s f o r c o m p u t i n g s o l u t i o n s t o c o r r e s p o n d i n g o p t i m i z a t i o n p r o b l e m s . o p t i m i z a t i o n m e t h o d s a r e w i d e l y u s e d i n fi e l d s o f e c o n o m i c m o d e l i n g , fi n a n c e , n e t w o r k s a n d t r a n s p o r t a t i o n , d a t a b a s e s a n d c h i p d e s i g n , i m a g e p r o c e s s i n g , n u - c l e a r a n d m e c h a n i c a l d e s i g n , c h e m i c a l e n g i n e e r i n g d e s i g n a n d c o n t r o l , m o l e c u l a r b i o l o g y , a n d s o o n . o u r t a s k i s t o c o n s t r u c t a n d s t u d y o n v a r i o u 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 g v a r i o u s o p t i miz a t i o n m o d e l s . c o n s i d e r t h e c o n s t r a i n e d o p t i mi z a t i o n m in b (x ) c ) 三 d e 俨1 尹( ， 一i ) 0 ; a n d g i v e n a n y m a x i m a l m o n o t o n e o p e r a t o r t , r e a l n u m b e r c 0 , a n d x e ? , w e h a v e t h a t 0 e t ( x ) i f a n d o n l y i f j ( x ) = x ( 1 , 1 0 ) . a ll o f t h e s e f a c t s i m p l y t h e i m p o r t a n ce o f i n v e s t i g a t i n g m e t h o d s f o r fi n d i n g f ix e d p o i n t s o f s o m e c e rt a i n o p e r a t o r s . 1 . 3 ba s i c n o t a t i o n a n d o r g a n i z a t i o n t h r o u g h o u t t h i s t h e s i s , w e d e n o t e 勿 r t h e r e a l l i n e , a n d r n t h e e u c l i d e a n n - d i m e n s i o n a l s p a c e . 9 -l d e n o t e s a r e a l h i l b e r t s p a c e w i t h i n n e r p r o d u c t ( ， a n d i n d u c e d n o r m! 1 ( i n t h e c a s e o f r= r n , ( ， ) a n d a r e t h e e u c li d e a n i n n e r p r o d u c t a n d n o r m , r e s p e c t i v e l y . a n d t h e c o r r e s p o n d in g m a t r i x n o r m i s j ja jj = m a x jja x jj .) i is e it h e r th e id e n t it y m a p p in g o n 9 -l o r th e id e n tit y m a tr ix . t h eii= 11= 1 s u p e r s c r i p t t is t r a n s p o s e , a n d t h e s u p e r s c r i p t .- 1 i s t h e i n v e r s e o f a n o p e r a t o r o r a m a t r i x v i n d i c a t e s t h e g r a d i e n t o f a r e a l f u n c t i o n . we d e n o t e饰 p c c h a p t e r 1 . i n t r o d u c t i o n a n d p r e l i min a r ie s t h e o r t h o g o n a l p r o j e c t i o n s o n t o n o n e m p t y c l o s e d mi n i m i z e s 1 1 c 一x 1 1 o v e r a l l c e c . s e t c , t h a t i s , p c ( x ) t h e r e s t o f t h i s t h e s is i s o r g a n i z e d a s f o l l o w s . i n c h a p t e r 2 , w e in v e s t i g a t e i t e r a t i v e m e t h o d s f o r c o mp u t i n g fi x e d p o i n t s o f a n o p e r a t o r . we g e n e r a li z e t h e e x i s t i n g k r a s n o s e ls k i - m a n n i t e r a t i o n a n d t h e o r e m , t h e n , w e a p p l y t h e g e n e r a l i z e d k m s c h e m e s a n d t h e o r e m s t o t h e c o n v e x f e a s i b i l it y p r o b l e m a n d v a r i a t i o n a l i n - e q u a li t y . i n c h a p t e r 3 , w e p r o p o s e s e v e r a l s o l u t i o n m e t h o d s s p e c i a ll y f o r t h e s p li t f e a s i b i l i t y p r o b l e m . c h a p t e r 4 d e a ls w i t h a g e n e r a l v a r i a t i o n a l i n e q u a li t y ( 1 . 2 .2 ) , w h i c h c o n t a i n s t h e t r a d i t i o n a l v i a s a s p e c i a l c a s e , u n d e r w e a k c o - c o e r c i v i t y . i n c h a p t e r 5 w e c o n s i d e r t h e c o n s t r a in e d m o n o t o n e i n c l u s i o n p r o b l e m, a n d e x t e n d p . t s e n g s m o d i fi e d f o r w a r d - b a c k w a r d s p l i t t i n g m e t h o d ( 1 5 ) f o r s o l v i n g i t . a t l a s t , w e g i v e a s u m m a r y f o r t h e w h o l e t h e s i s c h a p t e r 2 . k r a s n o s e l s k i- ma n n t h e o r e m a n d i t s g e n e r a l i z a t i o n s c h a p t e r 2 kr a s n o s e l s k i - m a n n t h e o r e m a n d i t s g e n e r a l i z a t i o n s we k n o w t h a t a ll t h e o p t i m i z a t i o n p r o b l e m s m e n t i o n e d i n c h a p t e r 1 c a n b e t r a n s f o r m e d i n t o a p r o b l e m o f fi n d i n g a f ix e d p o in t o f s o m e o p e r a t o r s . t h i s f a c t l e a d s u s t o s t u d y o n t h e f ix e d p o i n t p r o b l e m i n t h e p r e s e n t c h a p t e r . t h e k r a s n o s e ls k i - m a n n ( k m ) a p p r o a c h f o r fi n d i n g a fi x e d p o i n t o f n i s f o l l o w i n g : t k + 1 = ( 1 一 a k ) 2 k + a k n x k w h e r e n i s a n o n e x p a n s iv e o p e r a t o r o n a h i l b e r t s p a c e a n d a k e 0 , 1 . t h e k m s c h e m e p r o v i d e s a u n i fi e d f r a m e w o r k f o r m a n y a lg o r i t h m s i n v a r i o u s fi e l d s , a n d t h e a s s o c i a t e d k r a s n o s e l s k i - ma n n t h e o r e m a s s e rt s t h a t t h i s i t e r a t i v e p r o c e d u r e 十 刀 c o n v e r g e s w e a k l y t o a f i x e d p o i n t o f n , p r o v i d e d 艺a k ( 1 一 a k ) =+ o o , w h e n e v e r 无 -o s u c h p o i n t s e x i s t . c h a p t e r 2 . k r a s n o s e l s k i - ma n n t h e o r e m a n d i t s g e n e r a l i z a t i o n s g o r i t h m w h e n e v e r t h e p r o b l e m s t u d i e d h a s n o s o l u t i o n s . f o r e x a m p l e , b o r w e i n e t .a l . s h o w e d i n 1 7 t h a t i x p r o d u c e d 场k r a s n o s e l s k i - m a n n ( k m ) i t e r a t i o n w a s u n b o u n d e d i f t h e n o n e x p a n s i v e o p e r a t o r n h a d n o fi x e d p o i n t s , a n d e c k s t e i n a n d b e r t s e k a s p r o v e d i n 1 0 s i m il a r r e s u l t s f o r t h e p r o x i m a l p o i n t a l g o r i t h m f o r ma x i ma l mo n o t o n e o p e r a t o r s . i n t h i s c h a p t e r , w e f u rt h e r i n v e s t i g a t e t h e c o n v e r g e n c e r e s u l t o f t h e k m i t e r a t i o n . f i r s t , w e e x t e n d t h e r e s u l t s i n 4 , 1 7 , 1 8 f o r t h e k m i t e r a t i o n t o t h e c a s e w h e n n i s fi r m l y n o n e x p a n s i v e a n d r e l a x a t i o n p a r a m e t e r s n o w a l l o w e d t o b e i n t h e i n t e r v a l 0 , 2 , w h e r e w e o ff e r a s i m p l e r p r o o f t h a n t h a t i n 1 7 . t h e n , w e f u rt h e r d is c u s s o n t h e c o n v e r g e n c e p r o p e r t i e s o f i n e x a c t a n d p e r t u r b e d k m s c h e m e s . i n p a r t i c u l a r , w e s h o w t h a t x g e n e r a t e d b y t h e k m i t e r a t i o n a n d i n e x a c t a n d p e rt u r b e d k m i t e r a t i o n s a r e u n b o u n d e d i f n h a s n o fi x e d p o i n t s , a n d o u r p r o o f i s d i r e c t a n d e a s y . f o r i ll u s t r a t i o n , w e a ls o a p p ly t h e s e g e n e r a l iz a t i o n s t o s o l v i n g t h e c o n v e x f e a s i b i l i t y p r o b l e m a n d v a r i a t i o n a l i n e q u a l i t i e s . 2 . 1 kr a s n o s e l s k i - m a n n t h e o r e m i n s p i t e o f i t s s i m p l e f o r m , t h e k r a s n o s e l s k i - m a n n ( k m ) i t e r a t io n is r e m a r k - a b l y u s e f u l f o r fi n d i n g fi x e d p o i n t s o f a n o n e x p a n s i v e o p e r a t o r n, a n d p r o v i d e s a u n i fi e d fr a m e w o r k f o r m a n y a lg o r it h m s i n v a r i o u s fi e l d s . i n d e t a i l , l e t h b e a r e a l h i l b e r t s p a c e w i t h i n n e r p r o d u c t ( ， ) a n d i n - d u c e d n o r m . b y t h e w e ll - k n o w n d e fi n i t i o n , a n o p e r a t o r n o n 9 -t is c a l l e d n o n e x p a n s i v e i f , f o r a n y x a n d y i n 9 , j n x 一n y 0 s u c h t h a t (g ( x ) 一 g (y ), x 一 y ) ? v llg ( x ) 一 g ( y ) ii2 we s e e t h a t a fi r m l y n o n e x p a n s i v e o p e r a t o r f i s 1 - c o - c o e r c i v e . i t i s al s o k n o w n t h a t a n o p e ra t o r n is n o n e x p a n s i v e if a n d o n ly if its c o m p le m e n t i 一 n is 盖 - c o - c o e r c i v e ( 4 ) . n o w w e c a n g e n e r a li z e t h e k m t h e o r e m a s f o l l o w s t h e o r e m 2 . 2 . l e t n b e a n o n e x p a n s i v e o p e r