A novel randomized approach to fixed-order controller design is proposed for discrete-time SISO plants. It is based on random generation of stable polynomials and finding for each of them the closest element in the set of closed-loop characteristic polynomials of the system. The affine set of closed-loop characteristic polynomials is specified by the fixed structure of the controller. The idea behind the approach is threefold. First, to generate Schur stable polynomials, an efficient recursive procedure is used, which is accomplished in the bounded domain in the space of auxiliary parameters, not in the original coefficient space. Second, if the set of stable closed-loop polynomials is nonempty (the stability domain in the controller coefficient space is nonempty), projecting a sampled polynomial onto this set is aimed at finding a stabilizing controller. Finally, if the sampling-projecting process fails to find a stable closed-loop polynomial, a locally optimizing procedure is applied which iteratively shifts the closed-loop zeros towards the stability region (the unit circle on the complex plane). This nonsmooth optimization procedure is based on the ideas of perturbation theory for the roots of polynomials. The efficiency of the approach is demonstrated by illustrative examples of stabilization via PI-controllers.