Monte Carlo Policy Gradient Method for Binary Optimization

Author name not available (Why is that?)

Publication date: 3 July 2023

Abstract: Binary optimization has a wide range of applications in combinatorial optimization problems such as MaxCut, MIMO detection, and MaxSAT. However, these problems are typically NP-hard due to the binary constraints. We develop a novel probabilistic model to sample the binary solution according to a parameterized policy distribution. Specifically, minimizing the KL divergence between the parameterized policy distribution and the Gibbs distributions of the function value leads to a stochastic optimization problem whose policy gradient can be derived explicitly similar to reinforcement learning. For coherent exploration in discrete spaces, parallel Markov Chain Monte Carlo (MCMC) methods are employed to sample from the policy distribution with diversity and approximate the gradient efficiently. We further develop a filter scheme to replace the original objective function by the one with the local search technique to broaden the horizon of the function landscape. Convergence to stationary points in expectation of the policy gradient method is established based on the concentration inequality for MCMC. Numerical results show that this framework is very promising to provide near-optimal solutions for quite a few binary optimization problems.

Has companion code repository: https://github.com/optsuite/mcpg

Mathematics Subject Classification ID

No records found.

This page was built for publication: Monte Carlo Policy Gradient Method for Binary Optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6442349)