Summary: Let \(\vartheta \mapsto P(\vartheta)\) be a set-valued mapping from \(\mathbb R^d\) into the family of closed compact polyhedra in \(\mathbb R^s\). Let \(\xi\) be a \(\mathbb R^s\) valued random variable. Many stochastic optimization problems in computer networking, system reliability, transportation, telecommunication, finance, etc. can be formulated as a problem to minimize (or maximize) the probability \(\mathbb P \{ \xi \in P(\vartheta) \}\) under some constraints on the decision variable \(\vartheta\). For a practical solution of such a problem, one has to approximate the objective function and its derivative by Monte Carlo simulation, since a closed analytical expression is only available in rare cases. In this paper, we present a new method of approximating the gradient of \(\mathbb P \{ \xi \in P(\vartheta) \}\) w.r.t. \(\vartheta\) by sampling, which is based on the concept of setwise (weak) derivative. Quite surprisingly, it turns out that it is typically easier to approximate the derivative than the objective itself.