Simulated Annealing with Hit-and-Run for Convex Optimization: Rigorous Complexity Analysis and Practical Perspectives for Copositive Programming

Research output: Working paperOther research output

Abstract

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.
Original languageEnglish
Place of PublicationIthaca
PublisherCornell University Library
Number of pages21
Publication statusSubmitted - 2019

Publication series

NamearXiv
Volume1907.02368

Fingerprint Dive into the research topics of 'Simulated Annealing with Hit-and-Run for Convex Optimization: Rigorous Complexity Analysis and Practical Perspectives for Copositive Programming'. Together they form a unique fingerprint.

  • Cite this