Die Forschungsinteressen der Arbeitsgruppe Optimierung liegen in der algorithmischen Behandlung von NP-schweren kombinatorischen Optimierungsaufgaben. Da für derartige Probleme keine effizienten Algorithmen bekannt sind und möglicherweise gar nicht existieren, stellt sich aus praktischer Sicht die Frage nach effizienten Näherungsmethoden.
Bei einer Reihe von Graphenproblemen hat sich gezeigt, dass man mit rein linearen Ansätzen die Menge der zulässigen Punkte des Problems nur sehr ungenau beschreiben kann, siehe etwa „Färbungszahl“ oder „Max-Cut“. Der polyedrische Zugang erfordert entweder eine stückweise lineare Approximation oder eine höherdimensionale Einbettung des Problems. Im Gegensatz dazu bieten „Matrixrelaxierungen“ die Möglichkeit, quadratische Terme direkt zu behandeln. Dabei wird die zulässige Menge, bestehend aus semidefiniten Matrizen mit Rang Eins, eingebettet in den Kegel der semidefiniten Matrizen.
Die Arbeitsgruppe untersucht solche Matrixrelaxierungen in Verbindung mit konvexer Analysis. Das Hauptaugenmerk liegt dabei auf linearen Optimierungsaufgaben über dem Kegel der positiv semidefiniten Matrizen, die Nichtlinearität liegt somit nur im Kegel. Eine Reihe von Graphenzerlegungsproblemen führen auf derartige Matrixrelaxierungen. Die algorithmische Herausforderung liegt in der Behandlung grosser Instanzen, etwa mit Matrizen der Ordnung 1000 und einer Vielzahl an kombinatorischen Nebenbedingungen. Dazu werden neben Standardmethoden der nichtlinearen Optimierung auch Subgradientenmethoden und Projektionstechniken verwendet.
Die untersuchten Relaxierungen und die dafür entwickelten Lösungsmethoden werden in Branch-and-Bound Verfahren eingebettet um exakte Algorithmen zu Lösung der kombinatorischen Optimierungsprobleme zu erhalten. Die von der Arbeitsgruppe betreute Internetseite BiqMac (biqmac.aau.at) bietet die Möglichkeit, quadratische Probleme mit 0-1 Variablen exakt zu lösen.
Ein weiterer Fokus der Arbeitsgruppe liegt in der Entwicklung von Aktive-Mengen-Methoden, die auf kontinuierliche quadratische konvexe (und neuerdings auch nicht-konvexe) Optimierungsprobleme mit verschiedenen Nebenbedingungstypen angewandt werden können.
