Semialgebraische Methoden in der algorithmischen Geometrie
Zusammenfassung der Projektergebnisse
Die algorithmische Geometrie hat sich in den letzten 30 Jahren entwickelt. Aus natürlichen Gründen konzentrierte man sich in den Anfangsjahren auf lineare (d.h. polyedrische) Probleme. Die dabei auftretenden geometrischen Probleme fallen in der Regel in den Bereich der diskreten oder kombinatorischen Geometrie. Ats algbrithmisches Werkzeug ist die lineare Optimierung von zentraler Bedeutung. Ausgangspunkt des Forschungsprojekts Semialgebraische Methoden in der algorithmischen Geometrie war die zentrale Herausforderung, Methoden, Strukturen und Algorithmen, die für polyedrisch definierte Objekte wohluntersucht und weitgehend verstanden sind, auf durch Kurven und Flächen definierte Objekte zu übertragen. Diese Forschungsrichtung wird auch als nichtlineare algorithmische Geometrie bezeichnet. Bei diesem Übergang kommt neben den im polyedrischen Fall zentralen algorithmischen und kombinatorischen Aspekten eine algebraisch-geometrische Komponente hinzu. Diese neue Komponente äußert sich oft darin, dass geometrische Algorithmen unter Zuhilfenahme von Methoden zum Lösen polynomialer Gleichungssysteme und Ungleichungssysteme formuliert werden. Viele dieser algorithmisch-geometrischen Grundprobleme bereiten vom Blickwinkel der algebraischen Geometrie große Herausforderungen, da es beispielsweise erforderlich ist, reelle Lösungen polynomialer Gleichungssystemen zu studieren, Degeneriertheiten vollständig zu charakterisieren sowie effiziente (symbolische, numerische, hybride, . . . ) und stabile Lösungsalgorithmen zu entwerfen. Vom Standpunkt der Optimierung entsprechen viele dieser Fragen dem Übergang von der linearen Optimierung zu quadratischen bzw. semidefiniten Problemen. Speziell wurden in dem Projekt Bernstein-Schranken für die Anzahl der Einbettungen von Laman-Graphen entwickelt, geometrische Konfigurationsprobleme der nichtlinearen algorithmischen Geometrie studiert, der Übergang von der linearen Optimierung zu Low- Rank-Optimierungsproblemen weiterentwickelt sowie die Beziehungen zur algebraischen Geometrie untersucht.
Projektbezogene Publikationen (Auswahl)
-
Exploiting symmetries in SDP-relaxations for polynomial optimization. Optimization online, Preprint 1466, 2006
L. Jansson, J.B. Lasserre, C. Riener, T. Theobald
-
Games of fixed rank: A hierarchy of bimatrix games. Economic Theory 42:157-173, 2010. Proc. Symposiumon Discrete Algorithms, 1124-1132, New Orleans (LA), 2007
R. Kannan, T. Theobald
-
Algorithmische Geometrie. Polyedrische und algebraische Methoden. Vieweg, Wiesbaden, 2008
M. Joswig, T. Theobald
-
Line problems in nonlinear computational geometry. In J.E. Goodman and J. Pach (eds.), Surveys on Discrete and Gompuiational Geometry: Twenty years later, Contemporary Mathematics, vol. 453, 411-432, AMS, 2008
F. Sottile, T. Theobald
-
Mixed volume techniques for embeddings of Laman graphs. Computational Geometry 43:84-93, 2010. Proc. European Workshop on Computational Geometry, 25-28, Nancy, 2008
R. Steffens, T. Theobald
-
Positive Polynome und semidefinite Optimiemng. Jahresberichte der DMV 110:57-76, 2008
C. Riener, T. Theobald
-
Enumerating the Nash equilibria of rank 1-games. In D. Avis, D. Bremner, A. Deza (eds.). Polyhedral computation, AMS/CRM, 115-130, 2009
T. Theobald
-
Mixed Volumes, Mixed Ehrhart Theory and Applications to Tropical Geometry and Linkage Configurations. Dissertation, Goethe-Universität Frankfurt, 2009
R. Steffens
-
Tropical bases by regular projections. Proceedings of the American Mathematical Society 137:2233-2241, 2009
K. Hept, T. Theobald
-
Nonlinear Computational Geometry. The IMA Volumes in Mathematics and its Applications, vol. 151. Springer-Verlag, New York, 2010
I. Emiris, F. Sottile, T. Theobald
