（运筹学与控制论专业论文）pareto特征值理论与计算.pdf

f ；) 湃六謦 t o n g j iu n l v e r s i t y ad i s s e r t a t i o ns u b m i t t e dt o t o 画iu i l i v e r s 时i nc o n f o m i 够w i t ht h er e q u i r e m e n t sf o r t 1 1 ed e 班eo fm a s t e ro fs c i e n c e t h e o 哕a n da l g o r - t h mo fp a r e t oe i g e n v a i u e p r o b l e m c a n d i d a t e ：y a c h a oq i s t u d e n tn u m b e r ：0 7 2 010 2 0 2 3 d e p a n m e n t ：d e p a n m e n to fm a t h e m a t i c s d i s c i p l i n e ：m a t l l e m a t i c ss c i e n c e m a j o r ：o p e r a t i o n a lr e s e a r c ha n dc o n t r o lt h e o r y s u p e i v i s o r ：p r o x i o n g d ac h e n s u d e r v l s o r ：上j r o t x l o n g d ac h e n m a r c h ，2 0 1 0 学位论文版权使用授权书 本人完全了解同济大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名：徊建鱼 如l o 年弓月l6 日，一v 一，vh 同济大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 学位论文作者签名： 蒜亚超 1 口f o 年；月j 石日 摘要 摘要 p a r e t o 特征值问题是定义在正卦限上一类锥约束特征值问题，它具有简单的 提法，却开拓了全新的数学理论领域，使得传统代数特征值问题在更广泛的理论 空间展现出新的巨大生命力，具有全新理论研究价值和广阔实际应用性。近年来， 随着实际工程中大量问题的涌现和相关理论的发展，p a u r e t o 特征值问题理论与计 算引起学者们的关注和热情。a s e e g e r 等对锥约束特征值问题进行分析研究，特 别对p a 弛t o 特征值问题给出一个理论与计算方法。 本论文分为五章来叙述。第一章介绍p 甜e t o 特征值问题背景以及一些必备数 学基础知识。第二章给出了p 甜e t o 特征值概念和基本性质。第三章包含三节，给出 了几种特殊矩阵的p 村e t o 特征值问题。其中第一节对正矩阵p g u r e t o 特征值分析讨 论，确定其最大最小p a u r e t o 特征值。第二节引进一类新矩阵，加以讨论给出其部分 理论性质，它的最大p 盯e t o 特征值可被直接计算。第三节对佗维实矩阵p a r e t o 特征 值个数上界问题给出了新的上界，并利用第二节中引进的一类新矩阵性质，给出矩 阵实例。第四章利用互补函数性质，给出求解p 甜e t o 特征值的数值计算方法，并证 明其收敛性，最后对实际问题进行相关的数值计算。数值实验表明：f b i m 收敛性 较好，与理论结果一致。第五章我们总结了全文并列出一些开放问题，如p 盯e t o 特 征值敏感性等。 关键词：p 村e t o 特征值，锥约束，特征值，非负矩阵，加边矩阵，互补函数 a b s t r a c t a bs t r a c t t h ep 盯e t oe i g e m r a l u ep r o b l e m ( p e p ) i sa ni m p o r t a n tp r o t o t y p eo fc o n 争 c o n s t r a i n e dp r o b l e m s ，w h i c he x h i b i t 8a l r e a d ym a i l yo fm a t h e m a t i c a ld i 佑c u l t i e s 龇i s i n gi nt h ec o n t e x to fc o m p l e m e d t 撕锣c o n d i t i o n si n v o l v i n gt h ep o s i t i v eo r t h a n t t h i st h e s i si j so r g a n i z e d 弱f o l l o w s c h a p t e r1c o m p r 鼬t h 砌es e c t i o n si i l w h i c hw ei n t r o d u c et h eb a c k 留o u n da n dd e v e l o p m e n to fp e p ，r e v i e wb a s i cu n e a r a l g e b r aa n di n t r o d l l c e dt h eg e n e r a lc o n c e p t so fc o n ea n dd u a lc o n e ，e c t c h a p t e r 2i 80 nc o n c e p t s0 fc o n e - c o n s t r a i n e dp r o b l 明_ l s ，e s p e c i a l l y t h ep e pa n di t st h e 0 - r e t i c a li 鹃u e s c h a p t e r3c o n s i s t s0 ft h r e es e c t i o n s i ns e c t i o n3 1 ，w ed i s c u s 8t h e m 蹦i m ma n dm i i l i m u mp a r e t oe i g e m r a l u eo fp o s i t i v em a t r i xa n dt h eb o u n do f p a r e t oe i g e m ， 虹u e sf o r 酉v e nr e 以m a t r i c e 8 i ns e c t i o n3 2 ，t 、on e wl 【i n d so fm a 广 t r i ) ( a r ei n t r o d u c e da n da n a l y z e d ，n a m e l y q m a t r i ) ( a n dl m a t r i ) ( ，w h o s el a u r g e s t p 盯e t oe i g e n v a l u e sc a nb ee s t i m a t e d i n8 e c t i o n3 3 ，t h eb o u n d sf o rt h ep a r e t o c a p a c i t y 缸ed i s c u s s e da n d8 0 l em a t r i ) 【e x 锄p l e sa r e 西v e n i nc h p a t e r4 ，s p e c i a l a t t e n t i o ni 8p a i dt ot h e 肌m e r i c 甜t e c h n i q u e sf o rs o m n gp e p ，n 锄e l y f i 8 c h e r - b u r m e i s e ri t e r a t i v em e t h o d ( f b i m ) ，a n ds o m ep r e l i m i n a 可i m m e r i c a lr e 8 u l ti s p r e 8 e i l t e d h lc h a p t e r5 ，w em 址【eo u rc o n c l u s i o n sa n d1 e a v eo p e nq u e s t i o n sf 6 r f i l r t h e r 出s c u s s i o n k e yw 0 r d s ：p 盯e t o ，c o n e - c o n s t r a i n e d ，e i g e i a l u e ，n o n n e g a t i v em a t r i x ，b o r d e r e d m a t r i ) 【，c o m p l 锄e n t a r i t y i i 目录 目录 第l 章引言 1 1 1 问题背景1 1 2 数学基础 2 1 3 锥的概念 5 第2 章p a u r e t o 特征值理论 7 2 1p a r e t o 特征值概念7 2 2 p a r e t o 特征值的理论性质 9 第3 章特殊矩阵的p a r e t o 特征值问题 1 0 3 1 正矩阵的p a r e t o 特征值问题 1 0 3 2 q 一矩阵的p 盯e t o 特征值问题 1 2 3 3 矩阵p 跚e t o 特征值个数上界问题 1 7 第4 章p a u r e t o 特征值数值算法及其收敛性 2 0 4 1 f b i m 算法 2 0 4 2 数值试验结果 2 5 第5 章结论与开放问题 2 9 5 1 结论 2 9 5 2 开放问题 3 0 致谢 参考文献 附录 个人简历 3 1 3 2 3 6 4 1 第1 章引言 第1 章引言 1 1 问题背景 矩阵不仅是数学学科，而且是理工学科的重要数学工具。矩阵理论是极富创 造性的领域，它的创造性又极大地推动和丰富了其他众多学科的发展。许多新的 理论、方法和技术的诞生与发展就是矩阵理论的创造性应用于推广的结果。 在矩阵众多问题中，矩阵特征值问题有着一种特殊的魅力，它充分的显示出 所谓经典数学与数值计算之间的差异。矩阵特征值基本理论多年来已为人们所熟 知，然而欲求其精确解就会遇到各种挑战性问题。矩阵特征值问题不仅可直接解 决数学中诸如非线性规划、优化、常微分方程，以及各类数学计算问题，而且在 结构力学、工程设计、计算物理和量子力学中具有重要作用，目前矩阵特征值问 题的应用大多来自于解数学物理方程、差分方程、m a r k o v 过程等。正因为它具有 重要意义和广泛的应用，所以矩阵特征值问题是当前国内外高性能计算机的主要 计算任务之一。 p a r e t o 特征值问题【1 ，2 3 】是定义在正卦限上一类锥约束特征值问题【1 8 ，2 7 _ 2 9 1 。它具有简单的提法，却具有全新理论研究价值和广阔实际应用性。最初在工 程中研究摩擦弹性系统稳定性和数学研究分叉理论变分不等式算子时出现，在很 多领域都有其重要应用，许多工程中平衡问题、交通模型、数学物理方程、统计 分析、自动控制等方面的研究最后都归结到此问题。其理论价值在于将传统的代 数特征值问题推广扩展，开拓了全新的数学理论领域，使得受人爱戴的传统代数 特征值问题在更广泛的理论空间展现出新的巨大生命力，而其实用性使包括工程 师、物理学家、数学家等许多人都感兴趣。随着实际工程中大量问题的涌现和相 关理论的发展，在本世纪近几年中逐渐引起人们的关注和热情。 1 9 9 8 年，a s e e g e rf 2 7 】一篇具有奠基性的论文，由线性对偶条件引出的控制 平衡过程的实际背景，将锥约束特征值问题全新的呈现在人们面前。在h i l l b e r t 空 间上闭凸锥及其对偶锥上，给出了锥特征值( 也称肝特征值) 的定义，并给出了锥 特征值存在性和当锥是有限生成时锥特征值个数的上界，特别是p 盯e t o 特征值问 题特征值个数上界理论，并提出了其他的新问题。 1 第1 章引言 2 0 0 3 年，a s e e g e r 和m 1 b r l 【i 【2 8 】针对扎阶实矩阵和实数空间上闭凸锥，给 出了闭凸锥关于n 阶实矩阵谱分析的线性对偶问题的一些基础理论，研究了谱映 射的主要性质，讨论了多面锥和非多面锥的一些结构差别。 2 0 0 7 年，a s e e g e r 和m ，】b r k i 【2 9 】研究了仃阶实对称矩阵上，凸锥上二次规 划问题的线性对偶局部极小问题，这一结果把凸锥的谱分析理论和矩阵代数结合 起来，并进行了推广。 2 0 0 8 年，a p 砒od ac 0 8 t a 和a s e e g e r 【2 3 】对锥约束特征值问题进行了分 析，讨论了锥特征值个数的最大估计，特别对p 踮e t o 特征值这一特殊情形进行了 详细分析，并给出了两个数值算法。 2 0 0 9 年，s a d l y 和a s e e g e r 1 】对锥约束特征值问题给出了两种非光滑算法， 并证明其收敛性。 本论文将继续他们的研究工作，进一步研究p 盯e t o 特征值的理论性质，并引 进一类新矩阵加以讨论其性质，它的最大p a 鹏t o 特征值可被直接计算。最后给出 数值计算方法，并证明其收敛性，最后对实际问题进行相关的数值计算。数值实 验表明：f b i m 收敛性较好，与理论结果一致。 1 2 数学基础 本节介绍用到的一些数学基础知识【3 3 ，3 8 ，3 9 】 我们用r 表示实数域，p 表示几维实空间。同样地，用c 表示复数域，c n 表 示佗维复空间，m m m 表示全体m n 阶实矩阵集合，m n 表示全体竹阶实矩阵。 用大写字母表示矩阵，如果不作另外说明，矩阵假定为礼阶实矩阵，矩阵a 的( i ，歹) 元素记为，a 亦记为a = ( a 巧) 向量用小写字母表示，一般假定为几维。 向量z 的第z 个分量记为觋，o 亦记为z = ( ) 同时我们采用如下记号： a ( t ，：) 兰矩阵4 的第i 行， a ( ：，歹) 兰矩阵a 的第歹列， a 兰矩阵a 的子矩阵i j ，歹z d e t ( a ) 三矩阵a 的行列式 2 第1 章引言 矩阵a 转置矩阵记为矩阵a r ，其元素( i ，歹) 等于啄类似地，z t 表示z 的转置行 向量，它的第t 个分量等于祝 礼阶单位矩阵用磊表示，它的( i ，歹) 元素记为如，即k r o n e c k e r 符号。于是我们 有 如= o ( t 歹) ， 如= 1 ( 1 1 ) 既的第i 列记为e i ，用e 表示向量e 1 + e 2 + + e 竹，它的每一个分量等于1 记号l a l 表示( i ，歹) 元素等于i l 的矩阵，记号 i a i i b i ，( 1 2 ) 意即 i i 1 i ，歹 ( 1 3 ) 接下来我们给出几个基本概念的定义【4 2 】： 定义1 2 1 设y 是实数域r 上的线 生空间，在y 中规定一个二元实函数，记为( q ，卢) ( 即对y 中任意两个向量q ，p ，有一个实数( q ，p ) 与之对应) ，且具有如下性质： ( n ，p ) = ( p ，q ) ， ( 后q ，p ) = 尼( a ，p ) ， ( q + p ，7 ) = ( q ，7 ) + ( p ，y ) ， ( q ，a ) o ，当且仅当q = o 时，( q ，q ) = o 这里，a ，p ，7 y ，后r ，则称( q ，p ) 为向量q 与p 的内积。定义了内积的实线性 空间y 称为欧氏空间 定义1 2 2 映射：职_ r 称为p 上的范数，当且仅当它具有下列性质： 非负性：0 z l i o ，l l z 0 = o 当且仅当z = o ， 齐次性：l l l i = i c i l i z 0 ， 三角不等式m z + 训忪0 + l i ， 则l 为称为p 上范数。 3 第1 章引言 向量z = ( z 1 ，z 2 ，) t 的岛范数定义为 i l z l i p = ( 喜l z t l p ) ；，1 p ， ( 1 4 ) p = i 蚶) ，1 p ， ( 1 4 ) 扛l 其中，常用p = 1 ，2 ，o o 三种向量范数【9 ，1 1 ，4 2 】： 。= 蚓= 剐+ 蚓+ 蚓， i = 1 ( 1 5 ) ( 1 6 ) 。2 燃腩i ，蚓，蚓) ( 1 7 ) l 本文中，我们定义欧氏空间p 上的内积为( z ，秒) = z r 秒= 甄犰，同时范数 t = l 定义为内积形式忪0 ：( z ，z ) 类似于向量范数的定义，可以定义矩阵范数。 定义1 2 3 如果矩阵a 地的某一非负实值函数( a ) = i i a i i ，满足如下条件： 非负性：l l a i l o ，0 a 0 = o 当且仅当a = o ， 齐次性：l l c a i i = l c f i i a i i ， 三角不等式：i i a + b 0 i i a | l + i i b i i ，b m n ， l i a b i l 0 a 0i l b l i ，b m n ， 则称( a ) = 0 a l l 飙上一个矩阵范数。 常用矩阵范数有【9 ，1 1 ，4 2 】： ，= m 磬蚓， = n 垮蚓， 悄0 2 = ( 入a ? a ) 考， f = ( 蚶) n n 、喜 j = 1t = l 其中入a t a 表示a 的最大特征值。 4 ( 1 8 ) ( 1 9 ) ( 1 1 0 ) ( 1 1 1 ) 第1 章引言 1 3 锥的概念 我们记= 1 ，2 ，佗) ，对指标集j ，记l j | 为集合j 的势，即j 中元素个 数。 若集合s p ，存在r o ，使得b ( z ，r ) = 可舻：陌一z | l o ，则z 称为属于s 的闭包，记 做z 雪如果s = 雪，则s 称为闭集【4 2 】 设x 是拓扑空间，如果x 的任意开覆盖都有有限子覆盖，则称x 为紧空间。 设a 是x 的子集，如果x 的子空间a 是紧空间，则称a 是x 的紧子集 3 6 】 定义1 3 1 若集合k r n 满足条件 v z k 及q 0 ，口z k ， 则称k 是一个锥 2 6 】若对任意z ，秒c 点集及实数q o ，1 】，都有 q z + ( 1 一q ) 可c ， 则称c 为一个凸集。一个锥若是凸集，称为凸锥。如果凸锥k 又是一个闭的，那么 称k 是一个闭凸锥。我们用符号k ( 融) 表示 k ( 时) = k 戤：k 是一个闭凸锥) 若k k ( p ) 满足 k n k = o ) ， 则称锥k 是有指向的。换言之，一个凸锥k 是有指向当且仅当它不包含任何直线。 定义1 3 2 假设锥k k ( 瞅) ，称集合 k + = 秒r ，：( y ，z ) o ，v 2 k ) 为锥k 的对偶锥。从几何意义上说，若内积为欧氏内积，则锥k k ( r n ) 的对偶 锥就是与中任意向量夹角为锐角的向量组成的锥。 5 第1 章引言 进一步，如果锥k k ( 职) 以及其对偶锥k + 满足 k = k + ，( 1 1 2 ) 则称锥k 为自对偶锥 2 ，2 5 ，2 6 ，3 2 】 两种特殊锥及其对偶锥为： k = 舻，即佗维实空间，k + 退化为零点，即k + = o ) ； = 畔，即扎维正卦限，k 为自对偶锥，即k + = k = r 华 6 第2 章p a r e t o 特征值理论 第2 章p a r e t o 特征值理论 2 1p a r e t o 特征值概念 问题l ：给定实矩阵a m n 及锥k k ( p ) ，我们称如下问题( 2 1 ) 为锥约束特征 值问题，具体形式为： 求解a r 和非零向量z p 满足 k 弓z 上( 月z a z ) = 秒k + ( 2 1 ) 其中k + 表示锥k k ( 孵) 的对偶锥。特别地，下面两种情况： ( 1 ) 当k = p 时，k + 退化为零点，即k + = o ) ，( 2 1 ) 为如下形式： 求解a r 和非零向量z p 满足 秒= a z a z = o ( 2 2 ) 此时锥约束特征值问题转化为一般意义上的特征值问题，本文中称为普通特征值 问题，并采用如下记号： 仃( a ) 三实矩阵a 的谱( 普通特征值集合) ， p ( a ) 三实矩阵a 的谱半径 ( 2 ) 当k = 畔时，k 为自对偶锥，即k + = k = 晦，( 2 1 ) 为如下形式： ( 2 3 ) ( 2 4 ) 求解入r 和非零向量z 瞅满足 珥z 上( a z a z ) l 啤 ( 2 5 ) 此时锥约束特征值问题称为p a r e t o 特征值问题。如果存在非零向量z 舻满足( 2 5 ) ， 则我们称实数入是给定实矩阵a 的一个p a r e t o 特征值。相应地，z 称作实矩 阵a 对应p a u r e t o 特征值a 的p a r e t o 特征向量。实矩阵a m n 的p a r e t o 特征值集合 称作a 的p 盯e t o 谱，记做 ( a ) = 入r ：( z ，入) 是问题1 之( 2 5 ) 的解) 7 第2 章p a r e t o 特征值理论 ( 2 5 ) 也可以写作如下形式： 0 z 上a z 一入z = 可0 ( 2 6 ) ( 2 6 ) 中不等号“为分量形式意义，即z = ( z 1 ，z 2 ，z n ) r 舻，z o 当且仅 当任意i 1 ，2 ，佗) 都有戤o ，其中z t 表示向量z 的转置向量。由( 2 6 ) 中正 交性可以得出入和z 的关系可以表示为& 桫l e i g l 卜r i t z 商 入= ( z ，a z ) ( z ，z ) ，( 2 7 ) 不过这里并不要求“残差”向量 y = a z a z ( 2 8 ) 为零，这比普通特征值a z = a z 中条件宽松，但另一方面，z ，必须满足z ， 狂殴和对偶条件，即互补松弛条件。 问题2 ：给定实对称矩阵a 砜，求解如下形式约束最优化问题： m i n 三( z ，血) s t 扛，z ) = 1 ， z 避 ( 2 9 a ) ( 2 9 b ) 此问题的l a g r a n g e 函数为 l ( z ，a ，秒) ：昙( z ，a z ) + 昙a ( 1 一缸，z ) ) 一( z ，秒) ， ( 2 1 0 ) 其中z ，秒啤，可是非负约束( 2 9 b ) 的l a g r a n g e 乘子，a r 是等式约束( 2 9 a ) 的 l a g r a n g e 乘子。化简( 2 1 0 ) 的一阶必要条件，我们可以得到问题2 任意解z 满足如 下条件： a z 一入z 一剪= 0 ， 1 一( z ，z )= 0 ， ( z ，剪)= 0 ， z ，秒r 罩 ( 2 1 1 b ) 表明忙l | 2 = l ，( 2 1 1 a ) ，( 2 1 1 c ) 和( 2 1 l d ) 可以表示为如下形式： 0 z 上a z a z = 秒0 由以上可知，普通的约束优化问题可以转化为p a r e t o 特征值问题求解。 8 ( 2 1 1 a ) ( 2 1 1 b ) ( 2 1 1 c ) ( 2 1 1 d ) ( 2 1 2 第2 章p a r e t o 特征值理论 2 2 p a u r e t o 特征值的理论性质 对于如何求解p a r e t o 特征值问题，有如下定理： 定理2 2 1 ( 参见【2 3 】) 假设a m n ，则a r 是实矩阵a m n 的一个p a r e t o 特 征值当且仅当存在非空指标集j 冬= 1 ，2 ，佗) 和一个向量酞叽满足 g ，j = ， ( 2 1 3 ) a j j = a ，砒( r 粤) ，( 2 1 4 ) a i ，0 ( 2 1 5 ) 则向量z 舻有分量如下 i 磊，如果i ， 甄2 1 o ，如果i z 是实矩阵a 相应于p 盯e t o 特征值入的一个p a r e t o 特征向量。 计算一个给定实矩阵a 的p a u r e t o 特征值谱比求解其普通特征值谱要困难求得。 我们可以看到( 2 1 4 ) 是求解其子矩阵a j ，普通特征值问题。当然，这里要求相应的 特征向量专i n t ( 酞坚i ) 因此，有 = 2 n l ( 2 1 6 ) 种方法选取非空指标集，这导致有个普通特征值求解问题。 空间m n 的p a r e t o 特征值个数上界定义为 = 罂擎c a r d 【唧m t o ( a ) 】， ( 2 1 7 ) ” j 4 m n 。p “。”。7 1 、。7 即空间砜中实矩阵p a r e t o 特征值个数最大值。计算以及找到一个实矩阵a m n 可以达到( 2 1 7 ) 中的上界并非易事。序列 ) n s l 关于n 呈指数形式增长。事实 上，满足如下关系( 参见【2 3 】) 7 k n 2 n 一1 一( n 一1 ) ，( 2 1 8 ) 其中 g n ：触一掣+ 矿( 亿) ， 这里矿：n _ n 表示 妒( p ) ：p 2 p 一1 + 坐# 的离散f e n c h e l 共轭，n 表示自然数集。 9 第3 章特殊矩阵的p a r e t o 特征值问题 第3 章特殊矩阵的p a r e t o 特征值问题 3 1 正矩阵的p a r e t o 特征值问题 定义3 1 1 ( 参见【1 1 】) 对实矩阵a = ( n 巧) 地，如果 n 玎 o ，v i ，歹= 1 ，2 ，n ) ， 则称a 为正矩阵，记做a 0 同时，记 耽= a m n ：a o ) 注：在与巩有关的矩阵性质中，我们可以放松晚的矩阵类，由正矩阵放松为不可 约非负矩阵【1 1 】 对于正矩阵a 既，有如下p e r r o n 定理： 定理3 1 1 ( p e r r o n 定理， 1 1 】) 如果a ，且a o ，则 1 p ( a ) 0 ； 2 p ( a ) 是a 的一个特征值； 3 存在z p 且z o ，a z = p ( a ) z ； 4 p ( a ) 是矩阵a 的代数重数( 和几何重数) 为1 的特征值； 5 对入p ( a ) 有， o ，血= p ( a ) z ，我们称p ( a ) 为正矩阵a 的p e r r o n 特征值，并 记做p p e 玎( a ) 由( 2 5 ) 可知p p e 丌0 n ( a ) 也是矩阵a 的一个p a r e t o 特征值，z o 为相 应的p a 舱t o 特征向量。接下来，我们讨论给定j 下矩阵a n 的p 甜e t o 特征值，记 a p 批三a 的p 眦t o 特征值，其中a 畋 ( 3 1 ) 1 0 第3 章特殊矩阵的p a r e t o 特征值问题 引理3 1 1 设a 给定非空指标集厶c 厶= 1 ，2 ，佗) ，4 如的 主子阵a 和a j 2 j 2 的p e r r o n 特征值分别为j d p e 盯。n ( a j 。j 。) 和p p e 肿n ( a 比如) ，则 o 时得( 3 2 ) ，指标集j 1 2 取集合= 1 ，2 ，佗) 时 得( 3 3 ) 证毕。 口 对一般实矩阵a n 戤的p 盯e t o 特征值界，有如下性质： 定理3 1 3 假设a 地，则 i a p 删。( a ) i 邝e 丌。n ( i a i ) ， 其中i a l = ( i o 巧i ) i 庆表示矩阵a 按分量取绝对值，= 1 ，2 ，他) 证明：对矩阵a 的主子阵a m 假定a l ，( a j j ) 是a j r j 的普通特征值。由p e h o n 定理， 对i a j j l q j l 有， i a ，( a j j ) l 肛，m n ( i a j j i ) 另一方面， i 入p 删。( a ) i 搿臀m 删搿纬一( 训肛咖n ( a ) 证毕。口 1 1 第3 章特殊矩阵的p a r e t o 特征值问题 3 2 q 一矩阵的p a u r e t o 特征值问题 我们讨论了a 职的最小p a u r e t o 特征值和最大p a u r e t o 特征值p p e 肿n ( a ) 以及一 般矩阵的p 骶e t o 特征值界。同时，我们也对如下加边矩阵的最大p a r e t o 特征值感 兴趣。 定义3 2 1 假定a ，b ，c ，d 是正矩阵，相应的维数是礼死，m 似，n m ，m m 我们称正矩阵a 的加边矩阵 q = 三二三 c 3 5 ， 为列向量符号相同矩阵。因为任意i = 1 ，2 ，n ) ，列向量q ( ：，i ) o ，以 及i m = 佗+ 1 ，n + 2 ，n + m ) ，列向量q ( ：，i ) 0 时，我们记列向量符号相同矩阵为 三= 二斗 6 ， 我们采用记号 q m 三 q m n + m ：q 是加边矩阵( 3 5 ) ) ， k + 1 兰 l 地+ l：l 是加边矩阵( 3 6 ) ) 首先来看一个引理。 引理3 2 1 ( 参见【1 1 】) 假设正矩阵a 畎，w = 入r a ，当入 肛盯。n ( a ) o 时， 则非奇异( 即可逆) ，且1 是正矩阵即一1 0 证明：我们分两步来证明。 1 由a 纬e ”。n ( a ) o ，知o 邝一( a ) o ，所以 。 o ，得一1 o ， 证毕。 口 推论3 2 1 假设三= 二三 满足条件c 3 6 ，存在邱鲥c 舢 。和。 邝e ，( a ) o 首先矩阵l 的特征多项式是 妒( a ) = d e t ( 入e k + 1 一l ) 一t ( 一a 入 =( a + a + 乱t ( a r a ) 一1 ) d e t ( a r a ) ( 3 7 ) ( 3 8 ) ( 3 9 ) ( 3 1 0 ) 由引理3 2 1 知，入玩一a 非奇异，即d e t ( a r a ) o 且( a r a ) 一1 o 又因 为入+ q o ，u o 和秒 o ，因此入+ q + 让t ( a 鼠一a ) 一1 移 o 可得妒( a ) o ，即 当入 邝一n ( a ) o 时，特征多项式咖( a ) = o 无解。因此 入邝一n ( a ) 证毕。 口 定理3 2 1 假设三= 二三 满足条件c 3 6 ，存在眼一c a ， 。和。 o ，j 即主子阵元素全大于0 ：由( 3 3 ) 知，a 删。瑚x ( a j j ) = 邝鲥( a j j ) o ，再由单调性( 3 4 ) 知， 搿肛一( 山，) 服一( a ) ； 2 j = 佗+ 1 ) ，以j j = 【- q 】即主子阵元素全小于等于o ：主子阵普通特征值为一q ， 相应的全部正普通特征向量为0 0 ，所以 一秽z o 我们根据矩阵q 的分块情况将向量z 跫寸m 分为两部分 。- 玎 其中，= 1 ，2 ，n ) ，j = 礼+ 1 ，佗+ 2 ，礼+ m ) 若a r 和z r 寸m 满足 q z = 入z ，( 3 1 3 ) 将其改写为分块形式 ( a a e ，) z j c z ，= o ， b z j 一( d + a ) z j =0 ， z jo ， z ， 0 由a 邝。玎o n ( a ) o 可得a a 昂可逆，且( a a r ) - 1 o ，由( 3 1 4 ) 得 z j = ( a a 晶) 1 沈j ， ( 3 1 4 ) ( 3 1 5 ) ( 3 1 6 ) ( 3 1 7 ) ( 3 1 8 ) 又因为( a 一入政) 一1 o ，b o ，c o ，所以b ( a a 取) 一1 c o 代入( 3 1 5 ) 左 边得 ( d + a + b ( a a 取) 一1c ) z j a z j o ( 3 1 9 ) 矛盾。 证毕。 口 1 5 第3 章特殊矩阵的p 盯e t o 特征值问题 定取2 硼设q = 三二三 满足删3 脚，存在c 砂。袱 p ，满足a = p p e 。( a ) ，则列向量符号相同矩阵q 最大p a u r e t o 特征值 入p 础一( 三) = 肛一( a ) ， ( 3 2 0 ) 相应的p 雏e t o 特征向量可取为 甄= r 翥羹：茎篓 其中= 1 ，2 ，佗) ，m = 佗+ 1 ，死+ 2 ，他+ m ) 证明：根据主子阵的选取，非空指标集可以分为三类： 1 j ，a j j o 即主子阵元素全大于o ：由( 3 3 ) 知，a p 啪t 。m 越( a j ，) = j d p 。n d n ( a j a 再由单调性( 3 4 ) 知， 器器胁( a j j ) 陆田m ( a ) ； 2 ，m ，a j ， o ，即主子阵元素全小于等于o ：假设存在r 和向量r 坚i ， 满足 a i i = 入i 乏 取j = t 1 ，2 ，m + 佗) ，因为q ，j = 三二三 ，j 是 二三 的子块，可 知q i ，j o ，所以 q j ，= 三二三 ，f o = t 7 ( z ) o ，v 亡 o ，v z k ， 坼= 扛k ：7 - ( z ) = 1 ) 是紧集 则称r ：k 一已是闭凸锥k 的一个规范函数。同时，我们称z k 是一个丁规范向 量当且仅当7 ( z ) = 1 一个有限维空上的闭凸锥都存在规范函数，比如： 7 - ( z ) = 忪| i ( 4 1 ) 特别是当k 是有指向锥时，如k = r 至，一个让我们感兴趣的规范函数是 1 - ( z ) = ( e ，z ) ， e i n t ( k + ) ( 4 2 ) 我们的目标是如下问题： 问题3 ：给定实矩阵a m n 及锥咚，求解a r 和非零向量z 舻满足 ( a a ) z = 可，( 4 3 ) r 军弓z 上可r 罩， ( 4 4 ) 1 - ( z ) = 1 ( 4 5 ) 以上形式是问题1 之( 2 5 ) 的另一种写法，只是增加了规范函数条件( 4 5 ) 对偶条 件( 4 4 ) 表示z 埤，y 啤，( z ，可) = o 当然对于正比例因子s o ，同样成立： z r 军，s 秒毫华，( z ，s 矽) = o ( 4 6 ) 引理4 1 1 对正卦限r 华，秒上z 畔 o ) ，有z s 可o 2 0 第4 章p a r e t o 特征值数值算法及其收敛性 证明：反证法。假设蛩r ，有z 一轫= o 因为z 畔和轫一z = o 酞军，所以 与z 0 矛盾。 o ( z ，秒一z ) = 一0 2 0 2 ， ( 4 7 ) 证毕。口 给定矩阵a m n ，求解其全部p a r e t o 特征值并非易事，但是我们可以采用迭 代方式求解其局部解。首先我们介绍互补函数 定义4 1 2 如果函数西：瞅舻_ p 满足 ( n ，6 ) = o 兮n r 华，6 瓜车，( n ，6 ) = o ( 4 8 ) 则称( 口，6 ) 是p 上的互补函数。 常用互补函数有 1 f i s c h e r - b u n n e i s e r ： 如b ( n ，6 ) = 口+ 6 一、孑丽，v ( 口，6 ) 酞2 ；( 4 9 ) 加( o ，6 ) = 、币= 巧丁干万磊一n 一6 ，p 【o ，4 ) ，v ( n ，6 ) r 2 ； ( 4 1 0 ) 3 j s c h e n ： 如( 口，6 ) = ( i o i p + 1 6 i p ) ；一。一6 ，p ( 1 ，o o ) ，v ( 口，6 ) p ( 4 1 1 ) 接下来我们给出算法： 算法1 ( c f i m ) ： 1 给定参数：常数a ( o ，1 ) ，比例因子s o ，允许误差e ”； 2 初始向量扩：任意向量0 牡珥，定义 护2 高； 2 1 ( 4 1 2 ) 第4 章p a r e t o 特征值数值算法及其收敛性 3 计算： 枷镨； ( 4 1 3 ) 4 残量矿： 矿= 4 z 。一入z ；( 4 1 4 ) 如果矿= o 算法终止，否则进行下一步； 5 计算： 口= 一咖( z ，s 可) ；( 4 1 5 ) 6 计算z 件1 ： + 1 _ ( 1 ) + 焉； ( 4 1 6 ) 7 如果i i z 件1 一0 e r r ，则算法终止；否则进行下一次迭代。 步骤4 中，如果某次迭代后可= 0 ，没有必要在进行下一次迭代，因为+ 1 = ， 已经找到一个解。实际上此时( ，凡) 是矩阵的普通特征值和特征向量，其中o 珥 步骤5 中，对于向量z ，秒舻，有向量( z ，可) ，其第t 个元素为 ( ( z ，可) ) = ( z i ，犰) ， ( 4 1 7 ) 其中戤，犰分别表示向量z ，秒的第i 个元素。本文中我们采用( 4 9 ) f b 互补函数，相 应的算法称为f b i m 算法如果对向量z ，秒p ，规定 zo = ( z 1 玑，z 2 耽，蜘) t ( 4 1 8 ) 对向量z r 至，规定 z 2 = ( z ；，遁，) r ， ( 4 1 9 ) z = g 溺，z 主) t ( 4 2 0 ) 那么对向量z ，可舻，有z 2 + 护衅，因此互补函数f b ( z ，可) 有如下形式： 如b ( z ，可) ：z + 一( z 2 + 犷) ( 4 2 1 ) 第4 章p a r e t o 特征值数值算法及其收敛性 定理4 1 1 假设算法f b i m 选定参数q ( 0 ，1 ) 和比例因子s o ，迭代序列 ) t o 收敛至i 】牙r 2 ，则 仇) 伽一天 ) 伽_ 雪 并且( 牙，天，雪) 是问题3 的一个解。 伍，触) 2 丽( 牙，牙) = 触一入牙 ( 4 2 2 ) ( 4 2 3 ) 证明：首先，因为 ) t 0 一