（计算数学专业论文）求解分裂可行问题的几个投影算法.pdf

摘要 摘要 分裂可行问题( s f p ) 是要求z c ，使a x q ，如果这样的z 存在。其中集 合c 和q 分别是和r g 中的非空闭凸集，a 是mxn 阶实矩阵。这类问题 产生于信号处理中，特别是在图像重构和其他的图像还原问题中。同时，分裂可 行问题还与凸可行问题密切相关。凸可行问题( c f p ) 就是要找有限个闭凸集的非 空交集中的点，它在数学，物理等许多学科中是一个基本的问题。因此，研究如 何求解分裂可行问题具有重要的意义。 c q 算法是求解s f p 的一种简洁的方法。在本文中，我们首先给出了c q 算 法的一个非精确松弛格式，当正交投影岛和尸。不容易求得时，此格式比c q 算 法更具实用性。然后我们讨论了变步长的c q 算法，并且说明，不论是带固定步 长的c q 算法，还是变步长的c q 算法，都是梯度投影算法的一个具体实现。相 对于固定步长，变步长可以提高算法的收敛速度。此外我们还提出了变步长c q 算法的非精确格式以及非精确松弛格式。最后，我们在一个更弱的假设下给出了 求解分裂可行问题的一个方法，而且此方法本身向我们揭示了凸可行问题和不动 点问题的紧密联系。 关键词：分裂可行问题凸可行问题非精确格式投影算法 a b s t r a c t a b s t r a c t t h e s p l i tf e a s i b i l i t yp r o b l e m ( s f p ) i st of i n dz c ，w i t ha 2 7 q ，i fs u c hze x i s t ， w h e r eca n dqa l en o n e m p t yc l o s e dc o n v e xs e t si nr a n dr m ，r e s p e c t i v e l y , a n dai s a nm b yn r e a lm a t r i x s u c hp r o b l e m sa r i s ei ns i g n a lp r o c e s s i n g ，e s p e c i a l l yi np h a s e r e t r i e v a la n do t h e ri m a g er e s t o r a t i o np r o b l e m s m e a n w h i l e t h es f pi sc l o s e l yr e l a t e dt o t h ec o n v e xf e a s i b i l i t yp r o b l e m ( c f p ) ，i e ，t of i n dap o i n ti nt h en o n e m p t yi n t e r s e c t i o n o ff i n i t e l ym a n yc l o s e da n dc o n v e xs e t s t h el a t t e ri saf u n d a m e n t a lp r o b l e mi nm a n y d i s c i p l i n e s ，s u c ha sm a t h e m a t i c sa n dp h y s i c a ls c i e n c e ，e t c s oi ti so fg r e a tm e a n i n gt o s t u d yo nh o w t os o l v et h es p l i tf e a s i b i l i t yp r o b l e m t h es o - c a l l e dc qa l g o r i t h mi sab r i e fm e t h o df o rs o l v i n gt h es f pi nt h i sp a p e r , w ef i r s tg i v ea ni n e x a c tr e l a x e ds c h e m eo ft h ec qa l g o r i t h m ，w h i c hi sm o r ep r a c t i c a b l et h a nt h ec q a l g o r i t h mw h e no r t h o g o n a lp r o j e c t i o n sp ca n d 砀a r en o te a s yt o g e t t h e nw ed i s c u s sa b o u tt h ev a r i a b l es t e p s i z ec qa l g o r i t h ma n dd e m o n s t r a t et h a t t h ec q a l g o r i t h mw i t hf i x e ds t e p s i z ea n dv a r i a b l es t e p s i z ec qa l g o r i t h ma l eb o t ha s p e c i f i cr e a l i z a t i o no fg r a d i e n tp r o j e c t i o na l g o r i t h m t h ev a r i a b l es t e p s z e c o m p a r i n g w i t haf i x e do n e ，c a na c c e l e r a t et h e c o n v e r g e n c eo fa l g o r i t h m w ea l s oo f f e ra ni n e x a c t s c h e m eo fv a r i a b l es t e p s i z ec qa l g o r i t h ma n di t sr e l a x e dv e r s i o n i nt h ee n d ，u n d e ra m i l d e ra s s u m p t i o n w ep r e s e n tas o l u t i o nm e t h o df o rt h es f pm o r e o v e lt h em e t h o d i t s e l fs h o w su si n t i m a t er e l a t i o n sb e t w e e nt h ec f pa n dt h ef i x e dp o i n tp r o b l e m k e yw o r d s ：s p l i tf e a s i b i l i t yp r o b l e m c o n v e xf e a s i b i l i 哆p r o b l e m i n e x a c t s c h e m e p r o j e c t i o na l g o r i t h m 南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名： 年月日 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名：学位论文作者签名： 解密时间：年月日 各密级的最长保密年限及书写格式规定如下： r 7 。一一7 。一 | 内部5 年( 最长5 年，可少于5 年) l i 秘密1 0 年( 最长1 0 年，可少于1 0 年) l | 机密一t 2 0 年( 最长2 0 年，可少于2 0 年) ，。? 。一。一。一，。j ： 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行研究工作 所取得的成果。除文中已经注明引用的内容外，本学位论文的研究成果不包含 任何他人创作的、己公开发表或者没有公开发表的作品的内容。对本论文所涉 及的研究工作做出贡献的其他个人和集体，均已在文中以明确方式标明。本学 位论文原创性声明的法律责任由本人承担。 学位论文作者签名： 年月日 c h a p t e r1 i n t r o d u c t i o n i it w op r o b l e m s ：t h ec f pa n ds f p t h ec o n v e xf e a s i b i 盯t yp r o b l e m ( c f p ) i st of i n dap o i n ti nt h en o n e m p t yi n t e r - s e c t i o no ff i n i t e l ym a n yc l o s e da n dc o n v e xs e t s ，s u c ha s q 0 坠1 i t saf u n d a m e n t a l p r o b l e mi nm a n ya r e a so fm a t h e m a t i c sa n dp h y s i c a ls c i e n c e s ，( s e e ，e g ，c o m b e t t e s 【21 ，2 2 a n dr e f e r e n c e st h e r e i n ) i th a sb e e nu s e dt om o d e ls i g n i f i c a n tr e a l - w o r l dp r o b - l e m si ni m a g er e c o n s t r u c t i o nf r o mp r o j e c t i o n s ，( s e e ，e g ，h e r m a n 【2 4 】) ，i nr a d i a t i o n t h e r a p yt r e a t m e n tp l a n n i n g ，( s e ec e n s o r , a l t s c h u l e ra n dp o w l i s 【18 】a n dc e n s o r 19 1 ) ， a n di nc r y s t a l l o g r a p h y , ( s e em a r k s ，s i n k l e ra n dl a n d r e e 【2 5 1 ) ，t on a m eb u taf e w , a n d h a sb e e nu s e du n d e ra d d i t i o n a ln a m e ss u c ha ss e t t h e o r e t i ce s t i m a t i o no rt h ef e a s i b l es e t a p p r o a c h t r a d i t i o n a l l y , ac o m m o na p p r o a c ht os u c hp r o b l e m si st ou s ep r o j e c t i o na l g o r i t h m s , ( s e e ，e g ，b a u s c h e ka n db o r w e i n 【3 1 ) ，w h i c he m p l o yo r t h o g o n a lp r o j e c t i o n s ( i e ，n e a r e s tp o i n tm a p p i n g s ) o n t ot h ei n d i v i d u a ls e t sq i t h eo r t h o g o n a lp r o j e c t i o n r ( z ) o fap o i n tz 舻o n t oa c l o s e dc o n v e xs e tq 册i sd e f i n e db y p h ( z ) ：= a t g m i n l l z z i l 2 iz q ) ， w h e r e ，t h r o u g h o u tt h i sp a p e r , ”i2a n d ( ，) d e n o t et h ee u c l i d e a nn o r ma n d i n n e r p r o d u c t r e s p e c t i v e l y , i n 舻i nr e c e n ty e a r s ，m u c hw o r kh a sb e e nd o n ew i t hg e n e r - a l i z e dd i s t a n c ef u n c t i o n sa n dg e n e r a l i z e dp r o j e c t i o n sa s s o c i a t e dw i t ht h e ms u g g e s t e d b yb r e g m a n 【2 6 1 t h a tm e a n s d i f f e r e n td i s t a n c ef u n c t i o n sg i v er i s et od i f f e r e n tp r o j e c - t i o n s ，i n c l u d i n go r t h o g o n a lp r o j e c t i o n sa sas p e c i a lc a s e m e a n w h i l e ，s e v e r a lp r o j e c t i o n a l g o r i t h ms c h e m e sf o rt 1 1 ec 0 1 v e xf e a s i b i l i t yp r o b l e m ，w h i c ha r e ，i ng e n e r a l ，e i t h e r s e - q u e n t i a lo rs i m u l t a n e o u so rb l o c k i t e r a t i v e ，h a v eb e e np r o p o s e d ，( s e e ，e g ，c e n s o ra n d z e n i o s 【13 】a n dt h er e v i e wp a p e ro fb a u s c h e ka n db o r w e i n 【3 d i tg a l lb es a i dt h a t ， i nt h ec o u r s eo fs o l v i n gt h ec f p , t h ep r o j e c t i o na l g o r i t h mh a su n d e r g o n ec o n t i n u o u s d e v e l o p m e n ta n dt r e m e n d o u sp r o g r e s s a n o t h e rp r o b l e mi sc a l l e dt h es p l i tf e a s i b i h t yp r o b l e m ( s f p ) l e tca n dq b e n o n e m p t yc l o s e dc o n v e xs e t si nr a n d 尺m ，r e s p e c t i v e l y , a n da b ea nm b yn r e a l c h a p t e r1 i n t r o d u c t i o n m a t r i x t h es f pi st of i n dz c ，w i t ha z q ，i fs u c hze x i s t s u c hp r o b l e m sa r i s ei n s i g n a lp r o c e s s i n g ，e s p e c i a l l yi np h a s er e t r i e v a la n do t h e ri m a g er e s t o r a t i o np r o b l e m s ， ( s e e ，e g ，【l ，2 1 ) p a r t i c u l a r l y , k o t z e re ta 1 【2 】h a v eu s e dt h ef o r m u l a t i o no fa ”s p l i t ” f e a s i b i l i t yp r o b l e mt om o d e lt h ed e s i g no fan o n l i n e a rs y n t h e t i cd i s c r i m i n a n tf i l t e rf o r o p t i c a lp a t t e r nr e c o g n i t i o n i nf a c t 。t h es f pi sas p e c i a lk i n do fc o n v e xf e a s i b i l i t y p r o b l e m t h a ti s ，l e ta 一1 ( q ) = zia x q ) ，w h i c hi sa l s oan o n e m p t yc l o s e d c o n v e xs e ta n df=c na 。1 ( q ) ，t h e no u rp r o b l e mi st of i n ds o m ep o i n t si n 肛 at w o s e tc f p s op r o j e c t i o na l g o r i t h m sf o rs o l v i n gt h ec f p , i n v o l v i n go r t h o g o n a lo r g e n e r a l i z e dp r o j e c t i o no n t o t h ei n d i v i d u a lc o n v e xs e t s ，c a nb et h e na p p l i e dt os o l v et h e s f p f r o ma n o t h e rp o i n to fv i e w , i fw el e ta b e ，i e ，i d e n t i c a lm a t r i x ，t h e nt h es f pc a n b ec o n s i d e r e da sag e n e r a l i z a t i o no ft w o - s e tc f p i ti sas i m i l a rc a s ew h e n c o n s i d e r i n g m o r et h a nt w os e t s ( s e e ，e g ，c e n s o ra n dz e n i o s 【13 】) t h a ts h o w st h ec f pa n ds f p a r ec l o s e l yr e l a t e dt oe a c ho t h e r i nt h i sp a p e r , w em a i n l yf o c u so ns e v e r a lp r o j e c t i o n a l g o r i t h m sf o rs o l v i n gt h es f p 1 2 w h y c h o o s ep r o j e c t i o nm e t h o d s ? t h er e a s o nw h yf e a s i b i l i t yp r o b l e m so fv a r i o u sk i n d sa r el o o l ( e da tf r o mt h ev i e w - p o i n to fp r o j e c t i o nm e t h o d sc a nb ea p p r e c i a t e db yt h ef o l l o w i n gb r i e fc o m m e n t s p r o j e c t i o n so n t os e t sa r eu s e di naw i d ev a r i e t yo fm e t h o d si no p t i m i z a t i o nt h e o r yb u tn o t e v e r ym e t h o dt h a tu s e sp r o j e c t i o n sr e a l l yb e l o n g st ot h ec l a s so fp r o j e c t i o nm e t h o d s p r o j e c t i o nm e t h o d sa r ei t e r a t i v ea l g o r i t h m st h a tu s ep r o j e c t i o n so n t os e t sw h i l er e l y i n go nt h eg e n e r a lp r i n c i p l et h a tw h e naf a m i l yo f ( u s u a l l yc l o s e da n dc o n v e x ) s e t si s p r e s e n tt h e np r o j e c t i o n so n t ot h eg i v e ni n d i v i d u a ls e t sa r ee a s i e rt op e r f o r mt h a np r o j e c t i o n so n t oo t h e rs e t s ( i n t e r s e c t i o n s ，i m a g es e t su n d e rs o m et r a n s f o r m a t i o n ，e t c ) t h a t a r ed e r i v e df r o mt h eg i v e ni n d i v i d u a ls e t s a p r o j e c t i o na l g o r i t h mr e a c h e si t sg o a l ，r e l a t e dt ot h ew h o l ef a m i l yo fs e t s ，b y p e r f o r m i n gp r o j e c t i o n so n t ot h ei n d i v i d u a ls e t s p r o j e c t i o na l g o r i t h m se m p l o yp r o j e c t i o n so n t oc o n v e xs e t si nv a r i o u sw a y s t h e ym a yu s ed i f f e r e n tk i n d so fp r o j e c t i o n s a n d ，s o m e t i m e s ，e v e nu s ed i f f e r e n tp r o j e c t i o n sw i t h i nt h es a m ea l g o r i t h m t h e ys e r v e t os o l v eav a r i e t yo fp r o b l e m sw h i c ha r ee i t h e ro ft h ef e a s i b i l i t yo rt h eo p t i m i z a t i o n t y p e s 1 h e yh a v ed i f f e r e n ta l g o r i t h m i cs t r u c t u r e s ，o fw h i c hs o m ea r ep a r t i c u l a r l ys u i t a b l ef o rp a r a l l e lc o m p u t i n g ，a n dt h e yd e m o n s t r a t en i c ec o n v e r g e n c ep r o p e r t i e sa n d o r 2 c h a p t e r1 i n t r o d u c t i o n g o o dl n i t i a lb e h a v i o rp a t t e r n s a p a r tf r o mt h e o r e t i c a li n t e r e s t ，t h em a i na d v a n t a g eo fp r o j e c t i o nm e t h o d s ，w h i c h m a k e st h e ms u c c e s s f u li nr e a l w o r l da p p l i c a t i o n s ，i sc o m p u t a t i o n a l t h e yc o m m o n l y h a v et h ea b i l i t yt oh a n d l eh u g e s i z ep r o b l e m so fd i m e n s i o n sb e y o n dw h i c ho t h e r , m o r e s o p h i s t i c a t e dc u r r e n t l ya v a i l a b l e ，m e t h o d sc e a s et ob ee f f i c i e n t t h i si ss ob e c a u s et h e b u i l d i n gb r i c k so fap r o j e c t i o na l g o r i t h ma r et h ep r o j e c t i o n so n t ot h eg i v e ni n d i v i d u a l s e t s ( a s s u m e da n da c t u a l l ye a s yt op e r f o r m ) a n dt h ea l g o r i t h m i cs t r u c t u r ei se i t h e rs e q u e n t i a lo rs i m u l t a n e o u s ( o ri n b e t w e e n ) s e q u e n t i a la l g o r i t h m i cs t r u c t u r e sc a t e rf o r t h er o w - a c t i o na p p r o a c h ，( s e ec e n s o r 【16 】) ，w h i l es i m u l t a n e o u sa l g o r i t h m i cs t r u c t u r e s f a v o rp a r a l l e lc o m p u t i n gp l a t f o r m s ，( s e e ，e g ，c e n s o ra n dg o r d o n 【15 1 ) 1 3 e a r l yw o r ko ns o l v i n gt h es f p t h ec o n c e p t i o no ft h es p l i tf e a s i b i l i t yp r o b l e mw a sb r o u g h tu pb yc e n s o ra n d e l f v i n gi n 【17 1f o rt h ef i r s tt i m e ，i nw h i c ht h e yu s e dt h e i rs i m u l t a n e o u sm u l t i p r o j e c t i o n s e d g o r i t h m ( s m a ) o nt h es f p , t oo b t a i na ni t e r a t i v em e t h o dt h a ts o l v e st h es f p f o rt h e c a s em = n w i t hs o m em o d i f i c a t i o n 。t h e i rm e t h o da p p l i e dt ot h ec a s em n t h e ni n 4 】，u s i n gt h em s g pa l g o r i t h mt h a th ep r o p o s e db e f o r e ， b y r n eo b t a i n e da ni t e r a t i v es o l u t i o nt ot h es f pf o rt h ec a s em n a s w e l la si t e r a t i v e a l g o r i t h m sf o rt h er e m a i n i n gc a s e st h a ta r es o m e w h a ts i m p l e rt h a nt h o s eo b t a i n e db y u s i n gt h es m a l a t e ri n 【6 1 ，h i sm u l t i p r o j e c t i o ns e q u e n t i a ls p l i tf e a s i b i l i t ya l g o r i t h m w a sn a m e db yt h ec q a l g o r i t h m i th a st h ef o l l o w i n gi t e r a t i v es t e p ： x k + l= 昂( z 七一7 a t ( ，一p q ) a x 七) ， w h e r e7 ( 0 ，2 l ) ，w i t hlt h el a r g e s te i g e n v a l u eo ft h em a t r i xa t aa n d 尼a n dp q d e n o t et h eo r t h o g o n a lp r o j e c t i o n so n t oca n dq ，r e s p e c t i v e l y c o m p a r i n gw i t hc e n - s o t sa l g o r i t h ma n do t h e r so b t a i n e dl a t e r , t h ec q a l g o r i t h mi n v o l v e so n l yt h eo r t h o g o n a l p r o j e c t i o n so n t oc a n dq ，w h i c hb y r n eh a sa s s u m e da r ee a s i l yc a l c u l a t e d ，a n di n v o l v e s n om a t r i xi n v e r s e s t h a t st h em a i na d v a n t a g eo ft h ec qa l g o r i t h m b e s i d e s ，i fai s n o r m a l i z e ds ot h a te a c hr o wh a sl e n g t ho n e ，t h e nld o e sn o te x c e e dt h em a x i m u mn u m b e ro fn o n z e r oe n t r i e si na n yc o l u m no fa ，w h i c hp r o v i d e sa h e l p f u le s t i m a t eo fl f o r s p a r s em a t r i c e s p a r t i c u l a rc a s e so ft h ec q a l g o r i t h ma r et h el a n d w e b e ra n dp r o j e c t e dl a n d w e b e r 3 c h a p t e r1 i n t r o d u c t i o n m e t h o d sf o ro b t a i n i n ge x a c to ra p p r o x i m a t es o l u t i o n so ft h el i n e a re q u a t i o na x = 6 ：t h e a l g e b r a i cr e c o n s t r u c t i o nt e c h n i q u eo fg o r d o n ，b e n d e ra n d h e r m a ni sap a r t i c u l a rc a s e o fab l o c k i t e r a t i v ev e r s i o no ft h ec qa l g o r i t h m o n ea p p l i c a t i o no ft h ec qa l g o r i t h m w h i c hi st h es u b j e c to fo n g o i n gw o r ki sd y n a m i ce m i s s i o nt o m o g r a p h i ci m a g er e c o n s t r u c t i o n ，i nw h i c h t h ev e c t o rzi st h ec o n c a t e n a t i o no fs e v e r a li m a g e sc o r r e s p o n d i n gt o s u c c e s s i v ed i s c r e t et i m e s t h em a r xaa n dt h es e tqt h e nc a nb es e l e c t e dt oi m p o s e c o n s t r a i n t so nt h eb e h a v i o ro v e rt i m eo ft h ei n t e n s i t i e sa tf i x e dv o x e l s ，a sw e l la st o r e q u i r ec o n s i s t e n c y ( o rn e a rc o n s i s t e n c y ) w i t hm e a s u r e d d a t a i tm a yb es e e nt h a ti ft h eo r t h o g o n a lp r o j e c t i o n so n t oca n dqa r ee a s i l yc a l - c u l a t e d ，t h et o t a lc o s to fc o m p u t a t i o ni sn o tg r e a t i n 【6 】，b y r n ea s s u m e dt h a tb o t h p r o j e c t i o n sa r ee a s i l yc a l c u l a t e di nt h ec qa l g o r i t h m h o w e v e r , i ns o m e c a s e si ti si m - p o s s i b l eo rn e e d st o om u c hw o r kt oe x a c t l yc o m p u t e t h eo r t h o g o n a lp r o j e c t i o n t h e r e - f o r e ，i ft h i sc a s ea p p e a r s ，t h ee f f i c i e n c yo fp r o j e c t i o n t y p em e t h o d s ，i n c l u d i n gt h ec q a 培o f i t h m ，w i l lb es e r i o u s l ya f f e c t e d i nt h a ts i t u a t i o n ，i n e x a c tt e c h n o l o g yp l a y sa n i m p o r t a n tr o l ei nd e s i g n i n ge f f i c i e n t ，e a s i l yi m p l e m e n t e da l g o r i t h m sf o rs o l v i n go p t i - m i z a t i o np 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 ds oo n ( s e e ，e g ，【9 ，10 ，1 1 ，12 】) t h er e l a x e dp r o j e c t i o nm e t h o dm a yb ev i e w e da so n eo ft h ei n e x a c tp r o j e c t i o n t y p e m e t h o d s i n 【2 7 ，b yu s i n gt h er e l a x e dp r o j e c t i o nt e c h n o l o g y , y a n gp r e s e n t e d ar e l a x e d c qa l g o r i t h mf o rs o l v i n gt h es f p , w h e r eh eu s e dt w oh a l f s p a c e s 伉a n dq 惫i np l a c eo f ca n dq ，r e s p e c t i v e l y , a tt h ek t hi t e r a t i o na n dt h eo r t h o g o n a lp r o j e c t i o n so n t oc ka n d q 知a r ee a s i l ye x e c u t e d i na n o t h e rp a p e r 【3 0 1b yy a n ga n dz h a o ，t h ei n v e r s ep r o b l e mo ft h es p l i tf e a s i b i l i t y p r o b l e mw a sd e f i n e d ，w h i c hw a s c a l l e di n v e r s es p l i tf e a s i b i l i t yp r o b l e m ( i s f p ) b yt h e e q u i v a l e n tr e l a t i o n sb e t w e e nt h es f p a n ds o m eo r t h o g o n a lp r o j e c t i o nf i x e dp o i n t p r o b - i c t u sa n dt h ei n v e r t i b i l i t yb e t w e e nt h es f pa n di s f p , t h e yp r e s e n t e ds e v e r a lp r o j e c t i o n a l g o r i t h m sf o rs o l v i n gt h es f 只a m o n gw h i c h ，a ni n e x a c ts c h e m e o ft h ec q a l g o r i t h m w a sp r o p o s e da n dp r o v e dt ob ec o n v e r g e n t i th a sb e e nn o t i c e dt h a tb o t ht h ec qa l g o r i t h ma n dt h er e l a x e dc qa l g o r i t h mu s ea f i x e ds t e p s i z er e l a t e dt ot h el a r g e s te i g e n v a l u eo ft h em a t r i xa t a ，w h i c hs o m e t i m e sa f - f e c t sc o n v e r g e n c eo ft h ea l g o r i t h m s i n 【2 0 ，b q ua n dn x i up r e s e n t e dm o d i f i c a t i o n s