Tropical lower bounds for extended formulations
type: Item
instance of: scholarly article
title: Tropical lower bounds for extended formulations
zbMATH Open document ID: 1331.15021
published in: Mathematical Programming. Series A. Series B
publication date: 2015-10-14T00:00:00Z
review text: Let \(A\in\mathbb{R}^{f\times n}\) and \(b\in\mathbb{R}^{f}\) and suppose that \(P\) is the polytope in \(\mathbb{R}^{n}\) consisting of all points \(x\) such that \(Ax\geq b\). If \(s_{1},\dots,s_{v}\) are the vertices of \(P\), we define \(S(P,A,b)\) as the \(f\times v\) matrix whose \(i\)th column is \(As_{i}-b\) and call this a slack matrix for \(P\). The extension complexity of \(P\) can be characterized as the least integer \(q\) such that \(S(P,A,b)\) can be written as a product of \(f\times q\) and \(q\times v\) nonnegative matrices [\textit{M. Yannakakis}, J. Comput. Syst. Sci. 43, No. 3, 441--466 (1991; Zbl 0748.90074)]. Now consider the Puiseux series \(\mathcal{R} :=\mathbb{R}t\) whose elements are formal series \(a(t)=\) \(\sum _{e\in\mathbb{R}}a_{e}t^{e}\) for which the support \(E\) is a well-ordered subset of \(\mathbb{R}\); define \(\deg a(t):=\min E\) (with \(\deg0=\infty\)) and let \(\mathcal{R}_{+}\) consist of all elements with \(\deg a(t)>0\). It is known that \(\mathcal{R}\) is a real closed field under the usual operations of \(+\) and \(\cdot\) for series. Since extension complexity is defined by a first-order formula, theorems concerning extension complexity over \(\mathbb{R}\) remain valid over \(\mathcal{R}\). The image of \(\mathcal{R}_{+}\) under the degree map \(\deg\) is \(\mathbb{R}_{+}\cup\left\{ \infty\right\} \) and the operations \(+\) and \(\cdot\) are mapped onto the tropical operations \(\oplus\) (minimum) and \(\otimes\) (usual \(+\)). The author is interested in showing how this latter map can be used to infer results about the extension complexity of a polytope. For example (Corollary 4.2), he shows that if \(\mathcal{P}\) is a polytope in \(\mathcal{R}^{n}\) and \(S\in\mathcal{R}^{m\times n}\) is a slack matrix for \(\mathcal{P}\), then the extension complexity of \(\mathcal{P}\) is not smaller than the tropical factorization rank of \(\deg S\).
reviewed by: John D. Dixon
Mathematics Subject Classification ID: 15A80
Mathematics Subject Classification ID: 52B55
Mathematics Subject Classification ID: 15A23
Mathematics Subject Classification ID: 15B48
zbMATH DE Number: 6494240
zbMATH Keywords: convex polytope
zbMATH Keywords: tropical operation
zbMATH Keywords: extension complexity
zbMATH Keywords: nonnegative matrices
zbMATH Keywords: Puiseux series
zbMATH Keywords: tropical factorization
author: Ya. N. Shitov
MaRDI profile type: Publication
full work available at URL: s10107-014-0833-6
OpenAlex ID: W2073007675
cites work: Computing a nonnegative matrix factorization -- provably
cites work: Two Algorithmic Results for the Traveling Salesman Problem
cites work: Three notions of tropical rank for symmetric matrices
cites work: Nonnegative ranks, decompositions, and factorizations of nonnegative matrices
cites work: Extended formulations in combinatorial optimization
cites work: Tropical secant varieties of linear spaces
cites work: Q5290261
cites work: Q3661541
cites work: Extended formulations for polygons
cites work: Tropical patterns of matrices and the Gondran-Minoux rank function
cites work: Lifts of Convex Sets and Cone Factorizations
cites work: Polytopes of minimum positive semidefinite rank
cites work: On the geometric interpretation of the nonnegative rank
cites work: Algebraically Closed Fields Analogous to Fields of Puiseux Series
cites work: The complexity of tropical matrix factorization
cites work: An upper bound for nonnegative rank
cites work: Studying Non-negative Factorizations with Tools from Linear Algebra over a Semiring
cites work: Expressing combinatorial optimization problems by linear programs
DOI: 10.1007/S10107-014-0833-6
description: scientific article; zbMATH DE number 6494240