（运筹学与控制论专业论文）对称锥互补问题的互补函数和价值函数研究.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 o c c p 和s d c p 的向量值隐拉格朗日函数，而且这个推广具有重要意义作为应用，给出 了实值隐拉格朗日函数及相应的价值函数，并且给出价值函数的稳定点成为s c c p 的解的一个充要条件在一致c a r t e s i a n - p 性质下，证明此价值函数可为s c c p 提 供个全局误差界最后，给出了求解s c c p 的一个混合牛顿算法 第三章我们主要感兴趣的是求解s c c p 的几种可能的算法中的正则光滑牛顿 算法首先给出l s w n e r 算子的广义雅可比的计算公式在此基础上，分析了一个 自然剩余函数的强半光滑性和雅可比的非奇异性，得到了在单调和严格可行性假 设下，s c c p 的自然剩余函数和惩罚的自然剩余函数的水平有界性继而我们构 造了s c c p 的自然剩余的c h e n - m a n g a z a r i a n 光滑函数，这也就提供了在更一般 的结构中c h e n - m a n g a s a r i a n 光滑函数的一个统一的可计算的公式同时，研究了 其一致逼近性质和( 强) 雅可比非奇异性最后，给出了求解s c c p 的一个正则光 滑化牛顿算法 第四章给出了s c c p 的e p 类互补函数，证明了其连续可微性和强半光滑 性其次，研究另一类著名的由m a n g a s a r i a n 在1 9 7 6 年给出的互补函数，从而肯 定解答了t s e n g 在1 9 9 8 年提出的个公开问题进一步，我们研究l s w n e r 算子 的单调性，分别给出了判别其单调、严格单调和强单调的充分必要条件 关键词：对称锥互补问题；欧几里得若当代数；互补函数；价值函数；混合牛顿 北京交通大学博士学位论文中文摘要 算法；正则光滑化牛顿算法 分类号：0 2 2 4 北京交通大学博士学位论文英文摘要 a b s t r a c t a b s t r a c t ：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 ( s c c p ) i n c l u d e st 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 s - i t yp 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 l a m e - w o r k i th 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 rf i e l d s t h i st h e s i si sm a i n l yc o n c e r n e dw i t hc o m p l e m e n t a r i t yf u n c t i o n s ( c - f u n c t i o n s ) a n dm e r i tf u n c t i o n sf o rs c c p j o r d a na l g e b r a i ct e c h n i q u ep r o v i d e sau s e f u lt o o lf o rd e s c r i b i n ga n da n a l y z i n g s y m m e t r i cc o n eo p t i m i z a t i o np r o b l e m ，a n dt h ej o r d a nf l a m ep l a y sa ni m p o r t a n t r o l ei ne u c l i d e a nj o r d a na l g e b r a s i nc h a p t e r1 ，r e c a l l i n gs o m ec o n c e p t sa n d r e s u l t so ne u c l i d e a nj o r d a na l g e b r a s ，w eg i v en e c e s s a r ya n ds u m c i e n tc o n d i t i o n s u n d e rw h i c ht h e r ei sau n i q u ej o r d a nf l a m ei nae u c l i d e a nj o r d a na l g e b r a i nc h a p t e r2 ，e m p l o y i n gt h ej o r d a n a l g e b r a i cs t r u c t u r e ，w ee x t e n dt h ei m - p l i c i tf u n c t i o nb ym a n g a s a r i a na n ds o l o d o vf o rn c p t ot h ev e c t o r - v a l u e di m p l i c i t l a g r a n g i a nf o rs c c p , a n ds h o wt h a ti ti sac o n t i n u o u s l yd i f f e r e n t i a b l ea n ds t r o n g l y s e m i s m o o t hc - f u n c t i o nf o rs c c pa sa na p p l i c a t i o n w ed e v e l o pt h er e a l - v a l u e d i t r l p l i c i tl a g r a n g i a na n dt h ec o r r e s p o n d i n gs m o o t hm e r i tf u n c t i o nf o rs c c p ，a n d g i v ean 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 rt h es t a t i o n a r yp o i n to ft h em e r i tf u n c - t i o nt ob eas o l u t i o no fs c c pw ea l s os h o wt h a tt h i sm e r i tf u n c t i o nc a np r o v i d e ag l o b a le r r o rb o u n df o rs c c pw i t ht h eu n i f o r mc a r t e s i a np p r o p e r t y f i n a l l y , ah 3 7 b r i dn c w t o nm e t h o di se s t a b l i s h e d ，w h i c hi sq u a d r a t i c a l l yc o n v e r g e n tu n d e r a p p r o p r i a t ea s s u m p t i o n s c h a p t e r3r e n e w st h el 6 w n c ro p e r a t o ra n dd e v e l o p ss o m en e wr e s u l t so n t h ej a c o b i a no p e r a t o r t h e nw cs t u d yt h es t r o n gs c m i s m o o t h n e s sa n dj a c o b i a n n o n s i n g u l a r i t yo fan a t u r a lr e s i d u a lf u n c t i o nf o rs c c p ，a n di n v e s t i g a t et h el e v e l - b o u n d e d n e s so ft h er e l a t e dm e r i tf u n e t i o n sf o rs c c pu n d e rc e r t a i nm o n o t o n i c - i t yc o n d i t i o n s b a s e do nt h eu n i f o r ma p p r o x i m a t i o np r o p e r t ya n dj a c o b i a nc o n - s i s t e n c yo ft h ec h e n m a n g a s a r i a nc l a s so fr e g u l a r i z e ds m o o t h i n gf u n c t i o n s ，w e d e v e l o pag l o b a l l ya n dq u a d r a t i c a l l yc o n v e r g e n ta l g o r i t h mf o rs o l v i n gm o n o t o n e s c c p s 北京交通大学博士学位论文英文摘要 i nc h a p t e r4 ，w ee s t a b l i s he pc l a s s e sa n dm a n g a s a f i a nc l a s so fc - f u n c t i o n s w h i c hs o l v e sa no p e nq u e s t i o nb yt s e n gi n1 9 9 8 w ea l s os h o wt h a tt h ef o r m e r a r ec o n t i n u o u s l yd i i t e r e n t i a b l ea n ds t r o n g l ys e m i s m o o t he v e r y w h e r e m o r e o v e r ， w em a i n l ys h o wn 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 n sf o rl o c a l l yl i p s c h i t zl s w n c r o p e r a t o rt ob em o n o t o n e ，s t r i c t l ym o n o t o n ea n ds t r o n g l ym o n o t o n e 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 na l - g e b r a ，c f u n c t i o n ，m e r i tf u n c t i o n ，h y b r i dn e w t o nm e t h o d ，r e g u l a r i z e d s m o o t h i n g m e t h o d c l a s s n o ：0 2 2 4 符号说明 舻，表示礼维实向量空间； 殿，表示 维非负实向量空问； 磁+ ，表示n 维正实向量空间； 爿、y ，表示定义在冗上的有限维向量内积空问； c 爿，表示爿的子集g ； i n t c ，表示c 的内部； r i c ，表示e 的相对内部； a f f c ，表示e 的仿射包； c o n v c ，表示e 的凸包； s p a n c ，表示由g 张成的子空间； d i s t ( a ，g ) ，表示点n 到集合g 的距离； 歹，表示欧几里得若当代数； ( ，) ，表示欧几里得若当代数的内积； ”i i ，表示由内积诱导而成的模； b ( z ，) ，表示以z 爿为中心，半径为e 0 的开球； 陋，y 】，表示闭集 z 了：z = t x + ( 1 一) y ，0 t s l ) z 兰ky ， 表示。一y 耳； $ - ky ，表示x y i n t k ； a 三b ，表示a b 为半正定算子； a 卜b ，表示以一b 为正定算子； a t ，表示对a 转置运算； a ，表示对a 求逆运算； ，表示恒等算子； v f ( z ) ，表示f ( z ) 的雅可比； 8 f ( z ) ，表示f ( x ) 的广义雅可比； m i n ，求极小值； m a x ，求极大值； 口，表示证明结束 v l l 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国 家有关部门或机构送交论文的复印件和磁盘。 学位论文作者签名： 孔专怠 签字日期：溯年石月，z 日 导师签名乏力移 ) 签字日期：厶。7 年么月f 2 日 致谢 本论文的工作是在我的导师修乃华教授的悉心指导下完成的，修乃华教授严 谨的治学态度和深厚的数学功底以及高尚的人格给了我极大的帮助和影响另外， 他在生活上也给予了我无微不至的关怀在此衷心感谢三年来修老师对我的关心 和指导 刘彦佩教授、常彦勋教授，冯衍全教授、郝荣霞教授、江中豪教授、罗振东教 授、王金亭副教授、王周宏副教授，何卫力副教授和于永光副教授等对于我的科 研工作和论文都提出了许多宝贵的意见，在此表示衷心的感谢 特别要感谢中国科学院应用数学研究所的韩继业教授，三年来韩老师对我的 学习给予了极其重要的关心和指导特别是他对科学的献身精神谦虚和严谨扎 实的工作方法使我终生受益，在此表示衷心的感谢 在撰写论文期间。罗自炎、秦林霞、孙连菊、许燕，阎爱玲，王苏皖、周垂香， 曹静杰、刘文忠屈彪王朝阳、王高阳、杨建仅，以及周金川等同学对我论文中 的一些研究工作给予了热情帮助；我的老同学如数学系的钟波老师和研究生院的 锤7 不远老师等等，在我攻读博士期问给予了热情的帮助和重要支持，在此向他们 表达我的感激之情 最后要说的是，我的家庭一直都是我的生活中爱和欢乐的源泉，我欠他们的 是不能用言语所能描述的我的妻子给予我的理解、鼓励和重要支持使我的研究 工作成为可能，我永远都感激她我们的父母，我们的姐姐和哥哥在生活中的理解 和支持使我能够在学校专心学习还有我们的女儿，给予我生活中真正的快乐， 伴随着她的成长和幸福，使我能够安心完成我的学业 第一章绪论 本章首先描述了对称锥互补问题的内容和意义为了便于清楚地概述其研究 历史和现状，接着介绍了欧几里得若当代数的基本概念和相关理论以及关于若当 基底唯性的研究结果再次，从理论和算法两个方面综述对称锥互补问题的研 究现状最后，简要介绍本文的工作和结构 1 1 研究问题的内容和意义 对称锥互补问题是指在对称锥约束条件下，两组决策变量之问满足一种互 补关系正如最新文献【1 2 9 所叙，其核心是运用严谨的数学方法并以电子计算 机与网络为工具，研究存在这种互补关系的各种复杂系统及相应的解决方案，为 决策者提供科学决策的依据，最终达到复杂系统运行的均衡和谐目标该模型有 如下三个特征； ( i ) 它为标准非线性规划与互补问题 3 l ，3 5 ，5 2 ，5 8 】、当今流行的二阶锥规划 与互补问题【1 ，7 ，9 6 ，1 2 4 ，1 3 2 ，以及目前十分活跃的半定规划与互补问题6 4 ， 1 2 6 ，1 3 3 】提供了个统一框架，并且与组合优化，不确定优化，鲁棒优化、博弈 与均衡理论等分支有密切的联系 ( i i ) 它较古典的互补问题而言，更能较好地体现和谐发展的理念( 两者共存、 互利双赢) ，为当今社会经济所接受事实上在最近的几年里，它被广泛应用在经 济、管理、交通、工程设计，通信、控制等实际部门【1 ，4 3 ，6 4 ，7 9 ，1 2 6 ，其半定规 划被誉为“2 1 世纪的线性规划” ( i i i ) 对称锥具有优美的几何结构( 例如三维的二阶锥形如冰激凌，因此又称二 阶锥为冰激凌锥) ，鲜明的代数特征( 若当代数) ，以及能在该锥上进行整体函数 值分析 这表明对称锥互补问题是一类内容新，涵盖面宽理论丰富且有广泛应用 背景的均衡优化问题 然而，直到最近几年对称锥互补问题才引起人们的重视主要原因可能有以 下几个方面； ( i ) 1 9 9 4 年，f a r a u t 和k o r d n y i 出版了本专著【3 7 】，他们应用欧几里得若 当代数技术，对对称锥进行了系统和深入的分析，那时人们才对它有了较为全面 的认识 1 第一章绪论 ( i i ) 1 9 9 7 年，f a y b u s o v i c h 3 8 ，3 9 i 应用欧几里得若当代数技术，把著名的内点 法专家n e s t e r o v 和n e m i r o v s k i 开拓建立的锥( 特别是二阶锥) 规划内点法 9 5 1 推 广到对称锥线性优化，并证明了其多项式复杂性在2 0 0 1 年和2 0 0 3 年，s c h m i e t a 和a l i z a d e h 1 1 1 ，1 1 2 1 对此进行了深入研究，得到了漂亮的理论结果从而，显示 了欧几里得若当代数技术是一个强有力的工具，对称锥规划和互补问题有丰富的 内涵 ( i i i ) 科学研究总是由简单到复杂，人们对互补问题的研究也不例外事实上， 从非负锥互补问题到二阶锥和半定锥互补问题，再到对称锥互补问题，每个阶段 都需要条件和时间 近几年，人们借助欧几里得若当代数技术，在对称锥互补问题的研究方面获得 了突破性进展并逐渐受到重视在概述对称锥互补问题的研究历史和现状之前， 下面介绍欧几里得若当代数的相关知识 1 2 欧几里得若当代数概述 本节我们将介绍欧几里得若当代数的基础知识，这些内容对理解和研究对称 锥互补问题是必需的我们主要参考k o e c h c r 在1 9 6 2 年 6 5 】的讲义以及1 9 9 4 年 f a r a u t 和k o r s n y i 的专著 3 7 1 ，简单了解可查阅文献【3 8 ，4 9 ，1 1 2 ，1 2 1 】等 1 2 1 基本概念和基本定理 欧几里得若当代数( e u c l i d e a nj o r d a na l g e b r a ) ( 了，( ，) ，o ) ( 简记j ) 是指， ( 了，( ，) ) 是个定义在实数域上的有限维内积空问，( z ，g ) 一z 。y ：了歹一j 是一个满足下述条件的双线性影射； ( 1 ) ( 2 ) ( 3 ) xoy = 0 zvz ，y 了； z o ( z 2 。y ) = 护o po y ) vz ，y 其中x 2 ：= zo z ( 。0y ，z ) = ( x ，y 0z ) vz ，y ，z ， 我们称。0 为元素z 和y 的若当积此外，我们假设在歹中总存在一个元素e ， 称为单位元，满足x0e = e0 茹= z ，v z ， 给定一个欧几里得若当代数歹，我们说元素c 了是一个幂等元，如果c 2 = c 0 ，进一步，一个幂等元是基本幂等元，如果它不能分解为两个幂等元的和 设 c ”，吼) 是歹的一个幂等元集合，我们说它是一个幂等元正交完备系，如 2 北京交通大学博士学位论文 果 c foc j = 0vi j ，c l + - + c k = e 进步，如果这个正交完备系中的每个元素都是基本幂等元，则称之为欧几里得 若当代数了的一个若当基底已经证明 37 ，的一个若当基底中元素的个数等 于r k ( 了) 对于任意元素z 了，设m 是使得 e ，f 2 ， 线性相关的最小正整数， 则称m 为元素z 的度，记为d e g c x ) 了的秩r k ( 了) 定义为r k ( 了) ：= m a x d e g ( x ) ： 。歹) 设d i m ( j ) 表示歹的维数，显然r k ( j ) sd i m ( j ) 设了是一个秩为r 的欧几里得若当代数，元素z j 称为正则元，如果d e g ( x ) = r 文献 37 】的性 质i i 2 1 给出了下述结果；欧几里得若当代数歹的所有正则元素组成的集合是一 个开集，同时也是稠密集 利用若当积，我们可方便地定义平方锥k ：= z 2 ：z 歹 从文献【37 1 的第 4 6 页可知；欧几里得若当代数歹的平方锥必是对称锥换言之，是一个 自对偶的闭凸锥并且满足齐次性，即对任意两点x ，y i n t ( k ) ，存在一个可逆线 性变换f ：一了使得r ( k ) = k ，r ( x ) = y 下面我们介绍重要的向量的谱分解理论 定理1 2 1r 谱分解类型，f 定理f j z ，3 例j 设歹是一个欧几里得若当代数， 则对于每一个元素x 了，t 必存在唯一的一组互不相同的实数a i ，一，k ，和唯一 的幂等元正交完备系 c l ，吼) ，使得 z = a 1 c 1 + + a 定j 氅1 2 2 ( 谱分解类型i i ( 定理i i i i 2 ，3 铂) ) 设j 乏一令农巍t 的农l 乙| 铸 若当代数，则对于每一个元素z j ，必存在一个若当基底( c l ，c r ) 和一组实 数a l ，使得 x = a 1 c l + + c r 表达式z = a 1 c l + + c r 称为元素z 的一个谱分解，实数九= 九( z ) ( i = 1 ，r ) 称为元素z 的特征值，c i ( i = 1 ，r ) 称为元素z 的相应于特征值九的 特征向量 3 第 一章绪 论 利用欧几里得若当代数的若当积和谱分解理论，我们可对空间中的元素作乘 法运算，从而可定义向量值) 函数并进行整体函数分析，使得函数表达式简单易 懂规律性强，结构优美例如，设z 了的谱分解为z = a 1 ( z ) c l + + a ，( z h ， 我们定义向量值投影函数 和模值函数 矿：= v ( z ) 岛 1 i z 一：= 百( z ) q u ( z ) l m 自a xa l ( z ) ，( z ) ；l m 。i n ，a i ( x ) ， 这里矿= m a x o ) 和t 一= ( 一) + ，t r 类似地，可定义h ， i c ) ( p ( z ) ，d o t ( x ) ，t r ( x ) 等一般地，给定函数f ：r r 和对称函数g 定义向量值和模值函数 ，( z ) = f ( a i ) c l ，0 * a ) ( z ) = 9 ( a - ( z ) ，( z ) ) ， z ，l n x ， 口一r ( 1 1 2 ) 分别称它们为l s w n e r 算子 函数，和谱函数在文献f 1 1 9 1 中，s u n 和s u n 分 析了它们的解析性，可微性和半光滑性其结果可视为( 1 9 ，4 0 1 关于位上的向量 值l 5 w n e r 函数分析， 2 4 ，2 5 ，1 1 0 】关于岛上的矩阵值l s w n e r 函数分析，以及 7 5 ，1 0 4 关于霹上的矩阵值谱函数分析的延续在本文中将涉及l 5 w n e r 算子的 可微性和单调性等等方面的研究 下面给出重要的空间分解理论，称为p c i r c e 分解定理 定理1 2 3 ( p e i r c e 分解类型i ( 6 2 页，p 乃w 设了是一个欧几里得若当代数， c 是了中的幂等元，则矢量空间了可分解为 j = 以( c ) o 如( c ) o 也( c ) 其中以( c ) = z ：z oc = i a ：，名了) ，i = 0 互1 ，1 定理1 2 4 ( p e i r c e 分解类型i i 健理i k 2 1 ，矽驯设j 是一个秩为r 的欧几 里得若当代数， c 1 ，一，c = r 是了的一个若当基底，则矢量空间，可分解为 v = o 山 i 0 为半径的球这表明存在正则元吼u ( z 1 ， 1 ) 由此定义r l ：= s p a n e ，z - ，z ：1 ，那么，f 1 是，的一个闭子集，且d i m ( f 1 ) = r k ( 了) ，显然， d i m ( u ( z l ，1 ) ) = d i m ( 歹) r k ( 刀，所以矿( ：l ，1 ) 正r 1 因此，存在z 2 u ( z l ，1 ) 且z 2 掣r 1 对于了中的闭凸集 z 2 和1 1 l ，应用凸集强分离定理( 详见 1 0 7 ) ，我 们得到，存在充分小的e 2 0 ，使得，池，e 2 ) cu ( z l ，1 ) 且u ( z 2 ，旬) n r l n 进 一步，存在正则元z 2 u ( z 2 ，2 ) 使得2 ；2gr 1 定义r 2 ：s p a n e ，z 2 ，。 ， 我们得到r 2 r 1 显然，d i m ( f 2 ) = r k ( 了) 0 ，使得u ( z s ，e 3 ) cu ( z 2 ，e 2 ) cu ( z i ，e 1 ) 且【，( 勿，9 3 ) f - ir 2 = q 显然， u ( z 3 ，3 ) nr l = q ( 因为u ( z 2 ，2 ) nr l = q ) 那么，存在正则元x 3 u ( z s ，3 ) 使得x 3 岩r 2 且z 3gr 1 定义r 3 = s p a n e ，x 3 ，z ；_ 1 ，我们得到i s r 2 且 f s r 1 重复上述过程，经过k 次后我们得到两两不同的子空间r ，r k + l ( c ) ： ( o ) 由引理1 2 1 2 易证 分析上述的证明过程，我们实际上也得出，若 c h ，白 是唯一的若当基 底，则，= s p a n o ，c r ，并且k 是由e l ，c r ) 生成的多面锥至此，我 们完成了全部证明口 我们称j 为简单欧几里得若当代数，如果它不能表示成两个欧几里得若当代 数之和设d j 表示空问如( i j ) ( 见定理1 2 4 ) 的维数，已经证明( 详见第7 1 页， 3 7 】或第1 4 页，【1 1 9 ) ，对于简单欧几里得若当代数了，奶ed ( i j ，l ，j = 1 ，r ) ，并且 d i m ( ，) = r k ( j ) + 兰r k ( ，) ( r k ( ，) 一1 ) 根据定理1 2 1 4 ，我们直接得出下列关于简单欧几里得若当代数的结果 1 0 北京交通大学博 士 学位论文 推论1 2 1 5给定秩为r 的简单欧几里得若当代数了，k 为其平方锥，d 定义 如上下列结论等价t r 叫了中有唯一的若当基底 ( b ) k 是多面椎 ( c ) r k ( f l 、= d i m ( j ) ， ( a 1d = 0 进一步，设 c l ，r ，c r 是了中的唯一若当基底，则j = s p a n c 1 ，c r ) ，并且 是由 c l ，一，白) 生成的多面锥 1 2 3 几个例子 为便于理解上述概念，我口】给出几个常见的例子 例1 1 考虑1 1 维实欧几里得空问形定义内积和若当积如下； ( z ，y ) ：= 戤玑，x 。y ：= x $ y ， 这里缸表示z 的第i 个分量， y 表示z 和y 的相应的分量乘积那么舻是 一个欧几里得若当代数，其平方锥为多面锥职单位元是由所有分量为1 的元 素集合 e 1 ，e 。) 是册中唯一的一个若当基底，其中岛是由第i 个分量为1 而其他分量为0 的元素口 例1 2 给定n 维实欧几里得空间舻，其内积如上例，记f 形为z = ( $ l ，z ) t ， 其中2 7 1 r 和z 2 舻定义若当积为 删= ( ( ：) ：= ( 。，测m ) ，眠，呱 则( 舻，( ，) ，o ) 形成个欧几里得若当代数( 简记为 ) ，其乎方锥a 罩( 又称二阶 锥，l o r e n t z 锥或冰激凌锥) 为 婶：= ( 钆z ) r ：z - l h 其中”n 表示z 一模单位元为e = ( 0 1 ) 根据定理l z m ，当n = z 时， ( i ， ) r ，( ，一) 7 是a 2 中的唯一的若当基底；当佗 2 时，若当基底是不唯一 的事实上，任意 ( 1 ，一，) r ， ( 1 ，v 7 ) r ) 都是舻的个若当基底，其中”是 尼_ 1 中满足陋i l = 1 的任意元素口 第一章绪论 例1 3 设驴表示所有n n 实对称矩阵组成的集合，其中内积和若当积分别定 义如下； ( x ，y ) ：= t r a c e ( x y ) ，xo y ：= ( x y + y x ) 2 容易验证，铲是一个欧几里得若当代数，其平方锥为所有半正定矩阵组成的集 合墨单位元为单位矩阵e 集合 e l ，b 构成驴的一个若当基底，其中 岛“ 1 ，2 ，n 是第( i ，i ) 个元素为1 其余元素为0 的对角矩阵任意给定 x s “，存在列向量为q l ，的正交阵q 和一个实对角阵a = d i a g ( a i ) ，使 得x = q a q 7 = a l q l q + + a 。蠢，其中九( i = l ，n ) 是义的特征值， 吼( i = 1 ，n ) 是相应的特征向量根据定理1 2 1 4 ，当n 1 时，眇的若当 基底不是唯一的事实上，任意 g e l g t ，g e 2 伊，g e , 。g 7 ) 都是一个若当基 底，其中g 是任意的n n 正交阵口 1 3 对称锥互补问题的研究历史和现状 1 3 1 对称锥互补问题的研究历史 对称锥互补问题是通常意义下的互补问题的推广和发展，而互补问题( c o m - p l e m e n t a r i t yp r o b l e m s ，以示区别，下面称之为标准互补问题) 首先由著名运筹学 家，数学规划的创始人g b d a n t z i g 和他的学生r w c o t t l c 于1 9 6 3 年提出次 年，c o t t l e 2 7 1 在其博士学位论文“n o n l i n e a rp r o g r a m sw i t hp o s i t i v e l yb o u n d c d j a c o b i a n s ”中第一次提出了求解它的非线性规划算法这一数学问题在初期曾被 称为“拼合问题”( c o m p o s i t ep r o b l c m ) ，“基本问题”( f u n d a m e n t a lp r o b l e m ) 或 “互补转辅问题”( c o m p l e m e n t a r i t yp i v o tp r o b l e m ) 等标准互补问题是从线性 规划和非线性规划推广而形成的【2 8 ，2 9 ，3 0 ，3 2 】，特别地，它可能来源于求解一个 非线性的优化问题的k a r u s h k u h n - t u c k c r ( k k t ) 系统该问题很快引起了当时运 筹学界和应用数学界的广泛关注和浓厚兴趣，许多人参与了这类问题的研究至 8 0 年代中后期，经过2 0 余年的努力，在理论和算法两个方面都已取得了比较丰 硕的成果关于1 9 9 0 年以前的工作，可见h a r k e r 和p a n g 的综述文章 5 3 1 以及该 时期的优秀专著 3 1 】由于互补问题与最优化、变分不等式、平衡问题、博弈论、 不动点理论等数学分支的紧密联系，以及它在科技与经济方面的广泛应用，越来 越显示其重要性这刺激人们对之进一步研究，出现了二十世纪9 0 年代以来的高 潮在这十余年的时间里不仅改进和丰富了其理论成果，而且还提出多种有效算 法有兴趣的读者可参阅综述文章 6 ，9 7 ，1 2 8 】以及该时期的优秀专著【3 5 ，5 8 ，8 4 】- 1 2 北京交通