Sums of squares in convex algebraic geometry

点击翻译按钮获取中文摘要

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. One can easily see that any such set is convex and semi-algebraic. Conversely, plenty of important classes of convex semi-algebraic sets are known to have semidefinite representations. For many years it was therefore conjecture that every convex semi-algebraic set should have a semidefinite representation (so-called Helton-Nie conjecture). This conjecture was recently shown to be false by the project leader. With the help of a new characterization, classes of explicit counter-examples were constructed. This characterization is based on representations of positive polynomials by sums of squares. However, in concrete cases it is often cumbersome to decide whether this condition holds. This is why alternative criteria are needed that can be handled in a more flexible way. Besides, a variety of new open question has emerged through the disproof of the Helton-Nie conjecture. One of the main goals of this project is to isolate such flexible criteria for semidefinite representability, and to answer at least some of the open questions. Another question of theoretical and practical importance asks for the complexity of semidefinite representations of given sets. Very little is known here in general. For convex hulls of curves however, concrete results seem possible, which is another major goal of the project. As with the first goal, sums of squares representations are at the center of this question as well, and the problem is to give upper bounds for the degrees of the summands. A third subproject studies the family of all sums of squares representations of a given polynomial. They form a compact convex body about whose structure only little is known so far. The use of new techniques is expected to bring a significant advance here.