Hit-and-Run from a Corner
From MaRDI portal
Publication:5470722
DOI10.1137/S009753970544727XzbMath1103.52002OpenAlexW3023788998WikidataQ101001960 ScholiaQ101001960MaRDI QIDQ5470722
László Lovász, Santosh Vempala
Publication date: 1 June 2006
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s009753970544727x
Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Convex sets in (n) dimensions (including convex hypersurfaces) (52A20) Randomized algorithms (68W20)
Related Items
On the mixing time of coordinate Hit-and-Run ⋮ A practical volume algorithm ⋮ Oracle lower bounds for stochastic gradient sampling algorithms ⋮ Entanglement in bipartite quantum systems: Euclidean volume ratios and detectability by Bell inequalities ⋮ \(t\)-copula from the viewpoint of tail dependence matrices ⋮ Unnamed Item ⋮ Stochastic Billiards for Sampling from the Boundary of a Convex Set ⋮ On the computational complexity of MCMC-based estimators in large samples ⋮ Sampling from a log-concave distribution with projected Langevin Monte Carlo ⋮ An empirical evaluation of walk-and-round heuristics for mixed integer linear programs ⋮ Geodesic Walks in Polytopes ⋮ Hit-and-Run for Numerical Integration ⋮ Computing and estimating the volume of the solution space of SMT(LA) constraints ⋮ Complexity Analysis of a Sampling-Based Interior Point Method for Convex Optimization ⋮ Gaussian Cooling and $O^*(n^3)$ Algorithms for Volume and Gaussian Volume ⋮ Heat-bath random walks with Markov bases ⋮ Multiobjective Interacting Particle Algorithm for Global Optimization ⋮ Hit and Run Sampling from Tropically Convex Sets ⋮ Convex set of quantum states with positive partial transpose analysed by hit and run algorithm ⋮ Complexity results for MCMC derived from quantitative bounds ⋮ Optimal scaling of random-walk Metropolis algorithms on general target distributions ⋮ John’s walk ⋮ Hit and run as a unifying device ⋮ Computational results of an \(O^{\ast }(n^{4})\) volume algorithm ⋮ Convergence of Gibbs sampling: coordinate hit-and-run mixes fast ⋮ Pattern hit-and-run for sampling efficiently on polytopes ⋮ Comparison of hit-and-run, slice sampler and random walk Metropolis ⋮ Pattern discrete and mixed hit-and-run for global optimization ⋮ Error bounds for Metropolis-Hastings algorithms applied to perturbations of Gaussian measures in high dimensions ⋮ Statistics with set-valued functions: applications to inverse approximate optimization ⋮ Improved mixing rates of directed cycles by added connection ⋮ Unnamed Item ⋮ \(D\)-decomposition technique state-of-the-art ⋮ The accessibility of convex bodies and derandomization of the hit and run algorithm ⋮ The Markov chain Monte Carlo revolution ⋮ Simple conditions for metastability of continuous Markov chains ⋮ On randomized fictitious play for approximating saddle points over convex sets ⋮ On Sampling from Multivariate Distributions ⋮ Deterministic Construction of an Approximate M-Ellipsoid and its Application to Derandomizing Lattice Algorithms ⋮ Multinomial models with linear inequality constraints: overview and improvements of computational methods for Bayesian inference ⋮ A Supervised Learning Approach Involving Active Subspaces for an Efficient Genetic Algorithm in High-Dimensional Optimization Problems ⋮ Computation of Expectations by Markov Chain Monte Carlo Methods ⋮ An empirical evaluation of a walk-relax-round heuristic for mixed integer convex programs ⋮ The symplectic geometry of closed equilateral random walks in 3-space ⋮ Randomized interior point methods for sampling and optimization