Home // INFOCOMP 2011, The First International Conference on Advanced Communications and Computation // View article

Min-Sum-Min Message-Passing for Quadratic Optimization

Authors:
Guoqiang Zhang
Richard Heusdens

Keywords: Distributed optimization, Gaussian belief propagation, message-passing algorithms

Abstract:
We study the minimization of a quadratic objective function in a distributed fashion. It is known that the min-sum algorithm can be applied to solve the minimization problem if the algorithm converges. We propose a min-sum-min message-passing algorithm which includes the min-sum algorithm as a special case. As the name suggests, the new algorithm involves two minimizations in each iteration as compared to the min-sum algorithm which has one minimization. The algorithm is derived based on a new closed-loop quadratic optimization problem which has the same optimal solution as the original one. Experiments demonstrate that our algorithm improves the convergence speed of the min-sum algorithm by properly selecting a parameter in the algorithm. Furthermore, we find empirically that in some situations where the min-sum algorithm fails, our algorithm still converges to the right solution. Experiments show that if our algorithm converges, our algorithm outperform a reference method with fast convergence speed.

Pages: 137 to 142

Copyright: Copyright (c) IARIA, 2011

Publication date: October 23, 2011

Published in: conference

ISSN: 2308-3484

ISBN: 978-1-61208-161-8

Location: Barcelona, Spain

Dates: from October 23, 2011 to October 29, 2011