Random walks on polytopes and an affine interior point method for linear programming

Let K be a polytope in R n defined by m linear inequalities. We give a new Markov Chain algorithm to draw a nearly uniform sample from K. The underlying Markov Chain is the first to have a mixing time that is strongly polynomial when started from a "central" point x 0 . If s is the supremum over all chords pq passing through x 0 of (|p-x 0 |)/(|q-x 0 |) and ε is an upper bound on the desired total variation distance from the uniform, it is sufficient to take O(m n( n log (s m) + log 1/ε)) steps of the random walk. We use this result to design an affine interior point algorithm that does a single random walk to solve linear programs approximately. More precisely, suppose Q = {z | Bz ≤ 1} contains a point z such that c T z ≥ d and r := sup z ∈ Q |Bz| + 1, where B is an m x n matrix. Then, after τ = O(mn (n ln(mr/ε) + ln 1/δ)) steps, the random walk is at a point x τ for which c T x τ ≥ d(1-ε) with probability greater than 1-δ. The fact that this algorithm has a run-time that is provably polynomial is notable since the analogous deterministic affine algorithm analyzed by Dikin has no known polynomial guarantees.

Authors

• Ravindran Kannan
• Hariharan Narayanan

Keywords

• optimization
• randomized algorithms