A lower bound for the complexity of linear optimization from a quantifier-elimination point of view

Abstract

We analyze the arithmetic complexity of the feasibility problem in linear optimization theory as a quantifier-elimination problem. For the case of polyhedra defined by 2n halfspaces in R^n we prove that, if dense representation is used to code polynomials, any quantifier-free formula expressing the set of parameters describing nonempty polyhedra has size Ω(4n ).