Groupe d’études et de recherche en analyse des décisions

G-2019-30

Constrained stochastic blackbox optimization using probabilistic estimates

, , et

This work introduces Stoch-MADS, a stochastic variant of the mesh adaptive direct search (MADS) algorithm designed for deterministic blackbox optimization. Stoch-MADS considers the constrained optimization of an objective function \(f\) whose values can only be computed through a stochastic blackbox with some random noise of an unknown distribution. The proposed algorithm uses an algorithmic framework similar to that of MADS and utilizes random estimates of true function values obtained from their stochastic observations to ensure improvements since the exact deterministic computable version of \(f\) is not available. Such estimates are required to be accurate with a sufficiently large but fixed probability and satisfy a variance condition. The ability of the proposed algorithm to generate an asymptotically dense set of search directions is then exploited to show that it converges to a Clarke-hypertangent stationary point of \(f\) with probability one, with the help of martingale theory.

, 27 pages