<p>We introduce convex optimization methods to find upper bounds on the expected independence number of a random graph, in the vein of the Lovász theta function’s bound for the independence number of a deterministic graph. Specifically, we propose a hierarchy of semidefinite programs whose values upper bound the expected independence number. Our hierarchy can be applied to arbitrary random graph models, and only requires bounds on the probabilities that subsets of vertices are independent in the resulting graph. For symmetric random graphs, the last level of the hierarchy is equivalent to a linear program whose optimal value can often be calculated or approximated in closed form. We show that our methods provide good upper bounds in a number of examples, including Erdős–Rényi graphs and geometric random graphs.</p>