http://www.tu-ilmenau.de

Logo TU Ilmenau


Arbeitsgruppe Optimierung


headerphoto Arbeitsgruppe Optimierung
Ansprechpartner

Univ.-Prof. Dr. rer. nat. habil. Gabriele Eichfelder

Fachgebietsleiterin

Telefon +49 3677 69-3628

E-Mail senden

INHALTE

Mengen-Semidefinite Optimierung

Kopositive Optimierung

In der mengen-semidefiniten Optimierung werden Optimierungsprobleme mit einer vektorwertigen Zielfunktion und speziellen Ungleichungsrestriktionen untersucht. Ist Y ein normierter Vektorraum und K eine Teilmenge von Y, so basieren diese Ungleichungsrestriktionen auf einer Halbordnung im Raum der stetigen linearen Abbildungen L(Y,Y * ), die durch den Kegel C^K_L der so genannten K-semidefiniten Abbildungen gegeben ist:

C^K_L := C^K_{L(Y, Y^*)} := \{A \in L(Y, Y*) \; | \; \langle Ay, y \rangle \geq 0 für alle y \in K\}.

Es wird also gefordert, dass die zur linearen Abbildung A gehörige quadratische Form nichtnegativ auf einer Teilmenge K des Raumes Y ist. Im endlichdimensionalen Fall Y=R^n erhalten wir für K=R^n semidefinite und für K=R^n_+ kopositive Optimierungsprobleme und erweitern diese wichtigen Problemklassen vektorwertig. Für den K-semidefiniten Kegel wurden bereits Rechenregeln und verschiedene Eigenschaften sowie der Dualkegel und das Innere untersucht. Für das Vektoroptimierungsproblem wurden Optimalitätsbedingungen sowie Dualitätsaussagen entwickelt. Zur Lösung dieser Probleme steht ein Penalty-Ansatz zur Verfügung.

Es konnte weiterhin gezeigt werden, dass sich quadratische nichtkonvexe Optimierungsprobleme mit linearen Nebenbedingungen und Binärvariablen über einer Menge K unter geeigneten Voraussetzungen an K als lineare Optimierungsprobleme über den Dualkegel der K-semidefiniten Matrizen formulieren lassen.

Ausgewählte Publikationen:

G. Eichfelder und J. Jahn, Set-semidefinite Optimization, Journal of Convex Analysis, 2008.

G. Eichfelder und J. Jahn, Foundations of set-semidefinite optimization. Kapitel 18 in: Nonlinear Analysis and Variational Problems, P. Pardalos, Th. M. Rassias und A. A. Khan (Eds.), Springer, 259 – 284, 2009.

G. Eichfelder und J. Povh, On the set-semidefinite representation of nonconvex quadratic programs over arbitrary feasible sets, Optimization, Vol. 62(5), 597 - 627, 2013.

P. Dickinson, G. Eichfelder und J. Povh, On the set-semidefinite representation of nonconvex quadratic programs over arbitrary feasible sets, Optimization Letters Vol. 7(6), 1387 – 1397, 2013.

Zuletzt geändert am 01.04.2015

Nach oben

Numerische Verfahren der kopositiven Optimierung

Kopositive Optimierungsprobleme sind lineare Optimierungsprobleme über dem Kegel der kopositiven Matrizen. Diese Problemklasse ist von besonderem Interesse, da sich etwa das Max-Clique-Problem als kopositives Optimierungsproblem formulieren lässt. Eine Matrix A ist kopositiv, wenn deren quadratische Form xTAx für alle nicht-negativen x nur nicht-negative Werte annimmt. Um eine Matrix auf Kopositivität zu testen, wurde ein Branch-and-Bound-Verfahren entwickelt, welches auf verschiedenen hinreichenden Kriterien und Simplexpartitionierungen basiert. Zur Auswertung der hinreichenden Kriterien sind lineare und konvexe Optimierungsprobleme zu lösen.

Unter Nutzung von theoretischen Resultaten, die sich durch einen Zusammenhang zu gemischt-ganzzahligen Optimierungsproblemen und zu linearen Komplementaritätsproblemen ergeben, wurden weitere hinreichende und notwendige Kriterien für Kopositivät entwickelt und zu einem weiteren numerischen Algorithmus kombiniert.

Ausgewählte Publikationen:

G. Eichfelder und I. Bomze, Copositivity detection by difference-of-convex decomposition and ω-subdivision. Mathematical Programming Ser. A, Vol. 138, 365 – 400, 2013.

C. Brás, G. Eichfelder und J. Júdice, Copositivity tests based on the Linear Complementarity Problem. Preprint-Serie des Instituts für Mathematik, TU Ilmenau, 2014.

Zuletzt geändert am 01.04.2015

Nach oben