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.