于慧慧，王永麗,陳勇勇，周秀娟

(1.山東科技大學(xué) 數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院，山東 青島 266590;2.山東科技大學(xué) 信息科學(xué)與工程學(xué)院，山東 青島 266590)

求解無約束一致性優(yōu)化問題的分布式擬牛頓算法

于慧慧1，王永麗1,陳勇勇1，周秀娟2

(1.山東科技大學(xué) 數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院，山東 青島 266590;2.山東科技大學(xué) 信息科學(xué)與工程學(xué)院，山東 青島 266590)

摘要:本文主要針對(duì)網(wǎng)絡(luò)中各個(gè)節(jié)點(diǎn)相互協(xié)作，最大限度地使本地費(fèi)用函數(shù)的總和最小的無約束一致性優(yōu)化問題，提出了一類分布式擬牛頓算法。算法僅利用了目標(biāo)函數(shù)的一階導(dǎo)數(shù)信息，每步通過選取一個(gè)滿足擬牛頓方程的正定對(duì)角矩陣來作為費(fèi)用函數(shù)Hesse矩陣逆的校正矩陣，克服了校正矩陣的非稀疏性對(duì)算法分布式實(shí)現(xiàn)造成的困難，減少了計(jì)算量和存儲(chǔ)空間。在適當(dāng)條件下，證明了分布式擬牛頓算法的全局收斂性及局部線性收斂速度，并通過數(shù)值實(shí)驗(yàn)驗(yàn)證了算法的優(yōu)越性。

關(guān)鍵詞:無約束; 一致性優(yōu)化; 分布式擬牛頓算法； 全局收斂; 線性收斂

(1)

其中y*表示問題(1)的最優(yōu)解。在現(xiàn)實(shí)生活中，這種形式的問題有很多，例如，大數(shù)據(jù)分析[1],分布式傳感器網(wǎng)絡(luò)[ 2-5 ]和分布式控制[6]等。

求解問題(1)的分布式方法分為兩類，一類是基于費(fèi)用函數(shù)一階信息的方法，該類方法中研究較多的是分布式梯度法[7-10]，分布式交替方向乘子法[11-13]和分布式對(duì)偶平均法[14-15]。雖然這些算法之間存在著很大的差異，但基本思想都可以歸結(jié)為先進(jìn)行本地下降步，然后與相鄰節(jié)點(diǎn)進(jìn)行變量交換和信息整合。由于該類計(jì)算僅涉及到一階信息，導(dǎo)致了對(duì)下降方向曲率估計(jì)的不準(zhǔn)確性，便得收斂速度較慢。另一類分布式方法是基于費(fèi)用函數(shù)二階信息的方法，即分布式牛頓類算法，主要的文獻(xiàn)有[16-17]等。目前，對(duì)分布式牛頓類算法的研究較少，這主要是因?yàn)榕ｎD法的分布式實(shí)現(xiàn)比較困難且計(jì)算目標(biāo)函數(shù)的二階信息計(jì)算量較大。但考慮到牛頓類算法比大多數(shù)一階方法具有更快的收斂速度，越來越多的學(xué)者開始了對(duì)該類算法的研究。

本文研究分布式求解問題(1)的擬牛頓方法，只需計(jì)算目標(biāo)函數(shù)的一階信息，通過選取一個(gè)滿足擬牛頓方程的正定對(duì)角矩陣來作為費(fèi)用函數(shù)Hesse矩陣逆的校正矩陣，來克服校正矩陣的非稀疏性對(duì)算法分布式實(shí)現(xiàn)造成的困難，從而實(shí)現(xiàn)擬牛頓法的分布式計(jì)算，減少計(jì)算量和存儲(chǔ)空間。同時(shí)，在適當(dāng)條件下證明分布式擬牛頓算法的收斂性，并通過數(shù)值試驗(yàn)驗(yàn)證算法的有效性。應(yīng)當(dāng)指出的是，這里的分布式是指每個(gè)節(jié)點(diǎn)僅知道其本地費(fèi)用函數(shù)，且只能夠與相鄰節(jié)點(diǎn)進(jìn)行信息交換。

1預(yù)備知識(shí)

首先給出關(guān)于問題(1)的一些預(yù)備知識(shí)。

假設(shè)1假設(shè)函數(shù)fi:Rp→R是系數(shù)為μ>0的強(qiáng)凸函數(shù)，即

(2)

并且具有常數(shù)為L(zhǎng)的Lipschitz連續(xù)梯度，即

‖▽fi(y)-▽fi(z)‖≤L‖y-z‖。

(3)

假設(shè)3矩陣W=WT∈Rn×n是元素為wij的隨機(jī)矩陣, 其中wij的定義如下：

且存在常數(shù)wmin,wmax使得

0

定義1[16]對(duì)于矩陣M=(Mij)∈Rnp×np，其中Mij∈Rp×p，定義M的范數(shù)如下：

類似的，對(duì)向量x∈Rnp，xi∈Rp，定義：

其中‖·‖2為歐式范數(shù)。

2分布式擬牛頓法

牛頓法的基本思想是利用目標(biāo)函數(shù)的二次Taylor展開來逼近目標(biāo)函數(shù)，但在實(shí)際問題中，尤其是大規(guī)模的高維問題中，如果所基于的網(wǎng)絡(luò)是稀疏的，則目標(biāo)函數(shù)的二階導(dǎo)也可能是稀疏的，從而使得所求解的問題具有特殊結(jié)構(gòu)。但遺憾的是，即使目標(biāo)函數(shù)的Hesse矩陣是稀疏的，但其逆卻是稠密的。為了減少計(jì)算量，避免Hesse矩陣逆的計(jì)算，我們利用目標(biāo)函數(shù)及其一階導(dǎo)數(shù)信息來近似Hesse矩陣的逆矩陣，通過構(gòu)造特殊的擬牛頓矩陣，實(shí)現(xiàn)擬牛頓矩陣的分布式計(jì)算。

2.1問題的等價(jià)變形

引入輔助函數(shù)Φ:Rnp→R，令x=(x1,…,xn)∈Rnp，并記Z∈Rnp×np為W和單位矩陣I∈Rp×p的Kronecker積：Z=W?I，則由文獻(xiàn)[18]可知問題(1)等價(jià)于如下問題：

(4)

其中α>0 為罰參數(shù)，Inp×np表示np×np的單位矩陣。

(5)

2.2算法框架

求解問題(4)的擬牛頓法的基本迭代格式為：xk+1=xk+εdk。

(6)

(7)

Hk是目標(biāo)函數(shù)Hesse矩陣逆矩陣的近似，滿足正定性和如下擬牛頓條件：

Hkyk=sk。

(8)

(9)

其中hij表示對(duì)角矩陣hi的第j個(gè)對(duì)角元，yij表示子向量yi中第j個(gè)分量，sij表示子向量si的第j個(gè)分量。

(10)

(11)

于是，由(7)式可以寫出在每個(gè)節(jié)點(diǎn)i處的下降方向：

(12)

(13)

由上述討論可得分布式擬牛頓算法(Distributed-DiagonalQuasi-Newton,D-DQN)的框架如下：

分布式擬牛頓算法 對(duì)每個(gè)節(jié)點(diǎn)i,給定α,ε>0。步1.初始化:對(duì)每個(gè)節(jié)點(diǎn)i,令k=0,給定初始點(diǎn)x0i,x1i∈Rp。步2.對(duì)每個(gè)節(jié)點(diǎn)i,將其迭代點(diǎn)xki傳遞給其相鄰節(jié)點(diǎn)j∈Oi,并從相鄰節(jié)點(diǎn)接收xkj.步3.對(duì)每個(gè)節(jié)點(diǎn)i,計(jì)算搜索方向:dki=-hkiα▽fixki()+∑j∈Oiwijxki-xkj()[]步4.對(duì)每個(gè)節(jié)點(diǎn)i,更新其近似解:xk+1i=xki+εdki步5.由(10)式、(11)式計(jì)算hk+1i的元素,令k=k+1,返回步2.

注：注意到擬牛頓方法每步迭代都涉及到當(dāng)前節(jié)點(diǎn)及其相鄰節(jié)點(diǎn)前兩步的變量信息，因此在給定初始條件時(shí)，每個(gè)節(jié)點(diǎn)需要給出兩個(gè)初始值。在算法的第2步，每個(gè)節(jié)點(diǎn)需要與其相鄰節(jié)點(diǎn)進(jìn)行信息交換。 第3步中計(jì)算搜索方向時(shí)涉及到了參數(shù)α，這一參數(shù)的取值在文獻(xiàn)[18]中已有研究，本文在數(shù)值實(shí)驗(yàn)時(shí)取α為固定值。算法第4步，本文采用一個(gè)固定步長(zhǎng)ε，顯然變量的迭代只涉及到自身的函數(shù)信息和相鄰節(jié)點(diǎn)的信息，實(shí)現(xiàn)了問題(1)的分布式計(jì)算。

3收斂性分析

引理1若假設(shè)1～3成立，則有‖dk‖≤M‖▽?duì)?xk)‖。

證明因?yàn)镠k為塊對(duì)角矩陣，由本文中范數(shù)的定義，可知：

因此，由dk的定義可得

(14)

(15)

(16)

證明由算法的迭代過程與題設(shè)可得

于是，由引理1可得

(17)

(18)

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

本節(jié)通過數(shù)值實(shí)驗(yàn)來驗(yàn)證D-DQN算法求解問題(1)的有效性，并將本文提出的算法與分布式梯度法(DGN)在迭代次數(shù)和運(yùn)行時(shí)間兩方面進(jìn)行比較。實(shí)驗(yàn)運(yùn)行環(huán)境為Pentium(R)E5500 2.77GHz雙核處理器，內(nèi)存2.00GB。所有算法程序均用Matlab2015a編寫。

實(shí)驗(yàn)生成節(jié)點(diǎn)個(gè)數(shù)為n的連通網(wǎng)絡(luò)，考慮如下形式一致性問題

當(dāng)全局變量維數(shù)p=3，圖1、圖2分別取不同網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)時(shí)，分布式梯度下降法(DGN)和分布式擬牛頓算法(D-DQN)迭代次數(shù)與誤差的關(guān)系曲線?？梢钥闯?，分布式擬牛頓算法的收斂速度要快于分布式梯度下降方法，且在剛開始迭代時(shí)表現(xiàn)出非常快的下降速度，從而體現(xiàn)出分布式擬牛頓法在求解大規(guī)模稀疏一致性優(yōu)化問題中的優(yōu)越性。

圖1　當(dāng)n=100時(shí)，D-DQN算法與DGN算法的比較

圖2　當(dāng)n=200時(shí)，D-DQN算法與DGN算法的比較

5結(jié)論

本文針對(duì)無約束一致性優(yōu)化問題(1)，提出了一類新的分布式擬牛頓算法，算法通過選取一個(gè)近似滿足擬牛頓方程的正定對(duì)角矩陣來近似費(fèi)用函數(shù)Hesse矩陣的逆，實(shí)現(xiàn)了擬牛頓算法的分布式實(shí)現(xiàn)。在取固定步長(zhǎng)的情況下，證明了算法的全局收斂性及局部線性收斂速度，并通過數(shù)值實(shí)驗(yàn)驗(yàn)證了算法的有效性。實(shí)驗(yàn)結(jié)果表明，分布式擬牛頓算法在求解大規(guī)模稀疏一致性優(yōu)化問題方面具有較好的應(yīng)用前景。

參考文獻(xiàn)：

[1]DANESHMAND A,FACCHINEI F,KUNGURTSEV V,et al. Hybrid random/deterministic parallel algorithms for nonconvex big data optimization[J].Journal of Inverstigative Medicine，2014，60(4)：671-675.

[2]SCHIZAS I D,RIBEIRO A,GIANNAKIS G B.Consensus in ad hoc WSNs with noisy links—Part I:Distributed estimation of deterministic signals[J].IEEE Transactions on Signal Processing,2008,56(1):350-364.

[3]KAR S,MOURA J M F,RAMANAN K.Distributed parameter estimation in sensor networks:Nonlinear observation models and imperfect communication[J].IEEE Transactions on Information Theory,2012,58(6):3575-3605.

[4]SAYED A H,LOPES C G.Adaptive Processing over distributed networks[J].Leice Transactions on Fundamentals of Electronics Communications and Computer Sciences,2007,E90-A(8):1504-1510.

[5]CATTIVELLI F S,SAYED A H.Diffusion LMS strategies for distributed estimation[J].IEEE Transactions on Signal Processing,2010,58(3):1035-1048.

[6]MOTA J F C,XAVIER J M F,AGUIAR P M Q,et al.Distributed optimization with local domains:Applications in MPC and network flows[J].IEEE Transactions on Automatic Control，2015,60(7):2004-2009.

[8]JAKOVETIC D,XAVIER J,MOURA J M F.Fast distributed gradient methods[J].IEEE Transactions on Automatic Control,2014,59(5):1131-1146.

[9]YUAN K,LING Q,YIN W.On the convergence of decentralized gradient descent[DB/OL].(2015-07-01)[2016-01-05].http://arXiv preprint arXiv:1310.7063.

[10]SHI W,LING Q,WU G,et al.Extra:An exact first-order algorithm for decentralized consensus optimization[J].SIAM Journal on Optimization,2015,25(2):944-966.

[11]LING Q,RIBEIRO A.Decentralized linearized alternating direction method of multipliers[C]//IEEE International Conference on Acoustics,Speech and Signal Processing (ICASSP),2014:5447-5451.

[12]BOYD S,PARIKH N,CHU E,et al.Distributed optimization and statistical learning via the alternating direction method of multipliers[J].Foundations and Trends in Machine Learning,2011,3(1):1-122.

[13]SHI W,LING Q,YUAN K,et al.On the linear convergence of the ADMM in decentralized consensus optimization[J].IEEE Transactions on Signal Processing,2014,62(7):1750-1761.

[14]DUCHI J C,AGARWAL A,WAINWRIGHT M J.Dual averaging for distributed optimization:convergence analysis and network scaling[J].IEEE Transactions on Automatic control,2012,57(3):592-606.

[15]TSIANOS K I,LAWLOR S,RABBAT M G.Push-sum distributed dual averaging for convex optimization[C]//IEEE 51st Annual Conference on Decision and Control (CDC),2012:5453-5458.

[16]BAJOVIC D,JAKOVETIC D,KREJIC N,et al.Newton-like method with diagonal correction for distributed optimization[DB/OL](2015-09-05)[2016-01-05].http：//arXiv preprint arXiv:1509.01703.

[17]MOKHTARI A,LING Q,RIBEIRO A.An approximate Newton method for distributed optimization[C]//IEEE International Conference on Acoustics,Speech and Signal Processing (ICASSP), 2015.

[18]JAKOVETIC D,MOURA J M F,XAVIER J.Distributed Nesterov-like gradient algorithms[C]//IEEE 51st Annual Conference on Decision and Control (CDC),2012:5459-5464.

[19]時(shí)貞軍,孫國(guó).無約束優(yōu)化問題的對(duì)角稀疏擬牛頓法[J].系統(tǒng)科學(xué)與數(shù)學(xué),2006,26(1):101-112.

SHI Zhenjun,SUN Guo.A diagonal-sparse quasi-Newton method for unconstrained optimization problem[J].Journal of Systems Science and Mathematical Sciences,2006,26(1):101-112.

(責(zé)任編輯：傅游)

Distributed Quasi-Newton Algorithm for Solving Unconstrained Consensus Optimization

YU Huihui1, WANG Yongli1, CHEN Yongyong1, ZHOU Xiujuan2

(1. College of Mathematics and Systems Science, Shandong University of Science and Technology, Qingdao Shandong 266590, China;2. College of Information Science and Engineering, Shandong University of Science and Technology,Qingdao, Shandong 266590, China)

Abstract:A class of distributed quasi-Newton algorithm was proposed for solving the unconstrained consensus optimization, where the network nodes work collaboratively to minimize the sum of their locally known convex costs. The new algorithm used only the first-order derivative information of the cost function. By choosing a positive definite diagonal matrix as the quasi-Newton correction of the inverse of the Hesse matrix of the cost function at each iteration, the proposed algorithm successfully overcame the difficulty caused by the non-sparsity of the correction matrix in the implementation of distribution, and greatly decreased computation and storage pressure. Under suitable conditions, the proposed distributed quasi-Newton algorithm was proved to be globally convergent with local linear convergence rate and its superiority was verified by numerical simulations.

Key words:unconstrained consensus optimization; distributed quasi-Newton algorithm; global convergence; linear convergence

收稿日期：2016-01-05

作者簡(jiǎn)介：于慧慧(1991—)，女，山東菏澤人，碩士研究生，主要從事分布式優(yōu)化算法的研究.E-mail：yxh622@163.com 王永麗(1977—)，女，山東棲霞人，博士，副教授，主要從事非線性優(yōu)化理論與算法、分布式優(yōu)化算法、并行計(jì)算的研究，本文通信作者.E-mail：wangyongli@sdkd.net.cn

中圖分類號(hào)：O224

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1672-3767(2016)03-0112-07