Quadratic Optimization:Copositive Modelling, Algorithms and Aspects of Duality

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

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Duy Van Nguyen
URN:urn:nbn:de:hbz:385-11424
Title Additional (German):Quadratische Optimierung: copositive Modellierung, Algorithmen und Aspekte der Dualität
Advisor:Mirjam Dür
Document Type:Doctoral Thesis
Language:German
Date of completion:2018/06/12
Publishing institution:Universität Trier
Granting institution:Universität Trier, Fachbereich 4
Date of final exam:2018/05/24
Release Date:2018/06/12
Tag:Copositive und Vollständig positive Optimierung
completely positive modelling and optimization; copositive optimization
GND Keyword:Dualitätstheorie; Quadratische Optimierung
Comment:
DOI: https://doi.org/10.25353/UBTR-0451-5300-21XX
Institutes:Fachbereich 4 / Mathematik
Dewey Decimal Classification:5 Naturwissenschaften und Mathematik / 51 Mathematik / 510 Mathematik

$Rev: 13581 $