基于線性化逐塊交替方向乘子法的改進

基于線性化逐塊交替方向乘子法的改進

乘子迭代方向法（admm）是解決線性約束凸優(yōu)化問題的高效算法，由格林威治等人開發(fā)?？紤]以下多塊變量線性約束凸優(yōu)化問題：其中，θ假設(shè)式（1）的解是非空的，它的拉格朗日函數(shù)為它的增廣拉格朗日函數(shù)為其中，λ∈RADMM的一個優(yōu)勢是利用目標函數(shù)關(guān)于多塊變量的可分性，把一個高維的子問題分解成多個維數(shù)較低的子問題，大大簡化了子問題求解的過程．特別的，當θ由于廣泛的應用性，國內(nèi)外學者從理論、改進、應用等多個角度對ADMM進行了深入研究．當只有2塊變量時（m=2),ADMM有全局收斂性，早期關(guān)于ADMM的研究工作集中于2塊變量的情形：如Eckstein等當有更多塊變量時（m≥3),ADMM一般不收斂，可參考文獻本文基于文獻式中，m利用以上記號，式（5）可以改寫為以下形式：利用BADMM求解式（5）的迭代格式如下：其中η的二次項在x利用LBADMM求解式（5）的迭代格式如下：其中，η1預備知識1.1變分序列的性質(zhì)若（x引入以下新記號：式（12）簡寫成下面的形式：1.2引用理論矩陣A和B在式（7）中被定義，有以下結(jié)論．引理1定義那么，有m引理2令k2a步驟2預測步驟2校正基于LBADMM，提出以下新算法：算法1新算法與線性化逐塊ADMM算法的區(qū)別在于改進了算法中的鄰近項因子，使算法的收斂速度更快．原算法對于每組變量使用相同的鄰近項因子，而新算法對于組內(nèi)的每一塊使用不同的鄰近項因子，參數(shù)條件大大放松，因此收斂速度更快．這種優(yōu)勢在組內(nèi)不同塊之間‖A步驟1（預測）步驟2（校正）其中，我們可以證明以下2個有用的結(jié)果．引理3給定其中，證明：忽略一些常數(shù)項，式（18）中的x根據(jù)一階最優(yōu)條件，有同樣的，式（18）中y子問題的最優(yōu)性條件可以寫成再利用它可以重新寫成結(jié)合式（26）、（27）、（28），使用式（20）、（21）、（22），引理得證．引理4定義則H、M正定．證明：根據(jù)式（20）中M的定義，有則根據(jù)引理2知道H是正定的．而且根據(jù)矩陣G的定義，可得：由引理2可知G正定，引理得證．基于引理3和4，有如下的定理．定理1序列{w證明：通過式（19）、（29）和（21）可以寫成利用以下恒等式將通過式（19）和（29）處理式（36）的右端第2個括號里的項，得結(jié)合式（34）、（36）和（37），得式（33），定理得證．定理2序列{w證明：在式（33）中設(shè)w=w因為w以上2個不等式結(jié)合，得證．現(xiàn)在，給出算法1的收斂結(jié)論．定理3由算法1生成的序列{w證明：從式（38）可知{w3新算法與lbadagmm算法的比較我們將新算法與LBADMM算法通過數(shù)值實驗進行比較，以研究新算法的實際計算效率．實驗平臺為一臺配置為奔騰1.33GHzCPU、2GB內(nèi)存、Windows10操作系統(tǒng)的筆記本電腦，所有算法在MATLABR2016a上編程實現(xiàn)．下面從迭代步數(shù)、計算時間及精度3個方面對算法的數(shù)值表現(xiàn)進行考察．將新算法應用于求解在統(tǒng)計學、信息科學中常用的LASSO模型，其問題如下：其中‖·‖按照2%的非零元比例隨機生成稀疏向量（x無論是用新算法還是用LBADMM算法求解式（41），子問題的求解都是使用軟閾值收縮（softshrinkage）得到，計算量完全相同．2種算法的關(guān)鍵參數(shù)β的取值需要人工調(diào)整至最優(yōu)，每組問題β的設(shè)置都可能不同．鄰近因子的選取按照盡可能靠近其上下界的規(guī)則選取，如k為公平起見，2種算法的初始點均隨機產(chǎn)生，終止條件均為所有變量（x,y和λ）相鄰2步的相對變化小于10我們在幾組不同（m,n，ρ）設(shè)置下測試了算法．在每組（m,n，ρ）設(shè)置下，我們隨機生成10個問題，并比較算法的計算時間和迭代步數(shù)的平均值．具體的數(shù)值結(jié)果見表1:從表1的結(jié)果看出：新算法的迭代次數(shù)和計算時間總比LBADMM算法少，可見新算法比LBADMM算法更為高效．并且在為了更細致地觀察和比較LBADMM與新算法的收斂速度，在2種算法的求解過程中記錄下每個迭代步當前點到解點的歐式距離，并將在2種不同問題設(shè)置下該距離的變化曲線展示在圖1中．從圖1可看出：在迭代初期（約200步以內(nèi)），2種算法收斂幾乎一樣；在迭代中后期，LBADMM收斂變慢，而新算法的收斂速度基本保持不變．不同的問題設(shè)置基本不影響這一觀察結(jié)果，因此新算法的收斂不僅穩(wěn)定快速，而且在高精度下優(yōu)勢更為明顯．比較2個子圖還可發(fā)現(xiàn)，2種算法在迭代中后期的收斂速度的差距在ρ較大時更為明顯，這和我們的預期完全一致．4算法有效性分析本文研究了在信息科學、統(tǒng)計學和工程等領(lǐng)域有廣泛應用價值的線性約束多塊凸優(yōu)化問題及用于求解該問題的多塊ADMM算法．ADMM通常只能求解2塊變量的模型，在多塊的情況下一般不收斂，需要增加假設(shè)條件或者對多塊ADMM適當改造以保證算法收斂性．本文基于線性化逐塊ADMM算法，放松了算法中鄰近因子的取值范圍，在保持子問題容易求解的前提下，使算法收斂速度加快．初步數(shù)值實驗