We present a fully probabilistic approach for solving binary optimization
problems with black-box objective functions and with budget constraints. In the
probabilistic approach, the optimization variable is viewed as a random
variable and is associated with a parametric probability distribution. The
original optimization problem is replaced with an optimization over the
expected value of the original objective, which is then optimized over the
probability distribution parameters. The resulting optimal parameter (optimal
policy) is used to sample the binary space to produce estimates of the optimal
solution(s) of the original binary optimization problem. The probability
distribution is chosen from the family of Bernoulli models because the
optimization variable is binary. The optimization constraints generally
restrict the feasibility region. This can be achieved by modeling the random
variable with a conditional distribution given satisfiability of the
constraints. Thus, in this work we develop conditional Bernoulli distributions
to model the random variable conditioned by the total number of nonzero
entries, that is, the budget constraint. This approach (a) is generally
applicable to binary optimization problems with nonstochastic black-box
objective functions and budget constraints; (b) accounts for budget constraints
by employing conditional probabilities that sample only the feasible region and
thus considerably reduces the computational cost compared with employing soft
constraints; and (c) does not employ soft constraints and thus does not require
tuning of a regularization parameter, for example to promote sparsity, which is
challenging in sensor placement optimization problems. The proposed approach is
verified numerically by using an idealized bilinear binary optimization problem
and is validated by using a sensor placement experiment in a parameter
identification setup.

我们提出了一种完全概率化的方法，用于解决具有黑盒目标函数和预算约束的二值优化问题。

概率方法在具有预算约束的黑盒二进制优化中的应用：传感器布置

Probabilistic Approach to Black-Box Binary Optimization with Budget  Constraints: Application to Sensor Placement

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.

通过使用概率模型和 Markov Chain Monte Carlo 技术，基于参数化的策略分布，对二进制优化问题进行近似优化，本文同时提出了一种滤波方案来扩展函数的景观，并证明了策略梯度法的期望收敛性。