A Markov chain approach to optimization
John Mount, Ravi Kannan, SRIDHAR R. TAYUR · OSTI OAI (U.S. Department of Energy Office of Scientific and Technical Information) · 1994
We propose to demonstrate how a near uniform convex body sampler can be used as the central routine in an effective randomized polynomial time algorithm for approximately minimizing a linear objective function over an up-monotone convex set Presented by a membership oracle. Our approach is to optimize using only local information. We present a non-uniform sampler for R{sup n} that obeys a probability distribution that grows geometrically in the direction of the objective function and falls off geometrically in distance from the convex body. It is an interesting side note that the Markov chain used to implement the sampler is closely related to the simulated annealing algorithm; however, this sampler converges in polynomial time.