Solving convex programs by random walks

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

zbMATH Keywords

minimizing quasi-convex functionsnew algorithm for convex optimizationsampling by random walk

Mathematics Subject Classification ID

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