Speaker: Hartwig Bosse

Title: Polynomial inequalities representing polyhedra

Abstract:

The power of linear programming, one of today's most important optimization techniques, is - to a large extent - based on deep insights into the interplay between the geometry and algebraic description of polyhedra. A new method of description is implied by recent results in real-algebraic geometry: Polyhedra fall into the class of basic closed semi-algebraic sets, the intersections of solutions of finitely-many non-strict polynomial inequalities. Due to a deep result of Broecker and Scheiderer ([Bro91] and [Sch89]), every n-dimensional basic closed semi-algebraic set (and hence every n-dimensional polyhedron) can be described by at most n(n+1)/2 polynomial inequalities. Surprisingly, this is true independently on the combinatorial, algebraic, or geometric complexity of the set. Unfortunately all known proofs of this general result are non-constructive. In this talk we present two new results on the description of polyhedra by polynomial inequalities: The number of polynomials needed is reduced from quadratic to linear (2n-1 inequalities suffice) and an explicit construction of such systems of polynomials is given. The general case will be deduced from a visual tour through the constructions in dimensions n=2 and n=3, the possibilites of different approaches will be discussed.

[Brö91] L. Broecker, On basic semi-algebraic sets, Expo Math. 9 (1991), 289-334.
[Sch89] C. Scheiderer, Stability index of real varieties, Inventiones Math 97 (1989), no.~3, 467-483.