求解极大相关问题的对偶方法.pdf

《求解极大相关问题的对偶方法.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第45卷第8期2015年8月中国海洋大学学报PERIoDICALOF0CEANUNIVERSITYOFCHINA45(8)：128～132Aug．，2015求解极大相关问题的对偶方法+李美然，刘新国(中国海洋大学数学科学学院，山东青岛266100)摘要：多组变量间的极大相关问题(MCP)有重要统计应用。目前已有的求解MCP的算法都不能保证获得MCP的全局解。本文通过求解MCP的对偶问题，给出了一种改进的Lagrange对偶方法。最后，数值实验结果说明了新方法能提高收敛到全局解的可能性。关键词：极大相关问题；

2、多元特征值问题；Lagrange对偶；强对偶；全局解；收敛性中图法分类号：0212．4文献标志码：A文章编号：1672—5174(2015)08—128一05DOI：10．16441／j．cnki．hdxb．201303230引舌多组变量的极大相关问题(Maximalcorrelationproblem，MCP)是经典的典型相关分析(Canonicalcor—relationanalysis，CCA)[卜2]的自然推广，已被广泛用于聚类分析、数据分析、模式识别、主成份分析以及动力系统的稳定性分析等问题中。多

3、组变量最大相关问题表述为下述最优化问题：给定实对称正定矩阵A∈R．X”和正整数集P一{行。，咒。，⋯，，z。}，并且满足∑兰，n。一，z，矩阵A分块如下：A==A11A21●：A。1A12A22●：A。2A1。A2。A一这里，Ai∈彤t蜘t，求解{max!}亍，缸。㈩St【．．x∈邑。⋯其中邑一{z一(西，⋯，《)T∈R：乃∈船，II乃112—1)。使用Lagrange乘子法可知，z∈己为MCP(1)的解的必要条件为：存在实数A1，．一，A。，使得：Ax—Ax：A—diag(21J。，，⋯，A。I‰)。(2

4、)式(2)称为多元特征值问题(MEP)[3I。若(以，z)满足(2)，则称(A，z)为MEP(2)的一个解。Chu和Watterson[引。证明如果A有"个不同特征值，则MEP(2)恰有I

5、‘二(2n。)个解。对于MEP(2)已有一些有效算法。Horst方法(t／z叫幂法)[4]是较早提出的一种迭代法，Hu[5]及Chu和Watterson[a]论证了Horst方法的收敛性。Sun[61把求解线性代数方程组的SOR方法的基本思想用于改进Horst方法，提出了P_SOR方法，并分析了收敛性。秦晓伟[7]对Hu

6、和Sun<5书]的结果给出了改进。由于MEP(2)仅是MCP(1)的解满足的必要条件，因此，Horst方法和P-SOR无法保证获得MCP(1)的全局最大点。Hanafi和TenBerge[8]证明了下述结果：设(以，z)为MEP(2)的一个解，如果A—A半正定，则z为MCP(1)的全局解。他们还证明了若m一2或者m≥3但A为正矩阵，则前述充分条件也为必要条件；对于一般的A，当优≥3时，前述充分条件不是必要的。最近，Zhang和Liao[9]及Grze96rski[10]独立地提出了求解MCP(1)的交替变量

7、法(AVM)(文献[10]中称之为交替投影法，APM)，数值实验结果表明，AVM比Horst方法及P—SOR方法更有可能获得MCP(1)的全局解。Liu和Wang[11]进一步分析了AVM方法，结果表明：AVM有不收敛情形(尽管很少见)，收敛时未必收敛于MCP(1)的全局解，与Horst方法及P-SOR方法类似之处是：收敛结果依赖于初始点的选择。注意到(1)是一类具约束的非线性最优化问题。AVM方法是常用的坐标下降法[12q3]的自然推广。自然地，可以考虑应用其它的最优化方法求解MCP(1)。本文分析求解(

8、1)的对偶方法。本文以下内容组织如下。在第二节，给出(1)的对偶形式，并使用对偶方法求解(1)。由于m≥3时(1)与其Lagrange对偶问题之间不是强对偶的，因此，给出了一种改进的对偶方法；最后，*基金项目：国家自然科学基金项目(11371333)资助收稿日期：2013—10—12；修订日期：2014—05—10作者简介：李美然(1988一)，女，硕士生。E-mail：limeiran5211314@126．com8期李美然，等：求解极大相关问题的对偶方法关于对偶方法做了大量的数值实验，结果表明，对偶方法

9、能有效地获得MCP的全局解。1对偶方法首先，将给出MCP(1)的Lagrange对偶问题。注意MCP(1)等价于下述最优化问题(见Sun[63)：』max，触(3)【S．t．xE力。。繇一{z一(32T，⋯，矗)T∈R：xjER"J，

10、

11、xjll2≤1)。易知，(3)的Lagrange对偶问题为：min∑A，<’一1(4)Ls．t．A—A≥0。这里，A—diag(2lJl'．一，A。J。)，若令F，一diag(0