求解極大相關問題的對偶方法?

李美然, 劉新國(中國海洋大學數學科學學院，山東 青島 266100)

?

求解極大相關問題的對偶方法?

李美然, 劉新國
(中國海洋大學數學科學學院，山東 青島 266100)

多組變量間的極大相關問題(MCP)有重要統計應用。目前已有的求解MCP的算法都不能保證獲得MCP的全局解。本文通過求解MCP的對偶問題，給出了一種改進的Lagrange對偶方法。最后，數值實驗結果說明了新方法能提高收斂到全局解的可能性。

極大相關問題；多元特征值問題；Lagrange對偶；強對偶；全局解；收斂性

0 引言

多組變量的極大相關問題(Maximal correlation problem,MCP)是經典的典型相關分析(Canonical correlation analysis,CCA)[1-2]的自然推廣，已被廣泛用于聚類分析、數據分析、模式識別、主成份分析以及動力系統的穩定性分析等問題中。

這里，Aii∈Rni×ni，求解

(1)

其中

使用Lagrange乘子法可知，x∈Σm為MCP(1)的解的必要條件為：存在實數λ1,…,λm，使得：

Ax=Λx；

Λ=diag(λ1In1,…,λmInm)。

(2)

式(2)稱為多元特征值問題(MEP)[3]。若(Λ,x)滿足(2)，則稱(Λ,x)為MEP(2)的一個解。Chu和Watterson[3]。

注意到(1)是一類具約束的非線性最優化問題。AVM方法是常用的坐標下降法[12-13]的自然推廣。自然地,可以考慮應用其它的最優化方法求解MCP(1)。本文分析求解(1)的對偶方法。本文以下內容組織如下。在第二節，給出(1)的對偶形式,并使用對偶方法求解(1)。由于m≥3時(1)與其Lagrange對偶問題之間不是強對偶的，因此，給出了一種改進的對偶方法；最后，關于對偶方法做了大量的數值實驗，結果表明，對偶方法能有效地獲得MCP的全局解。

1 對偶方法

首先，將給出MCP(1)的Lagrange對偶問題。注意MCP(1)等價于下述最優化問題(見Sun[6])：

(3)

易知，(3)的Lagrange對偶問題為：

(4)

這里，Λ=diag(λ1I1,…,λmIm)，若令Fi=diag(0,…,0,Ini,0,…,0)∈Rn×n，則(4)可以改寫為：

(5)

顯然，(5)是標準的半定規劃問題，可以使用內點法求解，且已有較好的軟件包，例如，Sedumi[14]，SDSP[15]。

(Λ*-A)x=0。

(6)

如果(6)存在解x*∈Σm，那么，由Hanafi和Ten Berge[8]的結果可知，x*就是MCP(1)的一個全局解，此時(5)與(3)是強對偶的，也就是MCP(1)與(5)強對偶。

命題1Λ*-A是奇異的。

算法1 (Modified Dual Method，MDM)

第二步 計算Λ*-A的最小特征值對應的特征向量

第三步 如果‖xj‖2≥1-ε0(這里ε0為某一給定的小正數)，j=1,2…,m，則x*為MCP的全局解，停機，否則執行下一步；

對于上述算法有以下幾點說明：

其中vi是Aii對應最大特征值的單位特征向量。

其次，正如引言所指出的，如果m=2或者m≥3且A為正矩陣，那么，Hanafi和Ten Berge[8,Result 5]表明：(3)與(5)是強對偶的，此時算法1中的Step(4)理論上是不必要的，即x*是MCP(1)的全局解。

第三，對于m≥3且A為一般的正定矩陣時，算法1的本質是：若(3)與(5)是強對偶的，則Step(3)結束后即可獲得MCP(1)的全局解；若(3)與(5)不是強對偶的，即(6)沒有解x*∈Σm，此時對偶方法為對稱G-S或AVM迭代法提供一種初始迭代策略。

(7)

令

(8)

(9)

已知，對對稱G-S及AVM方法而言目前已有的理論無法保證獲得MCP(1)的全局最大點，已有的數值實驗表明[16-17]，恰當地選擇初始迭代點不但可以提高Horst方法、G-S方法及P-SOR方法的收斂速度，而且可以提高獲取(1)的最優解的可能性。

2 數值實驗

本文的數值實驗是在Matlab7.6.0環境下完的，而且所用的矩陣A按如下2種方式形成：

首先，對上述2種方式形成的矩陣A做了充分的實驗，分別統計了MCP與其Lagrange對偶問題強對偶的概率。結果表明：矩陣A=DBTBD對應的MCP與其Lagrange對偶問題都是強對偶的,并且強對偶性與m和整數集p的取值無關(統計應用中常出現這類矩陣)；而對于方式二形成的矩陣并非都是強對偶的(見表1)，只有當m=2時全是強對偶的，而且隨著m的增大，強對偶的概率減小；并且隨著m和n的增大，平均花費時間增加，即，算法收斂速度變慢。

表1 強對偶的概率

由于MCP的Lagrange對偶問題是半定規劃，并且已有較好的求解軟件，因此，對于方式一中形成的矩陣A，可以通過求解其對偶問題來獲得MCP的全局解；而對于方式二中對應的非強對偶的情形，用改進的對偶方法(MDM)進行求解(見表2)，并統計此時獲得全局解的可能性。

表2 獲得全局解的可能性

表2中的結果表明，改進的對偶方法對于獲得MCP的全局解有改進，但對于困難問題仍不保證得全局解。

其次，為了更好的了解對偶方法對獲得全局解的改進，給出幾個已知全局解的例子進行數值實驗。

例1 取自[8]

m=3,p={2,2,2},ρ(x*)=378.9624。

例2 取自Chu和Watterson[3]

m=2,p={2,3},ρ(x*)=14.7302。

例3 取自Xu[17]

m=3,p={3,3,4},ρ(x*)=103.6819。

例4 取自Zhang,Liao and Sun[18]

m=3,p={1,1,1},ρ(x*)=14.000。

對上述給定的例子，利用Sedumi軟件求解其MCP的對偶問題，比較MCP與其對偶問題的最優值(Table3)。

表3 最優值的比較

根據上述結果，可以清楚地看到，例2和3對應的MCP與其對偶問題是強對偶的，那么我們可以通過求解其對偶問題得到MCP的全局最優解；而例1和4的MCP與其對偶問題是弱對偶的，并且此時利用修改的對偶方法(MDM)可獲得MCP的全局最優解和全局最優值。

表4 對偶差

若MCP與其對偶問題是強對偶的，則此時μ為零，即對偶問題的解是MCP的解；而當非強對偶時(表4)，μ的值不大，那么在一定的精度下，可以把對偶問題的解作為MCP的近似解；而此時若用改進的對偶方法求解MCP，則可以有效地獲得MCP的全局解。

[1] Hotelling H. The most predictable criterion [J]. J Educ Pyschol, 1935, 26: 139-142.

[2] Hotelling H. Relations between two sets of variates [J]. Biometrika,1936, 28: 321-377.

[3] Chu M T, Watterson J L. On a multivariate eigenvalue problem, Part I: Algebraic theory and a power method [J]. SIAM J Sci Comput, 1993(14): 1089-1106.

[4] Horst P. Relations among m sets of measures [J]. Psychometrika,1961, 26: 129-149.

[5] Hu D K. The convergence property of a algorithm about generalized eigenvalue and eigenvector of positive definite matrix [C]. Beijing: China-Japan Symposium on Statistics, 1984.

[6] 孫繼廣. 多參數特征值問題的一種算法[J]. 計算數學, 1986, 8(2): 137-149.

[7] 秦曉偉. 關于解極大相關問題P-SOR算法的收斂性 [J]. 計算數學， 2011, 33: 345-356.

[8] Hanafi M, Ten Berge J M F. Global optimality of the successive Maxbet algorithm [J]. Psychometrika, 2003(68): 97-103.

[9] Zhang L H, Liao L Z. An alternating variable method for the maximal correlation problem [J]. J Global Optim, DOI: 10. 1007/s 10898-011-9758-2.

[10] Grzegórski S M. On the convergence of the method of alternating projections for multivariate symmetric eigenvalue problem [C]. Chania: Conference in Numerical Analysis, 2010: 15-18.

[11] Liu X G, Wang K. A multigrid method for the maximal correlation problem,Numerical Algebra [J]. Control and Optimization, 2012, 2(4): 785-796.

[12] Nocedal J, Wright S J. Numerical Optimization [M]. New York: Springer, 1999.

[13] Boyd S, Vandenberghe L. Convex Optimization [M]. Cambridge: Cambridge University Press, 2004.

[14] JOS F. STURM,(using sedumi 1.02)A Matlab toolbox for optimization over symmetric cones [EB/OL]. Available online: http: //fewcal.kub. nl/～sturm.

[15] Steven J. Benson, DSDP5 user guide-Software for semidefinite programming [EB/OL]. http: //www.mcs. anl.gov/～benson

[16] Zhang L H, Chu M T. Computing absolute maximum correlation [J]. IMA J Numer Anal, 2011, DOI: 10.1093/imanum/drq029.

[17] 徐蓮花. 關于多元特征值問題的數值方法 [D]. 青島： 中國海洋大學數學科學學院, 2008.

[18] Zhang L H, Liao L Z, Sun L M. Towards the global solution of the maximal correlation problem [J]. J Global Optim, 2011(49): 91-107.

AMS Subject Classification: 62H20

責任編輯 陳呈超

A Dual Method for the Maximal Correlation Problem

LI Mei-Ran， LIU Xin-Guo
(School of Mathematical Sciences, Ocean University of China, Qingdao 266100, China)

The maximal correlation problem aiming at assessing the relationship between sets of variables plays a very important role in many areas of statistical application. Currently, several algorithms for the global maximizer of the MCP have been proposed, but they can not guarantee convergence to a global solution. In the present paper,by solving the dual problem of the MCP, a modified Lagrange dual method is proposed. Numerical experiments demonstrate the new algorithm can increase the probability of finding a global maximizer.

maximal correlation problem； multivariate eigenvalue problem； lagrange dual； strong dual； global maximizer； convergence

國家自然科學基金項目(11371333)資助

2013-10-12；

2014-05-10

李美然(1988-)，女，碩士生。E-mail：limeiran5211314@126.com

O212.4

A

1672-5174(2015)08-128-05

10.16441/j.cnki.hdxb.20130323