Solving convex programs by random walks
From MaRDI portal
Publication:5894078
DOI10.1145/1008731.1008733zbMath1204.90074OpenAlexW2106318612MaRDI QIDQ5894078
Santosh Vempala, Dimitris J. Bertsimas
Publication date: 1 February 2011
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1008731.1008733
Analysis of algorithms (68W40) Convex programming (90C25) Approximation methods and heuristics in mathematical programming (90C59)
Related Items (36)
Centerpoints: A Link Between Optimization and Convex Geometry ⋮ Unnamed Item ⋮ An empirical evaluation of walk-and-round heuristics for mixed integer linear programs ⋮ Random gradient-free minimization of convex functions ⋮ Sampling from the complement of a polyhedron: an MCMC algorithm for data augmentation ⋮ On the Complexity of Constrained Determinantal Point Processes ⋮ Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex Optimization ⋮ An exponential lower bound for Zadeh's pivot rule ⋮ From approximate to exact integer programming ⋮ On the generation of metric TSP instances with a large integrality gap by branch-and-cut ⋮ Query Complexity of Sampling and Small Geometric Partitions ⋮ Pattern hit-and-run for sampling efficiently on polytopes ⋮ Pattern discrete and mixed hit-and-run for global optimization ⋮ Sampling Hypersurfaces through Diffusion ⋮ Efficient Convex Optimization with Oracles ⋮ Randomized methods based on new Monte Carlo schemes for control and optimization ⋮ On the symmetry function of a convex set ⋮ A simple polynomial-time rescaling algorithm for solving linear programs ⋮ Robust semidefinite programming problems with general nonlinear parameter dependence: approaches using the DC-representations ⋮ Centerpoints: A Link between Optimization and Convex Geometry ⋮ Simulated annealing in convex bodies and an \(O^{*}(n^{4}\)) volume algorithm ⋮ Unnamed Item ⋮ A Hit‐and‐Run approach for generating scale invariant Small World networks ⋮ Integer convex minimization by mixed integer linear optimization ⋮ Comments on: Recent progress on the combinatorial diameter of polytopes and simplicial complexes ⋮ A stochastic subspace approach to gradient-free optimization in high dimensions ⋮ Essentials of numerical nonsmooth optimization ⋮ Monte Carlo method of batch iterations: probabilistic characteristics ⋮ On randomized fictitious play for approximating saddle points over convex sets ⋮ Projective re-normalization for improving the behavior of a homogeneous conic linear system ⋮ Multidimensional Binary Search for Contextual Decision-Making ⋮ The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg ⋮ Essentials of numerical nonsmooth optimization ⋮ An empirical evaluation of a walk-relax-round heuristic for mixed integer convex programs ⋮ Morphological Analysis of Brownian Motion for Physical Measurements ⋮ Randomized interior point methods for sampling and optimization
This page was built for publication: Solving convex programs by random walks
