It is known that many challenging problems in control theory belong to the class of the minimization of a concave function over convex constraints. These are, for instance, static output feedback and robust fixed order control. We propose new randomized algorithm for these problems as a reasonable alternative for global optimization techniques. The method consists of two steps: first, we generate asymptotically uniform random samples in a convex domain via Hit-and-Run method and then apply local descent procedure based on conditional gradient for a concave function treating samples as starting points. Due to the diversity of the samples we obtain that the portion of successful descents is large enough. Simulations for the problem of stabilization of the inverted pendulum confirm the efficiency of the proposed algorithm.