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.

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