A Proximal Dual Consensus ADMM Method for Multi-Agent Constrained Optimization
Tsung-Hui Chang⋆, Member, IEEE The work of Tsung-Hui Chang is supported by Ministry of Science and Technology, Taiwan (R.O.C.), under Grant NSC 102-2221-E-011-005-MY3. ⋆Tsung-Hui Chang is the corresponding author. Address: Department of Electronic and Computer Engineering, National Taiwan University of Science and Technology, Taipei 10607, Taiwan, (R.O.C.). E-mail:
Abstract
This paper studies efficient distributed optimization methods for multi-agent networks. Specifically, we consider a convex optimization problem with a globally coupled linear equality constraint and local polyhedra constraints, and develop distributed optimization methods based on the alternating direction method of multipliers (ADMM). The considered problem has many applications in machine learning and smart grid control problems. Due to the presence of the polyhedra constraints, agents in the existing methods have to deal with polyhedra constrained subproblems at each iteration. One of the key issues is that projection onto a polyhedra constraint is not trivial, which prohibits from closed-form solutions or the use of simple algorithms for solving these subproblems. In this paper, by judiciously integrating the proximal minimization method with ADMM, we propose a new distributed optimization method where the polyhedra constraints are handled softly as penalty terms in the subproblems. This makes the subproblems efficiently solvable and consequently reduces the overall computation time. Furthermore, we propose a randomized counterpart that is robust against randomly ON/OFF agents
中文速览
多智能体网络中的分布式优化经常遇到多面体约束（polyhedra constraint），而把变量投影到这类约束集上没有简单的闭合解，导致每轮迭代计算量大、整体耗时长。针对这一痛点，论文将近端最小化方法（proximal minimization method）与交替方向乘子法（ADMM，alternating direction method of multipliers）巧妙结合，提出了 PDC-ADMM 方法——把多面体约束"软化"为子问题中的惩罚项，使每个智能体只需求解带简单约束的子问题，从而大幅降低每步计算开销；同时还提出了随机化版本，可容忍智能体随机在线/离线和通信链路不完善的情况。理论分析证明两种方法均具有 O(1/k) 的最坏情况收敛速率，数值实验也表明相比已有的 DC-ADMM 方法，所提方法在计算时间上有显著优势，对机器学习和智能电网等实际应用具有重要参考价值。
原文 arXiv:1409.3307;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1409.3307v1