Martin Preiß

• 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 GrundideeDie 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 4This 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.…