Würzburg, Universiẗat, Diss., 2002.

Die vorliegende Arbeit untersucht die Analytizitätseigenschaften unzulässiger Innerer-Punkte Pfade bei monotonen Komplementaritätsproblemen und diskutiert mögliche algorithmische Anwendungen. In Kapitel 2 werden einige matrixanalytische Konzepte und Resultate zusammengestellt, die für die Beweisführung in den folgenden Kapiteln benötigt werden. Kapitel 3 gibt eine genaue Definition der Begriffe "monotones lineares Komplementaritätsproblem" (LCP) bzw. "semidefinites monotones lineares Komplementaritätsproblem" (SDLCP) und zeigt die Grundidee hinter den Innere-Punkte-Verfahren zur Lösung solcher Probleme. Kapitel 4 beinhaltet die analytischen Hauptresultate für monotone Komplementaritätsprobleme. In Abschnitt 4.1 werden einige wohlbekannte Resultate über die Analytizitätseigenschaften unzulässiger Innerer-Punkte-Pfade für LCP's wiedergegeben. Diese werden in Abschnitt 4.2 auf den semidefiniten Fall übertragen. Unter der Annahme, dass das zugrundeliegende SDLCP eine strikt komplementäre Lösung besitzt, wird gezeigt, dass die Inneren-Punkte-Pfade sogar noch im Randpunkt analytisch sind. Kapitel 5 benutzt die Resultate aus Kapitel 4, um die lokal hohe Konvergenzordnung einer Langschrittmethode zur Lösung von SDLCP's zu zeigen. Kapitel 6 führt eine neue Methode zur Lösung von LCP's und SDLCP's mit Hilfe von Inneren-Punkte-Techniken ein. Dabei werden die Pfadfunktionen derart gewählt, dass alle Iterierten auf unzulässigen zentralen Pfaden liegen. Es wird globale und lokale Konvergenz des Verfahrens bewiesen. / This thesis investigates the analyticity properties of infeasible interior point paths arising with monotone complementarity problems and discusses possible algorithmic applications. Chapter 2 summarizes some matrix analytical concepts and results that are needed for the proofs in the following chapters. Chapter 3 defines the terms "monotone linear complementarity problem" (LCP) and "semidefinite monotone linear complementarity problem" (SDLCP) exactly and shows the basic concept behind interior point methods for solving them. Chapter 4 contains the main analytical results for monotone complementarity problems. After repeating some well-known results on the analyticity properties of infeasible interior point paths for LCP's in section 4.1 these results are extended to the semidefinite case in section 4.2. Under the assumption that the underlying SDLCP has a strictly complementary solution it is shown that the interior point paths are analytical even at the boundary point. Chapter 5 uses the results of chapter 4 to show the locally high order of convergence of a long step method for solving SDLCP's. Chapter 6 introduces a new method for solving LCP's and SDLCP's respectively using interior point techniques. Here, the path functions are chosen in such a way that all the iterates are lying on infeasible central paths. Global and local convergence proofs are given.

Zugl.: Berlin, Freie Universiẗat, Diss., 2006.

Berlin, Humboldt-Universiẗat, Diss., 1999.

Zugl.: Dortmund, Techn. Univ., Diss., 2007

Es werden verschiedene Verfahren zur Lösung verallgemeinerter Nash-Gleichgewichtsprobleme mit dem Schwerpunkt auf deren globaler Konvergenz entwickelt. Ein globalisiertes Newton-Verfahren zur Berechnung normalisierter Lösungen, ein nichtglattes Optimierungsverfahren basierend auf einer unrestringierten Umformulierung des spieltheoretischen Problems, und ein Minimierungsansatz sowei eine Innere-Punkte-Methode zur Lösung der gemeinsamen Karush-Kuhn-Tucker-Bedingungen der Spieler werden theoretisch untersucht und numerisch getestet. Insbesondere das Innere-Punkte Verfahren erweist sich als das zur Zeit wohl beste Verfahren zur Lösung verallgemeinerter Nash-Gleichgewichtsprobleme. / In this thesis different algorithms for the solution of generalized Nash equilibrium problems with the focus on global convergence properties are developed. A globalized Newton method for the computation of normalized solutions, a nonsmooth algorithm based on an optimization reformulation of the game-theoretic problem, and a merit function approach and an interior point method for the solution of the concatenated Karush-Kuhn-Tucker-system are analyzed theoretically and numerically. The interior point method turns out to be one of the best existing methods for the solution of generalized Nash equilibrium problems.