A relevant family of control analysis and design problems can be reduced to the minimisation of a multivariate polynomial objective over a semialgebraic set. Such control problem formulations, however, are nonconvex in general and hard to solve in practice. In this paper, we propose a novel approach to polynomial control design based on iterations that involve either a fast coordinate-wise minimisation or a univariate minimisation along a randomly chosen direction. We provide a detailed iteration complexity analysis of the method, and we prove its convergence in probability to the global optimum. The practical effectiveness of the proposed method is also illustrated via a comparison with state-of-the-art tools available in the literature. An example of application to an automated space rendezvous manoeuvre is finally presented, showing how the method can be particularly relevant in the context of nonlinear model predictive control.