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

Riley Badenbroek; Etienne de Klerk

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

Research output: Working paper › Other 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 language	English
Place of Publication	Ithaca
Publisher	Cornell University Library
Number of pages	21
Publication status	Submitted - 2019

Publication series

Name	arXiv
Volume	1907.02368

Access to Document

https://arxiv.org/abs/1907.02368

Cite this

@techreport{fed15ebaa33b442b84bb94fb39e3147b,

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

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.",

author = "Riley Badenbroek and {de Klerk}, Etienne",

year = "2019",

language = "English",

series = "arXiv",

publisher = "Cornell University Library",

type = "WorkingPaper",

institution = "Cornell University Library",

}

TY - UNPB

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

AU - Badenbroek, Riley

AU - de Klerk, Etienne

PY - 2019

Y1 - 2019

N2 - 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.

AB - 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.

M3 - Working paper

T3 - arXiv

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

PB - Cornell University Library

CY - Ithaca

ER -

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

Abstract

Publication series

Access to Document

Fingerprint

Cite this