An Improved Three-Weight Message-Passing Algorithm
作者： Veit Elser , Jonathan S. Yedidia , Nate Derbinsky , José Bento
DOI:
关键词: Local consistency 、 Algorithm 、 Belief propagation 、 Convex optimization 、 Constraint satisfaction 、 Mathematical optimization 、 Computer science 、 Message passing 、 Circle packing
摘要: We describe how the powerful "Divide and Concur" algorithm for constraint satisfaction can be derived as a special case of message-passing version Alternating Direction Method Multipliers (ADMM) convex optimization, introduce an improved based on ADMM/DC by introducing three distinct weights messages, with "certain" "no opinion" weights, well standard weight used in ADMM/DC. The messages allow our to implement propagation case, while speed convergence some problems making focus only active constraints. three-weight give greatly performance non-convex such circle packing solving large Sudoku puzzles, retaining exact ADMM problems. also advantages compared other algorithms upon belief propagation.
arxiv.org
harvard.edu
jbento.info 参考文章(25)
Helmut Simonis, Sudoku as a Constraint Problem ,(2005)
Péter Gábor Szabó, Mihaly Csaba Markót, T. Csendes, Eckard Specht, Leocadio G Casado, Inmaculada García, New approaches to circle packing in a square : with program codes Springer. ,(2007)
Eric P. Xing, Pedro Aguiar, Noah A. Smith, M rio Figueiredo, Andr Martins, An Augmented Lagrangian Approach to Constrained MAP Inference international conference on machine learning. pp. 169- 176 ,(2011)
Jonathan S. Yedidia, Message-Passing Algorithms for Inference and Optimization Journal of Statistical Physics. ,vol. 145, pp. 860- 890 ,(2011) , 10.1007/S10955-011-0384-7
Takayuki Yato, Takahiro Seta, Complexity and Completeness of Finding Another Solution and Its Application to Puzzles IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences. ,vol. 86, pp. 1052- 1060 ,(2003)
Jim Douglas, H. H. Rachford, On the numerical solution of heat conduction problems in two and three space variables Transactions of the American Mathematical Society. ,vol. 82, pp. 421- 439 ,(1956) , 10.1090/S0002-9947-1956-0084194-4
J. R. Fienup, Phase retrieval algorithms: a comparison. Applied Optics. ,vol. 21, pp. 2758- 2769 ,(1982) , 10.1364/AO.21.002758
Simon Gravel, Veit Elser, Divide and concur: a general approach to constraint satisfaction. Physical Review E. ,vol. 78, pp. 036706- ,(2008) , 10.1103/PHYSREVE.78.036706
P. L. Lions, B. Mercier, Splitting Algorithms for the Sum of Two Nonlinear Operators SIAM Journal on Numerical Analysis. ,vol. 16, pp. 964- 979 ,(1979) , 10.1137/0716071
Jonathan S. Yedidia, Yair Weiss, William T. Freeman, Understanding belief propagation and its generalizations Exploring artificial intelligence in the new millennium. pp. 239- 269 ,(2003)