Würzburg, Univ., Diss., 2009.

In the generalized Nash equilibrium problem not only the cost function of a player depends on the rival players' decisions, but also his constraints. This thesis presents different iterative methods for the numerical computation of a generalized Nash equilibrium, some of them globally, others locally superlinearly convergent. These methods are based on either reformulations of the generalized Nash equilibrium problem as an optimization problem, or on a fixed point formulation. The key tool for these reformulations is the Nikaido-Isoda function. Numerical results for various problem from the literature are given. / Das verallgemeinerte Nash-Gleichgewichtsproblem ist ein Lösungskonzept für Spiele, in denen neben der Kostenfunktion eines Spielers auch dessen Strategiemenge von den Entscheidungen der anderen Spieler abhängt. In dieser Arbeit werden global konvergente und lokal superlinear konvergente Verfahren zur numerischen Berechnung eines verallgemeinerten Nash-Gleichgewichts vorgestellt. Die Verfahren basieren entweder auf einer Umformulierung des verallgemeinerten Nash-Gleichgewichtsproblems als Optimierungsproblem oder als Fixpunktproblem. Für diese Umformulierungen wird die Nikaido-Isoda Funktion verwendet. Es werden numerische Ergebenisse für einige Probleme aus der Literatur widergegeben.

Gegenstand der vorliegenden Arbeit sind Verfahren für große freie und restringierte Minimierungsprobleme. Dabei wird der Ansatz verfolgt, mit Hilfe des Raumzerlegungkonzepts Verfahren mit einer immanenten parallelen Struktur zu entwerfen, die damit zu grobkörnig parallelisierbaren Algorithmen führen.

Diese Diplomarbeit befasst sich mit stochastischen Gradientenverfahren als Methoden der numerischen Optimierung für die Anwendung in der adaptiven Optik. Die adaptive Optik wird insbesondere im Fall der Propagation von Licht durch die Atmosphäre zur Verbesserung der Abbildungseigenschaften eines optischen Systems verwendet. Als Verfahren der Wahl wird das Simultaneous Perturbation Stochastic Approximation Verfahren (SPSA-Verfahren) betrachtet, das aufgrund seiner geringen Anzahl von benötigten Zielfunktionsauswertungen pro Iteration sehr gut zu den Echtzeit-Anforderungen der Anwendung passt. Neben der Darstellung des physikalischen Hintergrunds wird Wert auf eine fundierte Verankerung der Analyse der Verfahren in der Wahrscheinlichkeitstheorie gelegt. Die verwendeten Resultate u.a. der Martingaltheorie werden im Rahmen der Arbeit in die benötigte Form gebracht. Als Hintergrund wird ein Einblick in die Theorie der deterministischen, ableitungsfreienGradientenverfahren gegeben. Die Konvergenz des SPSA-Verfahrens wird auf ein Konvergenztheorem für Stochastic-Approximation-Verfahren von Kushner und Clark zurückgeführt. Dabei wurde in der Konvergenztheorie zunächst Spall gefolgt, aufgrund von wahrscheinlichkeitstheoretischen Überlegungen werden dann aber teilweise geänderte Voraussetzungen verwendet.Der praktische Teil der Arbeit beschäftigt sich mit der Anwendung des Verfahrens in der adaptiven Optik am Beispiel eines Labor-Testsystems. Die Voraussetzungen der Theorie werden für die Anwendung gewürdigt. Zur Umsetzung des Verfahrens in einen konkreten Algorithmus wird auf die Parameterwahl und mögliche Erweiterungen eingegangen. Die Wahl der Parameter nach Spall wird um eine Überlegung aus der Theorie der numerischen Differentiation erweitert, so dass sich eine andere Empfehlung hinsichtlich der Wahl der Schrittweite für die Gradientenschätzung ergibt. Ein Optimierungsdurchgang wird dargestellt und bewertet und anschließend ein Ausblick für die mögliche Verwendung des Verfahrens in einem adaptiv-optischen System gegeben.

Gegenstand der vorliegenden Arbeit sind Verfahren für große freie und restringierte Minimierungsprobleme. Dabei wird der Ansatz verfolgt, mit Hilfe des Raumzerlegungkonzepts Verfahren mit einer immanenten parallelen Struktur zu entwerfen, die damit zu grobkörnig parallelisierbaren Algorithmen führen.