Selbstkonkordante Barrieren für Kegel nichtnegativer Polynome

Description

In der mathematischen Optimierung versucht man, einen Minimal- oder Maximalpunkt einer auf einer Menge <it>S</it> definierten Funktion numerisch mit Hilfe eines Rechners schnell zu finden. Ein bekanntes Beispiel, wo dies sehr gut gelingt, ist die lineare Optimierung, deren Anwendung in zahlreichen Gebieten der Wirtschaft und Technik selbstverständlich geworden ist. Es handelt sich dabei um die Minimierung einer linearen Funktion auf einem Polyeder <it>S<it>. Ein Polyeder ist definiert durch endlich viele lineare Ungleichungen, ist also ein "eckiges" konvexes Gebilde in einem mehr-, oft hochdimensionalen Raum, im Dreidimensionalen etwa ein Würfel oder eine Pyramide. Bei Inneren-Punkte-Verfahren wandert man im Inneren von <it>S</it> entlang absteigender Funktionswerte, um in ein Minimum zu gelangen. Man benötigt dazu gute sog. Barrieren für <it>S</it> zur Steuerung des Abstiegs, die anschaulich das Überschreiten des Randes von <it>S</it> in einer gewissen Weise ankündigen und durch eine passende Ablenkung verhindern. Es hat sich in letzter Zeit herausgestellt, dass man gute Barrieren auch für Mengen <it>S</it> finden kann, die allgemeiner sind als Polyeder, deren Ecken in gewisser Weise abgerundet sein dürfen. Dies führte zu einer sehr nützlichen Verallgemeinerung der linearen Optimierung, der sog. semidefiniten Optimierung. Diese neue Klasse der semidefiniten Optimierungsprobleme besitzt aus algebraischer Sicht völlig natürliche Verallgemeinerungen, die geometrisch einer noch größeren Abrundung der Ecken der Menge <it>S</it> entspricht. Ziel des Projektes ist es, auch für solche Mengen <it>S</it> gute Barrieren zu finden.




A barrier for a convex cone of a finite-dimensional real vector space is a real-valued function on the interior of the cone with certain properties. The most basic property is that they tend to infinity when one approaches a point on the boundary of the cone. The crucial quality of a barrier is however that its first three derivatives are interlaced in a certain way. These properties can be used to minimize a linear function defined on the intersection of an affine subspace with the cone. In search of the minimum, interior point methods wander around in the interior of the cone. It is such a barrier which steers them towards the minimum without leaving the cone. Every such cone posesses a barrier which can be written down in a certain way and is called the universal barrier. In general, the universal barrier is hard to compute. Examples where the universal barrier (up to scaling) turns out to be quickly computable are the following two cones: The nonnegative orthant in real n-space, and the cone of positive semidefinite quadratic forms in the vector space of quadratic forms in a fixed number of variables. This leads to polynomial time interior point methods for linear programming in the first case, and for semidefinite programming in the second case. The aim of the current project is to understand numerous other cones of positive polynomials from this perspective of interior point methods. As an example take cones of positive semidefinite forms of higher degree.

Institutions
  • FB Mathematik und Statistik
Funding sources
NameProject no.DescriptionPeriod
Bundesministerium für Wirtschaft und Technologie547/05no information
Further information
Period: 01.09.2005 – 31.08.2007