Algorithms to project convex sets with applications in nonconvex programming and for a calculus of convex sets

• Applicant: Professor Dr. Andreas Löhne
• Subject Area: Mathematics
• Term: from 2015 to 2022
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 271835661

• Final Report Year: 2022

Final Report Abstract

Kann ein Computer mit Mengen rechnen? Unter bestimmten Voraussetzungen ist das möglich. Zum einen müssen die Mengen endlich darstellbar sein. Zum anderen ist es für bestimmte Klassen von Mengen einfacher als für andere. In diesem Projekt wurden Theorie, Algorithmen und Software entwickelt um Operationen in bestimmten Klassen von Mengen ausführen zu können. Zunächst wurde das für konvexe Polyeder gemacht. Später wurde das (bisher nur in Bezug auf die Theorie) auf die Klasse der SD-darstellbaren Mengen (spectrahedral shadows) erweitert. Das sind Projektionen von Mengen, die sich durch lineare Matrixungleichungen darstellen lassen. Projektionsdarstellungen von bestimmten konvexen Mengen sind meist relativ einfach zu bekommen. Sie haben allerdings den Nachteil, dass bestimmte Informationen nicht direkt zugänglich sind. Im polyedrischen Fall kennt man im Allgemeinen weder eine Ungleichungs- noch eine Ecken-/Richtungs-Darstellung. Ohne diese ist etwa eine graphische Darstellung schwierig. Hier kommen die Algorithmen ins Spiel, die meist polyedrische Approximationen der Mengen in Projektionsdarstellung berechnen, die in Ungleichungs- und Ecken-/Richtungsdarstellung gegeben sind. Solche Algorithmen wurden im Projekt entwickelt und verbessert. Die Forschung soll fortgesetzt werden. Insbesondere sollen die theoretischen Ergebnisse des Projekts in eine neue Variante der Software bensolve tools einfließen. In den Approximationsalgorithmen taucht als Teilproblem die Berechnung von Ecken eines durch Ungleichungen dargestellten Polyeders auf. Gleitkommaratithmetik kann hierbei prinzipiell zu völlig falschen Ergebnissen führen. Exakte Arithmetik ist dagegen sehr langsam. Es wurden Ergebnisse für die Dimensionen 2 und 3 erzielt, die sicherstellen, dass Gleitkomma-Arithmetik wenigstens noch ein Ergebnis im approximativen Sinne liefert. Für weitergehende Untersuchungen zu dieser Problematik soll ein neuer Projektantrag gestellt werden.

Publications

• Approximation of Spectrahedral Shadows and Spectrahedral Calculus. Friedrich Schiller University Jena, PhD. thesis, 2019
  Daniel Ciripoi
  
• Computing convex hulls of trajectories. Revista de la Unión Matemática Argentina, 637-662.
  Ciripoi, Daniel; Kaihnsa, Nidhi; Löhne, Andreas & Sturmfels, Bernd
  
• Solving bilevel problems with polyhedral constraint set. Journal of Applied and Numerical Optimization, 1(3).
  Andreas Löhne; Daniel Dörfler; Alexandra Rittmann & Benjamin Weißing
  
• Solving polyhedral d.c. optimization problems via concave minimization. Journal of Global Optimization, 78(1), 37-47.
  vom Dahl, Simeon & Löhne, Andreas
  
• A Benson-type algorithm for bounded convex vector optimization problems with vertex selection. Optimization Methods and Software, 37(3), 1006-1026.
  Dörfler, Daniel; Löhne, Andreas; Schneider, Christopher & Weißing, Benjamin
  
• On the approximation error for approximating convex bodies using multiobjective optimization. Applied Set-Valued Analysis and Optimization, 3(3).
  Andreas Löhne; Fangyuan Zhao & Lizhen Shao
  
• A polyhedral approximation algorithm for recession cones of spectrahedral shadows
  Daniel Dörfler & Andreas Löhne
  
• Approximate vertex enumeration
  Andreas Löhne
  
• On the Approximation of Unbounded Convex Sets by Polyhedra. Journal of Optimization Theory and Applications, 194(1), 265-287.
  Dörfler, Daniel