Vi beskriver hur den kraftfulla "Divide and Concur" algoritmen för begränsningstillfredsställelse kan härledas som ett specialfall av en meddelande-passing version av Alternating Direction Method of Multipliers (ADMM) algoritm för konvex optimering, och införa en förbättrad meddelande-passing algoritm baserad på ADMM/DC genom att införa tre distinkta vikter för meddelanden, med "vissa" och "ingen åsikt" vikter, samt standardvikten som används i ADMM/DC. De "vissa" meddelandena gör att vår förbättrade algoritm att genomföra begränsning utbredning som ett specialfall, medan "no opinion" meddelanden hastighet konvergens för vissa problem genom att göra algoritmen fokusera endast på aktiva begränsningar. Vi beskriver hur vår tre-viktiga version av ADMM/DC kan ge avsevärt förbättrad prestanda för icke-konvexa problem som cirkelpackning och lösa stora Sudoku pussel, samtidigt som man behåller den exakta prestandan för ADMM för konvexa problem. Vi beskriver också fördelarna med vår algoritm jämfört med andra messagepassing-algoritmer baserade på trosutbredning.
REF studerar Divide and Concur algoritm som ett specialfall av en meddelande-passing version av ADMM, och införa en tre-viktig version av denna algoritm som avsevärt förbättrar prestandan för vissa icke konvexa problem som cirkelpackning och Sudoku pussel.
An Improved Three-Weight Message-Passing Algorithm
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics', 'Physics']}