亚洲免费av电影一区二区三区,日韩爱爱视频,51精品视频一区二区三区,91视频爱爱,日韩欧美在线播放视频,中文字幕少妇AV,亚洲电影中文字幕,久久久久亚洲av成人网址,久久综合视频网站,国产在线不卡免费播放

        ?

        求解極大相關(guān)問(wèn)題的對(duì)偶方法?

        2015-03-18 08:33:24李美然劉新國(guó)中國(guó)海洋大學(xué)數(shù)學(xué)科學(xué)學(xué)院山東青島266100
        關(guān)鍵詞:海洋大學(xué)對(duì)偶特征值

        李美然, 劉新國(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ì)偶;全局解;收斂性

        0 引言

        多組變量的極大相關(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的全局解。

        1 對(duì)偶方法

        首先,將給出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)解的可能性。

        2 數(shù)值實(shí)驗(yàn)

        本文的數(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

        猜你喜歡
        海洋大學(xué)對(duì)偶特征值
        一類帶強(qiáng)制位勢(shì)的p-Laplace特征值問(wèn)題
        單圈圖關(guān)聯(lián)矩陣的特征值
        中國(guó)海洋大學(xué)作品選登
        中國(guó)海洋大學(xué) 自主招生,讓我同時(shí)被兩所211大學(xué)錄取
        ?? ??? ???? ????
        基于商奇異值分解的一類二次特征值反問(wèn)題
        對(duì)偶平行體與對(duì)偶Steiner點(diǎn)
        La communication sino-fran?aise
        對(duì)偶均值積分的Marcus-Lopes不等式
        對(duì)偶Brunn-Minkowski不等式的逆
        东北老女人高潮疯狂过瘾对白 | 亚洲一区二区丝袜美腿| 国产一级黄色片在线播放| av在线免费观看蜜桃| 夜夜添夜夜添夜夜摸夜夜摸| 精品久久久久久中文字幕大豆网| 青青草视频华人绿色在线| 国产精品美女久久久久| 97人妻视频妓女网| 国产三级精品三级在线观看粤语| 人妻少妇偷人精品一区二区| 国产无套中出学生姝| 亚洲熟妇av日韩熟妇在线| 在教室伦流澡到高潮hnp视频| 色综合久久久久综合一本到桃花网| 国产精品亚洲二区在线| 久久精品免费一区二区喷潮| 真人做爰片免费观看播放| 推油少妇久久99久久99久久| 日韩精品有码在线视频| 新久久国产色av免费看| 亚洲日韩中文字幕在线播放| 日韩在线一区二区三区免费视频 | 久久国产精品岛国搬运工| 亚洲av一二三四五区在线| 99噜噜噜在线播放| 国产探花在线精品一区二区| 曰韩精品无码一区二区三区| 亚洲天堂av另类在线播放| 刚出嫁新婚少妇很紧很爽| 精品国产av一区二区三区| 综合久久给合久久狠狠狠97色| 亚洲不卡av不卡一区二区| 中文字幕亚洲一区二区三区| 日韩av午夜在线观看| 日韩精品无码av中文无码版| 亚洲无码毛片免费视频在线观看| 国产人妻久久精品二区三区老狼 | 久久99精品久久久久久| 日韩熟女一区二区三区| 久久国产成人午夜av免费影院|