（应用数学专业论文）约束优化无严格互补的快速收敛序列线性方程组算法.pdf

j i l 强 约束优化无严格互补的快速收敛 序列线性方程组算法 摘要 为了克服s q p 算法因解二次规划计算量增大的弱点，序列线性方程组( s s l e ) 算法成为求解非线性规划问题的有效算法之一，是目前研究的一个热点问题 由于可行s s l e 方法具有收敛速度快，迭代点可行，并且不需要任何= 次子规 划等优点，近年来得到了更为广泛的研究然而，这类算法在每步迭代通常要 解四五个线性方程组，因此计算量相对较大，而且还需要严格互补的假设， 这个条件相对较强难于验证 本文借助于约束梯度的扰动引人了新的构造线性方程组技术，从而给出了 求解光滑不等式约束非线性优化问题的一个新的序列线性方程组算法算法 包括两个循环：循环i 和循环i i 在循环i 的每次迭代中，迭代点都是可行的，并 且需要求解几个线性方程组，但是在循环i i 中只需要求解一个线性方程组 。进一步，当七充分大时，迭代将进人循环i i 并不再跳出这个循环，即有限次迭 代以后只需求解一个线性方程组此外，在不需要严格互补的温和条件下， 我们证明了算法的全局收敛性和超线性收敛性最后，进行了初步的数值试 验，数值结果表明在所计算问题的循环i 的每次迭代中，也只需求解两个具有 相同系数矩阵的线性方程组，计算量比其他的序列线性方程组算法要少 关键词：不等式约束非线性最优化序列线性方程组算法收敛性 譬 an e wf a s tc o n v e r g e n ts s l ea l g o r i t h mf o r i n e q u a l i t yc o n s t r a i n e do p t i m i z a t i o nw 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 a b s t r a c t s e q u e n t i a ls y s t e 脚o fl i n e 缸e q u a t i o n s ( s s l e ) a l g o r i t h m sa r ew i d e l ya c k n o w l e d g e dt ob e a m o n gt h em o s t8 u c c e s s f u la l g o r i t h m 8f o r8 0 l v i n gn o n l i n e a ro p t l m l z a t i o np r o b i e m s ，w h l c ha r e p r o p 0 b e dm a i n l yt oo v e r m et h ed e f a u l t so ft h ec l 勰s i c 以s q pm e t h o d ，s u c h 鹪t h e 1 1 8 i 8 t e n c y p r o b k m 柚dl 缸g ea m o u n to fc o m p u t a t i o n 胡砘tf o r8 0 l v i i 培aq ps u b p m b k m i nr e c e n td e c a d 馏， f e 勰i b ks s l ea 1 9 0 r i t h 瑚h a v eb ns t u d i e dw i d e l y s i n c et h e yh a v e 粥tr a t eo fc o n v e r g e n c e ， g e n e r a t el b 猫i b l e “e r a t ，跏dd on o to e q u 虹ea n yq u a d r a t i cs u b p r o g r a m h o w e v e r ，f e a s i b l e s s l ea 1 9 0 r i t h m s 瑚u a l l yr e q l l i r et o l v ef o l l ro r 矗v es y s t e 脚o fl i n e 甜e q u a t i o 珊( s l e ) a te a c h i t e r a t b n ，t h ec o m p u t a t i o n a lc 0 8 ti 8r e l a t i v e l yh i g h a n dt h e8 t r i c t m p l e m e n t 盯i t yc o n d i t i o n i 8n e c e 髓盯y w h i c hi 88 t r o n g 锄dd i m c u l tf b rt e s t i n g i nt h i 8p 印e r ，ak i n do f8 m o o t hn o n l i n e 盯o p t i m i z a t b np r o b k 瑚w i t hi n e q u a l 时c 0 璐t r a i n t s ， i 8c o 聃i d 训，眦dan 鲫a 1 酬t h mo f s s l ef o rt h ep r o b k 删i 8p r o p o 船db yi n t r o d u c i n gam w c o 邶t m c t i n gt e c h n i q u e0 ft h es l e ，w h i c h 舢r r e dt ot h ep e r t u r b a t i o no fc o 瑚t r a i n t 8 酗a d i e n t o l l ra 1 9 0 r i t h mi n c l u d 鹤t w oc y c k 培o fc y c l eia n dc y c l ei i a te a c hi t e r a t i o no fc y c l ei ，t h e i t e r a t 朗a j ea l lf e a 8 i b k ，a n da tk a 8 tt w or e d u c e ds l e 8 ，o t h e rt h a nt h eq u a d r a t i cp r o | p a m m i n 岛 n e e dt ob es o l 、，e d ，w h i ko n l yo n es l ei 8r e q u i r e dt ob e8 0 l v e di nc y c ki i m o r e a v e r ，w e8 h o w t h a tt h ei t e r a t i v ep r o 嗍w i e n t e ri n t o ( c l ei i 觚dn e v e rc o m eo u tt h i 8c y c l ef o r 詹l a r g e e n o u 吐，t h a ti 8 ，o n l yo s l l 王n e e d bt ob e 伽p u t e d 甜t e ra 丘n “en u m b e ro fi t e r a t i o n s u n d e r m i l da 船u m p t i o 衄w i t h o u tt h es t r i c tc o m p l e m e n t a r i t y ，i ti 88 h o w nt h a tt h ep r o p e da l g o r i t l l i n e n j o y bt h ep r 叩e r t i e so fg l o b a la i l d8 u p 盱l i n e 盯c o n v e r g e n f i n a u y m ep r e l i m i n a r yn 啪e r i c a l t 鹤t sa r e p o r t e d 觚dt h e 眦m e r i c a lr 髓u l t ss h o wt h a to n l yt w or e d u c e ds l e sw i t ht h e 昭m e c o e m c i e n tm a t r i 】【a 托r e q u i r e dt ob e l v e da te a c hi t e r a t b no fc y c l eif o ra ut 髑t e dp r o b l e 瑚， 锄dt h ea m o u n t0 fc o m p u t a t b ni s 加呱血l e 鲫t h 姐o t h e rs s u a l g o r i t h 脚 k e yw o r d s ：妇q l l a l 酊c o 越t 曲n t b ；n o n l i n e wo p t i m i z a t i o n ；q u e n t i a ls y 8 t e 脚o f l i n e 盯e q u a t i o m ；a 1 9 0 r i t h m ；c o n v e r g e n c e 冬i i 叶 耋皇查兰丝圭耋竺篁圭塑查丝些垄兰丝兰垫竺竺篁些竺垒型丝竺童堡垒墨童 l 1 i n t r o d u c t i o n i nt h i 8p a p e r ，w ea r ec o n c e r n e dw i t ht h en o n l l n e a rc o n s t r a l n e do p t l m l z a t i o np r o b l e mw l t h i n e q u a l i t yc o n s t r 础吐8 船f o l l o w s 竺翁 o ，倒_ 1 2 仇 ， ( 1 1 ) s t 易( z ) so ，j ，= 1 ，2 ，仇 ， ”一7 w h e r ez = ( z l ，z 2 ，z n ) r 舒w ed e n o t et h ef b a s i b l es e to fp r o b l e m ( 1 1 ) b y x = z r ”：缈( z ) o ，j ，) s i n c et h el a t e1 9 7 0 s ，t h es e q u e n t i a lq u a d r a t i cp m g r a m m i n g ( s q p ) m e t h o dh a sb e - c o m eo n eo ft h em o s te 色c t i v em e t h o d sf o r8 0 l v i n gn o n l i n e a rc o n s t r a i n e do p t i m i z a t i o n p r o b l e m sa dh 鹪b e e nw i d e l yi n v e s t i g a t e db ym a n ya u t h o r s ，8 e e ，e g 【1 】- 【4 】s i n c et h e s q pm e t h o dc a nb ev i e w e da st h en a t u r a le x t e n s i o no fn e w t o na 1 1 dq u a s i n e w t o nm e t h o d sf r o mt h eu n c o n s t r a i n e dt ot h ec o n s t r a i n e do p t i m i z a t i o n ，i te n i o y st h ec h a r a c t e r i s t i c s o fn e w t o n l i k em e t h o d ，j ，e ，j tp o s s e s s e st h ep r o p e r t i e s0 fr a p i dc o n v e r g e n c ew h e nt h e i t e r a t e sa r ec l ( ) 8 et ot h e8 0 l u “o n g e n e r a l l y t h es q pm e t h o dr e q u i r 髑t oc o m p u t eam 蠲t e rd i r e c t i o n 如a tt h e 缸t h i t e r a t i o nb y8 0 l 、，i n gt h e f o l l o 、) l r i n gq u a d r a t i cp r o g r a m ( q p ) s u b p r o b l e m m i nv ，( z ) + ；矿吼d s t ，毋( z ) + v 仍( ) 丁d o ，j ， ( 1 2 ) w h e r e i st h ec u r r e n ti t e r a t i v ep o i n t ，日膏舻。“i sa8 y m m e t r i ca n dp o s i t i v ed e 6 n i t e m a t r i ) 【嬲w e na sa ne s t i m a t eo ft h eh e s s i a no ft h el a 耵a n g i a n 龉s o c i a t e dw i t h ( 1 1 ) h o w e v e r ，i nt h et r a d i t i o n a is q pm e t h o d s ，t h eq p8 u b p r o b l e m ( 1 2 ) m a yb ei n c o n s i s t e n t ， t h a ti s ，t h ef e a s i b l e 鼬to f ( 1 2 ) m a yb ee m p t y t bo v e r c o m et h i ss h o r t c o m i n g ，v a r i o u s t e c h n i q u e sh a v eb e e np r o p o s e d ，s e e ，e g ，【5 】- 【9 卜h o w e v e r ，t h em 船t e rd i r e c t i o n 也g e m e r a t e db yq pm a yn o tb ef e a s i b l e ，s 0t h em o s to ft h ee a r l ys q pa l g o r i t h m 8b e l o n gt o t h es o - c a l l e di n f e a s i b l em e t h o d 8 i n1 9 8 7 ，p a n i e ra n dt i t s 8 1p r e s e n t e daf e 嬲i b l es q p ( f s q p ) a l g o r i t h mw h i c hi sg l o b a l l yc o n v e r g e n ta n dl o c a l l yt w 0 s t e ps u p e r l i n e a r l yc o n v e r - g e n t f i l r t h e rs t u d yo nt h ef s q pa l g o r i t h i 工l sc a nb ef o u n di n 1 0 一【1 5 】i na 1 1t h e s ef s q p a l g o r i t h m s ，a f t e rt h em a s t e rd i r e c t i o n 以b e i n go b t a i n e d ，i tm u s tb eu p d a t e db ys o m e s u i t a b l et e c h n i q u e s ，f o re x a m p l e ，s o i v i n ga n o t h e rq ps u b p r o b l e mo ras y s t e mo fl i n e a r e q u a t i o so ra ne x p l i c i tf o r m u l a o nt h eo t h e rh a n d ，t oo v e r c o m et h em a r a t o se f f 色c t ，a 8 u i t a b l e “h e i g h t o r d e r a u 姐l i 踟了d i r e c t i o nm u s tb ea d o p t e d i no r d e rt oo v e r c o m et h es h o r t c o m i n go ft h ei n f e 鹬i b i l i t yo f 以g e n e r a t e db y ( 1 2 ) ， k o s t r e v aa n dc h e n 【1 6 】，z h ua n dz h a n g 【1 刁p r e s e n t e dan e wt y p eo ff s q pa l g o r “h m s r 二= 一 llf矗， 皇查重堡圭兰竺篁圭竺叁垡丝垄兰丝墨! ! 丝竺兰些竺童型垒兰童堡垒苎童2 b yi n t r o d u d n ga 印e c i a lq p8 u b p m b l e m 粕f m l o w s m i nz + 矿凰d s t v ，( ) 7 d z ，( 1 3 ) 协( z ) + v 乃( z ) t d ，豫z ，j ， w h e r e 彳i s 觚a u x i l i a 可s c a l a rv a r i a b l e ，a n d 吼i sap o s i t i v ep a r a m e t e rc o r r e s p o n d i n gt o t h en e r a t i o np o i n t 如i n 【17 1 ，af e a s i b l ed e c e n td i r e c t i o ni so b t a i n e db ys o l v i n go n l yo n e q ps u b p r o b l e m ( 1 3 ) a tp e ri t e r a t i o n i nc o n t r a s tw i t ht r a d i t i o n a lf s q pa l g o r i t h m s ，i t n e e d st or e v i s et h em a s t e rd i r e c t i o n 以o n c et i m e u n d e rs o m ea s s u m p t i o n sw i t hs t r i c t c o m p l e m e n t a r i t y i ti sp r o v e dt h a tt h ea l g o r i t h mi sg l o b a l l ya n ds u p e r l l n e a “yc o n v e r - g e n t h o w e v e r ，f s q pa 1 9 0 r i t h m ss t i l lr e q u i r et os o l v eq ps u b p r o b l e m sw i t hi n e q u a l i t y c o 璐t r a i n t 8a te a c hi t e r a nw h i c hi 8c o m p u t a t i o n a l l ye x p e n s i v e i na d d i t i o n h o wt o u 8 es o m eg o o ds p a r s ea n ds y m m e t r i cp r o p e r t i e si ns o l v i n gq ps u b p r o b l e m sp e ri t e r a t i o n i 8v e r yi m p o r t 卸tf b rl a r g e8 c a l ep r o b l e m s ，b u ts q pt y p ea i g o r i t h m sd on o ts o l v et h e s e p r o b l 锄sw e l l h e n c e ，i ti 8d e s i r a b l et od e s i g na l g o r i t h m sw h i c ho n l yr e q u i r et h es o l u t i o n s o fl i n e a r8 y s t e m 8 i n1 9 8 8 ，p a n i e r ，t i t sa n dh e r s k o v i t s1 18 】p r o p o s e daf e a s i b l eq p f r e ea l g o r i t h mb 鹪e d o nt h ek k tc o n d i t i o 邶o f ( 1 2 ) ，i nw h i c h ，a te a c hi t e r a t i o n ，o n l yt w od i 吼r e n ts l e sn e e d t ob es o l v e d i no r d e rt oo b t a i naf b a s i b l ed e s c e n td i r e c t i o n i tn e e d st od oac o n v e xc o m b i n a t i o nw h i c hi 8e q u i v a l e n tt oas l e t h e yf u r t h e rb e n dt h ep r i m a ls e a r c hd i r e c t j o nb y 8 0 l v i n g8l e 船t8 q u a r e ss u b p r o b l e mt oa v o i dt h em a r a t o se f l e c t h o w e v e r ，i o r d e rt op r o v e t h eu n i f o mn o n - s i n p m l a r i t yo ft h ei t e r a t i o nm a t r 政s e q u e n c ea n dt h eb o u n d e d n e s so ft h e 印p r o x i m a t em u l t i p l i e rs e q u e n c e ，t h e ym u s ta s 8 u m et h a tt h es t r i c tc o m p l e m e n t a r i t yh o l d s a ta nf b 帮i b l ep o i n t 8 o t h e r w i s e ，t h ei t e r a t i o nm a t r i 】cm a yb e c o m ei l l c o n d i t i o n e d ，w h i c h w i l l l e a dt on o n _ c o n v e r g e n c e i nt h e 斟o b a l l yc o n v e r g e n tt h e o r e m ，t h e r ei sar e s t r i c t i v e c o n d i t i o nw h i c hr e q u i r e st 1 1 a tt h en u m b e ro f8 t a t i o n a r yp o i n t si s6 n i t e i na d d i n o n ，u n d e r t h ea s 8 u m p t i o n so ft h es t r i c tc o m p l e m e n t a r i t yc o n d i t i o na n dt h es e c o n do r d e r l ys u m c i e n t c o n d i t i o n ，l o c a l l yt w o _ 8 t e ps u p e r l i n e a rc o n v e r g e n c er e s u l t sa r ea l s oo b t a i n e d u n d e rt h es t i m u l a t i o no ft h ei d e a si n 1 8 1 ，s o m eo t h e ra u t h o r sp r e s e n t e ds o m es s l e a l g o r i t h m sw h i c ha r eq p f r e e ，s e e ，e 罾，【1 9 1 _ 【2 6 j q ia n dq i 【2 4 】p r o p o s e daf e a s i b l e q p f r e ea l g o r i t h mf o rs o l v i n g ( 1 1 ) b ym e a n so ft h ef i s c h e 卜b u r m e i s t e rf u n c t i o na n dt h e k k tn o n - s m o o t he q u a t i o ns y s t e m a te a c hi t e r a t i o n ，t h es u b p r o b l e mo ft h en e wq p 一 疳e em e t h o dc o n s i s t 8o ft h r e es l e s t ba v o i dt h em a r a t o se h e c t ，t h e ya l s os o l v eal e a s t s q u a r 髓蛐b p r o b l e m i n2 0 0 2 ，g a o ，g u d ，h ea n dw h 【2 5 1p r o p o s e daf e 船i b l ea l g o r i t h m o fs s l ef o r ( 1 1 1i nw h i c hf o u rs l e sw i t ht h e8 锄ec o e 珏l d e n tm a t r i xn e e dt ob e l v e d w i t h o u t l v i n gl e 蠲ts q u a r 档s u b p r o b l e ma te a c hi t e r a t i o n h o w e v e r ，i n 【2 4 】a n d 【2 5 1 ，a l l t h ei n e q u a l i t yc o n s t 嘣n t sm u s tb ei n v o l v e di nt h e i r8 u b p r o b l e m sw h i c hi sn o ts u i t a b l ef o r l a r g es c a l ep r o b l e m s m g ，“a dq i 【2 6 】i n t r o d u c e dt h ec o n c e p to f “w o r k i n g t ”w h i c h i 8a n 髑t i m a 七eo ft h ea c t i v ec o 璐t r a i n t ta i l dp r o p o s e daf e a s i b l es s l ea l g o r i t h m a t _ii“， 皇查兰塑圭兰竺篁耋丝叁垡些垄兰竺兰童竺竺兰些竺垒型丝兰奎堡垒墨童3 e a c hi t e r a t o n ，t h es u b p r o b l e mc o n 8 i s t so ff o u rr e d u c e ds u 王sw i t ho n l vt h ec o n s t r a i n t s i nw o r k i n gs e t ，w h i l et h o s en o ti nw o r k i n gs e ta r en e 西e c t e d i na d d i t i o n ，i tn e e d st od o ac o n v e xc o m b l n a t l o na te a c hi t e r a t i o nt oo b t a l na ni m p r o v m gd l r e c t l o i l _ f u r t h e r m o r e ， i n 【2 4 h 2 6 】，t h e 出o b a lc o n v e r g e n c el se s t a b l l s h e dw i t h o u tt h ea s s u m p t i o no fi s 0 1 a t e d n e 鹤 0 ft h e8 t a t i o n a r yp o i n t i no r d e rt oo b t a i nt h es u p e r l i n e a rc o n v e r g e n c e ，t h ea s s u m p t i o n 0 fs t r i c tc o m p l e m e n t 耐t yi sn e c e s s a r y w h i c hi sr a t h e rs t r o n ga n dd i 难c u l tt ot e s t i n a d d i t i o n ，t h ei t e r a t i o np o i n t sa r er e q u i r e dt ob es t r i c t l yi n t e r i o rp o i n ti n 【2 4 】a n d 【2 6 】 i no r d e rt oo v e r c o m et h ew e a k n e s si nt h em e t h o d ss t a t e da b o v p ，m a n ya u t h o r sm a n a g e dt or e m o v et h es t r o n gc o n d i t i o no fs t r i c tc o m p l e l e n t a r i t y i n2 0 0 1 ，x ua n d a i l g 【27 】p r o p o s e daq p f r e ea n ds u p e r l i n e a r l yc o n v e r g e n ta l g o r i t h mf o rp m b l e m ( 1 1 ) 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 yc o n d i t i o n a te a c hi t e r a t i o no ft h i sa l g o r i t h m ，o n em u s t8 0 l v eo n e o rf o u rs l 】王s ，a n dn e e d 8t od oac o n v e xc o m b i n a t i o nt oo b t a i na ni m p r o v i n gd i r e c t i o n ， w h i c hw i l la d dt h ea m o u n to fc o m p u t a t i o n o n l yo n es l en e e d st ob es o l v e da f t e ra f i n i t en u m b e ro fi t e r a t i o n s t br e d u c et h ea m o u n to ft h ec o m p u t a t i o n ，j i a nf 2 8 1 ，l i w a n ga n dh e 【2 9 】p r e s e n t e da n e wa l g o r i t h mo fs s l e ，r e s p e c t i v e l y a te a c hi t e r a t i o n ，t h e p m p o s e da l g o r i t h m sr e q u i r et os o l v eo n l yo n es u 王o rc o m p u t ea na u x i l i a r yd i r e c t i o nb y g e n e r a l i z e dg r a d i e n tp r o j e c t i o n ，w h i c hb e l o n gt oi n c o m p l e t es s l ea l g o r i t h m i nf 缸t ，t h i s t y p ea l g o r i t h mc a nb e 舱e n 嬲ac o m b i n a t i o no ft h es s l 】王m e t h o da n dt h et e c h n i q u eo f g e n e r a l i z e dg r a d i e n tp r o j e c t i o n t h e yo n l yn e e dt os o l v eo n es l ea n db e l o n gt oc o m p l e t e s s u 王a l g o r i t h mo n l yw h e nt h ei t e r a t i v ei n d e x 七i sl a 理ee n o u 曲t h e r e f o r e ，t h en u m e r i c a l e 能c ti 8n o tg o o ds i n c et h es e a r c hd i r e c t i o ni su s u a l l y y i e l d e db yt h eg e n e r a l i z e dg r a d i e n t p r o j e c t l o n u n d e rt h ew e a k e rc o n d i t i o n sw i t h o u ts t r i c tc o m p l e m e n t a r i t yc o n d l t i o n ，t h e s e a i g o r i t h m 8p o s s e s sg l o b a l ，s t r o n g ，s u p e r l i n e a ra n dq u a d r a t i cc o n v e r g e n c e i nt h i sp a p e r ，w ea i mt op r o p o s ean e wc o m p l e t es s l ea l g o r i t h mw i t h o u ts t r i c tc o m - p l e m e n t a r i t yc o n d i t i o n o u ri d e ai st or e p l a c et h eq ps u b p r o b l e m ( 1 3 ) b yo n eo rt w o s u 孺8 0t h a tt h ec o m p u t a t i o ne 疗o r tp e ri t e r a t i o ni sm u c hl e 豁t h a nt h a to ft h ea l g o r i t h m i n 【1 7 】s u p p o s et h a t ( 也，魂) i st h es o l u t i o no ft h es u b p r o b i e m ( 1 3 ) s oi ti sak k tp o i n t o f ( 1 3 ) 8 i n c et h ep r o b l e m ( 1 3 ) i sac o n v e xp r o g r a mw i t hl i n e a rc o n s t r a i n t 8 ，i e ，t h e r e e x i s t sac o r r e s p o n d i n gk k t m u l t i p l i e rv e c t o r ( p k ，a 酊，j ，) s u c ht h a t p i + 仇a 幻= 1 ，风d 女+ p v ，( z ) + 乏二a 幻v 毋( z ) = o ， 3 lj f o p 上( 一v ，( z 七) t d + 钰) o ， osa 幻上( 一毋( z 七) 一v 毋( z 量) 。z l d + ，珐z ) o ，j j ， w h e r et h en o t a t i o nz 上掣m e a n 8 护暑，= o b a s i n go nt h ek k t c o n d i t i o n 8a b o v e ，v i a i n t r o d u c i n ga na p p r o ) ( i m a t ea c t i v ec o n s t r a i n ts e t 厶o f ( 1 1 ) a tp o i n tz ia n dd i f r e r e n t n o n n e g a t i v ep a r a m e t e r 8t 硒f o r 歹，w h i c hc a n 印e e du pt h er a t eo fc o i l v e r g e n c e ，w e t ， 皇叁兰丝圭兰竺篁圭竺查垡些垄兰丝兰! ! 竺竺兰竺竺垒型竺竺童堡垒墨量 4 i n t r o d u c e a n e ws l e 嬲f o u o w b i 以+ 锄a o ，= 1 ，m 硪+ 破v ，( z k ) + 魁，v 缈( 巩) = o ， iv ，( 茹k ) t d 2 一z 2 = o ，a 2 j 幻( z e ) + v 岛( 。k ) 丁醒一辄j 碟= o ，j 厶 o b v i o u s l y t h es y s t e ma b o v ei se q u i v a l e n tt ot h ef o l l o w i n gs y s t e m 删+ 互a ( v 咖。一钧w o o ) _ - v “瓤) ， ( 1 4 ) ，“ 1 1 4 l 【( v 岛( z ) 一叩幻v ，( z ) ) t d 2 + a 2 j 毋( z k ) = o ，j 厶 i nt h i sw o r k ，w et a k et h es o l u t i o n 壤o f ( 1 4 ) a st h em a s t p rd i r e f t i o n h o w p v e r ， i sn o te n t i r e l ys u i t a b l ea sas e a r c hd i r e c t i o n i n d e e d ，a l t h o u g h 蠼i saf b a s i b l ed e s c e n t d i r e c t i o n ，i tm a yb ez e r oa ts o m ei t e r a t i o np o i n t sw h i c ha r en o tk k tp o i n t so f ( 1 1 ) ， s i n c et h ep r o p e r t yo fn o n n e g a t i v i t yo ft h em u l t i p l i e rv e c t o rm a yn o tb eg u a r a n t e e di ft h e a l g o r i t h m8 t o p sa tt h ep o i n t 瓢w i t h = o t h i se 髓c tc a nb ea v o i d e di fo n es u b s t i t u t e s an o n p o s i t i v e 肌m b e rv ，j i ne a c hr i 曲t h a n d8 i d eo f ( 1 4 ) e x c e p tf o rt h ef i r s t e q u a t i o n t h e r e f o r e ，a f t e rd 2b e i n go b t a i n e d ，w ei n t m d u c ea n o t h e rs l e 鹪f 0 1 1 0 w st o y i e l dan e wd i r e c t i o n 砚， i 丑以+ a ：，( v 毋( z 女) 一艰幻v ，( 巩) ) = 一v ，( z ) ，、 os c 纳耐 v 幻( z ) 一( 1 | v 毋扛) l l v ，p ) ，j t ，) n 他轨地f 讯却e 仃如耐扣r c ( 【o ，加 ) 】 p r o o f b yc o n t r a d i c t i o n ，w e8 u p p 0 8 et h a tf d re a c h “= ，t h e r ee x i s t s “【0 ，女】s u c h t h a tt h ev e c t o r