Simulation-Based Optimization for Convex Functions Over Discrete Sets

We propose a new iterative algorithm for finding a minimum point of f_*:X \subset \mathbb{R}^d \rightarrow \mathbb{R}, when f_* is known to be convex, but only noisy observations of f_*(\textbf{x}) are available at  \textbf{x} \in X for a finite set X. At each iteration of the proposed algorithm, we estimate the probability of each point \textbf{x} \in X being a minimum point of f_* using the fact that f_* is convex, and sample r points from X according  to these probabilities. We then make observations at the sampled points and use these observations to update the probability of each point \textbf{x} \in X  being a minimum point of f_*. Therefore, the proposed algorithm not only estimates the minimum point of f_* but also provides the probability of each point in X being a minimum point of f_*. Numerical results indicate the proposed algorithm converges to a minimum point of f_* as the number of iterations increases and shows fast convergence, especially in the early stage of the iterations.