TY - GEN
T1 - A Proximal Gradient Algorithm for Composite Consensus Optimization over Directed Graphs
AU - Zeng, Jinshan
AU - He, Tao
AU - Ouyang, Shikang
AU - Wang, Mingwen
AU - Chang, Xiangyu
N1 - Publisher Copyright:
© 2017 IEEE.
PY - 2018/8/24
Y1 - 2018/8/24
N2 - This paper proposes a decentralized algorithm for solving a consensus optimization problem defined in a directed networked multi-agent system, where the local objective functions have the smooth+nonsmooth composite form. Examples of such problems include decentralized compressed sensing and constrained quadratic programming problems, as well as many decentralized regularizatlon problems. We extend the existing algorithms PG-EXTRA and ExtraPush to a new algorithm PG-ExtraPush for composite consensus optimization over a directed network. This algorithm takes advantage of the proximity operator like in PG-EXTRA to deal with the nonsmooth term, and employs the push-sum protocol like in ExtraPush to tackle the bias introduced by the directed network. We show that PG-ExtraPush converges to an optimal solution under the boundedness assumption. In numerical experiments, with a proper step size, PG-ExtraPush performs surprisingly linear rates, and is significantly faster than Subgradient-Push, even when we hand-optimize the step sizes for the latter.
AB - This paper proposes a decentralized algorithm for solving a consensus optimization problem defined in a directed networked multi-agent system, where the local objective functions have the smooth+nonsmooth composite form. Examples of such problems include decentralized compressed sensing and constrained quadratic programming problems, as well as many decentralized regularizatlon problems. We extend the existing algorithms PG-EXTRA and ExtraPush to a new algorithm PG-ExtraPush for composite consensus optimization over a directed network. This algorithm takes advantage of the proximity operator like in PG-EXTRA to deal with the nonsmooth term, and employs the push-sum protocol like in ExtraPush to tackle the bias introduced by the directed network. We show that PG-ExtraPush converges to an optimal solution under the boundedness assumption. In numerical experiments, with a proper step size, PG-ExtraPush performs surprisingly linear rates, and is significantly faster than Subgradient-Push, even when we hand-optimize the step sizes for the latter.
UR - https://www.scopus.com/pages/publications/85053835205
U2 - 10.1109/CYBER.2017.8446454
DO - 10.1109/CYBER.2017.8446454
M3 - 会议稿件
AN - SCOPUS:85053835205
SN - 9781538604892
T3 - 2017 IEEE 7th Annual International Conference on CYBER Technology in Automation, Control, and Intelligent Systems, CYBER 2017
SP - 825
EP - 830
BT - 2017 IEEE 7th Annual International Conference on CYBER Technology in Automation, Control, and Intelligent Systems, CYBER 2017
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 7th IEEE Annual International Conference on CYBER Technology in Automation, Control, and Intelligent Systems, CYBER 2017
Y2 - 31 July 2017 through 4 August 2017
ER -