Centerpoints: A link between optimization and convex geometry

Basu A, Oertel T (2017)

Publication Type: Journal article

Publication year: 2017

Journal

SIAM Journal on Optimization Society for Industrial and Applied Mathematics

Book Volume: 27

Pages Range: 866-889

Journal Issue: 2

DOI: 10.1137/16M1092908

Abstract

We introduce a concept that generalizes several different notions of a "centerpoint" in the literature. We develop an oracle-based algorithm for convex mixed-integer optimization based on centerpoints. Further, we show that algorithms based on centerpoints are "best possible" in a certain sense. Motivated by this, we establish structural results about this concept and provide efficient algorithms for computing these points. Our main motivation is to understand the complexity of oracle-based convex mixed-integer optimization.

Authors with CRIS profile

Timm Oertel Professur für Mathematische Analyse von Daten (Data Analytics)

Involved external institutions

Johns Hopkins University (JHU) US United States (USA) (US) Cardiff University GB United Kingdom (GB)

How to cite

APA:

Basu, A., & Oertel, T. (2017). Centerpoints: A link between optimization and convex geometry. SIAM Journal on Optimization, 27(2), 866-889. https://dx.doi.org/10.1137/16M1092908

MLA:

Basu, Amitabh, and Timm Oertel. "Centerpoints: A link between optimization and convex geometry." SIAM Journal on Optimization 27.2 (2017): 866-889.

BibTeX: Download