（运筹学与控制论专业论文）对称锥互补问题的可解性研究.pdf

北京交通大学硕士学位论文中文摘要 中文摘要 摘要：对称锥上互补问题( s c c p ) 为标准互补问题( n c p ) 、二阶锥互补问题( s o c c p ) 和半定互补问题( s d c p ) 等提供了统一的框架，是一类内容新颖、涵盖面宽、理 论丰富、且有广泛应用背景的均衡优化问题由于引入了欧几里德若当代数这一 有力工具，近几年来发展迅速，得到了很多深入的结果本论文主要利用欧几里德 若当代数技术，对s c c p 的可解性进行了研究 本文共分为三章， 第一章简述对称锥互补问题的研究内容及发展状况，且作为预备知识。引入 了欧几里德若当代数这一技术，并对我们所关心的对称锥互补问题可解性的研究 历史和现状做了分析 第二章中，在对标准线性互补问题可解性研究情况进行分析、总结的基础上， 我们推广了其中的一些可解性结果定义了欧几里德若当代数上线性变换的充分 性性质，并证明这种充分性与其相应的对称锥互补问题的解的性质紧密相关其 中，列充分性质与s c c p 解集的凸性紧密相关，二行充分性质在一定条件下与 s c c p 解的存在性有关 第三章总结了本文的主要工作，同时对进一步可能的研究工作进行了展望 关键词：对称锥互补问题；欧几里德若当代数；线性变换；列充分；行充分 分类号：0 2 2 4 北京交通大学硕士学位论文 a b s t r a c t a b s t r a c t a b s t a c t ：s y m m e t r i cc o r l ec o m p l e m e n t a r i t yp r o b l e m ( s c c p ) i n c l u d 鹤t h e n o n n e g a t i v eo r t h a n tn o n l i n e a rc o m p l e m e n t a r i t yp r o b l e m ( n c p ) ，t h es e c o n d - o r d e r c o n ec o m p l e m e n t a r i t yp r o b l e m ( s o c c p ) ，a n dt h es e m i - d e f i n i t ec o m p l e m e n t a r i t y p r o b l e m ( s d c p ) t h i sm o d e lp r o v i d e sas i m p l e ，n a t u r a l ，a n du n i f i e df r a m e w o r k i t h a sw i d ea p p l i c a t i o n si ne n g i n e e r i n g ，e c o n o m i c s ，m a n a g e m e n ts c i e n c e ，a n do t h e r f i e l d s b ye m p t y i n gt h et e c h n i q u eo fe u c l i d e a nj o r d a na l g e b r a , w eg e tm a n y e m b e d d e dr e s u l t s t h i st h e s i si sm 血l yc o n c e r n e dw i t ht h es o l v a b i h t yo ft h e s c c p t h e r ea r et h r e ec h a p t e r si nt h i st h e s i s s i n c ee u c l i d e a nj o r d a na l g e b r at e c h n i q u ep r o v i d e sap o w e r f u lt o o lf o rd e - s c r i b i n gt h es t r u c t u r eo fs y m m e t r i cc o n e sa n ds e q u e n t i a l l ys o l v i n gs y m m e t r i cc o n e o p t i m i z a t i o np r o b l e m s ，i nc h a p t e r1 ，w er e c a l l e ds o m eb a s i cc o n c e p t sa n du s e f u l r e s u l t so fe u c l i d e a nj o r d a na l g e b r a s t h e nw ei n t r o d u c e dt h es y m m e t r i cc o n e c o m p l e m e n t a r i t yp r o b l e m i nc h a p t e r2 ，w ei n t r o d u c e dt h es o l v a b i l i t yr e s u l t so fs c c p a f t e rb r i e f l y s t a t e ds o m ei m p o r t a n tp r o p e r t i e sw i t hr e g a r d st ot h es o l v a b i l i t yo fs t a n d a r dc o m - p l e m e n t a r i t yp r o b l e m ，w eg i v et h es u f f i c i e n c yo fl i n e a rt r a n s f o r m a t i o n so ne u - c l i d e a nj o r d a na l g e b r a s ，a n ds h o wt h a tt h e yh a v ec l o s ec o n n e c t i o nw i t ht h ee x i s - t e n c ea n dc o n v e x i t yo ft h es o l u t i o ns e to fs c c p i nc h a p t e r3 ，t h em a i nc o n c l u s i o n sa n di n n o v a t i o no ft h i st h e s i sa r es u l n i n a - r i z e d a n dt h ef u r t h e rr e s e a r c ha r ep r e s e n t 碰la tl a s t k e y w o r d s ：s y m m e t r i cc o n ec o m p l e m e n t a r i t yp r o b l e m ；e u c l i d e a nj o r d a n a l g e b r a ；l i n e a rt r a n s f o r m a t i o n ；c o l u m n - s u f f i c i e n c y ；r o w - s u f f i c i e n c y c l a s s n o ：0 2 2 4 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规息特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅同意学校向国家 有关部门或机构送交论文的复印件和磁盘 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名；赤砗燕 签字日期；细8 年i 月日比了嵋 乃 ，填 弓蚍 h 萨 备 吃 北京交通大学硕士学位论文独创性声明 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研 究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得北京交通大学或其他教育机构的学位或证书 而使用过的材料与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意 学位论文作者签名： 毒帐 1 9 签字日期；眸珀z 日 致谢 作者衷心感谢导师修乃华教授三年来的悉心指导，修老师严谨的治学态度和 科学的工作方法是我的榜样，修老师在学术、工作和生活上给予我悉心的照顾和 帮助，在此衷心感谢三年来修老师对我的关心和指导l 特别感谢中科院应用数学所的韩继业教授，韩教授对于专业的热爱与执着， 对于科学的精益求精深深影响了我，将使我受益终生在此表示深深的感谢! 感谢研究生期间所有给予过我帮助的老师和同学，他们的耐心与热情使我在 前行的道路上倍感温暖； 感谢给我授课的所有老师，是他们的谆谆教诲让我打下了夯实的数学基础，又 是他们对数学的热爱给了我在科研的路上不断前进的动力； 感谢师兄孔令臣对我的帮助，本文的很多工作是在师兄的悉心指导下完成的， 师兄对我各方面的照顾及精神上的鼓励成为我不断学习、进行深入研究的极大动 力，在此深表感谢! 感谢罗自炎、曹静杰、阎爱玲、周金川、王苏皖、王高阳等同门兄弟姐妹对我 学业的热情帮助，尤其是罗自炎，在相互讨论的过程中，她扎实的专业功底给我提 供了很多帮助； 感谢三年来一直共同学习、共同进步的同窗；感谢同宿舍的李艳涛、赵琳、张 青青，她们对我无微不至的关怀与帮助让我对生活更加有热情，对明天充满信心； 感谢我的父母、家人对我一如既往的支持和鼓励，是他们无私和伟大的爱使 我一直保持积极向上的乐观态度和克服困难的勇气 最后感谢各位专家、学者在百忙中审阅我的论文，我愿意认真听取专家的宝 贵意见，在今后的学习工作中不断改进 北京交通大学硕士学位论文第一章绪论 第一章绪论 本章首先描述了对称锥互补问题的研究内容和意义接着引入对称锥研究中 最为重要的工具一一欧几里德若当代数，列举了基本概念和相关理论最后，简 要介绍了互补问题可解性方面的研究进展情况 1 引言 对称锥互补问题是指在对称锥约束条件下，两组决策变量之间满足一种互补 关系正如综述文献【4 3 】所叙其核心是运用严谨的数学方法并以电子计算机与网 络为工具，研究存在这种互补关系的各种复杂系统及相应的解决方案，为决策者提 供科学决策的依据，最终达到复杂系统运行的均衡和谐目标该模型有如下三个特 征： ( i ) 它为标准非线性规划与互补问题【1 0 ，2 4 ，2 5 】、当今流行的二阶锥规划与 互补问题【1 】、以及目前十分活跃的半定规划与互补问题【2 6 ，4 1 ，4 6 】提供了一个 统一框架，并且与组合优化、不确定优化、鲁棒优化，博弈与均衡理论等分支有密 切的联系 ( i i ) 它较古典的互补问题而言，更能较好地体现和谐发展的理念( 两者共存、 互利双赢) ，为当今社会经济所接受事实上在最近的几年里，它被广泛应用在经 济、管理、交通、工程设计、通信、控制等实际部门【1 ，2 6 ，3 0 ，4 1 】，其半定规划被 誉为“2 1 世纪的线性规划” ( i i i ) 对称锥具有优美的几何结构( 例如三维的二阶锥形如冰激凌，因此又称 二阶锥为冰激凌锥) ，鲜明的代数特征( 若当代数) ，以及能在该锥上进行整体 函数值分析这表明对称锥上互补问题是一类内容新、涵盖面宽、理论丰富、且有 广泛应用背景的均衡优化问题 然而，对称锥互补问题直到最近两年才引起人们的重视主要原因是： ( i ) 1 9 9 4 年，f a r a u t 和k o r d n y i 出版了一本专著 6 】，他们应用欧几里德若当 代数技术，对对称锥进行了系统和深刻的分析，那时人们才对它有了较为全面的认 识 ( i i ) 1 9 9 7 年，f a y b u s o v i c h 7 ，8 1 应用欧几里德若当代数技术，把著名的内点法 专家n e s t e r o v 和n e m i r o v s k i 开拓建立的锥( 特别是二阶锥) 规划内点法阻】推 广到对称锥线性优化，并证明了其多项式复杂性2 0 0 1 和2 0 0 3 年，s c l l i n i e t a 和 a l i z a d e h 3 7 ，3 8 】对此进行了深入研究，得到了漂亮的理论结果从而，显示了欧几 里德若当代数技术是一个强有力的工具，对称锥有丰富的内涵 ( r i d 科学研究总是由简单到复杂，人们对互补问题的研究也不例外事实上 北京交通大学硕士学位论文 第一章绪论 从非负锥互补问题到二阶锥和半定锥互补问题，再到对称锥互补问题，每个阶段都 需要条件和时间 近几年，人们借助欧几里德若当代数技术，在对称锥互补问题的研究方面获得 了突破性进展并逐渐受到重视下面我们首先介绍欧几里德若当代数的基本知识 2 欧几里德若当代数概述 本节我们将介绍欧几里德若当代数的基础知识，这些内容对理解对称锥及其 相关问题是必需的我们的表述主要基于1 9 9 4 年f a x a u t 和k o r f i n y i 的专著【6 】， 简单的了解可查阅文献【7 ，2 0 ，3 8 ，4 0 】 2 1 基本概念和定理 称( v ，( ，) ，o ) ( 简记1 夕) 为欧几里德若当代数( e u c l i d e a nj o r d a na l g e b r a ) ，其 中( y ，( ，) ) 是一个定义在实数域上的有限维内积空间，( z ，y ) hx o y ：vxy y 是一个满足下述条件的双线性影射： ( 1 ) z 0y = y0zv x ，y y ； ( 2 ) zo ( z 2 oy ) = x 2o ( zoy ) v z ，y y 其中z 2 ：= x oz ； ( 3 ) ( x o y ，名) = ( x ，y 0 z ) vx ，y ，z y 我们称z oy 为元素z 和y 的若当积此外，我们假设在y 中总存在个元素e ， 称为单位元满足z 0e = e0z = 茹，比y 给定个欧几里德若当代数v ，我们说元素c v 是一个幂等元，如果c 2 = c 0 进一步，一个幂等元是基本幂等元，如果它不能分解为两个幂等元的和设 c l ，o k 是y 的个幂等元集合，我们说它是个幂等元正交完备系，如果 c o 勺= 0 vi j i ，c l + + c k = e 进一步，如果这个正交完备系中的每个元素都是基本幂等元，则称它为欧几里德若 当代数y 的个若当基底 对于任意元素z y ，设m 是使得 e ，z ，z 2 ，z ”) 线性相关的最小正整数， 则称m 为元素z 的度，记为d e g ( x ) v 的秩r k ( v ) 定义为r k ( n ) ：= m a x d e g ( x ) ： z v ) 设d i m ( v ) 表示v 的维数，显然r k ( v ) d i m ( n ) 已经证明 6 1 ，v 的一个 若当基底中元素的个数等于r k ( v ) 下面我们介绍重要的谱分解理论 定理1 2 1 借分解类型，f ，卢，理i i i 1 驯设y 是一个欧几里德若当代数， 则对于每一个元素z v ，必存在唯一的一组互不相同的实数入l ，九，和唯一 2 北京交通大学硕士学位论文第一章绪论 的幂等元正交完备系c i ，c k ，使得 z = 入l c l + + a k e k 定理1 2 2 借分解类型伊，定理m _ f 驯设y 是一个秩为r 的欧几里德 若当代数，则对于每一个元素z 1 ，必存在一个若当基底 c l ，白) 和一组实 数a l ，使得 z = a l c l + - 4 - 入r 白 表达式z = a 1 c 1 + + 白称为元素z 的个谱分解，实数九= 九( z ) ( i = 1 ，r ) 称为元素z 的特征值，c ao = 1 ，r ) 称为元素z 的相应于特征值丸 的特征向量 利用欧几里德若当代数的若当积和谱分解理论，我们可对空间中的元素作乘 法运算，从而可定义向量值函数并进行整体函数分析，使得函数表达式简单易 懂、规律性强、结果优美例如设z y 的谱分解为z = a 1 ( z ) c 1 + + ( z ) c r ， 我们定义向量值投影函数 矿：= 对( z ) 臼， 、7 1 r z 一：= 耳( z ) c i 1 9 7 和模值函数 u ( z ) - 1 m i r a xa i ( z ) ，( z ) ：_ 1 r a i n ，, x i ( x ) ， 这里t + = m a x o ，t ) 和t 一= ( 一t ) + ，t 冗类似地，可定义，、，信，z 一，h z ， e x p ( x ) ，d e t ( x ) ，t r ( x ) 等般地，给定函数，：冗_ 冗和对称函数g ：r 一冗，定 义向量值和模值函数 ，( z ) = ，( 九) q ，( 夕a ) ( z ) = 夕( a 1 ( z ) ，( z ) ) ， l i 都是a n 的一个若当基底，其中是r 住一1 中满足m l = 1 的任意元素( 2 9 1 ，定理3 5 ) 例3 设伊表示所有n 竹实对称矩阵组成的集合，其中内积和若当积分别定义 如下： ( x ，y ) ：= t r a c e ( x y ) ，x oy ：= ( x y + y x ) 2 容易验证，伊是一个欧几里德若当代数，其平方锥为所有半正定矩阵组成的集合 霹单位元为单位矩阵e 集合 e l ，鼠) 构成伊的个若当基底，其中 晟( i 1 ，2 ，礼) ) 是第( i ，i ) 个元素为1 其余元素为0 的对角矩阵任意给定 x 5 _ ，存在列向量为9 1 ，的正交阵q 和一个实对角阵a = d i a g ( a i ) ，使 得x = q a q 丁= a i q l q f4 - + a 。爵，其中九g = 1 ，几) 是x 的特征值， 啦0 = l ，n ) 是相应的特征向量根据文献【2 9 】的定理3 5 ，当佗 1 时，扩的 若当基底不是唯一的事实上，任意 g e l g 丁，g e 2 g t ，c e g r 都是个若当 基底，其中g 是任意的n n 正交阵 本小节结束前，我们引述几个重要的等价条件( 【2 0 】) 命题1 2 6 令k 为欧几里德若当代数y 的对称锥对任意z ，y y ，下列条件 等价? ( a ) z ky kzo 暑，= 0 ( 6 ) z ky k ，( z ，y ) = 0 ( c ) z + y kz oy = 0 ( d ) z 一( z p ) + = 0 ，v 丘 0 ( e ) z + y v + y 2 。= 0 在上述每种情况下，z 和可都算子可交换 3 互补问题可解性的研究情况 对称锥互补问题是指：给定欧几里德若当代数1 ，对称锥k 和向量函数f ： y _ y 求z y 使得 z kf ) + q k 扛，f 0 ) + g ) = 0 ， ( 1 ) 5 北京交通大学硕士学位论文 第一章绪论 其中q y 当f ( z ) = m x 为线性算子时，称( 1 ) 为对称锥线性互补问题，记 为s c l c p ( 简记为l c p ( mk ，g ) ) ；否则，称( 1 ) 为对称锥非线性互补问题，记为 s c n c p 两者统称为对称锥互补问题，简记为s c c p 我们称s c c p 是可行的，如 果约束集合缸y ：z k ，f ( x ) + q k ) ( 又称可行集) 非空；称s c c p 是严 格可行的，如果内点约束集合0 y ：z i n t ( k ) ，f ( z ) + q i n t ( k ) ( 又称严 格可行集) 非空我们称s c c p 是可解的，如果集合扛v ：x kf ( x ) + g k ，( z ，f ( x ) + q ) = o ) ( 又称解集) 非空 显然，当y = 7 护和k = 7 珥时，( 1 ) 退化为标准互补问题( 简记c p ) ；当 y = 和k = a ：时，( 1 ) 退化为二阶锥互补闻题( 简记s o c c p ) ；当y = 伊和 k = 岛时，( 1 ) 退化为半定互补问题( 简记s d c p ) 对称锥互补问题可以说是标 准互补问题的最近的更一般的推广和发展，它包括标准互补问题、二阶锥互补问 题和半定互补问题等，为之提供了一个简单、自然且统一的框架这使得我们可以 从更高层次上研究和认识e 述三类具体的互补问题 可解性作为互补问题研究的个重要方面，历来受到广大学者的重视标准线 性互补问题中，可解性的研究已相对完善为了解决线性互补问题解的存在性、唯 性、解集的有界性、误差界等问题，人们提出了p 矩阵、岛矩阵、充分矩阵和 s 矩阵等概念f 5 ，1 1 ，1 2 ，1 5 ，2 4 ，随着互补问题发展到半定锥、二阶锥上，相应问 题的可解性研究也开始出现【1 6 ，l 】近几年，人们借助欧几里德若当代数，对对称 锥互补问题的研究越来越深入，其中亦不乏可解性方面的研究【1 7 ，1 8 ，1 9 ，2 0 ，2 1 】 对于对称锥互补问题的研究，除了理论方面的结果，人们在算法方面也进行 了很多尝试，但大多都集中在内点法的推广【7 ，8 ，9 ，3 7 ，3 1 ，3 8 ，3 5 ，4 4 ，4 5 】，另有 少数的光滑化算法【2 8 ，2 3 | 本文中，我们将矩阵充分性的概念推广到欧几里德若当代数上的线性变换中， 并通过引入线性变换的交叉可交换性质，证明了列充分性与s c c p 解集凸之间的 等价性；另一方面，在某种条件下，线性变换的行充分性是相应互补问题有解的 一个必要条件 6 北京交通大学硕士学位论文第二章对称锥互补问题的可解性 1 问题引入 第二章对称锥互补问题的可解性 对于线性互补问题l c p ( 尬g ) ，矩阵m 的特性与互补问题解的存在性和其 它性质有密切关系，所以要针对不同的矩阵类来研究线性互补问题下面给出一 个特殊的矩阵类 定义2 1 1 矩阵m 缈炳被成为列充分矩阵，若对任意z 缈，有蕴含关系： x ( m x ) i 0 ，i = 1 ，2 ，礼兮x i ( m x ) i = 0 ，i = 1 ，2 ，佗 矩阵m 被成为行充分矩阵，若 矿是列充分矩阵若m 既是行充分矩阵又是列 充分矩阵，则称m 是充分矩阵 矩阵充分性的提出，是为了刻画相应线性互补问题解的性质参考文献f 2 4 】， 可知对于列充分矩阵，我们有如下结论 定理2 1 2 矩阵m 为一列充分矩阵的充要条件是，对任意矢量q 缈，l c p ( 尬g ) 的解集是凸集( 可能是空集) 由于互补问题最早可能来源于求解个非线性优化问题的k a r u s h - k u h n - t u c k e r ( k k t ) 系统，因此其与优化问题有着天然的联系将互补问题等价转化为优化问 题，从而利用较为成熟的优化理论来求解，常常会有不错的结果为研究行充分矩 阵性质，我们考虑如下二次规划( q p ) o 。 m i nx t ( m x + q ) s t z 0 ，m ( x ) + g 0 显然二次规划( q p ) o 的目标函数在可行集p 7 ：泸：z 0 ，m x + q o 中 有下界( 为零) ，根据般二次规划的最优解存在的个基本定理一一f r a n k - w o l f e 定理，可知其必有全局最优解，下面引述这一定理 定理2 1 3 若任意二次函数，在一非空多面体x 阿以是无界集j 中有下界，则， 在x 中必有全局极小解 对于行充分性质，我们有如下定理 定理2 1 4 矩阵m 是行充分矩阵的充要条件是，对任意矢量g ，若z 是二次规 划( q p ) o 的k k t 点，u 是相应的乘子矢量，则点z 是l c p ( 旭g ) 的解 利用矩阵的列充分及行充分性质，我们很好地刻画了相应线性互补问题的解 集凸性及解的存在性那么，对于更一般的对称锥互补问题，能否利用欧几里德若 7 北京交通大学硕士堂位迨塞 第二章对称锥互补问题的可解性 当代数上定义的线性变换的某些性质，来刻画其解的性质呢? 这便是下节要解决 的问题 2 对称锥线性互补问题的可解性 本节我们定义了欧几里德若当代数上线性变换的两种充分性质，并利用欧几 里德若当代数与对称锥的特殊关系，建立了线性变换c ：y y 与其相应对称锥 互补问题l c p ( c ，k ，g ) 可解性之间的联系 首先我们给出欧几里德若当代数上线性变换的列充分性质的概念 定义2 2 1 考虑线性变换c ：y _ y 称c 具有 ( a ) j o r d a n 列充分性质( j o r d a nc s u ) ，如果x o ( z ) - k 兮z o l ( x ) = o ； ( b ) 列充分性质( c s u ) ，如果x 与( z ) 算子可交换，且 zoc ( z ) 一k 号z0c ( z ) = 0 注( i ) 当y = 7 护且k = 7 ：砼，j o r d a l lc s u 与c s u 等价，且退化为相应矩阵 的充分性 ( i i ) 当y = 伊，此处我们定义的列充分性质不同于g o w d aa n ds o n g 在 【1 6 】中所给的定义，那里他们定义线性变换c 的列充分性质为其相应的互补问 题l c p ( ，酽，q ) 解集为凸 ( i i i ) 对于g o w d a ，s 匝a j d e r 及【2 0 】定义的p 和p o 性质，我们有 p c s u p 0 由定义，我们可立即得到以下线性变换列充分的个充要条件 命题2 2 2 给定线性变换c ：y y ，c 有列充分性质当且仅当对任意z 1 ， 当z 与z ( x ) 算子可交换，则以下包含关系成立： j ( z + ，( c ( z ) ) + ) = 0。j ( z + ，( c ( z ) ) 一) = 0 i ( z 一，( c ( z ) ) 一) = 0 。i 扛一，( c ( z ) ) + ) = 0 证明显然，c 为列充分的，即是说对任意满足z oc ( z ) 0 且z 与c ( z ) 算 子可交换的z y ，z oc ( z ) 的特征值不能都为非正的结论显然口 下面我们回顾线性变换c 的一个性质，它在后面的分析中是十分重要的 8 北京交通大学硕士学位论文 第二章对称锥互补同题的可解性 定义2 2 3 ( 定义1 3 ，f 2 0 】) 称线性变换c ：y _ 1 ，具有交又可交换性，如果 对任意q v 及l c p ( c ，k ，q ) 的任意两个解x l ，x 2 ，有t , i 和协算子可交换 ( i ，歹= 1 ，2 ，i 歹) ，其中y i = c ( 鼢) + q ，i = 1 ，2 为了研究列充分性质，由参考文献【1 0 】中命题2 4 1 0 ，易得如下引理由于证 明手法类似，此处我们省去证明过程 引理2 2 4 令1 ，为一欧几里德若当代数，k 为其相应的对称锥，q y ，对任一 线性变换：v y ，则下述结论等价： 纠l c p ( ，k ，q ) 解集为凸集 俐对l c p ( c ，k ，q ) 的任意两个解x 和y ，必有 缸，c ( y ) + g ) = ( y ，c ( z ) + q ) = 0 下面我们给出并证明这部分的主要结论 定理2 2 5 对任意线性变换c ：v y ，下列结论等价： 有列充分性及交叉可交换性 例v g y ，l c p ( ，k ，q ) 解集为凸阿能为空， 证明( 口) 号( 6 ) 若l c p ( ：，k ，q ) 至多有2 个解，结论显然否则，假设x 和 y 为l c p ( c ，k ，q ) 的任意两个相异解，即 x kc ( z ) + q k往，c ) + q ) = o ； y kc ( 可) + q k( y ，c ( y ) + q ) = 0 由交叉可交换性定义，有 yo ( c ( z ) + q ) k z o ( l ( y ) + q ) k ( z y ) y ，( c ( z ) + q ) 一( c ( y ) + q ) = c ( z y ) y 从而， ( z y ) oc ( z y ) = - - yo ( c ( z ) + q ) 一z0 ( c ( 可) + q ) 一k 由于z y 与c ( x - - y ) 算子可交换，由c 的列充分性，可得到( x - - y ) o c ( z y ) = 0 从而有 ( z ，c ( y ) + q ) = ( y ，c ( z ) + g ) = 0 由引理2 2 4 ，结论得证 9 北京交通大学硕士学位论文第二章对称锥互补问题的可解性 ( 6 ) 今( a ) 假设c 不具有列充分性则存在z y ，使得z 与c ( z ) 算子可交 换且z oc ( z ) 一k ，但zoc ( z ) 0 因此，存在一个若当基底 c 1 ，c r 使得 z = a i c ，c ( z ) = 雕q ，九肌0 一，r ) ， 及下标k 使得a 鲰 0 定义 牙= 一c ( z + ) + ( c 0 ) ) 一 易证 + ，z 一) 是二次规划问题( q p ) 的个k k t 点，且已知( x + - - x 一) 和r + 一 z 一) 算子可交换因此矿是l c p ( c ，k ，动的一个解，从而有 + ，( c + ( z ) ) 一) = ( z + ，c ( z + ) + 彩= 0 产生矛盾 1 3 口 北京交通大学硕士学位论文第三章结论 第三章结论 1 本文工作总结和主要创新 借助于欧几里德若当代数技术，经过最近几年的快速发展，对称锥互补问题 的理论研究已经有了相当的结果其中很重要的一部分，即是对称锥互补问题可 解性的研究主要是g o w d a 等人将p ，q ，g u s , z 等一系列与互补问题相关的矩 阵类推广到了欧几里德若当代数上有了关于可解性的结果，人们设计了很多高 效的算法来求解对称锥互补问题 本文主要是将两种充分矩阵的概念推广到定义在欧几里德若当代数上的线性 变换中，并利用欧几里德若当代数和对称锥的紧密联系，建立了这两种充分性质 同对称锥互补问题可解性之间的联系：列充分性质加上交叉可交换性即等价于相 应的对称锥互补问题解集的凸性；而在一定条件下，线性变换的行充分性可作为 相应对称锥互补问题解存在的必要条件 2 未来工作展望 对称锥互补问题的研究方兴未艾由于其自身强大的生命力，越来越多的入 投身到研究对称锥互补问题的行列中来本文中也是对对称锥互补问题的可解性 进行了初步探讨实际上，对称锥互补问题仍然有许多问题有待解决 就本文而言，虽然我们将充分性的概念推广到欧几里德若当代数上，并试图 建立这样的特殊线性变换与相应互补问题可解性之间的关系然而，由于对称锥 的非多面性，7 1 护上一些结论并不能直接推广到对称锥中，比如对于本文中定义的 线性变换的行充分性质，我们没能建立其与相应对称锥互补问题解存在性的充要 条件，而只是给出文中特殊二次规划k k t 点的个必要条件 另一方面，定义了两种线性变换的充分性后，能否据此设计出合理、高效的 算法来求解特殊的对称锥互补问题，也可以作为未来研究工作的一个出发点 总之，对称锥上互补问题作为一个比较新的研究领域，还有很大的探索空间 只要找准方向，深入思考。就一定可以做出有意义的结果。 1 4 北京交通大学硕士学位论文 参考文献 参考文献 【1 1a l i z a d e h ，f ，g o l d f a r b ，d ：s e c o n d - o r d e rc o n ep r o g r a m m i n g ，m a t h p r o g r a m s e t b ，9 5 ，3 - 5 1 ( 2 0 0 3 ) 【2 1 2b o n n a n s ，j f ，s h a p i r o ，a ：p e r t u r b a t i o na n a l y s i so fo p t i m i z a t i o np r o b l e m s s p r i n g e r - v e r l a g ，n e w1 蜘r k ，2 0 0 0 【3 】c o t t l e ，r w ，g u u ，s - m ：t w oc h a r a c t e r i z a t i o n so fs u f f i c i e n tm a t r i c e s l i n e a ra l g e b r a a p p l 1 7 0 ，6 5 - 7 4 ( 1 9 9 2 ) 【4 】c o t t l e ，r w ，p a n g ，j - s ，s t o n e ，r e ：t h el i n e a rc o m p l e m e n t a r i t yp r o b l e m a c a d e m i c p r e s s ，b o s t o n ，1 9 9 2 【5 】5 c o t t l e ，r w ，p a n g ，j 一s ，v e n k a t e s w a r a n ，v ：s u f f i c i e n tm a t r i c e sa n dt h el i n e a rc o m p l e - m e n t a r l t yp r o b l e m l i n e a ra l g e b r aa p p l 1 1 4 1 1 5 ，2 3 1 - 2 4 9 ( 1 9 8 9 ) e lf a r g u t ，j ，k o r f i y i ，a ：a n a l y s i s0 ns y m m e t r i cc o n e s o x f o r du n i v e r s i t yp r e s s ，o x f o r d ， 1 9 9 4 【7 lf a y b u s o v i c h ，l ：e u c l i d e a nj o r d a na l g e b r a sa n di n t e r i o r - p o i n ta l g o r i t h m s ，p o s i t i d t y , 1 ，3 3 1 - 3 5 7 ( 1 9 9 7 ) 【8 】f a y b u s o v i c h ，l ：l i n e a rs y s t e m si nj o r d a na l g e b r a sa n dp r i m a l - d u a li n t e r i o rp o i n ta l g o - r i t h m s j o u r n a lo fc o m p u t a t i o n a la n da p p l i e dm a t h e m a t i c s ，8 6 ，1 4 9 - 1 7 5 ( 1 9 9 7 ) f 9 】f a y b u s o v i c h ，l a n da x a n a ，r ：al o n g - s t e pp r i m a l - d u a la l g o r i t h mf o rt h es y m m e t r i cp r o - g r a m m i n gp r o b l e m ，t e c h n i c a lr e p o r t ，d e p a r t m e n to fm a t h e m a t i c s ，n o t r ed a m eu n i v e r s i t y , 2 0 0 0 【1 0 】f a c c h i n e i ，f ，p a n g ，j - s ：f i n i t e - d i m e n s i o n a lv a r i a t i o n a li n e q u a l i t i e sa n dc o m l e m e n t a r i t y p r o b l e m s s p r i n g e r - v e r l a g ，n e wy o r k ，2 0 0 3 【1 1 】f i e d l e r ，m ，p t a k ，v ：o nm a t r i c e sw i t hn o n - p o s i t i v eo f f - d i a g o n a la n dp o s i t i v ep r i n c i p a l m i n o r s c 淝c h o s l o y a km a t h e m a t i c a lj o u r n a l ，1 2 ，3 8 2 ( 1 9 6 2 ) 【1 2 】f i e d l e r ，m ，p t 8 k ，v ：s o m eg e n e r a l i z a t i o n so fp o s i t i v ed e f i n i t e n e s sa n dm o n o t o n i c i t y n m m e r i s c h em a t h e m a t i k ，9 ，1 6 3 ( 1 9 6 6 ) 【1 3 g o w d a ，m 川s o nt h ee x t e n d e dl i n e a rc o m p l e m e n t a r i t yp r