logo资料库

projected gradient method.pdf

第1页 / 共24页
第2页 / 共24页
第3页 / 共24页
第4页 / 共24页
第5页 / 共24页
第6页 / 共24页
第7页 / 共24页
第8页 / 共24页
资料共24页,剩余部分请下载后查看
M a t h e m a t i c a l P r o g r a m m i n g 3 9 ( 1 9 8 7 ) 9 3 - ! 1 6 9 3 N o r t h - H o l l a n d P R O J E C T E D G R A D I E N T M E T H O D S F O R L I N E A R L Y C O N S T R A I N E D P R O B L E M S P a u l H . C A L A M A I * U n i v e r s i t y o f W a t e r l o o , O n t a r i o , C a n a d a J o r g e J . M O R I ~ * * A r g o n n e N a t i o n a l L a b o r a t o r y , A r g o n n e , I L , U S A R e c e i v e d 9 J u n e 1 9 8 6 R e v i s e d m a n u s c r i p t r e c e i v e d 1 6 M a r c h 1 9 8 7 T h e a i m o f t h i s p a p e r i s t o s t u d y 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 t h e g r a d i e n t p r o j e c t i o n m e t h o d a n d t o a p p l y t h e s e r e s u l t s t o a l g o r i t h m s f o r l i n e a r l y c o n s t r a i n e d p r o b l e m s . T h e m a i n c o n v e r g e n c e r e s u l t i s o b t a i n e d b y d e f i n i n g a p r o j e c t e d g r a d i e n t , a n d p r o v i n g t h a t t h e g r a d i e n t p r o j e c t i o n m e t h o d f o r c e s t h e s e q u e n c e o f p r o j e c t e d g r a d i e n t s t o z e r o . A c o n s e q u e n c e o f t h i s r e s u l t i s t h a t i f t h e g r a d i e n t p r o j e c t i o n m e t h o d c o n v e r g e s t o a n o n d e g e n e r a t e p o i n t o f a l i n e a r l y c o n s t r a i n e d p r o b l e m , t h e n t h e a c t i v e a n d b i n d i n g c o n s t r a i n t s a r e i d e n t i f i e d i n a f i n i t e n u m b e r o f i t e r a t i o n s . A s a n a p p l i c a t i o n o f o u r t h e o r y , w e d e v e l o p q u a d r a t i c p r o g r a m m i n g a l g o r i t h m s t h a t i t e r a t i v e l y e x p l o r e a s u b s p a c e d e f i n e d b y t h e a c t i v e c o n s t r a i n t s . T h e s e a l g o r i t h m s a r e a b l e t o d r o p a n d a d d m a n y c o n s t r a i n t s f r o m t h e a c t i v e s e t , a n d c a n e i t h e r c o m p u t e a n a c c u r a t e m i n i m i z e r b y a d i r e c t m e t h o d , o r a n a p p r o x i m a t e m i n i m i z e r b y a n i t e r a t i v e m e t h o d o f t h e c o n j u g a t e g r a d i e n t t y p e . T h u s , t h e s e a l g o r i t h m s a r e a t t r a c t i v e f o r l a r g e s c a l e p r o b l e m s . W e s h o w t h a t i t i s p o s s i b l e t o d e v e l o p a f i n i t e t e r m i n a t i n g q u a d r a t i c p r o g r a m m i n g a l g o r i t h m w i t h o u t n o n - d e g e n e r a c y a s s u m p t i o n s . K e y w o r d s : L i n e a r l y c o n s t r a i n e d p r o b l e m s , p r o j e c t e d g r a d i e n t s , b o u n d c o n s t r a i n e d p r o b l e m s , l a r g e s c a l e p r o b l e m s , c o n v e r g e n c e t h e o r y . 1 . I n t r o d u c t i o n W e a r e i n t e r e s t e d i n t h e n u m e r i c a l s o l u t i o n o f l a r g e s c a l e m i n i m i z a t i o n p r o b l e m s s u b j e c t t o l i n e a r c o n s t r a i n t s . A l g o r i t h m s f o r s o l v i n g t h e s e p r o b l e m s u s u a l l y r e s t r i c t t h e c h a n g e i n t h e d i m e n s i o n o f t h e w o r k i n g s u b s p a c e b y o n l y d r o p p i n g o r a d d i n g o n e c o n s t r a i n t a t e a c h i t e r a t i o n . T h i s i m p l i e s , f o r e x a m p l e , t h a t i f t h e r e a r e k ~ < n c o n s t r a i n t s a c t i v e a t t h e s o l u t i o n b u t t h e s t a r t i n g p o i n t i s i n t h e i n t e r i o r o f t h e f e a s i b l e s e t , t h e n t h e m e t h o d w i l l r e q u i r e a t l e a s t k i t e r a t i o n s t o c o n v e r g e . T h i s s h o r t c o m i n g d o e s n o t a p p l y t o m e t h o d s b a s e d o n p r o j e c t e d g r a d i e n t s , a n d f o r t h i s r e a s o n t h e r e h a s b e e n r e n e w e d i n t e r e s t i n t h e s e m e t h o d s . * W o r k s u p p o r t e d i n p a r t b y t h e A p p l i e d M a t h e m a t i c a l S c i e n c e s s u b p r o g r a m o f t h e O f f i c e o f E n e r g y R e s e a r c h o f t h e U . S . D e p a r t m e n t o f E n e r g y u n d e r C o n t r a c t W - 3 1 - 1 0 9 - E n g - 3 8 . * * W o r k s u p p o r t e d i n p a r t b y t h e A p p l i e d M a t h e m a t i c a l S c i e n c e s s u b p r o g r a m o f t h e O f f o f E n e r g y R e s e a r c h o f t h e U . S . D e p a r t m e n t o f E n e r g y u n d e r C o n t r a c t W - 3 1 - 1 0 9 - E n g - 3 8 .
9 4 P . H . C a l a m a i , J . J . M o r d / P r o j e c t e d g r a d i e n t m e t h o d s G r a d i e n t p r o j e c t i o n m e t h o d s f o r m i n i m i z i n g a c o n t i n u o u s l y d i t t e r e n t i a b l e m a p - p i n g f : R " ~ R o n a n o n e m p t y c l o s e d c o n v e x s e t 1 2 c R " w e r e o r i g i n a l l y p r o p o s e d b y G o l d s t e i n ( 1 9 6 4 ) a n d L e v i t i n a n d P o l y a k ( 1 9 6 6 ) . I t i s h e l p f u l t o s t u d y t h e g e n e r a l p r o b l e m m i n f ( x ) : x ~ O } , ( 1 . 1 ) b e c a u s e i t c l a r i f i e s t h e u n d e r l y i n g s t r u c t u r e o f t h e a l g o r i t h m s . H o w e v e r , a p p l i c a t i o n s a r e u s u a l l y c o n c e r n e d w i t h s p e c i a l c a s e s o f ( 1 . 1 ) . M o s t o f t h e c u r r e n t i n t e r e s t i n p r o j e c t e d g r a d i e n t s h a s b e e n c o n c e r n e d w i t h t h e c a s e w h e r e S 2 i s d e f i n e d b y t h e b o u n d c o n s t r a i n t s O = { x c R n : l < ~ x < ~ u } ( 1 . 2 ) f o r s o m e v e c t o r s 1 a n d u ; w e a r e i n t e r e s t e d i n t h e g e n e r a l l i n e a r l y c o n s t r a i n e d c a s e w h e r e O i s a p o l y h e d r a l s e t . G i v e n a n i n n e r p r o d u c t n o r m . a n d a n o n e m p t y c l o s e d c o n v e x s e t / 2 , t h e p r o j e c t i o n i n t o 1 2 i s t h e m a p p i n g P : R " ~ 2 d e f i n e d b y P ( x ) = a r g m i n { l l z - x l l : z c 1 2 } . ( 1 . 3 ) T h e d e p e n d e n c e o f P o n 1 2 i s u s u a l l y c l e a r f r o m t h e c o n t e x t , b u t i f t h e r e i s a p o s s i b i l i t y o f c o n f u s i o n w e s h a l l u s e P s i ( x ) t o d e n o t e t h e p r o j e c t i o n o f x i n t o O . G i v e n t h e p r o j e c t i o n P i n t o / 2 , t h e g r a d i e n t p r o j e c t i o n a l g o r i t h m i s d e f i n e d b y x g + l = P ( x k - a k V f ( x k ) ) , ( 1 . 4 ) w h e r e a k > 0 i s t h e s t e p , a n d V f i s t h e g r a d i e n t o f f w i t h r e s p e c t t o t h e i n n e r p r o d u c t a s s o c i a t e d w i t h t h e n o r m I 1 I - T h e r e a r e s e v e r a l s c h e m e s f o r s e l e c t i n g o ~ k w h i c h g u a r a n t e e t h a t a n y l i m i t p o i n t x * o f { X k } s a t i s f i e s t h e f i r s t o r d e r n e c e s s a r y c o n d i t i o n s f o r o p t i m a l i t y ( V f ( x * ) , x - x * ) > ~ O , x ~ g 2 . ( 1 . 5 ) A n y p o i n t x * t h a t s a t i s f i e s c o n d i t i o n ( 1 . 5 ) i s a s t a t i o n a r y p o i n t f o r p r o b l e m ( 1 . 1 ) . T h i s t e r m i n o l o g y i s a p p r o p r i a t e b e c a u s e i f t h e c o n s t r a i n t f u n c t i o n s t h a t d e f i n e 1 2 s a t i s f y a c o n s t r a i n t q u a l i f i c a t i o n t h e n x * i s s t a t i o n a r y i f a n d o n l y i f x * i s a K u h n - T u c k e r p o i n t . T h e r e s u l t s o f G o l d s t e i n ( 1 9 6 4 ) , a n d L e v i t i n a n d P o l y a k ( 1 9 6 6 ) s h o w t h a t i f V f i s L i p s c h i t z c o n t i n u o u s w i t h L i p s c h i t z c o n s t a n t K , a n d i f o ~ k s a t i s f i e s 2 e ~ O l k ~ - - ( l - - e ) K f o r s o m e e i n ( 0 , 1 ) , t h e n a n y l i m i t p o i n t o f { x k } i s a s t a t i o n a r y p o i n t o f p r o b l e m ( l . 1 ) . A n o b v i o u s d r a w b a c k o f t h e i r r e s u l t s i s t h e n e e d f o r t h e L i p s c h i t z c o n s t a n t K . M c C o r m i c k a n d T a p i a 1 9 7 2 e s s e n t i a l l y r e q u i r e t h e s t e p c ~ j , t o b e a g l o b a l m i n i m i z e r o f m i n { f ( P ( X k - - a l T f ( X k ) ) : o z > 0 } , ( 1 . 6 )
P , H . C a l a m a i , J . J . M o r ~ / P r o j e c t e d g r a d i e n t m e t h o d s 9 5 a n d p r o v e t h a t i f f i s c o n t i n u o u s l y d i f f e r e n t i a b l e t h e n l i m i t p o i n t s o f ( 1 . 4 ) m u s t b e s t a t i o n a r y . T h e y a l s o e s t a b l i s h t h i s r e s u l t u n d e r t h e a s s u m p t i o n t h a t ~ i s p o l y h e d r a l w i t h o r t h o g o n a l c o n s t r a i n t n o r m a l s a n d c ~ k i s a l o c a l m i n i m i z e r o f ( 1 . 6 ) . U n f o r t u - n a t e l y , c o m p u t i n g a m i n i m i z e r o f ( 1 . 6 ) f o r a p o l y h e d r a l ~ Q i s a d i f f i c u l t t a s k b e c a u s e i t r e q u i r e s t h e m i n i m i z a t i o n o f a p i e c e w i s e c o n t i n u o u s l y d i f f e r e n t i a b l e f u n c t i o n . F o r a d d i t i o n a l r e s u l t s w i t h t h i s c h o i c e o f s t e p , s e e P h e l p s ( 1 9 8 6 ) . B e r t s e k a s ( 1 9 7 6 ) w a s t h e f i r s t t o p r o p o s e a p r a c t i c a l f i n i t e p r o c e d u r e t o d e t e r m i n e t h e s t e p . G i v e n / 3 a n d / z i n ( 0 , 1 ) a n d y > 0 , B e r t s e k a s p r o p o s e d a n A r m i j o p r o c e d u r e w h e r e c ~ k = / 3 r ' ~ y ( 1 . 7 ) a n d m k i s t h e s m a l l e s t n o n n e g a t i v e i n t e g e r s u c h t h a t . / ' ( x k , , ) < ~ f ( x k ) + ~ ( V f ( x k ) , x k ~ , - x k ) . ( 1 . 8 ) A s s u m i n g t h a t f i s c o n t i n u o u s l y d i f f e r e n t i a b l e a n d ~ Q i s t h e c o n v e x s e t ( 1 . 2 ) , B e r t s e k a s ( 1 9 7 6 ) s h o w s t h a t l i m i t p o i n t s o f { X k } a r e s t a t i o n a r y p o i n t s o f ( 1 . 1 ) , a n d t h a t i f { x k } c o n v e r g e s t o a l o c a l m i n i m i z e r w h i c h s a t i s f i e s t h e s t r i c t c o m p l e m e n t a r i t y a n d s e c o n d o r d e r s u f f i c i e n c y c o n d i t i o n s , t h e n t h e s e t o f a c t i v e c o n s t r a i n t s i s i d e n t i f i e d i n a f i n i t e n u m b e r o f s t e p s . D u n n ( 1 9 8 1 ) a n a l y z e s t h e g r a d i e n t p r o j e c t i o n a l g o r i t h m f o r g e n e r a l c o n v e x s e t s S 2 a n d f c o n t i n u o u s l y d i f f e r e n t i a b l e . H e s h o w s t h a t i f c ~ k s a t i s f i e s ( 1 . 8 ) a n d o e k l > e f o r s o m e e > 0 , t h e n a n y l i m i t p o i n t o f { x ~ } i s s t a t i o n a r y . H e a l s o n o t e s t h a t i f ~ / " i s L i p s c h i t z c o n t i n u o u s w i t h L i p s c h i t z c o n s t a n t K , a n d a e k i s c h o s e n b y t h e A r m i j o p r o c e d u r e ( 1 . 7 , 1 . 8 ) t h e n { 2 } c ~ k ~ > m i n ~ , , - / 3 ( 1 - ~ . ) . K T h i s s h o w s t h a t a n y l i m i t p o i n t o f ( 1 . 4 ) i s a s t a t i o n a r y p o i n t p r o v i d e d V f i s L i p s c h i t z . A n u n p u b l i s h e d r e p o r t o f G a f n i a n d B e r t s e k a s ( 1 9 8 2 ) w a s b r o u g h t t o o u r a t t e n t i o n a f t e r c o m p l e t i n g t h i s w o r k . I n t h e i r r e p o r t t h e g r a d i e n t p r o j e c t i o n m e t h o d w i t h t h e A r m i j o p r o c e d u r e ( 1 . 7 , 1 . 8 ) i s c o n s i d e r e d , a n d i t i s s h o w n t h a t i f f i s c o n t i n u o u s l y d i f f e r e n t i a b l e t h e n a n y l i m i t p o i n t o f ( 1 . 4 ) i s a s t a t i o n a r y p o i n t o f p r o b l e m ( 1 . 1 ) f o r a g e n e r a l c o n v e x s e t S 2 . F o r a c o m p a c t s ' 2 t h i s r e s u l t c a n a l s o b e o b t a i n e d a s a s p e c i a l c a s e o f t h e w o r k o f G a f n i a n d B e r t s e k a s ( 1 9 8 4 ) . I n t h i s p a p e r w e g e n e r a l i z e t h e s e r e s u l t s b y i n t r o d u c i n g t h e n o t i o n o f a p r o j e c t e d g r a d i e n t a n d s h o w i n g t h a t t h e g r a d i e n t p r o j e c t i o n a l g o r i t h m d r i v e s t h e p r o j e c t e d g r a d i e n t t o z e r o . W e a r e a l s o i n t e r e s t e d i n c o n d i t i o n s w h i c h g u a r a n t e e t h a t t h e g r a d i e n t p r o j e c t i o n m e t h o d i d e n t i f i e s t h e o p t i m a l a c t i v e s e t i n a f i n i t e n u m b e r o f s t e p s . T h e f i r s t r e s u l t i n t h i s d i r e c t i o n w a s o b t a i n e d b y B e r t s e k a s ( 1 9 7 6 ) f o r t h e b o u n d c o n s t r a i n e d p r o b l e m ( 1 . 2 ) . R e l a t e d r e s u l t s h a v e b e e n o b t a i n e d b y B e r t s e k a s ( 1 9 8 2 ) f o r a p r o j e c t e d N e w t o n m e t h o d , a n d b y G a f n i a n d B e r t s e k a s ( 1 9 8 4 ) f o r a t w o - m e t r i c p r o j e c t i o n m e t h o d . W e c o n s i d e r t h e g r a d i e n t p r o j e c t i o n m e t h o d a n d g e n e r a l i z e t h e r e s u l t o f B e r t s e k a s ( 1 9 7 6 ) b y s h o w i n g t h a t i f t h e p r o j e c t e d g r a d i e n t s c o n v e r g e t o z e r o a n d i f t h e i t e r a t e s
9 6 P . H . C a l a m a i , J . J . M o r ~ / P r o j e c t e d g r a d i e n t m e l h o d s c o n v e r g e t o a n o n d e g e n e r a t e p o i n t , t h e n t h e o p t i m a l a c t i v e a n d b i n d i n g c o n s t r a i n t s o f a g e n e r a l l i n e a r l y c o n s t r a i n e d p r o b l e m a r e i d e n t i f i e d i n a f i n i t e n u m b e r o f i t e r a t i o n s . T h i s r e s u l t i s i n d e p e n d e n t o f t h e m e t h o d u s e d t o g e n e r a t e t h e i t e r a t e s a n d c a n b e a p p l i e d t o o t h e r l i n e a r l y c o n s t r a i n e d a l g o r i t h m s . T h e a b o v e r e s u l t s o n t h e i d e n t i f i c a t i o n o f t h e o p t i m a l a c t i v e c o n s t r a i n t s h a v e b e e n g e n e r a l i z e d i n r e c e n t w o r k . D u n n ( 1 9 8 6 ) p r o v e d t h a t i f a s t r i c t c o m p l e m e n t a r i t y c o n d i t i o n h o l d s , t h e n t h e g r a d i e n t p r o j e c t i o n m e t h o d i d e n t i f i e s t h e o p t i m a l a c t i v e c o n s t r a i n t s i n a f i n i t e n u m b e r o f i t e r a t i o n s . T h i s r e s u l t h a s b e e n e x t e n d e d b y B u r k e a n d M o r 6 ( 1 9 8 6 ) . T h e y p r o v e d , i n p a r t i c u l a r , t h a t u n d e r D u n n ' s n o n d e g e n e r a c y a s s u m p t i o n t h e o p t i m a l a c t i v e c o n s t r a i n t s a r e e v e n t u a l l y i d e n t i f i e d i f a n d o n l y i f t h e p r o j e c t e d g r a d i e n t c o n v e r g e s t o z e r o . 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 t h e p r o j e c t e d g r a d i e n t m e t h o d t h a t w e o b t a i n r e v o l v e a r o u n d t h e n o t i o n o f t h e p r o j e c t e d g r a d i e n t . T h i s c o n c e p t i s u s e d f r e q u e n t l y i n t h e o p t i m i z a t i o n l i t e r a t u r e , b u t i t i s i n v a r i a b l y a s s o c i a t e d w i t h a f f i n e s u b s p a c e s . T h e p r o j e c t e d g r a d i e n t f o r c o n v e x s e t s h a s h a d l i m i t e d u s e . F o r b o u n d c o n s t r a i n e d p r o b l e m s t h e p r o j e c t e d g r a d i e n t i s u s e d b y D e m b o a n d T u l o w i t z k i ( 1 9 8 3 ) a s a s e a r c h d i r e c t i o n a n d t o d e t e r m i n e s t o p p i n g c r i t e r i a f o r t h e s o l u t i o n o f q u a d r a t i c p r o g r a m ~ m i n g p r o b l e m s . F o r l i n e a r l y c o n s t r a i n e d p r o b l e m s , D e m b o a n d T u l o w i t z k i ( 1 9 8 4 , 1 9 8 5 ) u s e t h e p r o j e c t e d g r a d i e n t t o d e v e l o p r a t e o f c o n v e r g e n c e r e s u l t s f o r s e q u e n t i a l q u a d r a t i c p r o g r a m m i n g a l g o r i t h m s . F i n a l l y , f o r g e n e r a l c o n v e x s e t s , M c C o r m i c k a n d T a p i a ( 1 9 7 2 ) u s e t h e p r o j e c t e d g r a d i e n t t o d e f i n e a s t e e p e s t d e s c e n t d i r e c t i o n . T h e s l o w c o n v e r g e n c e r a t e o f t h e g r a d i e n t p r o j e c t i o n m e t h o d i s a n o b v i o u s d r a w b a c k , a n d t h u s c u r r e n t r e s e a r c h h a s b e e n a i m e d a t d e v e l o p i n g a s u p e r l i n e a r l y c o n v e r g e n t v e r s i o n o f t h e g r a d i e n t p r o j e c t i o n a l g o r i t h m . M a n y o f t h e s e a l g o r i t h m s , h o w e v e r , d o n o t h a v e t h e s i m p l i c i t y a n d e l e g a n c e o f t h e g r a d i e n t p r o j e c t i o n m e t h o d . F o r e x a m p l e , t h e p r o j e c t e d N e w t o n m e t h o d d e v e l o p e d b y B e r t s e k a s ( 1 9 8 2 ) u s e s a n a n t i - z i g z a g g i n g s t r a t e g y a n d t h e a c c e p t a n c e c r i t e r i o n i n t h e s e a r c h p r o c e d u r e d o e s n o t h a v e t h e a p p e a l o f ( 1 . 7 , 1 . 8 ) . S i m i l a r r e m a r k s a p p l y t o t h e p r o j e c t i o n m e t h o d s o f G a f n i a n d B e r t s e k a s ( 1 9 8 4 ) . I n t h i s p a p e r w e f o l l o w a d i f f e r e n t a p p r o a c h w h i c h u s e s a s t a n d a r d u n c o n s t r a i n e d m i n i m i z a t i o n a l g o r i t h m t o e x p l o r e t h e s u b s p a c e d e f i n e d b y t h e c u r r e n t a c t i v e s e t , a n d t h e g r a d i e n t p r o j e c t i o n m e t h o d t o c h o o s e t h e n e x t a c t i v e s e t . A s i m i l a r a p p r o a c h i s u s e d b y B e r t s e k a s ( 1 9 7 6 ) f o r o p t i m i z a t i o n p r o b l e m s s u b j e c t t o b o u n d c o n s t r a i n t s , a n d b y D e m b o a n d T u l o w i t z k i ( 1 9 8 3 ) f o r s t r i c t l y c o n v e x q u a d r a t i c p r o g r a m m i n g p r o b l e m s s u b j e c t t o b o u n d c o n s t r a i n t s , b u t o u r a p p r o a c h a p p e a r s t o b e s i m p l e r a n d m o r e g e n e r a l . T h e a i m o f t h i s p a p e r i s t o s t u d y 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 t h e g r a d i e n t p r o j e c t i o n m e t h o d a n d t o a p p l y t h e s e r e s u l t s t o a l g o r i t h m s f o r l i n e a r l y c o n s t r a i n e d p r o b l e m s . A s a n a p p l i c a t i o n o f o u r t h e o r y , w e d e v e l o p q u a d r a t i c p r o g r a m m i n g a l g o r i t h m s t h a t i t e r a t i v e l y e x p l o r e a s u b s p a c e d e f i n e d b y t h e a c t i v e c o n s t r a i n t s . T h e s e a l g o r i t h m s a r e a b l e t o d r o p a n d a d d m a n y c o n s t r a i n t s f r o m t h e a c t i v e s e t , a n d c a n e i t h e r c o m p u t e a n a c c u r a t e m i n i m i z e r b y a d i r e c t m e t h o d , o r a n a p p r o x i m a t e m i n i m i z e r b y a n i t e r a t i v e m e t h o d o f t h e c o n j u g a t e g r a d i e n t t y p e . T h u s , t h e s e a l g o r i t h m s a r e a t t r a c t i v e f o r l a r g e s c a l e p r o b l e m s .
P . H . C a l a m a i , J . Z M o r d / P r o j e c t e d g r a d i e n t m e t h o d s 9 7 W e s t a r t t h e c o n v e r g e n c e a n a l y s i s o f t h e g r a d i e n t p r o j e c t i o n m e t h o d i n S e c t i o n 2 . O u r p r o c e d u r e f o r c h o o s i n g a k g e n e r a l i z e s t h e A r m i j o p r o c e d u r e ( 1 . 7 , 1 . 8 ) ; i n p a r t i c u l a r , w e d o n o t r e q u i r e t h a t { C ~ g } b e b o u n d e d . W e s h o w t h a t i f f i s c o n t i n u o u s l y d i f f e r e n t i a b l e t h e n l i m i t p o i n t s o f t h e g r a d i e n t p r o j e c t i o n m e t h o d a r e s t a t i o n a r y p o i n t s o f p r o b l e m ( 1 . 1 ) . W e a l s o s h o w t h a t i t i s p o s s i b l e t o o b t a i n a c o n v e r g e n c e r e s u l t w i t h o u t i m p o s i n g b o u n d e d n e s s c o n d i t i o n s o n { x k } . I n S e c t i o n 3 w e d e f i n e t h e n o t i o n o f a p r o j e c t e d g r a d i e n t a n d p r o v e t h a t t h e g r a d i e n t p r o j e c t i o n m e t h o d f o r c e s t h e s e q u e n c e o f p r o j e c t e d g r a d i e n t s t o z e r o . T h i s i s a n e w a n d i m p o r t a n t p r o p e r t y o f t h e g r a d i e n t p r o j e c t i o n m e t h o d . W e a l s o s h o w t h a t t h i s p r o p e r t y i m p l i e s t h a t l i m i t p o i n t s o f t h e g r a d i e n t p r o j e c t i o n m e t h o d a r e s t a t i o n a r y p o i n t s . W e c o n s i d e r t h e c a s e o f a p o l y h e d r a l S 2 i n S e c t i o n 4 , a n d p r o v e t h a t i f t h e p r o j e c t e d g r a d i e n t s c o n v e r g e t o z e r o a n d i f { x k } c o n v e r g e s t o a n o n d e g e n e r a t e p o i n t , t h e n t h e a c t i v e a n d b i n d i n g c o n s t r a i n t s a r e i d e n t i f i e d i n a f i n i t e n u m b e r o f i t e r a t i o n s . A n i n t e r e s t i n g a s p e c t o f t h i s r e s u l t i s t h a t i t i s i n d e p e n d e n t o f t h e m e t h o d u s e d t o g e n e r a t e { x k } a n d c a n t h u s b e a p p l i e d t o o t h e r l i n e a r l y c o n s t r a i n e d a l g o r i t h m s . S e c t i o n s 5 a n d 6 e x a m i n e a l g o r i t h m s w h i c h o n l y u s e t h e g r a d i e n t p r o j e c t i o n m e t h o d o n s e l e c t e d i t e r a t i o n s , w i t h S e c t i o n 6 r e s t r i c t e d t o a l g o r i t h m s f o r t h e g e n e r a l q u a d r a t i c p r o g r a m m i n g p r o b l e m . T h e r e s u l t s o f S e c t i o n 6 s h o w , i n p a r t i c u l a r , t h a t i t i s p o s s i b l e t o d e v e l o p a f i n i t e l y t e r m i n a t i n g q u a d r a t i c p r o g r a m m i n g a l g o r i t h m w i t h o u t n o n - d e g e n e r a c y a s s u m p t i o n s . 2 . C o n v e r g e n c e a n a l y s i s I n o u r a n a l y s i s o f t h e g r a d i e n t p r o j e c t i o n m e t h o d w e a s s u m e t h a t ~ Q i s a n o n e m p t y c l o s e d c o n v e x s e t a n d t h a t t h e m a p p i n g f : R " - + R i s c o n t i n u o u s l y d i f f e r e n t i a b l e o n ~ Q . G i v e n a n i t e r a t e x k i n ~ , t h e s t e p C ~ k i s o b t a i n e d b y s e a r c h i n g t h e p a t h X k ( O e ) = - - P ( X k - - O L V f ( x k ) ) , w h e r e P i s t h e p r o j e c t i o n i n t o . ( 2 d e f i n e d b y ( 1 . 3 ) . G i v e n a s t e p a k > 0 , t h e n e x t i t e r a t e i s d e f i n e d b y x k + ~ = X k ( C ~ k ) . T h e s t e p ~ k i s c h o s e n s o t h a t , f o r p o s i t i v e c o n s t a n t s 7 ~ a n d Y 2 , a n d c o n s t a n t s p ~ , a n d > 2 i n ( 0 , 1 ) , a n d 9 f ( x k + 1 ) - < f ( x k ) + t , , ( W ( x k ) , x k + , - x ~ ) , ( 2 . 1 ) c ~ k > ~ ' y ~ o r a k > ~ 7 2 ~ k > 0 ( 2 . 2 ) w h e r e 6 k s a t i s f i e s f ( x k ( 6 k ) ) > f ( x k ) + t x 2 ( V f ( x , , ) , X k ( 6 k ) - - x k ) . ( 2 . 3 ) C o n d i t i o n ( 2 . 1 ) o n ~ k f o r c e s a s u f f i c i e n t d e c r e a s e o f t h e f u n c t i o n w h i l e c o n d i t i o n ( 2 . 2 ) g u a r a n t e e s t h a t c ~ k i s n o t t o o s m a l l . S i n c e D u n n ( 1 9 8 1 ) h a s s h o w n t h a t i f x k
9 8 P . H . C a l a m a i , J . J . M o r d / P r o j e c t e d g r a d i e n t m e t h o d s i s n o t s t a t i o n a r y t h e n ( 2 . 3 ) f a i l s f o r a l l 6 k > 0 s u f f i c i e n t l y s m a l l , i t f o l l o w s t h a t t h e r e i s a n a k > 0 w h i c h s a t i s f i e s ( 2 . 1 ) a n d ( 2 . 2 ) p r o v i d e d p , ~ < ~ / z 2 . N o t e , i n p a r t i c u l a r , t h a t t h e A r m i j o p r o c e d u r e ( 1 . 7 , 1 . 8 ) s a t i s f i e s t h e s e c o n d i t i o n s w i t h T , = T , y 2 = / 3 , a n d p , ~ = ~ 2 = ~ . T h e a n a l y s i s o f t h e g r a d i e n t p r o j e c t i o n m e t h o d d e f i n e d b y ( 2 . 1 ) a n d ( 2 . 2 ) r e q u i r e s s o m e b a s i c p r o p e r t i e s o f t h e p r o j e c t i o n o p e r a t o r . L e m m a 2 . 1 . L e t P b e t h e p r o j e c t i o n i n t o ~ . ( a ) l f z e g 2 t h e n ( P ( x ) - x , z - P ( x ) ) ~ O j b r a l l x c R " . ( b ) P i s a m o n o t o n e o p e r a t o r , t h a t i s , ( P ( y ) - P ( x ) , y - x ) > ~ O . f o r x , y 6 R " . I f P ( y ) r P ( x ) t h e n s t r i c t i n e q u a l i t y h o l d s . ( c ) P i s a n o n e x p a n s i v e o p e r a t o r , t h a t i s , l i P ( y ) - P ( x ) l l < ~ I l y - x l l . / ' o r x , y 9 g n . L e m m a 2 . 1 i s w e l l k n o w n a n d e a s y t o p r o v e . F o r e x a m p l e , Z a r a n t o n e l l o ( 1 9 7 1 ) p r o v e s t h i s r e s u l t ( L e m m a s 1 . 1 a n d 1 . 2 ) a n d a l s o p r o v i d e s m u c h a d d i t i o n a l i n f o r m a - t i o n o n p r o j e c t i o n s . A n i m m e d i a t e c o n s e q u e n c e o f p a r t ( a ) i s t h a t I l x k ( o ~ ) - x k l l 2 ( V f ( x k ) , X k - - X k ( O ~ ) ) > ~ , a > 0 . ( 2 . 4 ) O g I n p a r t i c u l a r , t h i s i m p l i e s t h a t I I x k , , - x , , I I 2 ( V f ( X k ) , x k - - x k + l ) ~ > ( 2 . 5 ) I n e q u a l i t i e s ( 2 . 4 ) a n d ( 2 . 5 ) w e r e u s e d b y D u n n ( 1 9 8 1 ) i n h i s a n a l y s i s o f t h e g r a d i e n t p r o j e c t i o n m e t h o d . W e a l s o n e e d t o n o t e t h a t p a r t ( b ) o f L e m m a 2 . 1 i m p l i e s t h a t ( V f ( X k ) , X k - - X k ( ~ ) ) 1 > ( V f ( x k ) , X k - - X k ( / 3 ) ) i f a / > / 3 . ( 2 . 6 ) T h e n e x t r e s u l t i s d u e t o G a f n i a n d B e r t s e k a s 1 9 8 4 , b u t o u r p r o o f i s s i m p l e r . L e m m a 2 . 2 . L e t P b e t h e p r o j e c t i o n i n t o f 2 . G i v e n x e R " a n d d 9 R " , t h e f u n c t i o n 0 d e f i n e d b y ~ ( ~ ) _ l l P ( x + a d ) - x , , ~ > 0 , O f i s a n t i t o n e ( n o n i n c r e a s i n g ) . P r o o f . L e t a > / 3 > 0 b e g i v e n . I f P ( x + a d ) = P ( x + / 3 d ) t h e n 0 ( a ) ~ < t ) ( / 3 ) , s o w e o n l y c o n s i d e r t h e c a s e P ( x + a d ) ~ P ( x + / 3 d ) . W e n o w s h o w t h a t t h e r e s u l t f o l l o w s b y n o t i n g t h a t i f ( v , u - v ) > 0 t h e n I l u l l ( u , u - ~ ) I 1 ~ 1 1 ( , ~ , , , - v )
P . H . C a l a m a i , J . J . M o r d / P r o j e c t e d g r a d i e n t m e t h o d s 9 9 T h e p r o o f o f t h i s g e o m e t r i c a l r e s u l t o n l y r e q u i r e s a s h o r t c o m p u t a t i o n . I f w e s e t u = P ( x + a d ) - x , v = P ( x + f l d ) - x , t h e n p a r t ( a ) o f L e m m a 2 . 1 i m p l i e s t h a t ( u , u - v ) < ~ a ( d , P ( x + a d ) - P ( x + f l d ) ) , a n d t h a t ( v , u - v ) > ~ f l ( d , P ( x + o ~ d ) - P ( x + f l d ) ) . M o r e o v e r , s i n c e a > / 3 a n d P ( x + c ~ d ) r P ( x + f l d ) , p a r t ( b ) o f L e m m a 2 . 1 s h o w s t h a t ( d , P ( x + o ~ d ) - P ( x + ~ d ) ) > O . H e n c e ( v , u - v ) > 0 , a n d t h u s t h e r e s u l t f o l l o w s f r o m t h e a b o v e i n e q u a l i t i e s . W e n o w p r o c e e d t o t h e c o n v e r g e n c e a n a l y s i s o f t h e g r a d i e n t p r o j e c t i o n m e t h o d . I n t h e f o l l o w i n g r e s u l t w e d o n o t a s s u m e t h a t t x k } i s b o u n d e d b u t a s s u m e t h a t V f i s u n i f o r m l y c o n t i n u o u s ; l a t e r o n w e s h o w t h a t t h e u n i f o r m c o n t i n u i t y a s s u m p t i o n c a n b e d r o p p e d i f s o m e s u b s e q u e n c e o f { x k } i s b o u n d e d . T h e o r e m 2 . 3 . L e t . f : R " - ~ R b e c o n t i n u o u s l y d i f f e r e n t i a b l e o n J 2 , a n d l e t { x k } b e t h e s e q u e n c e g e n e r a t e d b y t h e g r a d i e n t p r o j e c t i o n m e t h o d d e f i n e d b y ( 2 . 1 ) a n d ( 2 . 2 ) . I f f i s b o u n d e d b e l o w o n 1 " 2 a n d V f i s u n i J o r m l y c o n t i n u o u s o n ~ t h e n l i m I l x k - . - x k l 1 - 0 . k ~ x , t t ' k P r o o f . A s s u m e t h a t t h e r e i s a n i n f i n i t e s u b s e q u e n c e K 0 s u c h t h a t I I x k . , - I I / > e > 0 , k c K o . O l k W e w i l l p r o v e t h a t t h i s a s s u m p t i o n l e a d s t o a c o n t r a d i c t i o n . F i r s t n o t e t h a t i f k r K o t h e n O ~ k a n d t h a t s i n c e { f ( x k ) } c o n v e r g e s , c o n d i t i o n ( 2 . 1 ) i m p l i e s t h a t { ( V f ( X k ) , X k - - X k . ~ ) } c o n v e r g e s t o z e r o . H e n c e , ( 2 . 5 ) a n d t h e a b o v e i n e q u a l i t y s h o w t h a t l i m ~ k = 0 a n d l i m I l X k + , - x k l = 0 . k ~ K o , k ~ ~ c k c ~ K . , k ~ x , I n p a r t i c u l a r , w e h a v e s h o w n t h a t e v e n t u a l l y a k < ) ' , a n d h e n c e , a k ~ > ~ ' 2 ~ ' k w h e r e a k s a t i s f i e s ( 2 . 3 ) . N o w s e t 2 k § - - - - - - X k ( & k ) a n d / 3 k ~ m i n ( a k , ~ k ) - L e m m a 2 . 2 i m p l i e s t h a t / 3 k a k ~ /
1 0 0 P . H . C a l a m a i , J . J . M o r d / P r o j e c t e d g r a d i e n t m e t h o d s a n d s i n c e x k + ~ - x k / > e ~ k a n d e e k > ~ y 2 d k f o r k ~ K o , w e o b t a i n t h a t t > e m i n { 1 , v ~ 4 1 1 x k + , - x ~ l l . T h i s i n e q u a l i t y , t o g e t h e r w i t h ( 2 . 4 ) a n d ( 2 . 6 ) , i m p l y t h a t f o r k z K o , m i n { ( V f ( x k ) , x k - x k § ) , ( V . f ( x k ) , x k - - x k + i ) } > / e m i n { i , T _ ~ } ~ k § x ~ l l . ( 2 . 7 ) W e n o w u s e ( 2 . 7 ) t o o b t a i n t h e d e s i r e d c o n t r a d i c t i o n . S i n c e { ( V f ( x k ) , x k - x k + ~ ) } c o n v e r g e s t o z e r o , ( 2 . 7 ) i m p l i e s t h a t { U & + ~ - x k U : k c K o } c o n v e r g e s t o z e r o . T h u s t h e u n i f o r m c o n t i n u i t y o f V f s h o w s t h a t i f f ( x k ) - f ( x k ( e e ) ) p k ( a ) = - ( V f ( x k ) , x , , - t h e n o ( l l , - x k l l ) ( W ( x k ) , x ~ - - ~ k , , ) " H e n c e ( 2 . 7 ) e s t a b l i s h e s t h a t p k ( 6 k ) > P - Z f o r a l l k e K o s u f f i c i e n t l y l a r g e . T h i s i s t h e d e s i r e d c o n t r a d i c t i o n b e c a u s e ( 2 . 3 ) g u a r a n t e e s t h a t p k ( d k ) < t ' 2 " N o t e t h a t i n T h e o r e m 2 . 3 t h e a s s u m p t i o n t h a t f i s b o u n d e d b e l o w o l l O i s o n l y n e e d e d t o c o n c l u d e t h a t { f ( x l ~ ) } c o n v e r g e s , a n d h e n c e , t h a t { ( V f ( x k ) , x k - - X k - ~ , ) } c o n v e r g e s t o z e r o . T h e a s s u m p t i o n t h a t V f i s u n i f o r m l y c o n t i n u o u s i s u s e d t o c o n c l u d e t h a t f ( ~ k + , ) - - f ( x k ) - - ( V f ( x k ) , . ~ k ~ , - - X k ) l = O ( g k + ~ - - X k ) - T h e s e o b s e r v a t i o n s l e a d t o t h e f o l l o w i n g r e s u l t . T h e o r e m 2 . 4 . L e t f : R " - - R b e c o n t i n u o u s l y d i f f e r e n t i a b l e o n g 2 , a n d l e t { x k } b e t i l e s e q u e n c e g e n e r a t e d b y t h e g r a d i e n t p r o j e c t i o n m e t h o d d e f i n e d b y ( 2 . 1 ) a n d ( 2 . 2 ) . / f s o m e s u b s e q u e n c e { x k : k e K } i s b o u n d e d t h e n l i m I I x , - x l l o . k ~ K , k ~ = o O . k M o r e o v e r ; a n y l i m i t p o i n t o f { x k } i s a s t a t i o n a r y p o i n t o f p r o b l e m ( 1 . 1 ) . P r o o f . W e a s s u m e t h a t t h e r e i s a n i n f i n i t e s u b s e q u e n c e K o c K s u c h t h a t O ~ k a n d r e a c h a c o n t r a d i c t i o n a s i n t h e p r o o f o f T h e o r e m 2 . 3 . T h e o n l y d i f f e r e n c e i s t h a t s i n c e { x k : k c K } i s b o u n d e d , { f ( x k ) } c o n v e r g e s a n d K o c a n b e c h o s e n s o t h a t { x k : k ~ K o } c o n v e r g e s . H e n c e , c o n t i n u i t y o f V f i s s u f f i c i e n t t o s h o w t h a t p k ( d k ) > I . z 2 f o r a l l k ~ K o s u f f i c i e n t l y l a r g e .
分享到:
收藏