（计算数学专业论文）非凸二次优化问题的进一步研究.pdf

南开大学学位论文使用授权书 根据南开大学关于研究生学位论文收藏和利用管理办法，我校的博士、硕士学位获 得者均须向南开大学提交本人的学位论文纸质本及相应电子版。 本人完全了解南开大学有关研究生学位论文收藏和利用的管理规定。南开大学拥有在 著作权法规定范围内的学位论文使用权，即：( 1 ) 学位获得者必须按规定提交学位论文( 包 括纸质e o , 话t j 本及电子版) ，学校可以采用影印、缩印或其他复制手段保存研究生学位论文， 并编入南开大学博硕士学位论文全文数据库：( 2 ) 为教学和科研目的，学校可以将公开 的学位论文作为资料在图书馆等场所提供校内师生阅读，在校园网上提供论文目录检索、文 摘以及论文全文浏览、下载等免费信息服务；( 3 ) 根据教育部有关规定，南开大学向教育部 指定单位提交公开的学位论文；( 4 ) 学位论文作者授权学校向中国科技信息研究所和中国学 术期刊( 光盘) 电子出版社提交规定范围的学位论文及其电子版并收入相应学位论文数据库， 通过其相关网站对外进行信息服务。同时本人保留在其他媒体发表论文的权利。 非公开学位论文，保密期限内不向外提交和提供服务，解密后提交和服务同公开论文。 论文电子版提交至校图书馆网站：h t t p ：2 0 2 1 1 3 2 0 1 6 1 ：8 0 0 1 i n d e x h t m 。 本人承诺：本人的学位论文是在南开大学学习期间创作完成的作品，并已通过论文答辩： 提交的学位论文电子版与纸质本论文的内容一致，如因不同造成不良后果由本人自负。 本人同意遵守上述规定。本授权书签署一式两份，由研究生院和图书馆留存。 作者暨授权人签字： 王亡丝 2 0 1 0 年6 月1 0 日 南开大学研究生学位论文作者信息 论文题目非凸二次优化问题的进一步研究 姓名王广锋 学号 2 1 2 0 0 7 0 0 2 0 答辩日期 2 0 1 0 年5 月2 9 日 论文类别博士口学历硕士口硕士专业学位口高校教师口同等学力硕士口 院 系 骶数学科学学院专业计算数学 联系电话l5 8 2 2 8 8 9 8 2 3e m a i l g f w 2 0 1 2 q 1 6 3 t o m 通信地址( 邮编) ：天津市南开大学西区公寓3 号楼3f - i4 0 7 室 备注： 是否批准为非公开论文 否 注：本授权书适用我校授予的所有博士、硕士的学位论文。由作者填写( 一式两份) 签字后交校图书 馆，非公开学位论文须附南开大学研究生申请非公开学位论文审批表。 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下进行研究工作所 取得的研究成果。除文中已经注明引用的内容外，本学位论文的研究成果不包 含任何他人创作的、己公开发表或者没有公开发表的作品的内容。对本论文所 涉及的研究工作做出贡献的其他个人和集体，均已在文中以明确方式标明。本 学位论文原创性声明的法律责任由本人承担。 学位论文作者签名： 王亡锤2 0 1 0 年6 月1 0 日 非公开学位论文标注说明 根据南开大学有关规定，非公开学位论文须经指导教师同意、作者本人申 请和相关部门批准方能标注。未经批准的均为公开学位论文，公开学位论文本 说明为空白。 论文题目 申请密级 口限制( 2 年)口秘密( 1 0 年)口机密( 2 0 年) 保密期限 2 0 年月日至2 0年月日 审批表编号批准日期 2 0 年月 日 限制2 年( 最长2 年，可少于2 年) 秘密1 0 年( 最长5 年，可少于5 年) 机密2 0 年( 最长l o 年，可少于1 0 年) 摘要 这篇文章我们讨论最小化非凸二次约束二次目标函数问题，当问题被 定义在复数域上时，我们证明强对偶性是成立的，并且得到最优点的充要条 件。相同的分析被推广到拉格朗日乘子的k k t 点。当问题被定义在实数域上 时我们证明了当约束个数m = 3 并且在一定的条件下，强对偶性是成立的。 在一定的假设条件下，根据实数域和复数域问题的关系我们也得到了一个近 似解。对于双二次最优化问题，我们也进一步研究了复数域上原问题与半定 松弛问题的紧性。 关键词：复矩阵分解；非凸二次优化问题；强拉格朗日对偶；半定规划松弛；双 二次优化问题；s 引理 a b s t r a c t i nt h i st h e s i sw ef i r s t l yc o n s i d e rt h ep r o b l e mo fm i n i m i z i n gan o n c o n v e x q u a d r a t i cf u n c t i o n ，s u b j e c tt ot h r e eq u a d r a t i ci n e q u a l i t yc o n s t r a i n t s w h e nt h ep r o b 1 e mi sd e f i n e do v e rc o m p l e xp l a n ew es h o wt h a ts t r o n gd u a l i t yh o l d sa n do b t a i n n e c e s s a r ya n d s u f f i c i e n to p t i m a l i t yc o n d i t i o n s t h es a m e a n a l y s i si se x t e n d e dt ot h e l a g r a n g i a nm u l t i p l i e r sa tak k tp o i n t w h e nt h ep r o b l e mi sd e f i n e do v e rt h er e a l p l a n e ，w ea l s od e v e l o pas u f f i c i e n tc o n d i t i o nf o rs t r o n gd u a l i t yu n d e rs o m em i l d c o n d i t i o n w ec a n p r o d u c ea na p p r o x i m a t es o l u t i o na c c o r d i n gt ot h er e l a t i o no fr e a l a n d c o m p l e xd o m a i np r o b l e mu n d e rs o m ea s s u m p t i o n s f o rb i q u a d r a t i co p t i m i z a - t i o np r o b l e m ，w ef u r t h e rc o n s i d e rt h et i g h t n e s so ft h ep r i m a lp r o b l e ma n dt h es d p p r o b l e m k e y w o r d s ：c o m p l e xm a t r i xd e c o m p o s i t i o n ，n o n c o n v e xq u a d r a t i co p t i m i z a t i o n p r o b l e m ，s t r o n gl a g r a n g i a nd u a l i t y , s e m i d e f i n i t ep r o g r a m m i n gr e l a x a t i o n ，b i q u a d r a t i co p t i m i z a t i o np r o b l e m ，s - l e m m a c o n t e n t s 摘 a b s t r a c t i c o n t e n t s i i i 1i n t r o d u c t i o na n dp r e l i m i n a r i e s 1 1t h ed e v e l o p m e n to fs o l v i n gn o n c o n v e xq u a d r a t i co p t i m i z a t i o n 1 2 n o t a t i o n 1 3r a n k - o n ed e c o m p o s i t i o no fp s dm a t r i c e s 1 4t h em a i nc o n t r i b u t i o n 2 s t r o n gd u a l i t yf o r ac l a s so fn o n c o n v e xq u a d r a t i cm i n i m i z a t i o n 2 1 s t r o n gd u a l i t yf o rt h er e a ld o m a i n ：an e c e s s a r ya n d s u f f i c i e n tc o n d i t i o n 2 1 1c o n v e xl a g r a n g i a nf u n c t i o n 1 4 4 7 8 8 1 0 2 1 2 s t r o n gd u a l i t y ：an e c e s s a r ya n d s u f f i c i e n tc o n d i t i o n1 0 2 1 3t h el a g r a n g i a nf u n c t i o na n dt h ek k tc o n d i t i o n 2 2t h ec o m p l e xc a s e 2 2 1c o n v e xl a g r a n g i a nf u n c t i o n i i i 1 1 1 2 1 3 c o n t e n t s i v 2 2 2 t h e l a g r a n g i a nf u n c t i o na n d t h ek k tc o n d i t i o n 3f u r t h e rr e s u l t sf o rn o n c o n v e xq u a d r a t i co p t i m i z a t i o nw i t ht h r e e c o n s t r a i n t s 3 1t h er e a lc a s e 3 2 t h ec o m p l e xc a s e 3 3t h ec o m p l e xr e l a x a t i o n 4 t i g h t n e s so fb i - q u a d r a t i co p t i m i z a t i o np r o b l e m 4 1t h er e a lb i q u a d r a t i co p t i m i z a t i o np r o b l e m 4 2t h ec o m p l e xb i - q u a d r a t i co p t i m i z a t i o np r o b l e m b i b l i o g r a p h y 致谢 个人简历 9 3 3 6 9 2 2 4 2 5 6 1 2 2 2 2 3 3 3 4 4 4 c h a p t e r 1 i n t r o d u c t i o na n l lr r e n m l n a r l e s 一 1 1n 1 1t h e d e v e l o p m e n t o f s o l v i n gn o n c o n v e xq u a d r a t i co p t i m i z a t i o n f o rt h ep r o b l e mo fm i n i m i z i n gan o n c o n v e xq u a d r a t i co b j e c t i v ef u n c t i o ns u b j e c tt o q u a d r a t i cc o n s t r a i n t s ，f e wa l g o r i t h m sa r ea v a i l a b l e w i t h o u tt h ec o n v e x i t ya s s u m p t i o n t h e r ei s ，i ng e n e r a l ，n oa s s u r a n c et h a tal o c a lm i n i m u mi sg l o b a l i nr e c e n ty e a r s ，t h e s e m i d e f i n i t er e l a x a t i o n ( s d r ) t e c h n i q u eh a sb e e na tt h ec e n t e ro fs o m eo ft h ev e r ye x - c i t i n gd e v e l o p m e n t si nt h ea r e ao fs i g n a lp r o c e s s i n ga n dc o m m u n i c a t i o n s a n ds d r h a sb e e ns h o w ng r e a ts i g n i f i c a n c ea n dr e l e v a n c eo nav a r i e t yo fa p p l i c a t i o n s r o u g h l y s p e a k i n g ，s d ri sap o w e r f u l ，c o m p u t a t i o n a l l ye f f i c i e n ta p p r o x i m a t i o nt e c h n i q u ef o ra h o s to fav e r yd i f f i c u l to p t i m i z a t i o np r o b l e m s e s p e c i a l l y ，i tc a nb ea p p l i e dt om a n y n o n c o n v e xq u a d r a t i c a l l yc o n s t r a i n e dq u a d r a t i cp r o g r a m s z h a n ga n dh u a n gs t u d i e dt h e a p p r o x i m a t i o na l g o r i t h m sf o rac l a s so fd i s c r e t eq u a d r a t i co p t i m i z a t i o np r o b l e m sf o r t h eh e m i t i a nc o m p l e xf o r mi n 1 】i nf a c t ，s d rh a sb e e ns t u d i e da n da p p l i e di nt h e o p t i m i z a t i o nc o m m u n i t yl o n gb e f o r ei tm a d ei t si m p a c to ns i g n a lp r o c e s s i n ga n d c o r n 。 m u n i c a t i o n s t h ei d e ao fs d rc a na l r e a d yb ef o u n di na np a p e ro fl o v t i s zi n19 7 9 【2 】，b u ti tw a sa r g u a b l yt h es e m i n a lw o r ko fg o e m a n sa n dw i l l i a m s o ni n19 9 5 【3 】t h a t s p a r k e dt h es i g n i f i c a n ti n t e r e s ta n dr a p i dd e v e l o p m e n t o fs d r t e c h n i q u e s i nt h a tw o r k ， i tw a ss h o w nt h a ts d rc a nb eu s e dt op r o v i d ea na p p r o x i m a t i o na c c u r a c yo fn ow o r s e t l l a n0 8 7 5 6f o rt h em a x i m u mc u t p r o b l e m i no t h e rw o r d s e v e nt h o u g ht h em a x i m u m c u tp r o b l e mi sn p h a r d ，o n ec o u l de f f i c i e n t l yo b t a i nas o l u t i o nw h o s eo b j e c t i v ev a l u ei s a tl e a s t0 8 7 5 6t i m e st h eo p t i m a lv a l u eu s i n gs d r s i n c et h e n ，w eh a v es e e nan u m b e r o fd e d i c a t e dt h e o r e t i c a la n a l y s i st h a te s t a b l i s ht h es d ra p p r o x i m a t i o na c c u r a c yu n d e r d i f f e r e n tp r o b l e m ，a n dt h a th a v eg r e a t l yi m p r o v e do u ru n d e r s t a n d i n go ft h ec a p a b i l i t i e s o f s d r i nt h i st h e s i s ，w em a i n l yc o n s i d e rt h ef o l l o w i n gn o n c o n v e xr e a la n dc o m p l e xq u a d r a t i c o p t i m i z a t i o np r o b l e m ( q p r ) m i nq o ( x ) = x t q o x 一2 x 丁b o s t 啦( z ) = x r q t z 一2 x t b i + q 0 ，i = l ，m w h e r eq i s 饥n ，b i r n ，勺r ，( 歹= 0 ，m ) ，z r 竹 ( q p c ) m i nq o ( z ) = z q o z 一2 7 z e ( z 盯b o ) s t q i ( z ) = z q i z 一2 t i e ( z 日玩) + c 0 ，i = 1 ，m w h e r eq 冗“，b i c 竹，c t r ，( i = 0 ，m ) ，z c n w h e nm = 1a n d ( 了1 _ 0i n ( q p r ) ，t h e ( q p r ) i sk n o w n a st h et r u s tr e g i o ns u b p r o b l e m t h es u b p r o b l e mh a st h e f o r m ( t r ) m i nx t b x + 2 9 t z s t i i x l l 2 6 z r n t h e p r o b l e mh a sb e e ns t u d i e d ( s e e 4 ) w h e nm = 2 ，t h ep r o b l e m ( q p r ) a p p e a r sa sa s u b p r o b l e m i ns o m et r u s tr e g i o na l g o r i t h m sf o rc o n s t r a i n e do p t i m i z a t i o nw h e r et h eo r i g i n a lp r o b l e mi st om i n i m i z eag e n e r a ln o n l i n e a rf u n c t i o ns u b j e c tt oe q u a l i t yc o n s t r a i n t s t h es u b p r o b l e mh a st h ef o r m i_i_-_-_-_-_-i_h_，-一一 c h a f 叮e r1 d n r o d u c t i o na n dp r e l n 缸n ar i e s3 ( t t r s ) m i nx t b x + 幻t z s t 1 i x l i a l i a t z + cj j 毒 z r n ( s e ee g 4 _ 8 】) s t u r r na n dz h a n g 【9 】s h o w e dt h a ti fm = 1 t h et h es d pr e l a x a t i o n o f ( q p r ) i st i g h t ，a n da no p t i m a ls o l u t i o nf o r ( q p r ) c a nb eo b t a i n e df r o ma no p t i m a ls o l u t i o no fi t ss d pr e l a x a t i o n y ea n dz h a n g 【1 0 】s h o w e dt h a ti fm = 2a n d c e r t a i na d d i t i o n a lc o n d i t i o n sa r es a t i s f i e dt h e nt h es d pr e l a x a t i o nf o r ( q p r ) c a ns t i l l b et i g h t i nt h et h e s i s ，w ew i l lp r o v et h a tt h es d pr e l a x a t i o no f ( q p r ) i sa l s ot i g h t i fm = 3u n d e rs o m ec o n d i t i o n s o p t i m i z a t i o np r o b l e m sw i t hc o m p l e xv a r i a b l e sa p p e a rn a t u r a l l yi nm a n ye n g i n e e r i n ga p p l i c a t i o n s f o re x a m p l e ，i ft h ee s t i m a t i o np r o b l e m i sp o s e di nt h ef o u r i e rd o m a i n ，t h et y p i c a l l yt h ep a r a m e t e r st ob ee s t i m a t e dw i l lb e c o m p l e x 1l 】【1 2 】i nt h ec o n t e x to fd i g i t a lc o m m u n i c a t i o n s ，m a n ys i g n a lc o n s t e l l a t i o n s a r em o d e l l e da sc o m p l e xv a l u e d a n o t h e ra r e aw h e r e c o m p l e xv a r i a b l e sn a t u r a l l ya r i s e i sn a r r o w b a n da r r a yp r o c e s s i n g 【1 3 1 i n 1 4 1 ，h u a n ga n d z h a n gc o n s i d e r e dt h ef o l l o w i n gt w ot y p e s o fc o m p l e x q u a d r a t i cm a x i m i z a t i o np r o b l e m s ：( i ) m a x i m i z a t i o nz h q z ， s u b j e c tt oz g = 1 ，( k = 1 ，n ) ，w h e r eq i sah e r m i t i a nm a t r i xw i t ht r q = 0 a n dz c ni st h ed e c i s i o nv e c t o r ；t h e yp r o p o s e da nf 2 ( 1 l o g n la p p r o x i m a t i o na l g o r i t h mf o rt h ec o m p l e xd i s c r e t ep r o b l e m g o e m a n sa n dw i l l i a m s o n 15 】p r o p o s e d ar a n d o m i z e da p p r o x i m a t i o na l g o r i t h mv i ac o m p l e xs d pr e l a x a t i o n ，f o rs o l v i n gt h e m a x 一3 一c u tp r o b l e m ，w h i c hi sf o r m u l a t e da saq u a d r a t i cm a x i m i z a t i o np r o b l e mw i t h c o m p l e x - v a l u e dd e c i s i o nv a r i a b l e s i np a r t i c u l a r , t h e yc o n s i d e rt h ef o l l o w i n gm o d e l m a x i m i z ez h q zs u b j e c tt o 耀= 1 ，( k = 1 ，n ) w i l l i a m s o ns h o w e dt h a tt h ea l - g o r i t h ma c h i e v e sa0 8 3 6a p p r o x i m a t i o nr a t i o z h a n ga n dh u a n g 1 】e x t e n d e dg o e m a n sa n dw i l l i a m s o n sm o d e l f o rt h ed i s c r e t ev e r s i o no ft h em o d e l ：m a x i m i z ez h q z s u b j e c tt oz 孑= 1 ，k = 1 ，礼，z h a n ga n dy eo b t a i n e dt l l em 2 ( 1 一c o s 等) 8 丌a p p r o x m a t i o nr a t i ob a s e do ng r o t h e n d i e c k si n e q u a l i t y h e ，l u oe ta lc o n s i d e r e dt w o q u a d r a t i co p t i m i z a t i o nm o d e l s ：( 1 ) m i n x c x l x a k x 1 ，z f n k = 0 ，m 】；( 2 ) m a x x + c x i x + a k x i ，x f n ，k = 0 ，1 ，m i fo n eo fa ：si si n d e f i n i t ew h i l e o t h e r sa n dca r ep o s i t i v es e m i d e f i n i t e ，t h e yp r o v e dt h a tt h er a t i ob e t w e e nt h eo p t i m a l c h a p r t e r1 巧i r o d u c t l 0 na n dp r e l n 厦i n a r i e s 4 v a l u eo f ( 1 ) a n di t ss d pr e l a x a t i o ni su p p e rb o u n d e db yb yo ( m 2 ) w h e nfi st h er e a l d o m a i nr ，a n db yo ( m ) w h e nfi st h ec o m p l e xp l a n ec a ia n dz h a n g 【1 6 】p r e s e n t e d av e r i f i a b l ec o n d i t i o nw h i c hi n d i c a t e sw h e t h e ro rn o tt h es d pr e l a x a f i o no f ( q p r ) i s t i g h t s i n c et h el a g r a n g i a nd u a lo fag e n e r a lq u a d r a t i c a l l yc o n s t r a i n e dq u a d r a t i cp r o - g r a mi st h ed u a lo fi t ss d pr e l a x a t i o n ，t h e yg e tan e c e s s a r ya n ds u f f i c i e n tc o n d i t i o nf o r s t r o n gd u a l i t y w em a k ea ne x t e n s i o nt oc o m p l e x d o m a i nb ye x p l o i t i n gt h e i rm e t h o d s 1 2n o t a t i o n t l 啪u g h o u tt h i st h e s i s ，rd e n o t e st h es e to fa l lr e a ln u m b e r s ，孑d e n o t e st h ec o n j u g a t eo fac o m p l e xn u m b e r 名c nd e n o t e st h es p a c eo fn d i m e n s i o n a lc o m p l e xv e c t o r s f o ra n yz c n ，z 月d e n o t e st h ec o n j u g a t et r a n s p o s eo fz i e ，f o rz = z + i y ，w h e r e z ，y c na n di 2 = 一l ，z 日= x t i y t 冗na n ds nd e n o t et h es e t so fn nc o m p l e xh e r m i t i a na n dr e a ls y m m e t r i cm a t r i c e s ，r e s p e c t i v e l y f o ra n yz 冗n ，r e z a n di m zd e n o t et h er e a lp a r ta n d i m a g i n a r yp a r to fz r e s p e c t i v e l y f o rag i v e nm a t r i xz 咒nm e a n st h a tr e zi ss y m m e t r i ca n di m zi ss k e w - s y m m e t r i c 爿华( h 华+ ) d e n o t e st h ec o n e so fc o m p l e xh e r m i t i a np o s i t i v es e m i d e f i n i t e ( p o s i t i v ed e f i n i t e ) m a t r i c e s ，i e z o ( z - 0 1 t h ei n n e rp r o d u c to fa n yt w oc o m p l e xm a t r i c e si sd e f i n e da s a b = r e ( t r a h b ) = t r ( r e a ) t ( b ) + ( i m a ) t ( i m b ) 】，w h e r e t rm e a n st h a t t h et r a c eo fam a t r i xa n dtd e n o t e st h et r a n s p o s eo fam a t r i x f o ras q u a r em a t r i xm ， t h en o t a t i o n r a n k ( m ) ，r a n g e ( m ) ，n u l l ( m ) s t a n df o r , r e s p e c t i v e l y , t h er a n k , t h e r a n g es p a c e ，a n dt h en u l ls p a c eo fm a t r i xm 1 3r a n k - - o n ed e c o m p o s i t i o no fp s dm a t r i c e s i nt h i ss e c t i o n ，w ep r e s e n ts e v e r a lr a n k o n ed e c o m p o s i t i o nt h e o r e m sf o rp o s i t i v e s e m i d e f i n i t em a t r i c e s l e m m a l 1a n dl e m m a l 2a l ea b o u tt h er e a ls y m m e t r i cs e m i d e f - i n i t em a t r i c e s l e m m a l 3 ，l e m m a l 4a n dt h e o r e m l 1a l ea b o u tt h eh e r m i t i a ns e m i d e f - i n i t ep o s i t i v em a t r i c e s c h a p t e r1 i n t r o d u c t i o na n dp r e l n l 矾 r i e s5 l e tx s nb ear e a ls y m m e t r i cp o s i t i v es e m i d e f i n i t e ( p s d ) m a t r i x ，a n da s nb ea r e a ls y m m e t r i cm a t r i x l e m m a1 1 1 l 1 0 1 ) l e tx 守b ear e a ls y m m e t r i cp o s i t i v es e m i d e f i n i t em a t r i xw i t h r a n kna n da s nb ear e a ls y m m e t r i cm a t r i x s u p p o s et h a ta x 0 t h e nt h e r e e x i s t sar a n k o n ed e c o m p o s i t i o n f o rxs u c ht h a t r x = 叩芗 i = l a n dx t a _ z i o f o ra l li = 1 ，7 i f , i n p a r t i c u l a r , g x = 0 ，t h e nz t g z = 0 f o ra l l i = 1 ，n l e m m a1 2 ( t h e o r e m3 4 ，j 7 1 ) l e ta i ，a 2 伊w i t ha a x = 6 1 ，a 2 x = 如 t fr ：= r a n k ( x ) 3 t h e ni np o l y n o m i a l t i m e ( r e a l n u m b e rc o m p u t a t i o n ) o n ef i n d sa r a n k o n ed e c o m p o s i t i o n f o rx s u c ht h a t r x = x i x r ， t = l n r 血 r t h e p r o p o s i t i o nc a nb ee x t e n d e dt ot h eh e r m i t i a nc a s e l e m m a1 3 r c o r o l l a r y2 2 ，j 8 1 jl e ta ，b 咒“b et w oa r b i t r a r ym a t r i c e s l e tz 咒nb e a p o s i t i v e s e m i d e f i n i t e m a t r i x w i t hr a n k ，：s u p p o s e t h a t a z t l o a n d b * z _ 2 0 t h e nt h e r ei sar a n k - o n ed e c o m p o s i t i o n f o rz s u c ht h a t z j z h 栌a 乃垒10a n d 才b z j 垒2 0 ， f o ra l lj = 1 ，r ， o 一 n r ， ， l 1 = | i 口口 0 = = t；丁； z z ： z z 1 2 a a ，i，、【 ，芦 = z c h a f 叮e r1 i n t r o d u c t l 0 na n dp r e l m i n a r i e s 6 w h e r e 垒d e n o t e s = ，o r l e m m a1 4 r t h e o r e m2 j 71 1 9 ) l e ta 1 ，4 2 ，a 3 7 - l n ，a n d x 冗2b ean o n z e r o h e r m i t i a np o s i t i v es e m i d e f i n i t em a t r i x t f7 = r a n k ( x ) 3 ，t h e no n ec a nf i n di n p o l y n o m i a l - t i m e ar a n k - o n ed e c o m p o s i t i o no fx s u c ht h a t x = ：巡 r ， 一必 一f， ：巡 r ， 甄z ， t h e o r e m1 1 ( t h e o r e m2 2 ，j 9 1 ) s u p p o s en 3 l e ta 1 ，a 2 ，a a 冗n ，a n dx 氕2 b ean o n z e r oh e r m i t i a np o s i t i v es e m i d e f i n i t em a t r i xh a v i