（计算数学专业论文）矩阵方程的双侧正交与p交换procrustes问题研究.pdf

r e s e a r c ho np r o c r u s t e sp r o b l e m sf o rt w o s i d e d o r t h o g o n a la n dp - e x c h a n g eo fm a t r i xe q u a t i o n s z h a os u f a n g b s ( s h a n d o n gu n i v e r s i t yo ft e c h n o l o g y ) 2 0 0 8 at h e s i ss u b m i t t e di np a r t i a ls a t i s f a c t i o no ft h e r e q u i r e m e n t sf o rt h ed e g r e eo f m a s t e ro fs c i e n c e l n c o m p u t a t i o n a lm a t h e m a t i c s i nt h e g r a d u a t es c h o o l o f h u n a nu n i v e r s i t y s u p e r v i s o r p r o f e s s o rl i a oa n p i n g ：a p r i l ，2 0 11 本人郑重 成果。除了文 已经发表或撰 文中以明确方 作者签名 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保 留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。 本人授权湖南大学可以将本学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密战 ( 请在以上相应方框内打“”) 作者签名：赵隶甍 导师躲房轰争 日期：1 一d f l 年多月 日 日期：幼，f 年名月日 动态 及s 阵集 其中 问题i v 给定矩阵a ，b 舻黼，p s 形黼，求x s 害使得 i l a x b i l = m i n ， 其中$ = x i x p = p x ，x s o r n n ) 。 我们称问题i 和问题i i 为双侧正交p r o c r u s t e s 问题，问题l l l i 1 问题i v 为p 交换 p r o c r u s t e s 问题 本文主要研究成果如下： 1 针对问题i 和问题i i ，我们通过可行集上梯度的投影能够用矩阵表示，给出了 计算投影h e s s i a n 的一种方法利用梯度投影和h e s s i a n 投影得到了问题i 和问题i i 的 第一阶和第二阶最优条件，同时，利用梯度投影的微分方程我们给出了得到全局( 局 部) 最优解的一种数值方法 2 关于问题i i i 和问题i v ，即p 一交换正交p r o c r u s t e s 问题和p 一交换对称正交p r o - c r u s t e s 问题，利用矩阵的奇异值分解和矩阵乘积的迹的性质给出了它们的一般解 的表达式，当解集非空时，得到了最佳逼近解的通解表达式，并分别通过数值例子 验证了结论的有效性 关键词：正交；投影梯度法；p 交换；p r o c r u s t e s 问题；奇异值分解 i i 硕士学位论文 4b s t r a c t p r o c r u s t e sp r o b l e m si so n eo fi m p o r t a n ti s s u e si nt h ef i e l do fn u m e r i c a la l g e - b r a a c t u a l l y , i ti sw i d e l yu s e di nm a n yf i e l d ss u c ha sc o n t r o lt h e o r y , d y n a m i cp r o g r a m m i n g ，s t a t i s t i c s ，t r a n s p o r t a t i o nt h e o r y ，a n de n g i n e e r i n gc o m p u t a t i o nf i e l d w ed e n o t e r e s p e c t i v e l yd r m n s f p na n ds 0 月，na sm 佗o r t h o g o n a lm a t r i x m ns y m m e t r i cm a t r i xa n dn n s y m m e t r i co r t h o g o n a lm a t r i x ，w h e r e ”i ls t a n d sf o rt h ef r o b e n i u sn o r m 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 ht h ep r o b l e m sa b o u tt w ok i n d so fp r o c r u s t e s p r o b l e m s t h a t p r o b l e mig i v e nt w om a t r i c e sa r m m ，b r m m ，f i n dx o 冗m ms u c h x t a x b i i = m i n p r o b l e mi ig i v e nt w om a t r i c e sa r m m ，b 衍n ，f i n dx 0 r m n ， m 礼s u c ht h a t l i x t a x 一例= m i n p r o b l e mi i ig i v e nt w om a t r i c e sa ，b 月：仇n ，p s i t l ，f i n dx s 譬 s u c ht h a t a x s t l = m i n ， w h e r e 蹄= x i x p = p x ，x o r n n ) p r o b l e mi vg i v e nt w om a t r i c e sa ，b r m n ，p s 舻n ， f i n dx 号罟 s u c ht h a t i i a x b i i = m i n ， w h e r e $ = x i x p = p x ，x s o r 似n ) w ec a l lp r o b l e mia n dp r o b l e mi if o rt w o - s i d e do r t h o g o n a lp r o c r u s t e sp r o b l e m s ， p r o b l e mi i ia n dp r o b l e mi vf o rp e x c h a n g ep r o c r u s t e sp r o b l e m s t h i sp a p e rm a i n l yr e s e a r c hw o r k sa r ea sf o l l o w s ： 1 a b o u tt w o - s i d e do r t h o g o n a lp r o c r u s t e sp r o b l e m s ，o nt h ef e a s i b l es e t ，a st h e p r o j e c t e dg r a d i e n tm a t r i c e sc a nn a t u r a l l yb ef o r m u l a t e db ym a t r i c e s ，w ep r e s e n t saw a y t ot h ep r o j e c t e dh e s s i a n u s i n gt h i sc a l c u l a t i o n ，w eg e tr e s p e c t i v e l yt h ec o m p l e t ec h a r - a c t e r i z a t i o no ft h ef i r s to r d e ra n dt h es e c o n do r d e ro p t i m a l i t yc o n d i t i o nf o rt w o - s i d e d o r t h o g o n a lp r o c r u s t e sp r o b l e m i nv i e wo ft h ep r o j e c t e dg r a d i e n tf o rf o r m u l a t i o n ， i i i 硕士学位论文 i tc a ns e r v ea sag l o b a l l yc o n v e r g e n tn u m e r i c a lm e t h o d t h ep r o p o s e da p p r o a c hi s i l l u s t r a t e db yn u m e r i c a le x a m p l e s 2 a b o u tp e x c h a n g ep r o c r u s t e sp r o b l e m s ，g e n e r a ls o l u t i o no fp e x c h a n g eo r t h o g - o n a lp r o c r u s t e sp r o b l e ma n dp e x c h a n g es y m m e t r i c a lo r t h o g o n a lp r o c r u s t e sp r o b l e m c a nn a t u r a l l yb es o l v e db yt h es i n g u l a rv a l u ed e c o m p o s i t i o no fm a t r i xa n dt h em a t r i xo f t h en a t u r eo ft r a c e w h i l es e to fs o l u t i o ni sn o te m p t y ，w ea l s oo b t a i n e dt h en e a r n e s s f i n a l l y , w ei l l u s t r a t e dt h em a i nt h e o r i e sa n da l g o r i t h mw i t hn u m e r i c a le x a m p l e s k e yw o r d s ：o r t h o g o n a l ；p r o j e c t i o ng r a d i e n tm e t h o d ；p - e x c h a n g e ； p r o c r u s t e sp r o b l e m ；t h es i n g u l a rv a l u ed e c o m p o s i t i o n i v 目录 学位论文原创性声明和学位论文版权使用授权书i 摘要i i a b s t r a c t i i i 第1 章绪论1 1 1 课题研究的意义与发展概况1 1 2 本文研究的问题及主要工作3 1 3 本文所用的记号3 第2 章矩阵方程x 丁a x = b 的正交p r o c r u s t e s 问题5 2 1 引言5 2 2x t a x = b 的正交均衡p r o c r u s t e s 问题6 2 3x t a x = b 的正交非均衡p r o c r u s t e s 问题1 4 第3 章矩阵方程a x = b 的p 一交换p r o c r u s t e s 问题2 3 3 1 引言2 3 3 2a x = b 的p 一交换正交p r o c r u s t e s 问题2 3 3 3a x = b 的p 一交换对称正交p r o c r u s t e s 问题3 0 结论3 7 参考文献3 9 附录( 攻读学位期问所发表的学术论文目录) 4 2 致谢4 3 v 硕士学位论义 第1 章绪论 1 1课题研究的意义与发展概况 约束矩阵方程问题是矩阵论的重要数学分支，在数学本身及其自然科学中有 着广泛的应用约束矩阵方程问题就是在满足一定约束条件下的矩阵集合中求矩 阵方程的解问题，不同的约束条件，不同类型的矩阵方程，都有不同的约束矩阵方 程问题例如：已知矩阵a ，b ，求满足某种约束条件的x 使得i l x t a x s l i = m i n ， 这就是最佳逼近问题，也可以说是最优化问题；约束矩阵方程问题广泛出现在结构 动力学、固体力学、物理、地质分了光谱学、参数识别、自动控制、非线性规划与 动态分析、有限元、线性最优控制、图的分块问题及教育实验问题等领域都有重要 的应用例如：在结构动力学中，对系统中质量矩阵和刚度矩阵的校正导致谱约束 下矩阵方程最佳逼近解问题在电学、光学或自动化控制的线性系统进行测试或复 原时，由于原有资料不全或者要求对已有资料进行检核等原因，也导致了谱约束下 的矩阵最佳逼近解问题此外，在有限元模型的修正、线性最优控制、线性模型中方 差及协方差的估计、电力系统的慢负荷分析和断电路研究等问题中，也导致了类似 地问题正是在这些领域中提出的许多不同类型的问题刺激了约束矩阵方程问题 理论的快速发展，使得约束矩阵方程问题成为当今计算数学领域中最热门，最活跃 的研究课题之一 一般来说，约束矩阵方程问题主要涉及两个方面：一个是理论上的可解性( 即 从理论上寻求问题的有解条件，包括充分条件和必要条件) ；另一个则是问题求解 的实际算法( 即从算法上实现问题的解) ，其中问题的求解算法研究又可分为两类， 一是直接解法，即利用特殊矩阵的结构分析以及矩阵分解等方法来给出问题解的 直接解法：另一类则是迭代算法，即根据所要求解的约束矩阵方程的类型建立迭代 格式，让迭代格式收敛到问题的解 到目前为止，国内外专家、学者的不断探讨，约束矩阵方程问题的研究己取 得了一系列丰硕的成果所研究的矩阵方程问题涉及的约束集合有对称矩阵、反 对称矩阵、中心对称矩阵、自反矩阵、双对称矩阵、对称正交对称矩阵、正交 矩阵、对称正交矩阵等( 见文献 1 ，2 ) ，都有了比较成熟的结论所用的方法包括奇 异值 j r ) f 辫- ( s v d ) 1 3 4 】、c h o l e s l y 分解【3 4 l 、广义奇异值分解( g s v d ) 1 5 ，6 l 、标准奇异值分 解( c c d ) 1 7 】、商奇异值分解( q s v d ) 8 l 、s c h u r 分解等当然当一个约束矩阵方程不相 容，也就是此矩阵方程在规定的约束矩阵集合中无解时，就要考虑求约束矩阵方程 的最小二乘解约束矩阵方程的最t j 、- - 乘问题也叫p r o c r u s t e s 问题 。 事实上，p r o c r u s t e s 问题就是求一个矩阵q ，使得a q 尽可能的接近b ，其中矩 一1 一 一类正交p r o c r u s t e s 问题和一类p 交换约束问题 阵a 和b 是给定的，即是l i a q b 怯= m i n s c h s n e m a n n 9 l 利用偏微分和拉格朗日 乘积研究了该矩阵方程a q = b 的正交p r o c r u s t e s 问题，给出了解的表达式，并用 数值例子验证了结论；2 0 0 6 年张振跃在文献 1 0 中提出了正交非平衡p r o c r u s t e s 问 题( s c h 5 n e m a n n 研究是n n 正交矩阵，也就是均衡问题，非均衡就是n m ) 的持 续投影算法，并用数值例子验证了此算法优越于其他方法；杜克勤在其硕士论文 中给出了该矩阵方程的正交均衡p r o c r u s t e s 问题的解的结构与性质；分析了正交非 均衡p r o c r u s t e s 问题的解的性质以及满足的条件；m o o d yt c h u 1 2 , 1 3 】分别讨论了 a q = b 和a q c = b 的均衡和非均衡p r o c r u s t e s 问题的最优条件，以及全局收敛 性数值方法由此我们考虑双侧p r o c r u s t e s 问题就是求一个矩阵x ，使得x r a x 尽 可能的接近b ，其中矩阵a 和b 是给定的，即是求解下列问题： ( x ) = m ，i ，ni i x la x b i i f( 1 1 ) 其中l i 怙为f r o b e n i u s 范数若矩阵x 满足于正交约束条件，那么问题( 1 1 ) 就成 了正交约束下的p r o c r u s t e s 问题，即为本文第二章研究的内容当m = n 时，我们 称( 1 1 ) 为均衡p r o c r u s t e s 问题；当m 儿时，我们称( 1 1 ) 为非均衡p r o c r u s t e s 问题 1 9 5 1 年，s j e r h a m m a r 1 4 l 利用广义逆得到了矩阵a x = b 有一般解的充要条 件和通解表达式自此以后，国内外很多学者：张磊【1 5 , 1 6 】、张磊和唐隆基【1 7 1 、h e n k d o n i s 、戴华【1 9 ，2 0 l 、廖安平、谢冬秀【2 2 - 2 4 、a l l w r i g h t 2 5 、w o o d g a t e 2 6 】、孙继广【2 7 】、 胡锡炎和张磊f 2 8 ，2 9 j 、胡锡炎、张磊和谢冬秀f 3 0 一3 3 j 、张忠志f 3 4 】以及他和胡锡炎和张 磊【3 5 ，3 6 】等都在都在相应的文献中对矩阵方程a x = b 进行了大量的研究，做了很多 工作，解决了关于求此方程的一些约束解和最小二乘解的问题；此外，在文 3 7 】和 3 8 】 中张磊和谢冬秀利用奇异值分解和迹的性质得到了正交矩阵约束下此方程的解存 在的充要条件和通解的表达式，以及该方程不相容时最小二乘解的表达式和算法； 2 0 0 6 年孟纯军在文f 2 1 中利用k 阶对称主子阵的n 阶正交矩阵的c s 分解，得到了 矩阵方程a x = b 有对称正交解的充要条件和通解的一般形式本文第三章在 此正交约束和对称正交约束基础上进一步研究矩阵方程a y = b 的p 一交换约束 p r o c r u s t e s 问题，对于任意给定的对称阵p ，若x 和p 可交换的，即是x p = p x ， 我们就称x 满足p 一交换约束 1 2本文研究的问题及主要工作 我们用煳、s 形加、d 舻跏、s d 印n 来分别表示m n 阶实矩阵、n n 阶对 称矩阵、m x t t 阶正交矩阵、礼礼阶对称正交矩阵；对于给定的对称矩阵p s 形跏， 令$ = x i x p = p x ，x o 册n ) 和$ = x i x p = p x ，x s d 酽n ) 本 硕士论文主要考虑以下两类矩阵方程的p r o c r u s t e s 问题： 一2 一 硕士学他论义 问题i 给定a r t m ，b 舻，求x 且满足x 丁x = k 使得 i i x 丁a x b i i = m i n 问题i i 给定a r t m 仇，b 舒加，求x 胛n 且满足x t x = 厶使得 l i x r a x b i i = m i n 问题i i i 给定矩阵a ，b 驴她，求x $ ，使得 l i a x b i | = m i n 问题i v 给定矩阵a ，b 黼，求x $ ，使得 i i a x b i i = m i n 以上i i i | 为f r o b e n i u s 范数 本文就以上问题，主要进行了以下工作： 第2 章主要研究问题i 和问题i i ，即是矩阵x 丁a x = b 的正交p r o c r u s t e s 问题， 通过可行集上的一些性质推导出了梯度函数在切空间上的投影的矩阵表达式，给 出了问题i 和问题i i 的局部最优解的第一阶必要条件，又通过对h e s s i a n 投影在切向 量上的作用给出了问题i 和问题i i 的局部最优解的第二阶充分条件，给出了一种计 算最优解的数值方法 第3 章研究了问题i i i 并f l 问题i v ，即使矩阵方程a x = b 在约束条件s 譬= x i x p = p x ，x o 毋姗) 和s 譬= x i x p = p x ，x s o r 似n ) 下p r o c r u s t e s 问题，利用 矩阵的奇异值分解和迹的性质推出了解一般表达式及最佳逼近解，并分别用数值 例子验证了结论的可行性 1 3本文所用的记号 r m n s 彤竹 a s 留n 0 x m 0 r m n s d 形竹 厶 ”怯 t r ( a ) 全体佗n 实矩阵的集合 全体佗x 礼阶实对称矩阵的集合 全体n n 阶反对称矩阵的集合 全体mxm 阶正交矩阵的集合 全体n n 阶列正交矩阵的集合 全体n 礼阶对称正交矩阵的集合 n 阶单位矩阵 矩阵的f r o b e n i u s 范数 矩阵a 的迹 一3 一 一类正交p r o c r u s t e s 问题和一类p - 交换约束问题 a ?矩阵a 的转置 d x ( t )函数x ( t ) 的微分 x 讹)函数x ( 亡) 的导数 v x ( t )函数x ( t ) 的梯度 m t矩阵m 的m o o r e - p e n r o s e 广义逆 a 上矩阵a 的正交补 还有一些特殊的记号将在具体用到时再做具体的说明 一4 一 第2 章矩阵 2 1引言 实数域上双侧矩阵方程 若只求它在实矩阵类r m 煳中的解x 和y ，则称此问题为非约束条件下双侧矩阵 方程问题若限定解x 和y 在舻黼的一个子类s 中，则称此问题为约束矩阵方 程问题比如限定s 为对称矩阵方程集合、正交矩阵集合等当这些问题的相容性 条件不满足时，我们就考虑求约束矩阵方程的最小二乘解问题，该问题也称为约束 p r o c r u s t e s 问题 约束p r o c r u s t e s 问题在统计学和数量经济学上有重要意义，由于正交矩阵的 良好的稳定性质及计算工作量小，使得对正交约束的p r o c r u s t e s 问题得到广泛研 究1 9 6 6 年s c h 6 n e m a n n 在文 3 9 利用偏微分得到了正交矩阵x 和y 使得i x a y t b l i = m i n ，并用相应地数值例子验证了结论的有效性；随后魏木纠4 0 】又利用矩阵 的奇异值分解和n e u m a n n 不等式得到了该矩阵方程p r o c r u s t e s 问题的正交解x 和 y 的一般表达式和最佳逼近解m o o d y t c h u 在文 1 2 ，1 3 中利用最速下降法得到了 矩阵方程a x = b 和a x b = c 在正交约束下的p r o c r u s t e s 问题的第一阶和第二 阶最优条件，还推导出了得到最优解的数值方法本章我们也将利用梯度投影法的 思想来解决矩阵方程 x ta x ：b 在正交矩阵约束下的p r o c r u s t e s 问题其中a r m m ，b p 肌是预先给定矩阵， x 0 舻加为待求矩阵当m = n 时，我们称该问题为双侧正交均衡p r o c r u s t e s 问 题( 简记为t o p p ) ；m 几时，我们称该问题为双侧正交非均衡p r o c r u s t e s 问题( 简 记为非均衡t o p p ) 下面我们先给出本章要用的一个引理： 引理2 1 1 4 1 1 若矩阵的标量函数f ( x ) 在m n 矩阵点x 可微分，则下列关系 成立： d f ( x ) = a 如营v 肛) = 掣= 以 d r ( x ) = 打( a d ) 兮v ，( x ) = 百o f ( f x ) = a t 式中，a 有可能与变元矩阵x 有关 一5 一 一类正交p r o c r u s t e s 问题和一类p 交换约束问题 2 2矩阵方程x t a x = b 的双侧正交均衡p r o c r u s t e s 问 题 2 2 1 问题引入 最近，矩阵计算领域把某些微分方程的动力系统和一些离散的数值算法联系 了起来关于这种联系我们可以参考文献【4 2 】；更详细的信息可参阅文献【4 3 】首先我 们把利用微分方程得到一个问题的解的过程叫做持续法，这种方法更多的是实现 基础问题的内在信息本节我们要讨论的就是利用持续实现方法来解决t o p p ，即 未知量x 是方正交阵约束 问题2 2 1 给定a 舻m ，b r m m ，求x o r m 仇使得 i i x r a x b i l = m i n ( 2 2 1 ) 本节将采用c h u 并i d r i e s s e l 在【4 4 】的梯度的投影能够显式表示的思想，当然该思 想也可适用于更一般的情况，当t 是长方形的正交矩阵( 即列正交) 时，这个问题我 们将在下节给予详细的讨论本节我们主要讨论的是x 是方正交矩阵时的一些结 论，得到了该问题存在局部解的最优条件 2 2 2 投影梯度法 投影梯度法是梯度动态系统中经典最优化法的一种特殊形式，其具体形式如 下： d t f ( t ) ：一v f ( 丁( 吼 ( 2 2 2 ) 一= 一v r1 i el i iz z zl 出 一、_ 。川、_ 1 其中目标函数f 满足约束条件以及f 的梯度v f 在可行集上能够明确表示式( 2 2 2 ) 表示的是标准梯度法中以负梯度v f 方向为函数f 的最快下降的搜索方向，简单 地说即是运动的速度指向f 的最速下降方向注意到( 2 2 2 ) 是独立存在的，即是等 式的右端明显不依靠变量t 如果采用负方向，那么( 2 2 2 ) 中的t ( t ) 是下降的，凶 为函数f 的导数总是是负方向： 掣却即( t ) ) ，掣) - - | l v 即) 1 1 2 ( 2 2 3 ) 相应地，如果采用正方向，t ( t ) 的方向就是上升的，即能够到达f 的极大点从( 2 2 3 ) 我 们可以看出若任意t ( t ) 的方向和v f 的夹角是锐角，搜索将沿着下降方向 注意到标准梯度法( 2 2 2 ) 中对t ( t ) 是没有任何限制的但若我们将t ( t ) 严格满 足于一个固定可行集，则梯度v f 的方向是不能确定的，未必就是下降方向原因 是梯度本身可能使t ( t ) 落在可行集外边，由于我们仅仅定义了函数f ，故它并不适 一6 一 硕士学位论文 用于所有的约束投影梯度法的核心思想就是保持t ( t ) 在可行集中的方向是我们 需要的、可控制的j 艮自然地我们选择梯度v f 在可行集上的切空间的投影夕( t ) 当 梯度的投影已知时，我们对( 2 2 2 ) 进行修改，得到投影梯度表达式的微分方程： d t 矿( t ) ：一夕( t ( 吼 出 叭一r 川。 确保了投影夕( 丁( 亡) ) 和梯度v f 的夹角是锐角，此外，由于t ( t ) 的运动方向是 一9 ( t ( t ) ) ，就保证了它一定在可行集上运动，也即是在可行集的切空间上如上面 的分析，一夕( t ( t ) ) 就是函数f 在可行集上的最速下降的方向当可行集合是一个子 空间时，约束法和非约束法是一致的，因为梯度的投影就是它本身 为了在本文应用投影梯度法，我们假设x 是变量t 的函数，并且对于所有的 t 0 ，矩阵x ( t ) 是正交的，即x ( t ) t x ( t ) = k 成立为了方便起见，下文简单记为 x 首先我们引入一个拓扑集合 o ( m ) ：= x r m m i x 丁x = k ) 表示所有的m m 正交矩阵的集合 目标函数f 在x ( t ) 的梯度v f 指向f 的最速下降方向，但是，在运动过程 中v f 的变量很可能会溢出可行集p ( m ) 然而梯度v f 在切空间o ( m ) 上的投影 g ( x ) 能够保证x 在运动过程中的方向就是下降方向又不会溢出可行集o ( m ) 梯度投影思想的关键就是切空间o ( m ) 上的投影能够显式表达易知o ( m ) 是 舻m 中m ( m 一1 ) 2 维的光滑流形，x 的切方向日( 即路径) 就是x ( t ) o ( m ) 的速度方向为了使切空间o ( m ) 上的投影能够显式表达，我们得到( 对x 丁x = k 微分) 任意正交矩阵x 在其切空间上的一般形式 g x o ( m ) = 日r m 仇1 日t x + x t h = o m ) = 日r m m i i x t h a s r m m ) 其中o m 是一个mxm 阶零矩阵事实上，x o ( m ) 上的任意切向量的必要形式 是x r h = k ，或h = x k 其中k a s r m m ，即有 及。( m ) = 兰，? 旧= x kk k a s 舻) ( 2 2 4 ) = x 跪f m l 上 为了方便，记瓣( m ) ：= _ 胛m 中的所有对称矩阵) ，引入两个矩阵x 和y 的 f r o b e n i o u s 内积： 一。 + 一 ( x ，y ) ：= t r ( x y t ) ( 2 2 5 ) 一7 一 一类正交p r o c r u s t e s 问题和一类p 交换约束问题 已知任意的对称矩阵s s 胛m ，反对称矩阵k a s r m m ，则有t r ( s k ) = 0 ，于 是从( 2 2 4 ) 可知，任意x o ( m ) 在正交矩阵集合o ( m ) 上的切空间t x o ( m ) 和 正规空间v x o ( m ) 分别是： t x o ( m ) = x o ( m ) 上， a x o ( m 1 = x o ( o 因p ( m ) 上是对应于f r o b e n i o u s 内积的p ( m ) 的正交补，故包含胪m 中所有的反 对称矩阵 已知矩阵a m ，b r m m ，考虑下面的函数： f ( q ) = 去( q 丁a q b ，q 丁a q b ) ( 2 2 6 ) q 是任意的舻m 显然，双侧正交均衡问题等价于在可行集0 ( m ) 上求f ( q ) 的 极小点问题，这是标准的约束优化问题 首先利用矩阵微分和标量函数的偏导( 即梯度) 的关系( 引理2 1 ) ，得到目标函数 f ( q ) 的梯度v f ( q ) 是： v f ( q ) = a 丁q ( q t a q b ) + a q ( q 丁a 丁q b t ) ( 2 2 7 ) 假如任一点x p ( 仇) 的梯度v f ( x ) 在切空间7 - x o 上的投影能够显式表达那 么微分方程是： d 万x ：一9 ( x ) ( 2 2 8 ) 班 j 、一厂 、 7 这样就于是定义了可行集流形o ( m )上的x ( t ) 相对于其他方向来说，函数值 f ( x ( ) ) 指向x ( t ) 的方向的下降速度是最快的事实上，我们得到 掣= ( v 跗) _ 舭) ) _ 一i i g ( x ( 啪1 1 2 由于夕( x ( t ) ) 是v f ( x ( t ) ) 在7 - x ( t ) o 上f i 勺i f _ 交投影从而知道v f ( x ( t ) ) 的值是严 格地从9 ( x ( 亡) ) 下降直到零，即得到了目标函数f 的局部极小值这种下降的趋势 是普遍存在的，与夕( x ( t ) ) 的初始值无关，于是我们可以得到9 ( x ( 芒) ) 是全局收敛 的 我们来求梯度的投影9 ( x ) ，任意的m 阶实矩阵集合都可分解为 r m m = t x o ( m ) en x o ( m ) = x 盼( m ) 上ox r ( m ) 故对任意矩阵y 舻m 有惟一的正交分解： y = x 1 ( x t q q 丁x ) 】+ x 三( x r q + q t x ) 】 一8 一 硕士学位论文 等式右端是 i x o ( m ) 和a r x o ( m ) 中元素的直和，因此我们得到v f ( x ) 在切空间 及o ( m ) 上的投影有以下形式： g ( x ) =吾 x 丁 a r x ( x 7 1 a x b ) + a x ( x 丁a r x b 丁) 】 一【( x t a 丁x b 丁) t c r a + ( x t a x b ) x 丁a r i x ( 2 2 9 ) ：x ( b t x t a x + b x t a t x x t a r x b x t a x b r ) 由式( 2 2 8 ) 我们得到微分方程： 等= 享( 砌t 姗+ x t 以b t b x t a t j e 7 m xa x ) ( 2 2 1 0 ) 从o ( m ) 中任一点开始，令x ( o ) = i ，我们由( 2 2 1 0 ) 中定义的x ( t ) 就可以得 到任意的初值问题的数值解x ( t ) 最终将收敛到t o p p 的局部最优解，于是我们 得到了t o p p 局部最优解的数值方法计算机实现的最佳选择是m a t l a bo d e s u i t e ( s h a m p i n ea n dr e i c h e l t 4 5 】) 中常微分初值问题的数值解函数：o d e l 5 和o d e l 3 当然，其 他的o d e 方法也可替代 最后，很容易知道如果x ( t ) 满足( 2 2 1 0 ) ，那么有t 0 ，x ( ) 丁x ( t ) = k 注意 到等式( 2 2 1 0 ) ，对反对称矩阵有性质面d x = x k ，由此计算得到： t d x t x = ( 警) t x + x t 警 = k t x t x + x t x k = x t xk k x tx 和初值条件x ( o ) 丁x ( o ) = k 1 9 7 0 壬v b e l l m a n 4 6 】解决了这个初值微分方程问题，得 到解x ( 亡) t x ( t ) = k 反之，我们有： 譬= ( 警) x t + x 警 ( 2 2 1 1 ) ：x k x t + x k t x ：0 、7 由o d e 理论【4 7 l 基本存在和惟一性定理，可以m ( 2 2 1 1 ) 推导出，对所有的t 0 有 x ( 亡) t x ( t ) = x ( o ) 丁x ( o ) = 厶 2 2 3 最优化条件 由梯度投影( 2 2 9 ) 的显式公式，我们就可以得到t o p p 的第一阶优化条件： 定理2 2 1 x o ( m ) 是t o p p 的一个稳定点的必要条件是矩阵b 丁x t a x + b x t a t x 是对称的 证明显然x 是的稳定点则有g ( x ) = 0 ，由( 2 2 9 ) 就可以得到 _ ，为了进一步确定稳定点，我们推导出第二阶优化条件我们借鉴c h u 和 d r i e s s e l 在文【4 8 】中提出的计算h e s s i a n 投影的方法来解决这个问题，这种方法的 9 一 一类正交p r o c r u s t e s 问题和一类p 交换约束问题 应用的前提是投影g ( x ) 能够显式表达下面我们应用这种方法来计算函数f 的 h e s s i a n 投影 定理2 2 2 ( 2 2 5 ) 中的函数f 在稳定点x c 0 ( m ) 处切向量x k ( k a s 舻m ) 上的h e s s i a n 投影作用是： ( g l ( x ) x k ，x k ) = 一 b k x 丁a 丁x + b t k x t a x ，k ) 一( b x t a 丁x + b r x t a x ，k 2 ) 证明从等式( 2 2 9 ) 中观察到g 在x 点关于一般的日的f r 6 c h e t 导数是： g t ( x ) 日： =i h ( b 丁x 丁a x + b x 丁a 丁x x 丁a 丁x b x r a x b t ) + x ( b h t a t x + b x t a t h + b 丁h t a x + b t x t a h 一( b x 丁a 丁日) t 一( b h t a 丁x ) t 一( b t h 丁a x ) t 一( b 丁x t a h ) t ) 根据定理2 2 1 ，上面等式右边的第一个括号里是0 ，那么在切向量h = x k 上的 h e s s i a n 投影作用计算如下： ( g l ( x ) x k ，x k ) = ( ；( b k 丁x 丁a 丁x + b x t a ? x k + b 丁k t x 丁a x + b t x 丁a x k 一( b x t a 丁x k ) 丁一( b k 丁x 丁a t x ) t 一( b 丁t x 丁a x ) t 一( b 丁x 丁a x k ) 丁，k ) =一( b k x r a 丁x + b 丁k x t a x ，k ) 一( b x t a t x + b t x t a x ，k 2 ) 这个论断是在内积的性质( x z ) = ( x ，z y t ) 和k t = 一k 的事实的基础上得到 的 一 i 下面的论断是优化理论的标准结果 推论2 2 1 x o ( m ) 上的稳定点是t o p p 的局部最优解的第二阶充分( 必 要) 条件是： ( b k t x 丁a 丁x ，k ) + ( b x 丁a t x + b 丁x 丁a x ，k 2 ) + ( b 丁k 丁x t a x ，k ) n 时的p r o c r u s t e s 问题 问题2 3 1 给定a r m m ，b r n 跏，求x 0 r m 黼使得 忧丁a x b i i = m i n ( 2 3 。1 ) 其中厶表示n n 单位矩阵 1 9 9 6 年魏木生【4 1 】给出了该问题( 已知矩阵a 和b ) 满足一定条件下的数值解， 更一般的情况还未涉及，所以对其进一步研究很有必要的我们仍然采用持续实 现法的思想来解决，因这个连续公式解决关于基础问题的解的性质方面有着优势， 一些看似我们不能处理的常规的离散问题，却能通过持续连续过程合理地解决本 节我们通过s t i e f e l 流形上的一些性质得到非均衡t o p p 的第一阶和第二阶最优条 件 2 3 2s t i e f e l 流形 集合毋( m ，n ) 表示所有的m n 列正交的实矩阵，它形成了一个光滑流形，s t i e f e l 在文献【5 0 】研究了该集合的一些性质，故简称为s t i e f e l 流形便于后面的讨论我们 写出它的一些重要的结论 一】4 一 j v r # ( m ，n ) = x 跄( n ) 有必要提起下面关于空间舻肌的下列直和分解 引理2 3 2 空间胛跏能够被写成3 个子空间的直和 黼= x 跪( n ) ox 盼( n ) 上o ( x 丁) ， 其中( x t ) ：= x 胛加i x t x = o ) 因此我们能够定义下面的投影引理 引理2 3 3 令z 舻黼那么 t 丁( z ) ：x 兰竿+ ( j 一x x 丁) z ， 定义了z 在切空间：r x 毋( m ，n ) 上的投影类似地， 。飘( z ) ；x x t z j 2 r z t x 定义了z 在正规空间a f x o ( m ，n ) 上的投影 一15 一类正交p r o c r u s t e s 问题和一类p 交换约束问题 2 3 3 最优化条件 已知a 彤p ，b r m 黼考虑雨数f ：舻黼一兄定义如下 1 f ( x ) ：= 去( x 丁a x b ，x 丁a x b ) ( 2 3 2 ) 厶 显然，非均衡t o p p 等价于求函数f ( x ) 在可行集毋( m ，n ) 上的极小值问题