Centerpoints: A Link Between Optimization and Convex Geometry
From MaRDI portal
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 several 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.
Recommendations
- Centerpoints: a link between optimization and convex geometry
- Characterizing centers of convex bodies via optimization
- An optimal generalization of the centerpoint theorem, and its extensions
- An optimal extension of the centerpoint theorem
- scientific article; zbMATH DE number 17652
- scientific article; zbMATH DE number 2079186
- On computing the center of a convex quadratically constrained set
- On the 2-center problem under convex polyhedral distance function
- Some geometrical aspects of efficient points in vector optimization
- Geometric p-center problems with centers constrained to two lines
Cites work
- COMPUTING THE CENTER OF AREA OF A CONVEX POLYGON
- Geometric algorithms and combinatorial optimization
- Helly numbers of algebraic subsets of \(\mathbb{R}^{d}\) and an extension of Doignon's theorem
- scientific article; zbMATH DE number 5080761 (Why is no real title available?)
- scientific article; zbMATH DE number 3770461 (Why is no real title available?)
- scientific article; zbMATH DE number 3541764 (Why is no real title available?)
- scientific article; zbMATH DE number 1859219 (Why is no real title available?)
- scientific article; zbMATH DE number 3229353 (Why is no real title available?)
- Integer Programming with a Fixed Number of Variables
- Intermediate sums on polyhedra: computation and real Ehrhart theory
- Introductory lectures on convex optimization. A basic course.
- On maximal S-free sets and the Helly number for the family of S-convex sets
- On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
- Partitions of mass-distributions and of convex bodies by hyperplanes
- Sharper bounds for Gaussian and empirical processes
- Solving convex programs by random walks
- The depth function of a population distribution.
- Transversal numbers over subsets of linear spaces
Cited in
(10)- Characterizing centers of convex bodies via optimization
- Tight bounds on discrete quantitative Helly numbers
- scientific article; zbMATH DE number 17652 (Why is no real title available?)
- Centers of sets with symmetry or cyclicity properties
- Tverberg theorems over discrete sets of points
- The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg
- Centerpoints: a link between optimization and convex geometry
- The geometry of the triangle and convex optimization go together\dots
- Minkowski centers via robust optimization: computation and applications
- An optimal extension of the centerpoint theorem
This page was built for publication: Centerpoints: A Link Between Optimization and Convex Geometry
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3186488)
