Distributed accelerated optimization algorithms: Insights from an ODE
- PDF / 309,433 Bytes
- 9 Pages / 612 x 792 pts (letter) Page_size
- 10 Downloads / 216 Views
. Article .
Print-CrossMark
https://doi.org/10.1007/s11431-020-1596-8
Distributed accelerated optimization algorithms: Insights from an ODE CHEN RuiJuan1, YANG Tao2* & CHAI TianYou2 1 School 2 State
of Artificial Intelligence and Automation, Huazhong University of Science and Technology, Wuhan 430074, China; Key Laboratory of Synthetical Automation for Process Industries, Northeastern University, Shenyang 110819, China Received March 18, 2020; accepted April 10, 2020; published online June 19, 2020
In this paper, we consider the distributed optimization problem, where the goal is to minimize the global objective function formed by a sum of agents’ local smooth and strongly convex objective functions, over undirected connected graphs. Several distributed accelerated algorithms have been proposed for solving such a problem in the existing literature. In this paper, we provide insights for understanding these existing distributed algorithms from an ordinary differential equation (ODE) point of view. More specifically, we first derive an equivalent second-order ODE, which is the exact limit of these existing algorithms by taking the small step-size. Moreover, focusing on the quadratic objective functions, we show that the solution of the resulting ODE exponentially converges to the unique global optimal solution. The theoretical results are validated and illustrated by numerical simulations. distributed accelerated optimization algorithms, exponential convergence, ordinary differential equation Citation:
Chen R J, Yang T, Chai T Y. Distributed accelerated optimization algorithms: Insights from an ODE. Sci China Tech Sci, 2020, 63, https://doi.org/10.1007/s11431-020-1596-8
1 Introduction For a network of agents, each of which has a local convex objective function, the goal of the distributed optimization problem is to minimize the global objective function formed by a sum of the local objective functions. The distributed optimization problem has a long history which can be traced back to the seminal works [1, 2]. Recently, distributed optimization has gained renewed interests due to its various applications, including source localization [3], power systems [4], large scale computation in machine learning [5] and sensor networks [6]. Most existing distributed optimization algorithms are based on the consensus theory [7–10] and the distributed (sub)gradient descent (DGD) method [11, 12], (see, e.g., refs. [13–19] and references therein). The DGD algorithm has been extended in several directions *Corresponding author (email: [email protected])
to handle more realistic scenarios, such as constrained optimization problems, directed time-varying networks, communication networks with delays and packet drops. However, the drawback of the DGD algorithm and its variants is that the convergence rate is rather slow due to the diminishing stepsize. With a fixed step-size, the DGD algorithm converges fast, but only to a neighborhood of an optimal point [20, 21]. Recent studies focused on developing distributed accelerated
Data Loading...
