A Decomposition/Synchronization Scheme for Formulating and Solving Optimization Problems*

Large-scale optimization problems, even when convex, can be challenging to solve directly. Recently, a considerable amount of research has focused on developing methods for solving such optimization problems in a distributed manner. The assumption that is usually made is that the global objective function is a sum of convex functions, which is restrictive. In this paper, we automatically decompose a convex function to be minimized into a sum of smaller functions that may or may not be convex and assign each sub-function to an agent in a networked system. Each agent is allowed to communicate with other agents in order to solve the original optimization problem. We propose an algorithm which will converge when the interaction between the agents is strong enough to lead to synchronization between common variables.