Solving convex programs by random walks
Top Cited Papers
- 1 July 2004
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 51 (4) , 540-556
- https://doi.org/10.1145/1008731.1008733
Abstract
Minimizing a convex function over a convex set in n -dimensional space is a basic, general problem with many interesting special cases. Here, we present a simple new algorithm for convex optimization based on sampling by a random walk. It extends naturally to minimizing quasi-convex functions and to other generalizations.Keywords
This publication has 12 references indexed in Scilit:
- The Brunn-Minkowski inequalityBulletin of the American Mathematical Society, 2002
- Random Vectors in the Isotropic PositionJournal of Functional Analysis, 1999
- A new algorithm for minimizing convex functions over convex setsMathematical Programming, 1996
- A Randomized Algorithm to Optimize Over Certain Convex SetsMathematics of Operations Research, 1995
- Convex Bodies: The Brunn–Minkowski TheoryPublished by Cambridge University Press (CUP) ,1993
- A random polynomial-time algorithm for approximating the volume of convex bodiesJournal of the ACM, 1991
- Geometric Algorithms and Combinatorial OptimizationPublished by Springer Nature ,1988
- On Linear Characterizations of Combinatorial Optimization ProblemsSIAM Journal on Computing, 1982
- The ellipsoid method and its consequences in combinatorial optimizationCombinatorica, 1981
- Partitions of mass-distributions and of convex bodies by hyperplanesPacific Journal of Mathematics, 1960