金青龍， 高前明

( 南京財(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算法雖然可以將一個高維問題分解成多個低維的子問題以解決一些優(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個變量以及乘子的最新信息并行計(jì)算其他變量，以此減少每次迭代的計(jì)算時間,從而提高計(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)時，矩陣G正定.由r>0,s>0可知，參數(shù)條件r>s(m-2)比算法PPADMM[7]中的參數(shù)條件(r>s(m-1))更加放松.

2 算法及其收斂性分析

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

2.1 收斂性分析

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

(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)化問題，同時可為研究快速ADMM算法提供參考.由于本文將PPADMMR算法的矯正步步長固定為1， 因此算法的收斂速度會受到固定步長的約束.在今后的研究中，我們將在該算法中引入自適應(yīng)步長技術(shù)，以更進(jìn)一步提高該算法的性能.