Geodesic Walks in Polytopes

DOI10.1137/17M1145999OpenAlexW2423159321MaRDI QIDQ5073522

Yin Tat Lee, Santosh Vempala

Publication date: 3 May 2022

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/17m1145999

zbMATH Keywords

ODESDEHessian manifoldgeodesic walklog barriersampling polytopes

Mathematics Subject Classification ID

Monte Carlo methods (65C05) Randomized algorithms (68W20) Manifolds of metrics (especially Riemannian) (58D17)

Cites Work

• Randomized interior point methods for sampling and optimization
• Primal central paths and Riemannian distances for convex sets
• Rapid mixing of geodesic walks on manifolds with positive curvature
• Sampling from a log-concave distribution with projected Langevin Monte Carlo
• On the Riemannian geometry defined by self-concordant barriers and interior-point methods.
• Hit-and-run mixes fast
• Efficient Monte Carlo Procedures for Generating Points Uniformly Distributed over Bounded Regions
• A First Course in the Numerical Analysis of Differential Equations
• Random walks in a convex body and an improved volume algorithm
• A random polynomial-time algorithm for approximating the volume of convex bodies
• Random walks and anO*(n5) volume algorithm for convex bodies
• Natural Algorithms for Flow Problems
• Fast Algorithms for Polynomial Interpolation, Integration, and Differentiation
• THE CURVATURE OF A HESSIAN METRIC
• Random walks on polytopes and an affine interior point method for linear programming
• Canonical Barriers on Convex Cones
• A Cubic Algorithm for Computing Gaussian Volume
• Hit-and-Run from a Corner
• Riemannian geometry and geometric analysis
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item