Simulated Annealing for Convex Optimization: Rigorous Complexity Analysis and Practical Perspectives
本文对Kalai和Vempala的模拟退火算法进行了严谨的复杂度分析，证明了其在仅使用可行集成员关系预言机时能以高概率在多项式时间内返回近优解，并提出了若干改进实际性能的修改及数值结果。
Abstract We give a rigorous complexity analysis of the simulated annealing algorithm by Kalai and Vempala (Math Oper Res 31(2):253–266, 2006) using the type of temperature update suggested by Abernethy and Hazan (International Conference on Machine Learning, 2016). The algorithm only assumes a membership oracle of the feasible set, and we prove that it returns a solution in polynomial time which is near-optimal with high probability. Moreover, we propose a number of modifications to improve the practical performance of this method, and present some numerical results for test problems from copositive programming.