This paper presents a gradient-based randomized algorithm to design a guaranteed cost regulator for a plant with general parametric uncertainties. The algorithm either provides with high confidence a probabilistic solution that satisfies the design specification with high probability for a randomly sampled uncertainty or claims that the feasible set of the design parameters is too small to contain a ball with a given radius. In both cases, the number of iterations executed in the algorithm is of polynomial order of the problem size and is independent of the dimension of the uncertainty. (C) 2006 Elsevier Ltd. All rights reserved.