Randomized interior point methods for sampling and optimization (Q259600)

In applied convex geometry, to pick a point from a nearly uniform distribution on a convex set is commonly used by a randomized method in computing the volume of a high dimensional convex set and in solving linear programming and convex programming. Usually, it is concerned with a barrier function and with running a nearly ergodic Markov ball walk for a practically long time. The nearness here is described by a mixing time and a complexity parameter. In the present paper, a Markov chain known as Dikin walk equipped with a self-concordant barrier is presented. This chain corresponds to a natural random walk with respect to a Riemannian metric defined using the Hessian of its barrier. It is shown that this algorithm allows us to efficiently pick a nearly random point from the uniform measure on the convex set. And the result is extended to a direct product of convex sets. Moreover, this study is adapted to give a Las Vegas algorithm random walk for optimizing a linear function.