Simulated annealing for convex optimization

• 成果类型: Article
• 署名作者: Kalai, Adam Tauman; Vempala, Santosh
• 署名单位: Toyota Technological Institute - Chicago; Massachusetts Institute of Technology (MIT)
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.1060.0194
• 发表日期: 2006
• 页码: 253-266
• 关键词: hit-and-run; volume algorithm; random-walks; bodies

摘要

We apply the method known as simulated annealing to the following problem in convex optimization: Minimize a linear function over an arbitrary convex set, where the convex set is specified only by a membership oracle. Using distributions from the Boltzmann-Gibbs family leads to an algorithm that needs only O*(root n) phases for instances in R-n. This gives an optimization algorithm that makes O*(n(4.5)) calls to the membership oracle, in the worst case, compared to the previous best guarantee of O*(n(5)). The benefits of using annealing here are surprising because such problems have no local minima that are not also global minima. Hence, we conclude that one of the advantages of simulated annealing, in addition to avoiding poor local minima, is that in these problems it converges faster to the minima that it finds. We also give a proof that under certain general conditions, the Boltzmann-Gibbs distributions are optimal for annealing on these convex problems.