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

ABSTRACT

Let K be a polytope in Rⁿ 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₀. If s is the supremum over all chords pq passing through x₀ of (|p-x₀|)/(|q-x₀|) 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.

REFERENCES

• 1: J. Abernethy, E. Hazan and A. Rakhlin, "Competing in the Dark: An Efficient Algorithm for Bandit Linear Optimization," 21st Annual Conference on Learning Theory, (COLT), 2008 263--274
• 2: Alexandre Belloni , Robert M. Freund, Projective re-normalization for improving the behavior of a homogeneous conic linear system, Mathematical Programming: Series A and B, v.118 n.2, p.279-299, January 2009 [doi>10.1007/s10107-007-0192-7]
• 3: Baur and V. Strassen, "The Complexity of Partial Derivatives," Theoretical Computer Science, 22 (1983) 317--330
• 4: . Diaconis and B. Efron, "Testing for independence in a two-way table: new interpretations of the chi-square statistic," Annals of Statistics &#;lt;b&#;gt; 13, pp. 845--913, 1995.
• 5: .I. Dikin, "Iterative solutions of problems of linear and quadratic programming," Soviet Math. Dokl 8 (1967)
• 6: Martin Dyer , Alan Frieze , Ravi Kannan, A random polynomial-time algorithm for approximating the volume of convex bodies, Journal of the ACM (JACM), v.38 n.1, p.1-17, Jan. 1991 [doi>10.1145/102782.102783]
• 7: Ravi Kannan , László Lovász , Miklós Simonovits, Random walks and an O*(n5) volume algorithm for convex bodies, Random Structures & Algorithms, v.11 n.1, p.1-50, Aug. 1997 [doi>10.1002/(SICI)1098-2418(199708)11:1<1::AID-RSA1>3.0.CO;2-X]
• 8: Ravi Kannan , Santosh Vempala, Sampling lattice points, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.696-700, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258665]
• 9: N. Karmarkar, A new polynomial-time algorithm for linear programming, Combinatorica, v.4 n.4, p.373-395, Dec. 1984 [doi>10.1007/BF02579150]
• 10: Yinyu Ye , Masakazu Kojima, Recovering optimal dual solutions on Karmarkar's polynomial algorithm for linear programming, Mathematical Programming: Series A and B, v.39 n.3, p.305-317, December 1, 1987 [doi>10.1007/BF02592079]
• 11: . Ledoux, "The concentration of measure phenomenon," Mathematical Surveys and Monographs 89, American Mathematical Society(2001).
• 12: . Lovász, "Hit-and-run mixes fast," Math. Programming, series A, 86 (1999).
• 13: . Lovász and M. Simonovits, "Random walks in a convex body and animproved volume algorithm," Random structures and algorithms, 4 (1993)
• 14: László Lovász , Santosh Vempala, Hit-and-Run from a Corner, SIAM Journal on Computing, v.35 n.4, p.985-1005, 2006 [doi>10.1137/S009753970544727X]
• 15: Laszlo Lovasz , Santosh Vempala, Fast Algorithms for Logconcave Functions: Sampling, Rounding, Integration and Optimization, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.57-68, October 21-24, 2006 [doi>10.1109/FOCS.2006.28]
• 16: László Lovász , Santosh Vempala, The geometry of logconcave functions and sampling algorithms, Random Structures & Algorithms, v.30 n.3, p.307-358, May 2007 [doi>10.1002/rsa.v30:3]
• 17: Ben J. Morris, Improved bounds for sampling contingency tables, Random Structures & Algorithms, v.21 n.2, p.135-146, September 2002 [doi>10.1002/rsa.10049]
• 18: . E. Nesterov and A. S. Nemirovskii, "Interior point polynomial algorithms in convex programming," SIAM Publications. SIAM, Philadelphia, USA,(1994)
• 19: Yu E. Nesterov , M. J. Todd, Self-scaled barriers and interior-point methods for convex programming, Mathematics of Operations Research, v.22 n.1, p.1-42, Feb. 1997 [doi>10.1287/moor.22.1.1]
• 20: James Renegar, A polynomial-time algorithm, based on Newton's method, for linear programming, Mathematical Programming: Series A and B, v.40 n.1, p.59-93, January 1988 [doi>10.1007/BF01580724]
• 21: Pravin M. Vaidya, A new algorithm for minimizing convex functions over convex sets, Mathematical Programming: Series A and B, v.73 n.3, p.291-341, June 30, 1996 [doi>10.1007/BF02592216]
• 22: P. M. Vaidya, An algorithm for linear programming which requires O((m+n)n² + (m+n)^1.5n)L) arithmetic operations, Mathematical Programming: Series A and B, v.47 n.2, p.175-201, Jun. 1990 [doi>10.1007/BF01580859]
• 23: . J. Vanderbei and J. C. Lagarias, "I. I. Dikin'sconvergence result for the affine-scaling algorithm," Contemporary mathematics, 114 (1990)

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Linear programming

General Terms:
Algorithms, Theory

Keywords:
optimization, randomized algorithms