Randomized interior point methods for sampling and optimization

DOI10.1214/15-AAP1104zbMath1345.65045OpenAlexW2962857086MaRDI QIDQ259600

Hariharan Narayanan

Publication date: 11 March 2016

Published in: The Annals of Applied Probability (Search for Journal in Brave)

Full work available at URL: https://projecteuclid.org/euclid.aoap/1452003248

zbMATH Keywords

algorithmlinear programmingrandom walksconvex programmingMarkov chaininterior point methodsmixing timecomplexity parameterDikin walkself-concordant barrieruniform measure

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Convex programming (90C25) Sums of independent random variables; random walks (60G50) Nonlinear programming (90C30) Linear programming (90C05) Stochastic programming (90C15) Interior-point methods (90C51) Numerical analysis or methods applied to Markov chains (65C40)

Related Items

On the mixing time of coordinate Hit-and-Run, Unnamed Item, An empirical evaluation of walk-and-round heuristics for mixed integer linear programs, Geodesic Walks in Polytopes, A Gibbs Sampler for a Class of Random Convex Polytopes, John’s walk, The mixing time of the Dikin walk in a polytope -- a simple proof, Unnamed Item, Unnamed Item, An empirical evaluation of a walk-relax-round heuristic for mixed integer convex programs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A new polynomial-time algorithm for linear programming
• Primal central paths and Riemannian distances for convex sets
• A polynomial-time algorithm, based on Newton's method, for linear programming
• The complexity of partial derivatives
• Isoperimetric constants for product probability measures
• An exact duality theory for semidefinite programming and its complexity implications
• Isoperimetry of waists and concentration of maps
• Log-concave and spherical models in isoperimetry
• On the Riemannian geometry defined by self-concordant barriers and interior-point methods.
• A new algorithm for minimizing convex functions over convex sets
• Hit-and-run mixes fast
• Semi-classical analysis of a random walk on a manifold
• An empirical evaluation of walk-and-round heuristics for mixed integer linear programs
• Simulated annealing in convex bodies and an \(O^{*}(n^{4}\)) volume algorithm
• Equivalence of Convex Problem Geometry and Computational Complexity in the Separation Oracle Model
• Sampling Hypersurfaces through Diffusion
• Random walks in a convex body and an improved volume algorithm
• A random polynomial-time algorithm for approximating the volume of convex bodies
• Self-Scaled Barriers and Interior-Point Methods for Convex Programming
• Hyperbolic Polynomials and Interior Point Methods for Convex Programming
• Random walks and anO*(n5) volume algorithm for convex bodies
• Random walks on polytopes and an affine interior point method for linear programming
• Hit-and-Run from a Corner
• Solving convex programs by random walks