Newton-Raphson consensus for distributed convex optimization

Abstract — We study the problem of unconstrained distributed optimization in the context of multi-agents systems subject to limited communication connectivity. In particular we focus on the minimization of a sum of convex cost functions, where each component of the global function is available only to a specific agent and can thus be seen as a private local cost. The agents need to cooperate to compute the minimizer of the sum of all costs. We propose a consensus-like strategy to estimate a Newton-Raphson descending update for the local estimates of the global minimizer at each agent. In particular, the algorithm is based on the separation of time-scales principle and it is proved to converge to the global minimizer if a specific parameter that tunes the rate of convergence is chosen sufficiently small. We also provide numerical simulations and compare them with alternative distributed optimization strategies like the Alternating Direction Method of Multipliers and the Distributed Subgradient Method. Index Terms — distributed optimization, convex optimization, consensus algorithms, multi-agent systems, Newton-Raphson methods I