Distributed Newton Optimization with Maximized Convergence Rate

YONG XU; DAMIÁN MARELLI; ZENGHONG HUANG; MINYUE FU

IEEE TRANSACTIONS ON AUTOMATIC CONTROL

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC

Lugar: New York; Año: 2021

0018-9286

The distributed optimization problem is set up in a collection of nodes interconnected via a communication network. The goal is to find the minimizer of a global objective function formed by the sum local functions known at individual nodes. A number of methods are available for addressing this problem, having different advantages. The goal of this work is to achieve the maximum possible convergence rate. As the first step towards this end, we propose a new method which we show converges faster than other available options. As the second step towards our goal we complement the proposed method with a fully distributed method for estimating the optimal step size that maximizes the convergence rate. We provide theoretical guarantees for the convergence of the resulting method in a neighborhood of the solution. We present numerical experiments showing that, when using the same step size, our method converges significantly faster than its rivals. Experiments also show that the distributed step size estimation method achieves an asymptotic convergence rate very close to the theoretical maximum.