大型稀疏極大極小問題的數(shù)值方法.pdf

1、大連理工大學博士學位論文大型稀疏極大極小問題的數(shù)值方法姓名：李軍祥申請學位級別：博士專業(yè)：計算數(shù)學指導教師：于波20080601A b s t r a c tI nt h et h e s i s ，s y m m e t r i c a l l y c o n s i s t e n t g r o u p - w i s eu p d a t i n gN e w t o n ．1 i k em e t h o d s ，i n e

2、 x a c tN e w t o nm e t h o d s a n d i n e x a c ts y m m e t r i c a l l y c o n s i s t e n tg r o u p - w i s eu p d a t i n gN e w t o n —l i k em e t h -o d s f o rl a r g es c a l es p a r s em i n i m a x p r o

3、b l e m s a r e s t u d i e d ．M a i nr e s u l t s o b t a i n e da r e s k e t c h e d a sf o l l o w s ：1 ·I nC h a p t e r 2 ，w e b e g i nw i t hs m o o t h p r o b l e m s a n d s t u d ys o m e i m p r o v e

4、d v e r s i o n s o fs y m m e t -r i c a l l yc o n s i s t e n t g r o u p - w i s eu p d a t i n gN e w t o n —l i k em e t h o d sa n ds y m m e t r i c a l l y c o n s i s t e n tg r o u p - w i s eu p d a t i n g C

5、 h o l e s k yf a c t o rt e c h n i q u e s ．A n da ni n e x a c ts y m m e t r i c a l l yc o n s i s t e n tg r o u p - w i s eu p d a t i n g N e w t o n - l i k em e t h o d i sp r e s e n t e d ．L o c a lq - s u p

6、e r l i n e a r c o n v e r g e n c ea n dg l o b a lc o n v e r g e n c e a r ep r o v e na n d r - c o n v e r g e n c er a t e so ft h e ma r ee s t i m a t e d ．2 ．I nC h a p t e r3 ，as y m m e t r i c a l l yc o n s

7、 i s t e n tg r o u p - w i s eu p d a t i n gm e t h o d f o rs p a r s em i n i m a xp r o b l e m si s g i v e n ．B e c a u s et h eo b j e c t i v ec o n c e r n sm f u n c t i o n s w i t hH e s s i a n si n d i f f

8、 e r e n ts p a r s e s t r u c t u r e s ，d i f f e r e n t g r o u p i a g s t r a t e g i e s f o rt h eH e s s i a n sm u s tb et a k e n ，a n dh e n c ep e r i o d s o ft h eH e s s i a n su p d a t i n gm a yb ed i

9、 f f e r e n t ．W i t h o u t s t r i c tc o m p l e m e n t a r i t y , q —s u p e r l i n e a rl o c a lc o n v e r g e n c ea n d g l o b a lc o n v e r g e n c ea r e p r o v e n ，a n da n r —c o n v e r g e n c er a

10、 t ei s e s t i m a t e d ．I na d d i t i o n ．e f f i c i e n tm e t h o d s b a s e d o i l t h em o d i f i e dC h o l e s k yf a c t o r i z a t i o na r eg i v e n t os o l v et h en o n c o n v e x m i n i m a x p

11、r o b l e m s ．3 ．I nc h a p t e r4 ，i n e x a c t N e w t o nm e t h o d sf o rt h em i n i m a xp r o b l e m sa r es t u d i e d ．I ne a c hi t e r a t i o n ，a q u a d r a t i cm i n i m a xp r o b l e mn e e d st ob

12、 ea p p r o x i m a t e l ys o l v e di n e x a c t l yb ys o l v i n gas e q u e n c eo fs p e c i a ll i n e a re q u a t i o ns y s t e m s ．P r e c i s i o nc o n t r o l l i n gc r i t e r i o n sf o rt h e b o t h

13、s t a g e s a r e g i v e n t op r e s e r v et h es u p e r l i n e a r c o n v e r g e n c ea n d t o 同9 , y ec o m p u t a t i o n o fs o l v i n gt h es u b p r o b l e m s ．W i t h o u t s t r i c t c o m p l e m e

14、n t a r i t y , l o c a lq - s u p e r l i n e a rc o n v e r g e n c ea n d g l o b a lc o n v e r g e n c ea r ep r o v e na n d t h eq - c o n v e r g e n c er a t ei s e s t i m a t e d ．4 ．I nc h a p t e r5 ，i n e x

15、 a c ts y m m e t r i c a l l yc o n s i s t e n tg r o u p - w i s eu p d a t i n gm e t h o d s f o rl a r g es c a l es p a r s em i n i m a x p r o b l e m sa r es t u d i e d ．P r e c i s i o nc o n t r o l l i n gc

16、 r i t e r i o n sf o rt h eb o t hs t a g e sa r eg i v e nt o p r e s e r v et h es u p e r l i n e a rc o n v e r g e n c ea n dt os a v e c o m p u t a t i o no fs o l v i n gt h es u b p r o b l e m s ．W i t h o u t

17、s t r i c t c o m p l e m e n t a r i t y , l o c a lq - s u p e r l i n e a rc o n v e r g e n c ea n d g l o b a lc o n v e r g e n c e a r ep r o v e na n d t h ec o n v e r g e n c er a t ei se s t i m a t e d ．A l l

18、 a l g o r i t h m sp r o p o s e di nt h i sp a p e ra r ei m p l e m e n t e d i n c ／c + + o r M a t l a bs y s t e m s a n dn u m e r i c a lt e s t sa r ed o n e ．N u m e r i c a l r e s u l t ss h o w st h a tt h e

19、 s em e t h o d sa r ee f f i c i e n t ．K e y w o r d s ：m i n i m a x p r o b l e m s ；s p a r s i t y ；g r o u p - w i s eu p d a t i n ga l g o r i t h m ；c o n s i s t e n tg r o u p i n g ；i n e x a c tN e w t o n