We give a rigorous complexity analysis of the simulated annealing algorithm by Kalai and Vempala [Math of OR 31.2 (2006): 253-266] using the type of temperature update suggested by Abernethy and Hazan [arXiv 1507.02528v2, 2015]. 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.
|Place of Publication||Ithaca|
|Publisher||Cornell University Library|
|Number of pages||21|
|Publication status||Submitted - 2019|
Badenbroek, R., & de Klerk, E. (2019). Simulated Annealing with Hit-and-Run for Convex Optimization: Rigorous Complexity Analysis and Practical Perspectives for Copositive Programming. (arXiv; Vol. 1907.02368). Cornell University Library. https://arxiv.org/abs/1907.02368