A randomized approach is considered for a feasibility problem on a parameter-dependent linear matrix inequality (LMI). In particular, a gradient-based and an ellipsoid-based randomized algorithms are improved by introduction of a stopping rule. The improved algorithms stop after a bounded number of iterations and this bound is of polynomial order in the problem size. When the algorithms stop, either of the following two events occurs: (i) they find with high confidence a probabilistic solution, which satisfies the given LMI for most of the parameter values; (ii) they detect in an approximate sense the non-existence of a deterministic solution, which satisfies the given LMI for all the parameter values. These results are important because the original randomized algorithms have issues to be settled on detection of convergence, on the speed of convergence, and on the assumption of feasibility. The improved algorithms can be adapted for an optimization problem constrained by a parameter-dependent LMI. A numerical example shows the efficacy of the proposed algorithms. (C) 2007 Elsevier Ltd. All rights reserved.