Fast convergence to an approximate solution by message-passing for complex optimizations
arXiv:2312.11909 · doi:10.1587/nolta.15.485
Abstract
Message-passing (MP) is a powerful tool for finding an approximate solution in optimization. We generalize it to nonlinear product-sum form, and numerically show the fast convergence for the minimum feedback vertex set and the minimum vertex cover known as NP-hard problems. From the linearity of MP in a logarithmic space, it is derived that an equilibrium solution exists in a neighborhood of random initial values. These results will give one of the reason why the convergence is very fast in collective computation based on a common mathematical background.
24 pages, 5 figures, 3 tables