In this paper we study the multi-agent saddle-point problems where multiple agents try to collectively optimize a sum of local convex–concave functions, each of which is available to one specific agent in the network. We propose a distributed primal–dual subgradient method under the constraint that agents can only communicate quantized information. The method can be implemented over a time-varying network while satisfying some standard connectivity conditions. We provide convergence results and convergence rate estimates for the proposed method. In particular, we provide an error bound on its convergence rate to highlight the dependence on the quantization resolution. We have also provided a numerical example to show the effectiveness of the proposed method.
BoydSGhoshAPrabhakarB. (2006) Randomized gossip algorithms. IEEE Transactions on Information Theory52(6): 2508–2530.
2.
CaoYRenW (2010) Optimal linear-consensus algorithms: an LQR perspective. IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics40(3): 819–830.
3.
DuchiJAgarwalAWainwrightM (2012) Dual averaging for distributed optimization: convergence analysis and network scaling. IEEE Transactions on Automatic Control57(3): 592–606.
4.
JadbabaieALinJMorseAS (2003) Coordination of groups of mobile autonomous agents using nearest neighbor rules. IEEE Transactions on Automatic Control48(6): 988–1001.
5.
JohanssonBKeviczkyTJohanssonM. (2008) Subgradient methods and consensus algorithms for solving convex optimization problems. In: Proceedings of the 47th IEEE Conference on Decision and Control, Cancun, Mexico, 2008, pp. 4185–4190.
LuJHoDWCKurthsJ (2009) Consensus over directed static networks with arbitrary finite communication delays. Physical Review E80(6): 066121.
8.
LuJTangCYRegierPR. (2011) Gossip algorithms for convex consensus optimization over networks. IEEE Transactions on Automatic Control56(12): 2917–2923.
9.
MateiIBarasJS (2011) Performance evaluation of the consensus-based distributed subgradient method under random communication topologies. IEEE Journal of Selected Topics in Signal Processing5(4): 754–771.
10.
NedicAOzdaglarA (2009a) Subgradient methods for saddle-point problems. Journal of Optimization Theory and Applications142(1): 205–228.
11.
NedicAOzdaglarA (2009b) Distributed subgradient methods for multi-agent optimization. IEEE Transactions on Automatic Control54(1): 48–61.
12.
NedicAOzdaglarA (2010) Cooperative distributed multi-agent optimization. In: PalomarDPEldarYC (eds), Convex Optimization in Signal Processing and Communications. Cambridge: Cambridge University Press, pp. 340–386.
13.
NedicAOzdaglarAParriloPA (2010) Constrained consensus and optimization in multi-agent networks. IEEE Transactions on Automatic Control55(4): 922–938.
Olfati-SaberRMurrayRM (2004) Consensus problems in networks of agents with switching topology and time-delays. IEEE Transactions on Automatic Control49(9): 1520–1533.
16.
RenWBeardRW (2005) Consensus seeking in multiagent systems under dynamically changing interaction topologies. IEEE Transactions on Automatic Control50(5): 655–661.
17.
RenWBeardRWAtkinsEM (2007) Information consensus in multivehicle cooperative control. IEEE Control Systems Magazine27(2): 71–82.
18.
XiaoLBoydS (2004) Fast linear iterations for distributed averaging. Systems and Control Letters53(1): 65–78.
19.
YuanDXuSZhaoH (2011) Distributed primal–dual subgradient method for multiagent optimization via consensus algorithms. IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics41(6): 1715–1724.
20.
YuanDXuSZhaoH. (2010) Distributed average consensus via gossip algorithm with real-valued and quantized data for 0 < q < 1. Systems and Control Letters59(9): 536–542.
21.
YuanDXuSZhaoH. (2012) Distributed dual averaging method for multi-agent optimization with quantized communication. Systems and Control Letters61(11): 1053–1061.
22.
ZhuMMartinezS (2012) On distributed convex optimization under inequality and equality constraints. IEEE Transactions on Automatic Control57(1): 151–164.
