Consider the problem of minimization of some cost function defined on the vertices of an undirected graph in a decentralized way. Each vertex in has an associated variable which can take values in a set . is the vector of decision variables. The optimization problem is defined to be

This is called the *pairwise graphical model* because each term involves at most a pair of decision variables. One of the methods to solve this problem in a decentralized way is called *message passing* or *min-sum algorithm*. The idea of the algorithm is that any vertex can compute an estimate of the minimum cost given the corresponding estimates of its neighbors. This is basically like solving a dynamic program for any of the vertices in which discrete time is replaced by hop distance. To see how it is similar to dynamic programming consider the simplest case of a chain of vertices. The optimization problem can be rewritten as

where is the indicator function and

and

The “cost-to-go” functions and show the effect of decision at vertex on the cost function of its neighbors on the left and right respectively. Each vertex iteratively updates his cost-to-go function using the cost-to-go function of its neighbors only. This is an implementation of the deterministic dynamic programming algorithm.

The case of a simply connected graph is not much harder. Each vertex now has to incorporate the cost-to-go function from all its neighbors in his minimization problem

where now denotes the set of all neighbors of vertex and is the cost-to-go from vertex to vertex . Again this is just a deterministic dynamic program which terminates with the number of iterations equal to the diameter of the graph (which corresponds to the time horizon in DP).

Cycles cause difficulty by creating non terminating recursions and paths of infinite length which make the dynamic program infinite horizon in nature. But according to [1] the min-sum algorithms can also be applied to graphs with cycles using the appropriate normalization constants in the cost-to-go function.

One of the most important applications of min-sum algorithms is the consensus problem where the vertices try to average a set of numbers in a distributed way. This problem can be transformed to the above mentioned problem by defining the decision variables as the believes of the vertices and the cost function as some measure of deviation from the mean.

In this project I want to apply approximate methods and finite horizon relaxations to solve the consensus problem using the min-sum algorithm in the deterministic case, and then try to investigate the effect of introducing uncertainties on the performance of the algorithm. I will also make comparison between the performance of this algorithm and the existing consensus algorithms, such as linear consensus.

[1] C.C. Moallemi.* A Message-Passing Paradigm for Optimization.* Ph.D. Thesis, Stanford University, Stanford, CA, September 2007.