In previous works the authors proposed to use Hit-and-Run (H&R) versions of Markov Chain Monte Carlo (MCMC) algorithms for various problems of control and optimization. However the results are unsatisfactory for ”bad” sets, such as level sets of ill-posed functions. The idea of the present paper is to exploit the technique developed for interior-point methods of convex optimization, and to combine it with MCMC algorithms. We present a new modication of H&R method exploiting barrier functions and its validation. Such approach is well tailored for sets dened by linear matrix inequalities (LMI), which are widely used in control and optimization. The results of numerical simulation are promising.