Stochastic optimization by message passing

Abstract

Most optimization problems in applied sciences realistically involve uncertainty in the parameters defining the cost function, of which only statistical information is known beforehand. In a recent work we introduced a message passing algorithm based on the cavity method of statistical physics to solve the two-stage matching problem with independently distributed stochastic parameters. In this paper we provide an in-depth explanation of the general method and caveats, show the details of the derivation and resulting algorithm for the matching problem and apply it to a stochastic version of the independent set problem, which is a computationally hard and relevant problem in communication networks. We compare the results with some greedy algorithms and briefly discuss the extension to more complicated stochastic multi-stage problems.

31 pages, 8 figures

References in corpus (3)

• Loop series for discrete statistical models on graphs
• Statistical Mechanics of Steiner trees
• The stochastic matching problem

Cited by in corpus (11)

• Spreading dynamics in complex networks
• Containing epidemic outbreaks by message-passing techniques
• A message-passing approach for recurrent-state epidemic models on networks
• Optimizing spread dynamics on graphs by message passing
• Large deviations of cascade processes on graphs
• Variational Algorithms for Marginal MAP
• Solving Optimization Problems by the Public Goods Game
• Cavity approach to variational quantum mechanics
• Coordination problems on networks revisited: statics and dynamics
• Some observations on the ambivalent role of symmetries in Bayesian inference problems
• Belief propagation for supply networks: Efficient clustering of their factor graphs