  We consider a generic decentralized constrained optimization problem over
static, directed communication networks, where each agent has exclusive access
to only one convex, differentiable, local objective term and one convex
constraint set. For this setup, we propose a novel decentralized algorithm,
called DAGP (Double Averaging and Gradient Projection), based on local
gradients, projection onto local constraints, and local averaging. We achieve
global optimality through a novel distributed tracking technique we call
distributed null projection. Further, we show that DAGP can be used to solve
unconstrained problems with non-differentiable objective terms with a problem
reduction scheme. Assuming only smoothness of the objective terms, we study the
convergence of DAGP and establish sub-linear rates of convergence in terms of
feasibility, consensus, and optimality, with no extra assumption (e.g. strong
convexity). For the analysis, we forego the difficulties of selecting Lyapunov
functions by proposing a new methodology of convergence analysis in
optimization problems, which we refer to as aggregate lower-bounding. To
demonstrate the generality of this method, we also provide an alternative
convergence proof for the standard gradient descent algorithm with smooth
functions. Finally, we present numerical results demonstrating the
effectiveness of our proposed method in both constrained and unconstrained
problems. In particular, we propose a distributed scheme by DAGP for the
optimal transport problem with superior performance and speed.
