Nonlinear Programming Methods for Distributed Optimization

Abstract

In this paper we investigate how standard nonlinear programming algorithms can be used to solve constrained optimization problems in a distributed manner. The optimization setup consists of a set of agents interacting through a communication graph that have as common goal the minimization of a function expressed as a sum of (possibly non-convex) differentiable functions. Each function in the sum corresponds to an agent and each agent has associated an equality constraint. By re-casting the distributed optimization problem into an equivalent, augmented centralized problem, we show that distributed algorithms result naturally from applying standard nonlinear programming tech- niques. Due to the distributed formulation, the standard assumptions and convergence results no longer hold. We emphasize what changes are necessary for convergence to still be achieved for three algorithms: two algorithms based on Lagrangian methods, and an algorithm based the method of multipliers. The changes in the convergence results are necessary mainly due to the fact that the (local) minimizers of the lifted optimization problem are not regular, as a results of the distributed formulation. Unlike the standard algorithm based on the method of multipliers, for the distributed version we cannot show that the theoretical super-linear convergence rate can be achieved.