The mixing time of the Dikin walk in a polytope-A simple proof

We study the mixing time of the Dikin walk in a polytope a random walk based on the log-barrier from the interior point method literature. This walk, and a close variant, were studied by Narayanan (2016) and Kannan-Narayanan (2012). Bounds on its mixing time are important for algorithms for sampling and optimization over polytopes. Here, we provide a simple proof of their result that this random walk mixes in time O(mn) for an n-dimensional polytope described using m inequalities. (C) 2016 Elsevier B.V. All rights reserved.


Published in:
Operations Research Letters, 44, 5, 630-634
Year:
2016
Publisher:
Amsterdam, Elsevier Science Bv
ISSN:
0167-6377
Keywords:
Laboratories:




 Record created 2016-11-21, last modified 2018-09-13


Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)