This paper considers the problem of synthesizing output feedback controllers subject to sparsity constraints. This problem is known to be generically NP-hard, unless the plant satisfies the quadratic invariance property. Our main results show that, even if this property does not hold, tractable convex relaxations with optimality certificates can be obtained by recasting the problem into a polynomial optimization through the use of polyhedral Lyapunov functions. Combining these ideas with rank minimization tools leads to a computationally attractive algorithm. As an alternative, we present a second relaxation, with lower computational complexity, based on finding the best sparse estimate of a desired control action. These results are illustrated with several examples.