Techn. University, Diss., 2005--Berlin.

Many optimization problems for a smooth cost function f on a manifold M can be solved by determining the zeros of a vector field F; such as e.g. the gradient F of the cost function f. If F does not depend on additional parameters, numerous zero-finding techniques are available for this purpose. It is a natural generalization however, to consider time-dependent optimization problems that require the computation of time-varying zeros of time-dependent vector fields F(x,t). Such parametric optimization problems arise in many fields of applied mathematics, in particular path-following problems in robotics, recursive eigenvalue and singular value estimation in signal processing, as well as numerical linear algebra and inverse eigenvalue problems in control theory. In the literature, there are already some tracking algorithms for these tasks, but these do not always adequately respect the manifold structure. Hence, available tracking results can often be improved by implementing methods working directly on the manifold. Thus, intrinsic methods are of interests that evolve during the entire computation on the manifold. It is the task of this thesis, to develop such intrinsic zero finding methods. The main results of this thesis are as follows: - A new class of continuous and discrete tracking algorithms is proposed for computing zeros of time-varying vector fields on Riemannian manifolds. This was achieved by studying the newly introduced time-varying Newton Flow and the time-varying Newton Algorithm on Riemannian manifolds. - Convergence analysis is performed on arbitrary Riemannian manifolds. - Concretization of these results on submanifolds, including for a new class of algorithms via local parameterizations. - More specific results in Euclidean space are obtained by considering inexact and underdetermined time-varying Newton Flows. - Illustration of these newly introduced algorithms by examining time-varying tracking tasks in three application areas: Subspace analysis, matrix decompositions (in particular EVD and SVD) and computer vision. / Das Optimieren einer glatten Kostenfunktion f auf einer Mannigfaltigkeit M kann oft dadurch erreicht werden, dass man die Nullstellen eines Vektorfeldes F bestimmt; z.B. dann, wenn F der Gradient von f ist. Für solche Problemstellungen gibt es zahlreiche Nullstellensuchmethoden, sofern F nicht von zusätzlichen Parametern abhängt. Es ist jedoch eine nahe liegende Erweiterung, zeitvariante Optimierungsaufgaben zu betrachten, für die dann Verfahren zur Berechnung der zeitvarianten Nullstelle von Vektorfeldern F(x,t) benötigt werden. Solche parametrisierte Optimierungsprobleme tauchen in vielen Teilgebieten der angewandten Mathematik auf, insbesondere Verfolgungsprobleme in der Robotik, rekursive Eigenwert- und Singulärwertbestimmung in der Signalverarbeitung sowie in der numerischen linearen Algebra und inverse Eigenwertprobleme in der Kontrolltheorie. In der Literatur gibt es bereits einige Nullstellen-Verfolgungsmethoden für solche Aufgaben. Jedoch wird dabei meistens nicht die Struktur der Mannigfaltigkeit hinreichend berücksichtigt, was aber wünschenswert wäre. Methoden, die direkt auf M arbeiten liefern nämlich andere und ggf. bessere Ergebnisse. Dies begründet unser Interesse an intrinsische Methoden, und es ist die zentrale Aufgabe dieser Arbeit, solche Methoden herzuleiten. Die Hauptergebnisse sind wie folgt: - Neue Klassen von diskreten und kontinuierlichen Methoden zur Verfolgung von Nullstellen von zeitvarianten Vektorfeldern auf Riemannschen Mannigfaltigkeiten werden etabliert. Dazu wurden der zeitvariante Newton Fluss und der zeitvariante Newton Algorithmus auf Riemannschen Mannigfaltigkeiten neu eingeführt und studiert. - Die Konvergenzanalyse wird auf beliebigen Riemannschen Mannigfaltigkeiten durchgeführt. - Die Ergebnisse werden durch Betrachtung von Untermannigfaltigkeiten konkretisiert. Dabei wird eine neue Klasse von Algorithmen hergeleitet, die lokalen Parametrisierungen der Mannigfaltigkeit nutzt. - Durch Betrachtung der Ergebnisse im euklidischen Raum werden diese zunächst weiter vereinfacht und dann um inexakte und unterbestimmte zeitvariante Verfahren erweitert. - Die neu eingeführten Algorithmen werden durch das ausführliche Studium von zeitvarianten Verfolgungsproblemen in drei Anwendungsgebieten veranschaulicht: Unterraumberechnung, Matrizenzerlegungen (insbesondere Diagonalisierung von Matrizen und Singulärwertzerlegung) und Bewegungsrekonstruktion aus Kamerabildern.

Chemnitz, Techn. Univ., Studienarb., 2007.

Partitionierung von Graphen ist im Allgemeinen sehr schwierig. Es stehen derzeit keine Algorithmen zur Verfügung, die ein allgemeines Partitionierungsproblem effizient lösen. Aus diesem Grund werden heuristische Ansätze verfolgt. Zur Analyse dieser Heuristiken ist man derzeit gezwungen zufällige Graphen zu Verwenden. Daten realer Graphen sind derzeit entweder nur sehr schwer zu erheben (z.B. Internetgraph), oder aus rechtlichen bzw. wirtschaftlichen Gründen nicht zugänglich (z.B. soziale Netzwerke). Die untersuchten Heuristiken liefern teilweise nur unter bestimmten Voraussetzungen Ergebnisse. Einige arbeiten lediglich auf einer eingeschränkten Menge von Graphen, andere benötigen zum Erkennen einer Partition einen mit der Knotenzahl steigenden Durchschnittsgrad der Knoten, z.B. [DHM04]. Der im Zuge dieser Arbeit erstmals implementierte Algorithmus aus [CGL07a] benötigt lediglich einen konstanten Durchschnittsgrad der Knoten um eine Partition des Graphen, wenn diese existiert, zu erkennen. Insbesondere muss dieser Durchschnittsgrad nicht mit der Knotenzahl steigen. Nach der Implementierung erfolgten Tests des Algorithmus an zufälligen Graphen. Diese Graphen entsprachen dem Gnp-Modell mit eingepflanzter Partition. Die untersuchten Clusterprobleme waren dabei große Schnitte, kleine Schnitte und unabhängige Mengen. Der von der Art des Clusterproblems abhängige Durchschnittsgrad wurde während der Tests bestimmt.

Partitionierung von Graphen ist im Allgemeinen sehr schwierig. Es stehen derzeit keine Algorithmen zur Verfügung, die ein allgemeines Partitionierungsproblem effizient lösen. Aus diesem Grund werden heuristische Ansätze verfolgt. Zur Analyse dieser Heuristiken ist man derzeit gezwungen zufällige Graphen zu Verwenden. Daten realer Graphen sind derzeit entweder nur sehr schwer zu erheben (z.B. Internetgraph), oder aus rechtlichen bzw. wirtschaftlichen Gründen nicht zugänglich (z.B. soziale Netzwerke). Die untersuchten Heuristiken liefern teilweise nur unter bestimmten Voraussetzungen Ergebnisse. Einige arbeiten lediglich auf einer eingeschränkten Menge von Graphen, andere benötigen zum Erkennen einer Partition einen mit der Knotenzahl steigenden Durchschnittsgrad der Knoten, z.B. [DHM04]. Der im Zuge dieser Arbeit erstmals implementierte Algorithmus aus [CGL07a] benötigt lediglich einen konstanten Durchschnittsgrad der Knoten um eine Partition des Graphen, wenn diese existiert, zu erkennen. Insbesondere muss dieser Durchschnittsgrad nicht mit der Knotenzahl steigen. Nach der Implementierung erfolgten Tests des Algorithmus an zufälligen Graphen. Diese Graphen entsprachen dem Gnp-Modell mit eingepflanzter Partition. Die untersuchten Clusterprobleme waren dabei große Schnitte, kleine Schnitte und unabhängige Mengen. Der von der Art des Clusterproblems abhängige Durchschnittsgrad wurde während der Tests bestimmt.