一種精確的增廣lagrange乘子算法

一種精確的增廣lagrange乘子算法

0低秩矩陣填充的算法矩陣填充問題是一個吸引人的新研究領域。它的著名應用是nit系統(tǒng)，用于圖像恢復。矩陣填充主要研究如何在數(shù)據(jù)不完整的情況下將缺失矩陣進行填充．大部分低秩矩陣(其數(shù)據(jù)分布在一個低維的線性子空間上)填充問題一般可以通過求解如下凸優(yōu)化問題來實現(xiàn):符號模式矩陣是組合矩陣論的一個新型研究分支，是近年來在組合數(shù)學中較為活躍的一個研究方向．符號矩陣本文結(jié)構安排如下:第1節(jié)首先回顧已有的對一般矩陣填充的ALM算法，然后詳細介紹針對符號矩陣填充的SM-ALM算法和GA算法;第2節(jié)給出了SM-ALM算法的收斂性分析;第3節(jié)通過數(shù)值實驗給出了SM-ALM算法和GA算法對符號矩陣填充的結(jié)果;最后在第4節(jié)對全文進行總結(jié)．為方便起見，1該算法首先回顧已有的對一般矩陣填充的ALM算法:1.1計算矩陣及相關算法ALM算法其Lagrange函數(shù)為:其中算法1(ALM算法)第0步:給定下標集合Ω，樣本矩陣D，參數(shù)μ第1步:計算矩陣(D-E第2步:令第3步:通過給定參數(shù)，若‖D-A第4步:令Y1.2充滿符號矩陣的算法在總結(jié)現(xiàn)有算法的基礎上，提出針對符號矩陣填充問題的算法．1.2.1yr算法2.2改進的alm算法符號矩陣的填充問題可以描述為以下凸優(yōu)化問題:其Lagrange函數(shù)為:其中A,D,E都是符號矩陣，Y∈R算法2(SM-ALM算法)第0步:給定下標集合Ω，樣本矩陣D，參數(shù)μ第1步:計算矩陣(D-E第2步:令第3步:令第4步:通過給定參數(shù)，若‖D-A第5步:令Y算法2在進行奇異值分解之后，根據(jù)矩陣的均值進行投影，然后進行填充，這樣可以保證每次產(chǎn)生的迭代矩陣都保持符號矩陣的結(jié)構．1.2.2新種群的生成遺傳算法(GA)下面我們提出針對符號矩陣填充的遺傳算法．算法3(GA算法)第0步:給定下標集合Ω，樣本矩陣D，參數(shù)ε，交叉概率，變異概率;第1步:給定種群大小，根據(jù)采樣率計算染色體長度，生成種群pop(其中元素為1,0);第3步:對pop中每一個個體進行選擇，得到新種群newpop;第4步:對新種群newpop進行交叉，變異得到newpop1;第5步:將newpop1中每一個個體代入D中(第6步:若第7步:比較newpop1中每一個個體適應度的大小，選出最優(yōu)個體．2收集劑分析本節(jié)討論算法2的收斂性．引理1引理2其中:為方便起見，將算法1中的A引理4若證明證明由引理4知，當k充分大時，有D-A3數(shù)值實驗在本節(jié)中，通過數(shù)值實驗比較SM-ALM算法與GA算法．在實驗中，M表示采樣矩陣，A表示輸出的最優(yōu)解，4sm-alm算法可行性分析在本文中，使用SM-ALM算法和GA算法來填充符號矩陣，結(jié)果表明SM-ALM算法是可行的，并能在很短的時間和很少的迭代步