（计算数学专业论文）关于凸可行问题投影算法的研究.pdf

摘要 大量的数学和物理方面的问题可以归结为寻找多个凸集 的交集的问题即凸可行问题( c o n v e xf e a s i b i l i t yp r o b l e m ) 。凸可 行问题的投影算法在提出之后有许多相关的论文研究了其收敛 速度以及对其改进包括松弛( r e l a x a t i o n ) ，加权( w e i g h t ) 以及代 替( s m r o g a t e ) 投影等技巧。我们首先给出了投影算法的一个比较 全面的介绍，包括其各种改进技巧和算法的收敛性质，我们研 究了代替投影方法所使用的超平面的构造。此后我们提出了一种 新的加权方式，这种方式是根据当前迭代点到集合的距离关系来 定义加权方式的，并且比较了我们这种加权方式和现在常用的平 均加权的方式，证明了我们的这种加权方式在理论上要比平均加 权要更好。 此外，由c e n s o r 等提出的多集合的分裂可行问题( m u i t i p l e - s e t ss p u tf e a s i b i l i t yp r o b l e m ) 是凸可行问题和分裂可行问 题( s p u tf e a s i b i l i t yp r o b l e m ) 的推广，我们对于应用到其上面 的投影算法的收敛性进行了证明。由于多集分裂可行问题是二个 概括了凸可行和分裂可行的更广泛的一个框架。因此在其上的投 影算法值得进一步研究。 关键字：次梯度，凸可行问题，投影算法，f e j 自单调，分裂可行 问题，多集分裂可行问题 a b s t r a c t m a n ym a t h e m a t i c a la n dp h y s i c a lp r o b l e m sc a nb er e d u c e d t ot h e p r o b l e m so f 丘n d i n gt h ei n t e r s e c t i o no fs e v e r 融c o n v e xs e t s ，n 锄e ly ， c o r l v e xf b a s i b i l i t yp r o b l e m ( c f p ) t h ep r o j e c t i o na l g o r i t h mf o r c o n v e xf e a s i b i l i t yp r o b l e mh a sb e e np r o p o s e df o rol o n gt i l ea n d m a n y 盯t i c l e sh a ei n v e s t i g a t e dt h er a t eo fc o n v e r g e n c ei nu n i 丘e d 丘a m e w o r ka b o u ts e v e r a lm o d m c a t i o n ss u 出a sr e l a x a t i o n ，w e i g h t a n ds u r r o g a t ep r o j e c t i o n t h i sp a p e ra tf i r s tg i v e sac o m p r e h e n s i v e i n t r o d u c t i o na b o u tp r o j e c t i o na 1 9 6 r i t h mw i t hv a r i o u sm o d i f i c a t i o 璐 a n dc o m r e r g e n tp r o p e r 订o fa l g o r i t h m ，t h e ni n v e s t i g a t e so n es p e c i a l h y p e r p l a n ef o rs u r r o g a t em e t h o d j a n dp r o p o s e sam e t h o d f o rw e i g h t a c c o r d i n g t ot h ed i s t a n c eb e t w e e nc u r r e n tp o i n ta n dt h ec o n v e xs e t s ， c o m p a r i n gt h i sw e i g h tm e t h o dw i t ha v e r a g ew e i g h t ，d e m o l l s t r a t i n g t h a tf o r m e ri sb e t t e rt h a nl a t t e ri nt h e o r e t i ca n 出y i s a d d i t i o n “y if o rt h er e c e n t l yp r o p o s e dm 山t i p l e - s e ts p l i tf e a s i b i l i t yp r o b l e mt h a tc o m p r i s e sc f p a n ds f p ( s p l i tf e a s i b i l i t yp r o b _ 1 e m ) ，w eg i v ead e t a i l e dp r o o f f o rap r o j e c t i o na l g o r i t h m s i n c ei t i sab r o a d e rf r 锄e w o r kc o n t a i n i n gc f pa n ds f p ，t h ep r o j e c t i o n 出g o r i t h m sf o ri td e s e r v e sf u r t h e ri n v e s t i g a t i o n k e y w o r d s s u b g r a d i e n t ，c o n v e xf e a s i b m t yp r o b l e m ，p r o j e c t i o n a l g o r i t h m s ，f 萄白m o n o t o n e ，s p l i tf b a s i b m t yp r o b l e m ，m u l t i p l e s e tf e a s i b i l i t yp r o b l e m i i y 9 6 8 6 9 3 南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务：学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名：燃康 口厶年歹月；d 日 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名：学位论文作者签名： 燃 解密时间：年月日 各密级的最长保密年限及书写格式规定如下 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 学位论文作者签名：撇 功。毛年，月j 。日 c h j a p t e r 1 i n t r o d u c t i o n 1 1c o i e xf e a s i b i l i t yp r o b l e m t h e r ea r em a l l yp r o b l e m sf r o mm a t h e m a t i c s ，p h y s i c sa n de n g i n e e r i n gc a nb er e d u c e dt o6 n dac o m m o np o i n to faf a m i l yo fc l o s e da n dc o n v e xs e t si n 对( o ri nh i l b e r t s p a c e ，b u “nt 1 1 i sa r t i c l ew ei n v e g t i g a t em a j n l yi nt h ee u c l i ds p a c er “，越1 dm a n y o u t c o m e sc a nb ee ) ( 七e n d e dt oh i l b e r ts p a c e ) t h i sh n do fp r o b l e m sa uh a et h ef o l l o w i n g f o r m u l a t i o nc a 王l e dc 0 删e 七f e o s 曲谢幻p m b z e m r 删 1 ，2 ，3 ，4 】： ( g f p ) ：f i n d i n gz g ，w h e r eg = f1 a 扛：l i nt h ea b o v e ，e v e r yo n eo fg 0 = 1 ，) i sac l o s e dc o n v e xs u b s e to f 船( o rh i l b e r t s p a c e ) h e r e ，t h es e tg i sc o n e zs e tm e a n sf o ra j l yt w op o i n tz 1 ，z 2 ga n dv a o ，1 】 t h e na 。1 + ( 1 一a ) z 2 g ：af u n c t i o nf ( x ) w i t hd o m ( ，) r ”a 以dd o m ( f ) i sc o n v e xs e t t h e nf ( x ) i sc o 舢血扎c 抚。扎m e a l l st h a tv a o ，1 1 ，z ，可d o m ( f ) ，w eh a v e ，( a z + ( 1 一a ) f ) a ，扛) + ( 1 一a ) ，0 ) a d m t i o n 越1 乳( c f p ) h a sa ne q u i v a l e n tf 1 1 n c t i o n a lc 0 1 1 1 1 t e r p 缸“n v 0 1 v i n gc o n v e x i n e q u a l i t i e s ( c i ) ：f i n d ，i fp o s s i b l e ，a tl e a s to n e xs u c ht h a t ( z ) s 挑，i = l ，几 w h e r ee a c h ：黔一ri s 弘o s i c o 舢e za n df d 伽e rs 已m i c 0 礼缸舢。乱s f o rt h ee q u i v a l e n c e o f ( c f p ) a d ( c i ) n o t et h a t ，g i v e n a n d 玑，w ec a nd e f i n eg = z ：五( 。) 玑) ；a n d c o i m r s e l y ig i v e ng ，w ec o u l df 1 ) 【玑= 0 ，a n d 1 e t ( z ) = d ( z ，c ：) = i n f | | z c | | ：c ( 五) b et h ed i s t a n c ef r o mxt og d e t a i l sa b o u tq u a s i c o n v e x ，s e l i c o n t i 姗o u sa n do t h e r b a c k g r o u n da b o u tc o n v e x v a r i a t i o n a la 丑a l y s i s ，r e a d e r sc a nr e f e rf 0 1 l o w i n gt w oc o m p r e h e 工l s i v em o n o g r a p h 【5 ，6 1 0 b v i o u s l 弘q u a s i c o n v e xc o n d i t i o ni sw e a k e rt h a nc o n v e x c o n d i t i o nb ya n a l y s i s f o re v e r yc o n v e xf u n c t i o n ，( z ) ，t h es e td e f i n e db y z i ，( z ) c ) i sc o n v e xs e t ，a n di n v e r s e l y ，w ec a ng e caq u a s i c o n v e xa n d1 0 w e rs e m i c o n t i n u o u s 1 c h a p t e r1 i n t r o d u c t i o n 2 f u n c t i o nf r o mac o n v e xs e t 4 】s ow ea s s u m et h a tt h ec l o s e db e t sga r ed e f i n e db y g = 。lc ) o ，茁r “) ，a n dq 扛) i sc 0 1 w e xf u n c t i o n i nt h i sp a p e r ，w ee m p h a s i z e o nt h ec f pi nt h e 兄“，f o rt h ec a s ei nt h eh i l b e r ts p a c e ，r e a d e r sc a nr e f e r 2 】 1 2 a p p l i c a t i o no fc o n v e xf e a s i b i l i t yp r o b l e m 。i h ec o n v e xf 色a s i b i l i t yp r o b l e ma p p e a r si nm a n ya r e a so fa p p l i c a t i o ns u c ha s i m a g er e c o n s t r u c t i o n ，a p p r o ) ( i m a t i o nt h e o r y ji n t e g r a le q u a t i o n s ，c o n t r 0 1t h e o r y js i g n “ a n di m a g ep r o c e s s i n b i o m e d i 邑a le n g i n e e r i n g ，c o m 工i l u n i c a t i o n ，a n dg e o 口h y s i c s f b r d e t a i l e da c c o u n t so fc o n c r e t ea p p l i c a t i o 璐，t h er e a d e rc a nr e f e rt o 【1 ，7 ，8 ，9 ，1 0 】a n d r e f e r e n c ei nt h e m 0 n eo ft h es i g n 洒c a n ta p p l i c a t i o n sf o rp r o j e c t i o na l g o r i t h i i l si si m a g er e c o i l s t r u c t i o n f o rc o m p u t e r i z e dt o m o g r a p h 弘t h ef i l n d a m e n t a lr e s e 缸c hc a nb er e f e r r e df r o mf l l l i fw ec o l l s i d e rt h el i n