Claudia Adams

• 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.