Some aspects of the optimization over the copositive and the completely positive cone

Einige Aspekte der Optimierung über dem kopositiven und dem vollständig positiven Kegel

  • Copositive programming is concerned with the problem of optimizing a linear function over the copositive cone, or its dual, the completely positive cone. It is an active field of research and has received a growing amount of attention in recent years. This is because many combinatorial as well as quadratic problems can be formulated as copositive optimization problems. The complexity of these problems is then moved entirely to the cone constraint, showing that general copositive programs are hard to solve. A better understanding of the copositive and the completely positive cone can therefore help in solving (certain classes of) quadratic problems. In this thesis, several aspects of copositive programming are considered. We start by studying the problem of computing the projection of a given matrix onto the copositive and the completely positive cone. These projections can be used to compute factorizations of completely positive matrices. As a second application, we use them to construct cutting planes to separate a matrix from the completely positive cone. Besides the cuts based on copositive projections, we will study another approach to separate a triangle-free doubly nonnegative matrix from the completely positive cone. A special focus is on copositive and completely positive programs that arise as reformulations of quadratic optimization problems. Among those we start by studying the standard quadratic optimization problem. We will show that for several classes of objective functions, the relaxation resulting from replacing the copositive or the completely positive cone in the conic reformulation by a tractable cone is exact. Based on these results, we develop two algorithms for solving standard quadratic optimization problems and discuss numerical results. The methods presented cannot immediately be adapted to general quadratic optimization problems. This is illustrated with examples.
  • Eine wichtige Problemklasse in der Optimierung stellen quadratische Probleme dar, welche im Allgemeinen aber schwer zu lösen sind. Ein Ansatz, der sich in den letzten Jahren entwickelt und verbreitet hat, besteht in der Umformulierung quadratischer Probleme in sogenannte kopositive Programme. Kopositive Programme sind lineare Optimierungsprobleme über dem Kegel der kopositiven Matrizen oder dem Dualkegel, dem Kegel der vollständig positiven Matrizen. Die Schwierigkeit dieser Probleme liegt in der Kegelbedingung. Ein besseres Verständnis dieser Kegel trägt daher zum besseren Verständnis und zum Finden neuer Lösungsmethoden für quadratische Probleme bei. In der vorliegenden Dissertation beschäftigen wir uns mit verschiedenen Aspekten der kopositiven Optimierung. Es wird gezeigt, wie die Projektion einer Matrix auf den kopositiven sowie den vollständig positiven Kegel berechnet werden kann. Diese Projektionen werden im Anschluss verwendet, um Faktorisierungen vollständig positiver Matrizen zu berechnen. Eine zweite Anwendung besteht in der Berechnung von Schnittebenen für Optimierungsprobleme über dem vollständig positiven Kegel. Für Matrizen, deren Graph dreiecksfrei ist, beschreiben wir eine alternative Methode zur Berechnung von Schnittebenen, die diese besondere Struktur ausnutzt. Schließlich betrachten wir kopositive und vollständig positive Programme, die sich als Umformulierungen quadratischer Optimierungsprobleme ergeben. Dabei beschäftigen wir uns zunächst mit dem Standard-quadratischen Optimierungsproblem. Wir untersuchen verschiedene Klassen von Zielfunktionen, für die der Optimalwert des Problems durch das Lösen eines linearen oder semidefiniten Programms bestimmt werden kann. Dies führt zu zwei Algorithmen zum Lösen Standard-quadratischer Optimierungsprobleme. Die Algorithmen werden anhand numerischer Beispiele illustriert und diskutiert. Die vorgestellten Methoden lassen sich nicht ohne Weiteres auf kopositive Formulierungen von allgemeineren quadratischen Optimierungsproblemen übertragen. Dies verdeutlichen wir anhand von Beispielen.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Julia Witzel
URN:urn:nbn:de:hbz:385-8346
Advisor:Mirjam Dür
Document Type:Doctoral Thesis
Language:English
Date of completion:2014/01/15
Publishing institution:Universität Trier
Granting institution:Universität Trier, Fachbereich 4
Date of final exam:2013/09/25
Release Date:2014/01/15
Tag:Schnittebenen; kopositiver Kegel; vollständig positiver Kegel
completely positive cone; copositive cone; cutting planes
GND Keyword:Kegel; Optimierung; Quadratische Optimierung
Institutes:Fachbereich 4 / Mathematik
Dewey Decimal Classification:5 Naturwissenschaften und Mathematik / 51 Mathematik / 510 Mathematik
MSC-Classification:90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C20 Quadratic programming
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C22 Semidefinite programming
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C26 Nonconvex programming, global optimization

$Rev: 13581 $