Discrete geometry and optimization
| dc.contributor.advisor | Joswig, Michael | |
| dc.contributor.author | Radons, Manuel | |
| dc.contributor.grantor | Technische Universität Berlin | |
| dc.contributor.referee | Joswig, Michael | |
| dc.contributor.referee | O'Rourke, Joseph | |
| dc.contributor.referee | Gaubert, Stéphane | |
| dc.date.accepted | 2022-10-26 | |
| dc.date.accessioned | 2022-12-09T14:12:58Z | |
| dc.date.available | 2022-12-09T14:12:58Z | |
| dc.date.issued | 2022 | |
| dc.description.abstract | This thesis analyses three problems from discrete geometry and optimization via discreteanalytic hybrid methods. The absolute value equation (AVE) is a piecewise linear system which is equivalent to the linear complementarity problem (LCP) and thus generalizes linear and quadratic programming. Unique solvability for arbitrary right-hand sides has long been comprehensively characterized for both systems, but not non-unique solvability. To fill this gap in the theory, we analyze homotopies of the identity map and the piecewise linear function corresponding to the AVE. Doing so, we identify certain real eigenvalues of the coefficient matrix of the AVE that determine the singularity-structure of these homotopies. Let k be the number of these eigenvalues which is larger than one. We prove that the mapping degree of the aforementioned piecewise linear function is congruent to (k +1)mod 2. We also derive an exact formula for the degree, which is more technical. Finally, we develop the analogous results for the LCP. The calibration of internal combustion engines is a problem that has risen to prominence during the so-called diesel crisis. Engine behavior can be modeled as a function from the space of actuators to the space of performance measurands. A calibration solution is a set of lookup tables that associate performance demands to points in the actuator space which achieve these demands, while respecting side constraints such as emission standards. We develop an adaptive multigrid method for identifying and circumventing loci of turbulence, which are the cause of emission spikes during the generation of the lookup tables. With the resulting algorithm we calibrate a benchmark engine model in accordance with several EURO emission norms. Dürer’s problem asks whether every 3-polytope has a net, that is, whether it is possible to cut it along some spanning tree of its edge graph so that the resulting connected surface may be unfolded flat into the plane without self-overlaps. A 3-prismatoid is the convex hull of two polygons A, B in parallel planes HA and HB. It is called nested if the orthogonal projection of A to HB is properly contained in B, or vice versa. We show that every nested prismatoid has a net. To this end we adapt and extend an unfolding technique pioneered by O’Rourke in his work on nearly flat, acutely triangulated convex caps. The basic approach is to project a nested prismatoid P—a convex cap by definition—to the plane HB, establish a cutting scheme for the flat polytope, lift the scheme back into P, and then prove that a certain continuous deformation of the unfolding of the flat polytope into the unfolding of P does not cause overlaps. | en |
| dc.description.abstract | Diese Arbeit behandelt drei Probleme aus der diskreten Geometrie und Optimierung mittels diskret-analytischer Hybridmethoden. Die Absolutwertgleichung (AWG) ist ein stückweise lineares Gleichungssystem, das äquivalent zum linearen Komplementaritätsproblem (LCP) ist und daher lineare und quadratische Programmierung generalisiert. Die vollständige Charakterisierung eindeutiger Lösbarkeit von AWG und LCP für beliebige rechte Seiten sind klassische Resultate der Literatur. Eine vergleichbare Charakterisierung der nicht-eindeutigen Lösbarkeit existiert jedoch nicht. Um diese Lücke in der Theorie zu schließen, analysiseren wir Homotopien der Identitätsabbildung und der stückweise linearen Funktion, welche durch die AWG definiert wird. Hierbei identifizieren wir bestimmte reelle Eigenwerte der Koeffizientenmatrix der AWG, welche die Singulariätsstruktur der untersuchten Homotopien determinieren. Es sei k die Zahl der besagten Eigenwerte, welche größer als eins sind. Wir beweisen, dass in diesem Fall der Abbildungsgrad der stückweise linearen Funktion, welche der AWG korrespondiert, kongruent zu (k + 1)mod 2 ist. Desweiteren leiten wir eine exakte Formel für den Abbildungsgrad her. Schließlich entwickeln wir die analogen Ergebnisse für das LCP. Die Kalibrierung von Verbrennungsmotoren ist ein Problem, das während der sogenannten Dieselkrise zur Prominenz gelangte. Das Motorenverhalten kann als eine Funktion vom Raum der Aktuatoren in den Raum der Leistungsmesswerte modelliert werden. Eine Kalibrierungslösung ist ein Satz von Lookup-Tabellen, die einer Menge von Leistungsanforderungen eine Menge von Punkten im Aktuatorenraum zuordnet, welche besagte Anforderungen, unter Berücksichtigung von Nebenbedingungnen wie z.B. Emissionsgrenzen, realisieren. Wir entwickeln ein adaptives Mehrgitterverfahren um bei der Erstellung der Kalibrierungslösung Regionen stark nichtlinearen Motorenverhaltens im Aktuatorenraum, welche eine Hauptursache von Emissionsspitzen sind, zu identifizieren und zu umgehen. Mittels des resultierenden Algorithmus kalibrieren wir ein Benchmark-Motorenmodell unter Einhaltung verschiedener EURO-Abgasnormen. Dürers Problem stellt die Frage, ob jedes 3-Polytop ein Netz hat, das heißt, ob man es entlang eines Spannbaums seines Kantengraphen aufschneiden kann, so dass die resultierende zusammenhängende Fläche ohne Selbstüberlappungen in die Ebene aufgefaltet werden kann. Ein 3-Prismatoid ist die konvexe Hülle zweier Polygone in parallelen Ebenen HA und HB. Es wird verschachtelt genannt, falls die orthogonale Projektion von A auf HB echt in B enthalten ist. Wir beweisen, dass jedes verschachtelte Prismatoid ein Netz hat. Hierzu adaptieren und erweitern wir eine Auffaltungsstrategie, die von O’Rourke eingeführt wurde. Der Grundgedanke ist, ein verschachteltes Prismatoid P nach HB zu projizieren, ein Schnittschema für das flache Polytop einzuführen, nach P zurück zu projizieren und dann zu beweisen, dass eine bestimmte stetige Verformung der Auffaltung des flachen Polytops in die Auffaltung von P nicht zu Überlappungen führt. | de |
| dc.identifier.uri | https://depositonce.tu-berlin.de/handle/11303/17792 | |
| dc.identifier.uri | https://doi.org/10.14279/depositonce-16581 | |
| dc.language.iso | en | |
| dc.rights.uri | https://creativecommons.org/licenses/by/4.0/ | |
| dc.subject.ddc | 510 Mathematik | de |
| dc.subject.other | absolute value equation | en |
| dc.subject.other | generalized Perron-Frobenius theory | en |
| dc.subject.other | degree theory | en |
| dc.subject.other | engine calibration | en |
| dc.subject.other | Duerers problem | en |
| dc.subject.other | nested prismatoids | en |
| dc.subject.other | unfoldability | en |
| dc.title | Discrete geometry and optimization | en |
| dc.title.translated | Diskrete Geometrie und Optimierung | de |
| dc.type | Doctoral Thesis | |
| dc.type.version | acceptedVersion | |
| tub.accessrights.dnb | free | |
| tub.affiliation | Fak. 2 Mathematik und Naturwissenschaften::Inst. Mathematik::FG Diskrete Mathematik / Geometrie | |
| tub.publisher.universityorinstitution | Technische Universität Berlin |