Semidefinite Darstellung konvexer Mengen


With the help of linear programming it is possible to optimize linear polynomials over polyhedra in an effective way. This technique is basically well-known since the 1940s and has countless applications. Since the 1980s it is known that also semidefinite programs can be solved in an effective way. They are a far reaching generalization of linear programs and have many important applications, e.g. in electrical engineering. A semidefinite program optimizes a linear objective function over the positive semidefinite matrices in a linear pencil of symmetric matrices. The question which problems can be modelled as semidefinite programs is of basic importance. It leads to the problem of characterizing the semidefinitely representable sets. It is easy to see that any such set is convex and semi-algebraic. Beyond this, no restrictions are visible. Since a few years the possibility has been discussed that conversely any convex semi-algebraic set might be semidefinitely representable, and has become known as the Helton-Nie conjecture. This conjecture has been verified for many important classes of examples, among them all convex sets in the plane. An important tool in establishing the conjecture for concrete examples is given by the so-called relaxation method. It constructs semidefinitely representable approximations which under favorable conditions become exact, i.e. coincide with the set to be approximated. However it is known that the conditions for exactness are frequently not satisfied. In such cases one is trying to combine the relaxation method with other techniques. To use relaxation in concrete applications one needs bounds within which the approximation becomes exact. These translate into degree bounds for generalized sums of squares representations of polynomials. So far, explicit degree bounds are known only in very few cases.

This proposal has two main goals. We plan to verify the Helton-Nie conjecture for large new classes of examples, among them many or even all convex sets in 3-space. On the other hand, we want to establish degree bounds in new situations, among them in particular lower bounds (hardly anything is known for those). For both goals, our point of departure is seen in new techniques that have so far not been used and that we expect to be powerful.

  • Department of Mathematics and Statistics
Funding sources
Name Finanzierungstyp Kategorie Project no.
Schwerpunktprogramm third-party funds research funding program 451/14
Further information
Period: 31.01.2014 – 30.01.2017