This paper shows that many robust control problems can be formulated as constrained optimization problems and can be tackled by using randomized algorithms. Two different approaches in searching reliable solutions to robustness analysis problems under constraints are proposed, and the minimum computational efforts for achieving certain reliability and accuracy are investigated and bounds for sample size are derived. Moreover, the existing order statistics distribution theory is extended to the general case in which the distribution of population is not assumed to be continuous and the order statistics is associated with certain constraints.