  We study the problem of minimizing a sum of convex objective functions where
the components of the objective are available at different nodes of a network
and nodes are allowed to only communicate with their neighbors. The use of
distributed gradient methods is a common approach to solve this problem. Their
popularity notwithstanding, these methods exhibit slow convergence and a
consequent large number of communications between nodes to approach the optimal
argument because they rely on first order information only. This paper proposes
the network Newton (NN) method as a distributed algorithm that incorporates
second order information. This is done via distributed implementation of
approximations of a suitably chosen Newton step. The approximations are
obtained by truncation of the Newton step's Taylor expansion. This leads to a
family of methods defined by the number $K$ of Taylor series terms kept in the
approximation. When keeping $K$ terms of the Taylor series, the method is
called NN-$K$ and can be implemented through the aggregation of information in
$K$-hop neighborhoods. Convergence to a point close to the optimal argument at
a rate that is at least linear is proven and the existence of a tradeoff
between convergence time and the distance to the optimal argument is shown.
Convergence rate, several practical implementation matters, and numerical
analyses are presented in a companion paper [3].
