• 
    

    
    

      99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

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

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

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

      ?

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

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

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

      極大相關(guān)問題;多元特征值問題;Lagrange對偶;強對偶;全局解;收斂性

      0 引言

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

      這里,Aii∈Rni×ni,求解

      (1)

      其中

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

      Ax=Λx;

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

      (2)

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

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

      1 對偶方法

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

      (3)

      易知,(3)的Lagrange對偶問題為:

      (4)

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

      (5)

      顯然,(5)是標(biāo)準(zhǔn)的半定規(guī)劃問題,可以使用內(nèi)點法求解,且已有較好的軟件包,例如,Sedumi[14],SDSP[15]。

      (Λ*-A)x=0。

      (6)

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

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

      算法1 (Modified Dual Method,MDM)

      第二步 計算Λ*-A的最小特征值對應(yīng)的特征向量

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

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

      其中vi是Aii對應(yīng)最大特征值的單位特征向量。

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

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

      (7)

      (8)

      (9)

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

      2 數(shù)值實驗

      本文的數(shù)值實驗是在Matlab7.6.0環(huán)境下完的,而且所用的矩陣A按如下2種方式形成:

      首先,對上述2種方式形成的矩陣A做了充分的實驗,分別統(tǒng)計了MCP與其Lagrange對偶問題強對偶的概率。結(jié)果表明:矩陣A=DBTBD對應(yīng)的MCP與其Lagrange對偶問題都是強對偶的,并且強對偶性與m和整數(shù)集p的取值無關(guān)(統(tǒng)計應(yīng)用中常出現(xiàn)這類矩陣);而對于方式二形成的矩陣并非都是強對偶的(見表1),只有當(dāng)m=2時全是強對偶的,而且隨著m的增大,強對偶的概率減?。徊⑶译S著m和n的增大,平均花費時間增加,即,算法收斂速度變慢。

      表1 強對偶的概率

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

      表2 獲得全局解的可能性

      表2中的結(jié)果表明,改進(jìn)的對偶方法對于獲得MCP的全局解有改進(jìn),但對于困難問題仍不保證得全局解。

      其次,為了更好的了解對偶方法對獲得全局解的改進(jìn),給出幾個已知全局解的例子進(jìn)行數(shù)值實驗。

      例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與其對偶問題的最優(yōu)值(Table3)。

      表3 最優(yōu)值的比較

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

      表4 對偶差

      若MCP與其對偶問題是強對偶的,則此時μ為零,即對偶問題的解是MCP的解;而當(dāng)非強對偶時(表4),μ的值不大,那么在一定的精度下,可以把對偶問題的解作為MCP的近似解;而此時若用改進(jìn)的對偶方法求解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ù)特征值問題的一種算法[J]. 計算數(shù)學(xué), 1986, 8(2): 137-149.

      [7] 秦曉偉. 關(guān)于解極大相關(guān)問題P-SOR算法的收斂性 [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)于多元特征值問題的數(shù)值方法 [D]. 青島: 中國海洋大學(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

      國家自然科學(xué)基金項目(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é)對偶特征值
      一類帶強制位勢的p-Laplace特征值問題
      單圈圖關(guān)聯(lián)矩陣的特征值
      中國海洋大學(xué)作品選登
      中國海洋大學(xué) 自主招生,讓我同時被兩所211大學(xué)錄取
      ?? ??? ???? ????
      基于商奇異值分解的一類二次特征值反問題
      對偶平行體與對偶Steiner點
      La communication sino-fran?aise
      對偶均值積分的Marcus-Lopes不等式
      對偶Brunn-Minkowski不等式的逆
      成安县| 江门市| 正宁县| 三明市| 东阳市| 白银市| 古田县| 中宁县| 定结县| 晋江市| 林州市| 萨迦县| 凯里市| 汉沽区| 会同县| 台东县| 格尔木市| 黎城县| 竹溪县| 咸丰县| 惠州市| 稻城县| 科技| 河东区| 牡丹江市| 安达市| 泊头市| 泽州县| 同德县| 庆云县| 永顺县| 宁夏| SHOW| 高邑县| 蛟河市| 平武县| 宁化县| 遵义市| 靖西县| 鲁山县| 通榆县|