Tropical lower bounds for extended formulations
The tropical arithmetic operations on \(\mathbb {R}\), defined as \(\oplus :(a,b)\rightarrow \min \{a,b\}\) and \(\otimes :(a,b)\rightarrow a+b\), arise from studying the geometry over non-Archimedean fields. We present an application of tropical methods to the study of extended formulations for convex polytopes. We propose a non-Archimedean generalization of the well known Boolean rank bound for the extension complexity. We show how to construct a real polytope with the same extension complexity and combinatorial type as a given non-Archimedean polytope. Our results allow us to develop a method of constructing real polytopes with large extension complexity.
extended formulation convex polytope tropical mathematics 15a23 15b48 52b05