呂凈閣，李德權(quán)

（安徽理工大學(xué) 數(shù)學(xué)與大數(shù)據(jù)學(xué)院，淮南 232000）

多個(gè)體系統(tǒng)是由大量自主個(gè)體或節(jié)點(diǎn)相互之間通過局部信息交流而構(gòu)成的網(wǎng)絡(luò)化系統(tǒng)［1］，其中每個(gè)個(gè)體或節(jié)點(diǎn)獨(dú)立地進(jìn)行計(jì)算和通信，并通過與鄰居個(gè)體相互協(xié)調(diào)可有效處理復(fù)雜任務(wù)。正因?yàn)槎鄠€(gè)體系統(tǒng)的自主性、智能性和協(xié)同一致性等特點(diǎn)，近年來隨著計(jì)算能力和網(wǎng)絡(luò)技術(shù)的快速發(fā)展而備受研究者的關(guān)注，并在眾多領(lǐng)域有著廣泛的應(yīng)用。作為多個(gè)體系統(tǒng)極為重要的一個(gè)應(yīng)用領(lǐng)域，分布式優(yōu)化問題研究的是系統(tǒng)中的n個(gè)個(gè)體如何協(xié)同地求解如下最小化問題：

其中，x∈R是所有個(gè)體所知的狀態(tài)決策變量，fi:R→R是個(gè)體i的局部目標(biāo)函數(shù)，個(gè)體間通過交流各自的本地局部目標(biāo)函數(shù)和狀態(tài)信息來求解問題（1）。解決問題（1）的典型分布式算法包括分布式（次）梯度算法（DG）［2，3］、對偶平均（DDA）［4，5］、交替方向乘子法（ADMM）以及變體［6-9］等方法。目前，這些分布式優(yōu)化算法廣泛應(yīng)用于機(jī)器學(xué)習(xí)、無線傳感器網(wǎng)絡(luò)等領(lǐng)域。分布式（次）梯度算法主要通過計(jì)算每個(gè)局部目標(biāo)函數(shù)的（次）梯度以及個(gè)體間的平均狀態(tài)來尋求最優(yōu)解；而對偶平均則針對凸但非平滑損失函數(shù)，通過對函數(shù)求一階（次）梯度來解決分布式問題；ADMM算法則通過引入拉格朗日函數(shù)完成對原問題的轉(zhuǎn)換而形成對偶問題，在對原始變量迭代的同時(shí)進(jìn)行對偶變量的迭代來尋求最優(yōu)解。

上述分布式優(yōu)化算法通常要求系統(tǒng)中的個(gè)體在每一次迭代時(shí)將本地估計(jì)傳遞給鄰居個(gè)體來尋求一致最優(yōu)解。但當(dāng)個(gè)體的狀態(tài)包括隱私信息時(shí)，例如醫(yī)院里的患者信息庫有疾病種類或者年齡等隱私信息，這種信息的直接交換會(huì)因?yàn)殡[私泄漏而導(dǎo)致安全隱患［10］。為了有效確保隱私，近年來隱私保護(hù)成為分布式優(yōu)化研究的一個(gè)熱點(diǎn)問題。最常見的隱私保護(hù)算法是差分隱私［11,12］，它通過在狀態(tài)上添加精心設(shè)計(jì)的擾動(dòng)來掩蓋敏感信息以達(dá)到保護(hù)隱私的效果，然而添加的擾動(dòng)會(huì)影響算法的收斂性；另外一種是信息加密［13-15］，但傳統(tǒng)的加密方法在沒有第三方協(xié)助的情況下難以直接應(yīng)用于分布式優(yōu)化問題。

本文主要研究基于共軛對偶梯度算法的隱私保護(hù)性，采用的同態(tài)加密［16］被證實(shí)能夠?qū)Ψ植际接?jì)算環(huán)境下的用戶隱私進(jìn)行有效保護(hù)。同態(tài)加密可分為部分同態(tài)加密、淺同態(tài)加密和全同態(tài)加密。本文通過結(jié)合部分同態(tài)加密技術(shù)和共軛對偶梯度算法提出一種具有隱私保護(hù)的共軛對偶梯度算法2（PP-CDG），與基于差分隱私的分布式優(yōu)化算法不同，算法2不僅能保證找到最優(yōu)解，也能夠確保多個(gè)體系統(tǒng)中個(gè)體的隱私信息不被竊取。

1 問題描述

圖論中，將n個(gè)個(gè)體構(gòu)成的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)用一個(gè)時(shí)變無向圖Gk(V,Ek,Ak)來表示，其中k表示時(shí)刻，V=(1,2,...,n)是通信網(wǎng)絡(luò)中的個(gè)體集，Ek?V×V代表個(gè)體之間的邊集，Ak∈Rn×n為拓?fù)鋱D對應(yīng)的權(quán)重矩陣；(j,i)∈Ek表示在k時(shí)刻個(gè)體j和i之間有邊相連，代表個(gè)體i的鄰居集合，代表個(gè)體i的度，代表度矩陣；若每個(gè)個(gè)體之間都有一條路徑，則稱圖為連通圖；本文假設(shè)網(wǎng)絡(luò)拓?fù)鋱D是無向圖，則其權(quán)重矩陣Ak是對稱矩陣，元素滿足：

考慮n個(gè)個(gè)體構(gòu)成的無向時(shí)變系統(tǒng)，共軛對偶梯度將問題（1）轉(zhuǎn)化為

其中，每個(gè)個(gè)體i有著局部的目標(biāo)函數(shù)fi:R→R。

假設(shè)1［17］每個(gè)個(gè)體的局部目標(biāo)函數(shù)fi,i∈V是1-強(qiáng)凸的，即?x,y∈Κ和fi在x處的次梯度?fi(x)有

假設(shè)2（1）最優(yōu)解存在；（2）Κ,C是閉凸集

2 共軛對偶問題

共軛函數(shù)的定義是：di(w)=supx∈Κ(w?x-fi(x))，受文獻(xiàn)［18，19］啟發(fā)，通過添加如下正則項(xiàng)防止共軛函數(shù)震蕩，且保證共軛函數(shù)的界更小，同時(shí)也便于有效地進(jìn)行對偶轉(zhuǎn)換：

相應(yīng)地，可將優(yōu)化問題（2）轉(zhuǎn)化為如下對偶形式：

式（3）表示的是一類典型的資源優(yōu)化分配問題［20，21］，可以采用基于梯度下降法或加權(quán)梯度算法進(jìn)行求解。進(jìn)一步地，由共軛函數(shù)的可微性可得：

再由假設(shè) 1，?di利普希茨連續(xù)［18］其常數(shù)為Γi=(θi+1)/θi=2。因此，?D的利普希茨常數(shù)為Γ=(θmin+1)/θmin=2 。

假設(shè)3 （周期連通性）存在B∈[1,∞)，使得對任何k≥0，在一個(gè)周期B內(nèi)，圖是連通的。

優(yōu)化問題（3）可以通過如下共軛對偶梯度算法來解決：選取對偶變量初始點(diǎn)w0且滿足1T?w0=0,w0Tw0=0，進(jìn)而迭代如下：

其中α＞0是固定步長。則（5）的矩陣形式為：

其中Pk=I-αLk是Perron矩陣，Lk是時(shí)變拉普拉斯矩陣，其定義為：

（6）式可以通過下述算法1來實(shí)現(xiàn)：

算法1共軛對偶梯度（CDG）

1：個(gè)體i選擇初始值并令

2：fork=0,1,...do

3：通訊：個(gè)體i∈V將其狀態(tài)傳遞給鄰居

4：接收到鄰居的狀態(tài)后，個(gè)體i更新對偶變量：

6：對沒有鄰居的個(gè)體保留前一時(shí)刻的狀態(tài)即

3 具有隱私保護(hù)的分布式共軛對偶梯度算法

和分布式優(yōu)化算法［2-8］類似，算法1要求所有個(gè)體在每一次迭代時(shí)，將本地估計(jì)傳遞給鄰居來達(dá)成共識，這易造成信息泄露［1］。為了避免信息在交流中被敵對個(gè)體竊取，已經(jīng)提出了許多保護(hù)隱私的方法，如在文獻(xiàn)［11，12］中提出的差分隱私，通過在狀態(tài)上添加擾動(dòng)來保護(hù)隱私，但添加的擾動(dòng)會(huì)影響算法的收斂性；文獻(xiàn)［13-15］中提出的加密（encryption），如全同態(tài)加密，在沒有第三方協(xié)助時(shí)卻難以直接應(yīng)用于分布式優(yōu)化。本文將Paillier Cryptosystem機(jī)制和算法1結(jié)合，進(jìn)行隱私保護(hù)。

3.1 同態(tài)加密

文獻(xiàn)［16］中介紹了public-key cryptographies密碼系統(tǒng)，使用兩種鑰匙：可以被任何個(gè)體用來加密信息的公鑰和用來解密的私鑰。此密碼系統(tǒng)有：RSA、EL-Gamal和 Paillier［7］。本文將采用的是Paillier Cryptosystem機(jī)制，與其他算法相比，該加密方法不僅適用于分布式系統(tǒng)、具有隱私保護(hù)性又能保證算法的收斂。具體算法如下：

（1）選擇兩個(gè)素?cái)?shù)p,q令n=pq，g=n+1，λ=(p-1)(q-1)。

（2）令μ=?(n)-1modn是?(n)的模乘逆.

（3）公鑰kp=(n,g)，私鑰ks=(λ,μ)

加密(c=ε(m))

定義：其中g(shù)cd()是最大公約數(shù).

這是一個(gè)思維難度較大、有多種結(jié)論的開放性問題，沒想到竟然有學(xué)生提出想知道鄧爺爺植樹的愿望是什么？教學(xué)目標(biāo)自然達(dá)成。我覺得這是一節(jié)高質(zhì)量的課堂。

（4）選擇一個(gè)隨機(jī)數(shù)

（5）密文是c=gm?rnmodn2其中

解密(m=D(c))

（6）定義整數(shù)分解函數(shù)Τ(μ)=(μ-1)/n.

（7）明文是m=Τ(cλmodn2)?μmodn

3.2 具有隱私保護(hù)的共軛對偶梯度算法

本節(jié)將結(jié)合上述Paillier Cryptosystem機(jī)制與算法1，確保在解決分布式問題（2）時(shí)可以對多個(gè)體系統(tǒng)中個(gè)體的隱私進(jìn)行保護(hù)。為此構(gòu)造權(quán)重對：，其中僅為個(gè)體i所知［7］。該構(gòu)造方法不僅可以防止兩個(gè)交互個(gè)體在交流中推斷彼此的狀態(tài)信息從而進(jìn)行了隱私保護(hù)，而且還能確保算法的收斂性。

算法2隱私保護(hù)的共軛對偶梯度算法（PP-CDG）

個(gè)體i選擇初始值并令

輸入：；輸出：

（1）個(gè)體i用公鑰kpi對加密得到

（2）個(gè)體i將和公鑰kpi傳遞給鄰居個(gè)體j∈Ni

（3）個(gè)體j∈Ni用公鑰對加密得到，通過同態(tài)性得

（4）個(gè)體j∈Ni計(jì)算權(quán)重為的差異再將傳遞給個(gè)體i

（5）個(gè)體i用私鑰ksi對進(jìn)行解密再乘上得到

（6）計(jì)算

（7）通過計(jì)算得到

（8）令k=k+1

對算法2，有下面幾點(diǎn)說明：

（1）的構(gòu)造是保護(hù)隱私的關(guān)鍵；

（2）對負(fù)狀態(tài)加密得到是因?yàn)樵摲椒ň哂屑臃ㄍ瑧B(tài)性；

（3）個(gè)體i的狀態(tài)以及中間狀態(tài)被加密得以保護(hù)。

4PP-CDG收斂性分析

算法收斂性分析與步長選擇密切相關(guān)，本文選取固定步長

假設(shè)4 拉普拉斯矩陣Lk的特征值滿足

假設(shè)4和（8）能夠保證Perron矩陣Pk是正定可逆矩陣。

引理1 當(dāng)假設(shè)1、2成立，wk是算法1生成的對偶序列，則對偶函數(shù)是有界函數(shù)，即存在一個(gè)正數(shù)M，使得對任意k≥0，序列wk成立

證明：由假設(shè)1知D(w)是可微的，故在閉區(qū)間C上是連續(xù)的，由閉區(qū)間上的連續(xù)函數(shù)一定是有界易知引理1成立。

定義，其中B是假設(shè)3中的周期，是正定可逆矩陣，為便于證明，令

其中 ΛΓ=diag(Γ1,Γ2,…,Γn)是對偶梯度的利普希茨常數(shù)組成的對角陣且是2I。

引理2 當(dāng)假設(shè)1、2、3、4成立，wk是算法1生成的對偶序列且步長滿足（8）、（9），則有：

證明：一方面由范數(shù)性質(zhì)得

另一方面由三角不等式得：

由?D的利普希茨連續(xù)性和三角不等式得：

則由上述三式易得

引理3如果假設(shè)1、2、3、4成立，wk是算法1生成的對偶序列且步長滿足（8）、（9），則對偶函數(shù)滿足周期性遞減，即：

證明：由范數(shù)的性質(zhì)得

再利用D(w)的可微性、假設(shè)4以及引理2即可得結(jié)論成立。

有了上面準(zhǔn)備知識，下面證明本文對偶函數(shù)的收斂性。

定理1 如果假設(shè)1、2、3、4成立，wk是算法1生成的對偶序列且步長滿足（8）、（9），并令D?是對偶函數(shù)的最優(yōu)解，則對偶函數(shù)收斂即limk→∞D(zhuǎn)(wk)=D?。

證明：由引理1、2、3知對偶函數(shù)序列存在極限，即存在任意小的正數(shù)ε＞0，使得當(dāng)時(shí)，由引理3知：

其中，則有

故對偶函數(shù)序列是平方收斂的。（11）式的第二個(gè)不等式主要依據(jù)下式得來的：

由假設(shè)3知，則：

從而有經(jīng)過迭代和換算可以得到對偶函數(shù)周期性的誤差為：

而可得

進(jìn)一步地，下面定理2證明原函數(shù)以及迭代序列收斂到最優(yōu)值。

定理2 如果假設(shè)1、2、3、4成立，設(shè)是算法1生成的原始序列且步長滿足（8）、（9），則有：

證明：由假設(shè)1知問題（2）和（3）強(qiáng)對偶，則對偶函數(shù)收斂時(shí)原始函數(shù)序列亦收斂且最優(yōu)值滿足F?=-D?，由凸函數(shù)的性質(zhì)，

由定理1和假設(shè)5知 limk→∞xk=x?；由對偶函數(shù)的定義知

故原函數(shù)的誤差：

因?qū)ε夹蛄惺窃陂]區(qū)間生成的，故有界，即存在正數(shù)A，使得對任意k≥0均成立故原始函數(shù)序列收斂。

下面證明算法2能收斂到最優(yōu)解。

定理3 如果隨機(jī)從(0,1)中選擇，則算法2能收斂到最優(yōu)解。

證明：由于故選取步長

滿足（8）式，則算法2能夠收斂到最優(yōu)解。

文章中個(gè)體狀態(tài)包含的敏感信息是，算法2意味著當(dāng)信息被加密之后，其他個(gè)體就不能推斷出其敏感信息。下面定理4和定理5證明了敵對個(gè)體通過收集多步驟的中間信息但卻不能獲取鄰居個(gè)體的狀態(tài)和函數(shù)信息。

定理4 假設(shè)所有個(gè)體都按照算法2進(jìn)行迭代，則敵對個(gè)體i不能推斷出鄰居個(gè)體j的狀態(tài)信息，除非

證明：從算法2中的第五步可知敵對個(gè)體i在第k次迭代能夠得到加權(quán)差異：

而中間變量由于被加密不為個(gè)體i所知。假若個(gè)體i通過收集K步的權(quán)重差異來推斷個(gè)體j的狀態(tài)信息：

這里已知，即2(K+1)個(gè)等式4(K+1)個(gè)未知量，方程組的解不唯一，故個(gè)體i不能推斷出個(gè)體j的狀態(tài)信息

定理5 假設(shè)系統(tǒng)中的個(gè)體都按照算法2進(jìn)行迭代，則敵對個(gè)體i不能推斷出鄰居個(gè)體j的隱私函數(shù)fj(xj)。

證明：假設(shè)敵對個(gè)體i通過收集K步信息來推斷鄰居個(gè)體j的函數(shù)信息，由

可以得到

其中?fi(xi)是函數(shù)fi在xi處的次梯度。敵對個(gè)體i可以建立K個(gè)等式：

在這K個(gè)等式中(k=1,...,K)是未知的，而通過算法2知當(dāng)個(gè)體j只有唯一的鄰居m時(shí)，

是已知的，否則是未知的。那么K個(gè)等式中有大于K個(gè)未知量，故個(gè)體i不能推斷出鄰居個(gè)體j的隱私函數(shù)fj(xj)。

5 結(jié)論

本文主要介紹了基于梯度下降法的分布式共軛對偶梯度算法（CDG）的隱私保護(hù)，解決了分布式優(yōu)化中可能存在的隱私隱患，當(dāng)目標(biāo)函數(shù)強(qiáng)凸、對應(yīng)的對偶函數(shù)可微時(shí)證明了所提算法的收斂性；最后證明了敵對個(gè)體即使收集多步驟的中間信息也不能推斷出鄰居個(gè)體的狀態(tài)信息和局部目標(biāo)函數(shù)。本文研究的是無向時(shí)變網(wǎng)絡(luò)且目標(biāo)函數(shù)是強(qiáng)凸，對有向非平衡網(wǎng)絡(luò)下的PP-CGD算法進(jìn)行研究將是下一步的主要工作。

［1］余智欣，黃天戍，楊乃擴(kuò)，等.一種新型的分布式隱私保護(hù)計(jì)算模型及其應(yīng)用［J］.西安交通大學(xué)學(xué)報(bào)，2007，41（08）：954-958.

［2］Nedic A，Ozdaglar A.Distributed subgradient methods for multiagent optimization［J］.IEEE Transactions on Automatic Control，2009，54（01）：48-61.

［3］Lobel I，Ozdaglar A.Distributed subgradient methods for convex optimization over random networks［J］.IEEE Transactions on Automatic Control，2011，56（06）：1291-1306.

［4］Agarwal A，Wainwright MJ，Duchi JC.Distributed dualaveraging in networks［C］.In Advancesin NeuralInformation Processing Systems，2010，23：550-558.

［5］Duchi JC，Agarwal A，Wainwright MJ.Dual averaging for distributed optimization：Convergence analysis and network scaling［J］.IEEE Transactions on Automatic control，2012，57（03）：592-606.

［6］Boyd S，Parikh N，Chu E，et al.Distributed optimization and statistical learning via the alternating direction method of multipliers［J］. Foundations &Trends in Machine Learning，2011，3（01）：1-122.

［7］Zhang C，Wang Y.Privacy-preserving Decentralized OptimizationBasedonADMM［J］.2017，arXiv：1707.04338.

［8］He BS，Xu HK，Yuan X.On the proximal jacobian decomposition of ALM for multiple-block separable convex minimization problemsand itsrelationship to ADMM［J］.Journal of Scientif i c Computing，2016，66（03）：1204-1217.

［9］許浩鋒，凌青.分布式在線交替方向乘子法［J］.計(jì)算機(jī)應(yīng)用，2015，35（06）：1595-1599.

［10］王杰，趙銘，于曉.云存儲(chǔ)數(shù)據(jù)安全關(guān)鍵技術(shù)研究［J］.長春理工大學(xué)學(xué)報(bào)：自然科學(xué)版，2014（02）：147-150.

［11］Huang ZQ，Mitra S，Vaidya N.Differentially private distributed optimization［C］.In Proceedings of the 2015 InternationalConference on Distributed Computing and Networking.2015：1-10.

［12］Han S，Topcu U，Pappas GJ.Differentially private distributed constrained optimization［J］.IEEE Transactions on Automatic Control，2017，62（1）：50-64.

［13］LazzerettiR，Horn S，Braca P，etal.Secure multi-party consensus gossip algorithms［C］.IEEE International Conference on Acoustics，Speech and Signal Processing.IEEE，2014：7406-7410.

［14］Freris NM，Patrinos P.Distributed computing over encrypted data［C］.Communication，Control&Computing.IEEE，2017：1116-1122.

［15］Gentry，Craig.Fully homomorphic encryption using ideal lattices［C］.ACM Symposium on Theory of Computing，2009：169-178.

［16］鞏林明，李順東，郭奕旻.同態(tài)加密的發(fā)展及應(yīng)用［J］.中興通訊技術(shù)，2016，22（01）：26-29.

［17］Bertsekas D P.Convex optimization theory［M］.北京：清華大學(xué)出版社，2011.

［18］Wu X，Lu J.Fenchel Dual Gradient Methods for Distributed Convex Optimization over Time-varying Networks［C］.IEEE 56th Annual Conference on Decision and Control（CDC）.2017：2894-2899.

［19］Bach F.Duality between subgradient and conditional gradient methods［J］.SIAM Journal on Optimization，2015，25（01）：491-492.

［20］Xiao L，Boyd S.Optimalscaling ofa gradient method for distributed resource allocation［J］.Journal of Optimization Theory&Applications，2006，129（03）：469-488.

［21］Lakshmanan H，De Farias DP.Decentralized Resource Allocation in Dynamic Networks of Agents［J］.SIAM Journal on Optimization，2008，19（02）：911-940.