| We consider a class of large-scale optimization programs that appear in many engineering and management settings. Such complex, decentralized systems are comprised of many individual components, each interacting with a limited number of neighboring components. The resulting optimization programs are characterized by the fact that the decision variables are coupled only in a localized and sparse fashion.; Message-passing algorithms are a new class of distributed and asynchronous methods for solving problems with graphical structure. They have emerged independently in a number of fields, and interest in these algorithms has been motivated by their empirical success as an approximation method for certain intractable problems. However, they are still poorly understood in the general optimization context. The objective of this thesis is to understand these algorithms and elucidate their relationship to standard analytical and algorithmic optimization techniques.; We first consider message-passing in the context of resource allocation problems. We demonstrate that message-passing provides a framework for decentralized management that generalizes classical price-based systems by allowing incentives to vary across activities and consumption levels. We demonstrate that message-based incentives lead to system-optimal behavior for convex resource allocation problems, yet yield allocations superior to those from price-based incentives for nonconvex resource allocation problems. We describe and demonstrate the resulting distributed and asynchronous protocol in the context of a network resource allocation problem.; Next, we consider the application of message-passing algorithms to the solution of unconstrained, convex optimization programs. We establish that message-passing asynchronously converges for a large class of such programs that are characterized by a scaled diagonal dominance condition. This condition is similar to known sufficient conditions for asynchronous convergence of other decentralized optimization algorithms, such as coordinate descent and gradient descent.; Finally, we apply message-passing to the distributed consensus problem, where a collection of numbers must be averaged across a network in a distributed and asynchronous fashion. We demonstrate that the resulting protocol, consensus propagation, converges, characterize the convergence rate for regular graphs, and show that the protocol exhibits better scaling properties than methods based on linear consensus, which is an alternative that has received much recent attention. |
