Suche   SiteMap
Home
A bis Z
BIB-KAT
Andere Bibliothekskataloge
Digitale Medien
Dokumentlieferung
Fachspezifische Informationen
Suchhilfen und Datenbanken
 
Eingang zum Volltext in OPUS

Hinweis zum Urheberrecht

Dissertation zugänglich unter
URN: urn:nbn:de:hbz:385-11424
URL: http://ubt.opus.hbz-nrw.de/volltexte/2018/1142/


Quadratic Optimization:Copositive Modelling, Algorithms and Aspects of Duality

Quadratische Optimierung: copositive Modellierung, Algorithmen und Aspekte der Dualität

Nguyen, Duy Van

pdf-Format:
Dokument 1.pdf (802 KB) (Die ganze Disseratition)

Bookmark bei Connotea Bookmark bei del.icio.us
SWD-Schlagwörter: Quadratische Optimierung , Dualitätstheorie
Freie Schlagwörter (Deutsch): Copositive und Vollständig positive Optimierung
Freie Schlagwörter (Englisch): copositive optimization, completely positive modelling and optimization
MSC - Klassifikation: MSC - Math
Institut: Mathematik
Fakultät: Fachbereich 4
DDC-Sachgruppe: Mathematik
Dokumentart: Dissertation
Hauptberichter: Dür, Mirjam Univ. Prof. Dr.
Sprache: Deutsch
Tag der mündlichen Prüfung: 24.05.2018
Erstellungsjahr: 2018
Publikationsdatum: 12.06.2018
Bemerkung: DOI: https://doi.org/10.25353/UBTR-0451-5300-21XX
Kurzfassung auf Deutsch: Quadratische Optimierungsprobleme (QP) haben ein breites Anwendungsgebiet, wie beispielsweise kombinatorische Probleme einschließlich des maximalen Cliquenroblems. Motzkin und Straus [25] zeigten die Äquivalenz zwischen dem maximalen Cliquenproblem und dem standard quadratischen Problem. Auch mathematische Statistik ist ein weiteres Anwendungsgebiet von (QP), sowie eine Vielzahl von ökonomischen Modellen basieren auf (QP), z.B. das quadratische Rucksackproblem. In [5] Bomze et al. haben das standard quadratische Optimierungsproblem (StQP) in ein Copositive-Problem umformuliert. Im Folgenden wurden Algorithmen zur Lösung dieses copositiviten Problems von Bomze und de Klerk in [6] und Dür und Bundfuss in [9] entwickelt. Während die Implementierung dieser Algorithmen einige vielversprechende numerische Ergebnisse hervorbrachten, konnten die Autoren nur die copositive Neuformulierung des (StQP)s lösen. In [11] präsentierte Burer eine vollständig positive Umformulierung für allgemeine (QP)s, sogar mit binären Nebenbedingungen. Leider konnte er keine Methode zur Lösung für ein solches vollständig positives Problem präsentieren, noch wurde eine copositive Formulierung vorgeschlagen, auf die man die oben erwähnten Algorithmen modifizieren und anwenden könnte, um diese zu lösen.
Diese Arbeit wird einen neuen endlichen Algorithmus zur Lösung eines standard quadratischen Optimierungsproblems aufstellen. Desweiteren werden in dieser Thesis copositve Darstellungen für ungleichungsbeschränkte sowie gleichungsbeschränkte quadratische Optimierungsprobleme vorgestellt. Für den ersten Ansatz wurde eine vollständig positive Umformulierung des (QP) entwickelt. Die copositive Umformulierung konnte durch Betrachtung des dualen Problems des vollständig positiven Problems erhalten werden. Ein direkterer Ansatz wurde gemacht, indem das Lagrange-Duale eines äquivalenten quadratischen Optimierungsproblems betrachtet wurde, das durch eine semidefinite quadratische Nebenbedingung beschränkt wurde. In diesem Zusammenhang werden Bedingungen für starke Dualität vorgeschlagen.
Kurzfassung auf Englisch: Quadratic optimization problems (QP) have a wide area of application such as combinatorial problems including the max clique problem. Motzkin and Straus [25] showed the equivalence between the max clique problem and the standard quadratic problem. Also mathematical statistics is another field of application of (QP): Many economic models are based on (QP), e.g. the quadratic knapsack problem. In [5] Bomze et al. reformulated the standard quadratic problem (StQP) into a copositive problem. Subsequently, algorithms to solve this copositive problem were established by Bomze and de Klerk in [6] and Dür and Bundfuss in [9]. While the implementation of those algorithms showed some promising numerical results, they were only able to solve the copositive reformulation of (StQP). In [11] Burer presented a completely positive reformulation for quadratic optimization problems (QP) even with binary constraints. Unfortunately he did not present a method to solve such a completely positive problem nor did he gave a copositive reformulation, for which one could have modify the algorithms mentioned above to solve these problems. This thesis will establish a new finite algorithm to solve a standard quadratic optimization problem. Furthermore in this thesis copositve representations for quadratic optimization problems restricted by inequalities as well as quadratic optimization problems restricted by equalities will be presented. For the first approach a completely positive reformulation of the (QP) was developed. The copositive reformulation could be obtained by considering the dual problem of the completely positive problem. A more direct approach was made by considering the Lagrangian dual of an equivalent quadratic optimization problem restricted by a semidefinit quadratic constraint. In this context conditions for strong duality are proposed.

Home | Suchen | Veröffentlichen | Hilfe | Viewer