Loading...
research article
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.
Type
research article
Web of Science ID
WOS:000384854700013
Authors
Publication date
2016
Publisher
Published in
Volume
44
Issue
5
Start page
630
End page
634
Peer reviewed
REVIEWED
EPFL units
Available on Infoscience
November 21, 2016
Use this identifier to reference this record