一種放松參數(shù)的部分并行ADMM算法

金青龍， 高前明

( 南京財(cái)經(jīng)大學(xué) 應(yīng)用數(shù)學(xué)學(xué)院， 南京 210023 )

0 引言

近年來隨著對優(yōu)化問題的深入研究，一些學(xué)者研究了如下具有多塊變量的線性可分凸優(yōu)化模型：

(1)

其中，θi:Rni→R(i=1,…,m)是閉的凸函數(shù)(不一定光滑)；A∈Rl ×ni、b∈Rl和Xi?Rni是給定的閉凸集.假設(shè)模型(1)的解集是非空的，矩陣A∈Rl ×ni列滿秩，則模型(1)的拉格朗日函數(shù)為

(2)

增廣拉格朗日函數(shù)為

(3)

(4)

研究表明，利用多塊ADMM算法雖然可以將一個(gè)高維問題分解成多個(gè)低維的子問題以解決一些優(yōu)化問題[1-3]，但在有些問題上多塊ADMM算法并不能完全保證其具有收斂性[4-5].目前，提高ADMM算法收斂性的方法主要有以下兩種：一是增加模型假設(shè)，如假設(shè)目標(biāo)函數(shù)為強(qiáng)凸函數(shù)，約束矩陣列滿秩等；二是對ADMM算法本身做一些修正而無需加強(qiáng)模型的假設(shè)條件，如改造子問題、增加矯正步或更換子問題計(jì)算順序等.在實(shí)際優(yōu)化問題中由于難以滿足模型的加強(qiáng)假設(shè)條件，所以一般利用第2種方法來實(shí)現(xiàn)多塊ADMM算法的收斂性.2013年， He等[6]提出了一種部分并行的分裂算法，該算法在更新第1塊變量后，對拉格朗日乘子進(jìn)行一次更新，然后再采用第1個(gè)變量以及乘子的最新信息并行計(jì)算其他變量，以此減少每次迭代的計(jì)算時(shí)間,從而提高計(jì)算速度.2016年， Hou等[7]提出了一種具有更一般形式的部分并行ADMM(PPADMM)算法，該算法在每次迭代中生成的預(yù)測點(diǎn)的迭代格式為：

(5)

上述迭代格式的矯正步為：

(6)

式中v=(x2,…,xm,λ)， 并滿足參數(shù)條件r>s(m-1).由上式可知，PPADMM算法存在參數(shù)取值范圍較小的問題，因此其收斂速度相對較慢.基于此，本文提出一種放松參數(shù)的部分并行ADMM算法，即通過擴(kuò)大參數(shù)的取值范圍來提高算法的收斂速度，并通過數(shù)值實(shí)驗(yàn)驗(yàn)證了該算法的有效性.

1 預(yù)備知識

1.1 變分不等式的性質(zhì)

(7)

(8)

1.2 相關(guān)矩陣的定義

定義

其中，r>0,s>0.由以上定義可得：

Q=HM，

并且當(dāng)r>s(m-2)時(shí)，矩陣G正定.由r>0,s>0可知，參數(shù)條件r>s(m-2)比算法PPADMM[7]中的參數(shù)條件(r>s(m-1))更加放松.

2 算法及其收斂性分析

步驟1(預(yù)測步)

2.1 收斂性分析

為證明本文提出的算法具有收斂性，首先證明以下2個(gè)引理.

(9)

證明根據(jù)一階最優(yōu)性條件，步驟1中的x1- 子問題可以寫為

(10)

xi- 子問題可以寫為

(11)

(12)

(13)

(14)

(15)

(16)

將式(15)代入到式(16)中即可得證引理1.

(17)

其中矩陣Q按1.2中被定義.

(18)

基于引理1和引理2， 本文給出如下的定理1和定理2.

(19)

證明由步驟2和引理2得：

因此定理1得證.

定理2由新算法生成的序列{wk}收斂于原問題的解點(diǎn).

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

數(shù)值實(shí)驗(yàn)采用的PC機(jī)的配置為： 1.80 GHz CPU， 8 GB內(nèi)存， Windows 10家庭中文版操作系統(tǒng).編程軟件為MatlabR 2018a.測試模型為如下二次線性規(guī)劃模型：

(20)

2) 選取算法參數(shù)：s=1.2，r=3s，β根據(jù)不同算法和問題設(shè)置進(jìn)行人工調(diào)優(yōu).

為了驗(yàn)證新算法的收斂速度是否得到提高，分別采用新算法(PPADMMR)和PPADMM算法[7]求解模型(式(20)).測試分為4組(n,mi)， 每組運(yùn)行10次，實(shí)驗(yàn)結(jié)果見表1.由表1可知：在KKT違反度方面， PPADMMR算法和PPADMM算法相近；在迭代次數(shù)方面， PPADMMR算法的迭代次數(shù)比PPADMM算法的迭代次數(shù)減少6%～13%.由此可知，PPADMMR算法的收斂速度優(yōu)于PPADMM算法,該結(jié)果符合本文的理論分析.

表1 PPADMMR算法和PPADMM算法的測試結(jié)果

為了更直觀地觀察PPADMMR算法與PPADMM算法在不同條件數(shù)(n,mi)下, Cond(Hi)中矩陣Hi的收斂效果，本文給出了兩種算法的迭代次數(shù)隨Cond(Hi)的變化情況，如圖1所示.由圖1可以看出，在Cond(Hi)較高的情況下， PPADMMR算法的迭代次數(shù)總是少于PPADMM算法的迭代次數(shù)，且這種性能優(yōu)勢隨著Cond(Hi)的變化始終保持穩(wěn)定.由此可知， PPADMMR算法的收斂效果優(yōu)于PPADMM算法.

圖1 PPADMMR算法和PPADMM算法在不同條件數(shù)下的迭代次數(shù)

4 結(jié)論

上述研究表明，本文提出的PPADMMR算法的收斂性能顯著優(yōu)于PPADMM算法，因此該算法可用于解決多塊線性約束可分凸優(yōu)化問題，同時(shí)可為研究快速ADMM算法提供參考.由于本文將PPADMMR算法的矯正步步長固定為1， 因此算法的收斂速度會受到固定步長的約束.在今后的研究中，我們將在該算法中引入自適應(yīng)步長技術(shù)，以更進(jìn)一步提高該算法的性能.