Das Suchergebnis hat sich seit Ihrer Suchanfrage verändert. Eventuell werden Dokumente in anderer Reihenfolge angezeigt.
  • Treffer 13 von 516
Zurück zur Trefferliste

Copositivity in Infinite Dimension

  • Many combinatorial optimization problems on finite graphs can be formulated as conic convex programs, e.g. the stable set problem, the maximum clique problem or the maximum cut problem. Especially NP-hard problems can be written as copositive programs. In this case the complexity is moved entirely into the copositivity constraint. Copositive programming is a quite new topic in optimization. It deals with optimization over the so-called copositive cone, a superset of the positive semidefinite cone, where the quadratic form x^T Ax has to be nonnegative for only the nonnegative vectors x. Its dual cone is the cone of completely positive matrices, which includes all matrices that can be decomposed as a sum of nonnegative symmetric vector-vector-products. The related optimization problems are linear programs with matrix variables and cone constraints. However, some optimization problems can be formulated as combinatorial problems on infinite graphs. For example, the kissing number problem can be formulated as a stable set problem on a circle. In this thesis we will discuss how the theory of copositive optimization can be lifted up to infinite dimension. For some special cases we will give applications in combinatorial optimization.
  • Viele kombinatorische Optimierungsprobleme können als konvexe Probleme über einem Kegel formuliert werden, beispielsweise das stabile Mengen Problem, das Cliquenproblem oder das Problem des maximalen Schnitts. Insbesondere NP-schwere Probleme können als copositive Optimierungsprobleme formuliert werden. Hierbei liegt die Schwierigkeit des neuen Problems vollständig in der Copositivitätsbedingung. Copositive Optimierung ist ein vergleichsweise neues Thema in der Optimierung. Es behandelt die Optimierung über dem sogenannten copositiven Kegel, welcher eine Obermenge des positiv semidefiniten Kegels darstellt. Sein Dualkegel ist der Kegel der vollständig positiven Matrizen, in welchem alle Matrizen enthalten sind, die als Summe von nichtnegativen, symmetrischen Vektor-Vektor-Produkten zerlegt werden können. Die zugehörigen Optimierungsprobleme haben eine lineare Zielfunktion, lineare Nebenbedingungen in der Matrixvariable und eine Kegelbedingung. Manche Optimierungsprobleme können als kombinatorische Probleme über unendlich dimensionalen Graphen formuliert werden, wie zum Beispiel die Berechnung der sogennanten Kusszahl, welche als stabile Mengen Problem über der Sphäre beschrieben werden kann. In der vorliegenden Arbeit werden wir diskutieren, inwieweit das Konzept der Copositivität in einem unendlichdimensionalen Raum verallgemeinert werden kann. Für Spezialfälle werden wir Anwendungen in der kombinatorischen Optimierung präsentieren.

Volltext Dateien herunterladen

Metadaten exportieren

Weitere Dienste

Teilen auf Twitter Suche bei Google Scholar
Metadaten
Verfasserangaben:Claudia Adams
URN:urn:nbn:de:hbz:385-1-10740
DOI:https://doi.org/10.25353/ubtr-xxxx-dad9-6163
Gutachter:Mirjam Dür, Leonhard Frerick
Betreuer:Mirjam Dür, Leonhard Frerick
Dokumentart:Dissertation
Sprache:Englisch
Datum der Fertigstellung:13.02.2019
Datum der Veröffentlichung:13.02.2019
Veröffentlichende Institution:Universität Trier
Titel verleihende Institution:Universität Trier, Fachbereich 4
Datum der Abschlussprüfung:11.02.2019
Datum der Freischaltung:14.03.2019
Freies Schlagwort / Tag:Coposititive, Infinite Dimension
GND-Schlagwort:Optimierung
Seitenzahl:120
Institute:Fachbereich 4
DDC-Klassifikation:5 Naturwissenschaften und Mathematik / 51 Mathematik / 510 Mathematik
Lizenz (Deutsch):License LogoCC BY-NC-ND: Creative-Commons-Lizenz 4.0 International

$Rev: 13581 $