The so-called scenario approach for uncertain optimization problems is here extended to a new paradigm called scenario with certificates (SwC). This extension is motivated by the observation that in many control problems only some of the optimization variables are used in the design phase, while the other variables play the role of certificates (e.g., parameter-dependent Lyapunov functions). These control problems include static anti-windup compensator design for uncertain linear systems with input saturation, where the goal is the minimization of the nonlinear gain from an exogenous input to a performance output. We show that randomization is a useful tool, specifically for anti-windup design, to make the overall approach less conservative as compared to the classical scenario approach. In particular, we demonstrate that the scenario with certificates reformulation is appealing because it provides a way to implicitly design the parameter-dependent Lyapunov functions