李美然, 劉新國(guó)(中國(guó)海洋大學(xué)數(shù)學(xué)科學(xué)學(xué)院,山東 青島 266100)
?
求解極大相關(guān)問(wèn)題的對(duì)偶方法?
李美然, 劉新國(guó)
(中國(guó)海洋大學(xué)數(shù)學(xué)科學(xué)學(xué)院,山東 青島 266100)
多組變量間的極大相關(guān)問(wèn)題(MCP)有重要統(tǒng)計(jì)應(yīng)用。目前已有的求解MCP的算法都不能保證獲得MCP的全局解。本文通過(guò)求解MCP的對(duì)偶問(wèn)題,給出了一種改進(jìn)的Lagrange對(duì)偶方法。最后,數(shù)值實(shí)驗(yàn)結(jié)果說(shuō)明了新方法能提高收斂到全局解的可能性。
極大相關(guān)問(wèn)題;多元特征值問(wèn)題;Lagrange對(duì)偶;強(qiáng)對(duì)偶;全局解;收斂性
多組變量的極大相關(guān)問(wèn)題(Maximal correlation problem,MCP)是經(jīng)典的典型相關(guān)分析(Canonical correlation analysis,CCA)[1-2]的自然推廣,已被廣泛用于聚類分析、數(shù)據(jù)分析、模式識(shí)別、主成份分析以及動(dòng)力系統(tǒng)的穩(wěn)定性分析等問(wèn)題中。
這里,Aii∈Rni×ni,求解
(1)
其中
使用Lagrange乘子法可知,x∈Σm為MCP(1)的解的必要條件為:存在實(shí)數(shù)λ1,…,λm,使得:
Ax=Λx;
Λ=diag(λ1In1,…,λmInm)。
(2)
式(2)稱為多元特征值問(wèn)題(MEP)[3]。若(Λ,x)滿足(2),則稱(Λ,x)為MEP(2)的一個(gè)解。Chu和Watterson[3]。
注意到(1)是一類具約束的非線性最優(yōu)化問(wèn)題。AVM方法是常用的坐標(biāo)下降法[12-13]的自然推廣。自然地,可以考慮應(yīng)用其它的最優(yōu)化方法求解MCP(1)。本文分析求解(1)的對(duì)偶方法。本文以下內(nèi)容組織如下。在第二節(jié),給出(1)的對(duì)偶形式,并使用對(duì)偶方法求解(1)。由于m≥3時(shí)(1)與其Lagrange對(duì)偶問(wèn)題之間不是強(qiáng)對(duì)偶的,因此,給出了一種改進(jìn)的對(duì)偶方法;最后,關(guān)于對(duì)偶方法做了大量的數(shù)值實(shí)驗(yàn),結(jié)果表明,對(duì)偶方法能有效地獲得MCP的全局解。
首先,將給出MCP(1)的Lagrange對(duì)偶問(wèn)題。注意MCP(1)等價(jià)于下述最優(yōu)化問(wèn)題(見Sun[6]):
(3)
易知,(3)的Lagrange對(duì)偶問(wèn)題為:
(4)
這里,Λ=diag(λ1I1,…,λmIm),若令Fi=diag(0,…,0,Ini,0,…,0)∈Rn×n,則(4)可以改寫為:
(5)
顯然,(5)是標(biāo)準(zhǔn)的半定規(guī)劃問(wèn)題,可以使用內(nèi)點(diǎn)法求解,且已有較好的軟件包,例如,Sedumi[14],SDSP[15]。
(Λ*-A)x=0。
(6)
如果(6)存在解x*∈Σm,那么,由Hanafi和Ten Berge[8]的結(jié)果可知,x*就是MCP(1)的一個(gè)全局解,此時(shí)(5)與(3)是強(qiáng)對(duì)偶的,也就是MCP(1)與(5)強(qiáng)對(duì)偶。
命題1Λ*-A是奇異的。
算法1 (Modified Dual Method,MDM)
第二步 計(jì)算Λ*-A的最小特征值對(duì)應(yīng)的特征向量
第三步 如果‖xj‖2≥1-ε0(這里ε0為某一給定的小正數(shù)),j=1,2…,m,則x*為MCP的全局解,停機(jī),否則執(zhí)行下一步;
對(duì)于上述算法有以下幾點(diǎn)說(shuō)明:
其中vi是Aii對(duì)應(yīng)最大特征值的單位特征向量。
其次,正如引言所指出的,如果m=2或者m≥3且A為正矩陣,那么,Hanafi和Ten Berge[8,Result 5]表明:(3)與(5)是強(qiáng)對(duì)偶的,此時(shí)算法1中的Step(4)理論上是不必要的,即x*是MCP(1)的全局解。
第三,對(duì)于m≥3且A為一般的正定矩陣時(shí),算法1的本質(zhì)是:若(3)與(5)是強(qiáng)對(duì)偶的,則Step(3)結(jié)束后即可獲得MCP(1)的全局解;若(3)與(5)不是強(qiáng)對(duì)偶的,即(6)沒(méi)有解x*∈Σm,此時(shí)對(duì)偶方法為對(duì)稱G-S或AVM迭代法提供一種初始迭代策略。
(7)
令
(8)
(9)
已知,對(duì)對(duì)稱G-S及AVM方法而言目前已有的理論無(wú)法保證獲得MCP(1)的全局最大點(diǎn),已有的數(shù)值實(shí)驗(yàn)表明[16-17],恰當(dāng)?shù)剡x擇初始迭代點(diǎn)不但可以提高Horst方法、G-S方法及P-SOR方法的收斂速度,而且可以提高獲取(1)的最優(yōu)解的可能性。
本文的數(shù)值實(shí)驗(yàn)是在Matlab7.6.0環(huán)境下完的,而且所用的矩陣A按如下2種方式形成:
首先,對(duì)上述2種方式形成的矩陣A做了充分的實(shí)驗(yàn),分別統(tǒng)計(jì)了MCP與其Lagrange對(duì)偶問(wèn)題強(qiáng)對(duì)偶的概率。結(jié)果表明:矩陣A=DBTBD對(duì)應(yīng)的MCP與其Lagrange對(duì)偶問(wèn)題都是強(qiáng)對(duì)偶的,并且強(qiáng)對(duì)偶性與m和整數(shù)集p的取值無(wú)關(guān)(統(tǒng)計(jì)應(yīng)用中常出現(xiàn)這類矩陣);而對(duì)于方式二形成的矩陣并非都是強(qiáng)對(duì)偶的(見表1),只有當(dāng)m=2時(shí)全是強(qiáng)對(duì)偶的,而且隨著m的增大,強(qiáng)對(duì)偶的概率減??;并且隨著m和n的增大,平均花費(fèi)時(shí)間增加,即,算法收斂速度變慢。
表1 強(qiáng)對(duì)偶的概率
由于MCP的Lagrange對(duì)偶問(wèn)題是半定規(guī)劃,并且已有較好的求解軟件,因此,對(duì)于方式一中形成的矩陣A,可以通過(guò)求解其對(duì)偶問(wèn)題來(lái)獲得MCP的全局解;而對(duì)于方式二中對(duì)應(yīng)的非強(qiáng)對(duì)偶的情形,用改進(jìn)的對(duì)偶方法(MDM)進(jìn)行求解(見表2),并統(tǒng)計(jì)此時(shí)獲得全局解的可能性。
表2 獲得全局解的可能性
表2中的結(jié)果表明,改進(jìn)的對(duì)偶方法對(duì)于獲得MCP的全局解有改進(jìn),但對(duì)于困難問(wèn)題仍不保證得全局解。
其次,為了更好的了解對(duì)偶方法對(duì)獲得全局解的改進(jìn),給出幾個(gè)已知全局解的例子進(jìn)行數(shù)值實(shí)驗(yàn)。
例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。
對(duì)上述給定的例子,利用Sedumi軟件求解其MCP的對(duì)偶問(wèn)題,比較MCP與其對(duì)偶問(wèn)題的最優(yōu)值(Table3)。
表3 最優(yōu)值的比較
根據(jù)上述結(jié)果,可以清楚地看到,例2和3對(duì)應(yīng)的MCP與其對(duì)偶問(wèn)題是強(qiáng)對(duì)偶的,那么我們可以通過(guò)求解其對(duì)偶問(wèn)題得到MCP的全局最優(yōu)解;而例1和4的MCP與其對(duì)偶問(wèn)題是弱對(duì)偶的,并且此時(shí)利用修改的對(duì)偶方法(MDM)可獲得MCP的全局最優(yōu)解和全局最優(yōu)值。
表4 對(duì)偶差
若MCP與其對(duì)偶問(wèn)題是強(qiáng)對(duì)偶的,則此時(shí)μ為零,即對(duì)偶問(wèn)題的解是MCP的解;而當(dāng)非強(qiáng)對(duì)偶時(shí)(表4),μ的值不大,那么在一定的精度下,可以把對(duì)偶問(wèn)題的解作為MCP的近似解;而此時(shí)若用改進(jìn)的對(duì)偶方法求解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] 孫繼廣. 多參數(shù)特征值問(wèn)題的一種算法[J]. 計(jì)算數(shù)學(xué), 1986, 8(2): 137-149.
[7] 秦曉偉. 關(guān)于解極大相關(guān)問(wèn)題P-SOR算法的收斂性 [J]. 計(jì)算數(shù)學(xué), 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] 徐蓮花. 關(guān)于多元特征值問(wèn)題的數(shù)值方法 [D]. 青島: 中國(guó)海洋大學(xué)數(shù)學(xué)科學(xué)學(xué)院, 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
責(zé)任編輯 陳呈超
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
國(guó)家自然科學(xué)基金項(xiàng)目(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