Randomized interior point methods for sampling and optimization
DOI10.1214/15-AAP1104zbMath1345.65045OpenAlexW2962857086MaRDI QIDQ259600
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
algorithmlinear programmingrandom walksconvex programmingMarkov chaininterior point methodsmixing timecomplexity parameterDikin walkself-concordant barrieruniform measure
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
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