Studienabschlussarbeiten am Institut

Die vorliegende Arbeit beschäftigt sich mit einem Optimierungsproblem auf Graphen. Hierbei werden den n Knoten des Graphen G und den zwischen ihnen verlaufenden Kanten positive Zahlenwerte zugeordnet und mit diesen wird eine quadratische Funktion betrachtet. Ziel dieser Arbeit ist es, das Maximum dieser Funktion über dem n-dimensionalen Einheitswürfel zu ermitteln. Die Lösung dieses Problems, die Funktion zu maximieren, ist nicht einfach, da das untersuchte Problem NP-vollständige Unterprobleme enthält. Es wird deutlich, dass im Allgemeinen das Maximum der Funktion durch einen induzierten Untergraphen H von G realisiert wird. Dieser hat je nach Wahl der den Knoten und Kanten zugeordneten Zahlenwerte bestimmte Eigenschaften. Da die explizite Maximierung der Funktion NP-vollständige Probleme als Unterprobleme enthält, wird der Maximalwert in dieser Arbeit als gegeben angenommen. Es wird festgestellt, dass das Maximum in einer Ecke des Einheitswürfels angenommen wird. Mithilfe dieses Resultats wird ein gewisser Untergraph H von G betrachtet, welcher durch bestimmte Knoten des Graphen G induziert werden kann. Wird der Untergraph H zusätzlich minimal gewählt, können weitere Aussagen über den Maximalwert getroffen werden. Durch die verschiedene Wahl der Zahlenwerte an Knoten und Kanten, können gewisse Eigenschaften des Untergraphen H erzwungen werden. Somit werden Resultate erhalten, welche die Existenz von induzierten Untergraphen eines gegebenen Graphen G sichern. Die in den letzten Kapiteln der Arbeit beschriebenen Sätze sagen aus, dass unter gewisser spezieller Wahl der Zahlenwerte an Knoten und Kanten ein induzierter Untergraph H von G mit einem gewissen Maximum existiert, welcher eine gewisse zusätzliche Eigenschaft besitzt. Zum Beispiel ist in bestimmten Fällen die Knotenmenge unabhängig oder die Maximalvalenz beschränkt.

Diese Arbeit handelt von einem kleinen Teil des weiten Feldes Compressed Sensing, welches heutzutage eine große Rolle in der Signal- und Bildverarbeitung spielt. Diese Arbeit besteht aus fünf Kapiteln. Das erste Kapitel erläutert einige grundlegende Begriffe im Zusammenhang mit Compressed Sensing. Unter anderem werden die Begriffe Sparsity, Kohärenz und der Kruskal-Rang eingeführt. Darüber hinaus wird das Vorgehen bei Sparsity Order Estimation beschrieben. Dies dient als Motivation im zweiten Kapitel zunächst das allgemeine Packungsproblem zu erläutern. Hier wird ein bekanntes Resultat für die n-dimensionale Sphäre auf einen projektiven Raum übertragen, welches es uns ermöglicht Schranken für die Packungszahlen von Matrizen mit Rang 1 herzuleiten. Dies ermöglicht die Ableitung von Schranken für die Kohärenz von Khatri-Rao-Produkten, welche ein zentrales Ergebnis dieser Arbeit darstellen. Das dritte Kapitel dreht sich um das Problem, wie man explizit Matrizen mit niedriger Kohärenz konstruieren kann, wobei reell- und komplexwertige Matrizen zum Tragen kommen. Wir stellen Strategien zur Konstruktion von beliebigen Matrizen, Khatri-Rao-Produkten und Vandermonde Matrizen vor. Der Algorithmus für letztere zieht auch untere und obere Köhärenzschranken nach sich. Kapitel vier illustriert einige numerische Resultate für die Schranken und Algorithmen, welche vorher hergeleitet wurden. Wann immer möglich werden numerische Resultate mit theoretischen verglichen. Das letzte Kapitel gibt eine kurze Zusammenfassung der Arbeit und zeigt einige Bereiche auf, welche noch offene Fragen beinhalten.

m Rahmen der vorliegenden Bachelorarbeit wird mit Hilfe verallgemeinerter Funktionen eine Lösungstheorie für eine bestimmte Gruppe linearer stochastischer Differentialgleichungen erarbeitet. Das dafür benötigte Wissen aus der Theorie der verallgemeinerten Funktionen sowie die benötigten Kenntnisse aus der Theorie der verallgemeinerten stochastischen Prozesse wird einleitend knapp und in einem modernen mathematischen Stil dargestellt. Darauffolgend nutzen wir dieses Wissen, um für eine gegebene stochastische Differentialgleichung eine Lösung zu ermitteln. Das Hauptergebnis besteht in der Formulierung sowie dem Beweis eines Theorems, welches Existenz und Eindeutigkeit der Lösung gewährleistet. Abschließend soll die Analyse zweier bekannter Beispiele zeigen, dass die entwickelte Theorie durchaus Anwendung in der Praxis findet.

Ein Sturm-Liouville-Problem besteht ist eine gewöhnliche Differentialgleichung der Form $$-(p(x)y'(x))'+(q(x)-\lambda w(x))y(x)=0\quad \text{für } -\infty \le a<x<b\le \infty,$$ für $\lambda\in \mathbb{C}$ mit Anfangswerten $y(x_0)=y_0, \quad y'(x_0)=y_1.$. Hier sind die Funktionen $p,q:(a,b)\mapsto \mathbb{C}$ und $w:(a,b)\mapsto \mathbb{R}$ meßbar und $\frac{1}{p},q,w$ sind lokal integrierbar. Zudem gelte für fast alle $x\in (a,b)$, dass $p(x)\neq 0$ und $r(x)>0$. Die Differentialgleichung besitzt zwei linear unabhängige Lösungen. Diese Lösungen müssen aber nicht unbedingt im Hilbertraum $$L^2(a,b,w\,dx):=\bigg\{u:(a,b)\mapsto \mathbb{C}:\int_{a}^{b}w|u|^2\,dx<\infty\bigg\}$$ liegen. Sind $p$ und $q$ reellwertige Funktionen, so besagt ein berühmtes Ergebnis von H. Weyl, dass entweder alle Lösungen des Eigenwertproblems für jedes $\lambda\in\mathbb{C}$ im Hilbertraum $L^2(a,b,w\,dx)$ liegen oder nur eine Lösung (und ihre Vielfachen) in $L^2(a,b,w\,dx)$ liegen. Liegen alle Lösungen im Hilbertraum $L^2(a,b,w\,dx)$, spricht man vom Grenzkreisfall anderenfalls vom Grenzpunktfall. In dieser Masterarbeit werden einige der Ergebnisse der Arbeit "Secondary conditions for linear differential operators of the second order" von A. R. Sims (Journal of Mathematics and Mechanics, 6 (1957), 247-285) vorgestellt. A. R. Sims erweiterte die Grenzpunkt-Grenzkreis-Klassifikation von Weyl auf komplexwertige Koeffizienten im Fall $p=w\equiv 1$. In dieser Klassifikation einen Fall mehr, als in der klassischen Klassifikation von H. Weyl für reelle Koeffizienten $p$ und $q$. Außerdem werden Eigenschaften der Weylschen $M$-Funktion untersucht und ein Lösungsoperator $R_{\lambda}$ erklärt. In den Fällen, in denen alle Lösungen in $L^2[a,b)$ liegen, ist dieser Lösungsoperator ein Hilbert-Schmidt Operator. Damit besteht das Spektrum in diesen Fällen nur aus isolierten Eigenwerten mit endlicher algebraischer Vielfachheit, welche in der unteren Halbebene liegen.

In meiner Bachelorarbeit befasse ich mich mit dem Direct-Algorithmus, den D.R. Jones, C.D. Perttunen und B.E. Stuckman 1993 in "Lipschitzian optimization without the Lipschitz constant" vorgestellt haben. Der Algorithmus wird zunächst erläutert und diskutiert. Daraufhin stelle ich einige auf Direct beruhende Ansätze, um die effiziente Menge von multikriteriellen Optimierungsproblemen zu approximieren, vor. Diese habe ich implementiert und an Testproblemen getestet. In Teilen der Arbeit beschränke ich mich auf bikriterielle Probleme.