Komplementaritäts- und Fixpunktalgorithmen in der mathematischen Programmierung, Spieltheorie und Ökonomie

In den letzten Jahren ist mit der Schaffung von Komplementaritats- und Fixpunkt algorithm en ein recht eigentlicher Durchbruch gegHickt, der sowohl in theoretischer Hinsicht uberzeugt als auch yom praktischen Standpunkt aus zu grossen Hoffnungen berechtigt. Theoretisch gesehen ist die Optimierungsthematik in einen viel breite ren als den ursprunglichen Rahmen gestellt worden und hat ihre Zusammenhange mit tiefliegenden mathematischen Erkenntnissen, die auf die Anfange dieses Jahr hunderts zuruckgehen, gefunden. Von praktischer Seite her erOffnen sich in ihrem Konzept gleichartige Behandlungsmethoden fur sehr unterschiedliche Aufgabenstel lungen aus voneinander weit entfernten Anwendungsgebieten und die Aussicht auf Entwicklung neuer Verfahren fUr bisher ungel6ste Probleme. Herr Dr. H.-J. Luthi hat die Wendung, welche die Dinge nahmen, in einem friihen Zeitpunkt klar erkannt. Er hat einen Studienaufenthalt in den Vereinigten Staaten vor einigen Jahren dazu benutzt, urn in die Entwicklung von erster Hand eingefUhrt zu werden und sich alsbald seIber daran zu beteiligen. Schon seine anschliessende Dissertation betreffend einen Algorithmus zur Approximation von L6sungen des nichtlinearen Komplementaritatsproblems brachte einen neuen Beitrag auf diesem Gebiet. 1m vorliegenden Werk st6sst er nun mit neuen Ideen weiter vor: die Ab schnitte 1. 9, 1. 11, 1. 12 und I. 16 sind in Form und teilweile Inhalt seine eigene Sch6pfung.

Inhalt

0. Einleitung.- I. Teil: Komplementaritaet.- I. 1 Das Komplementaritätsproblem.- I. 2 Ein elementares Lemma aus der Graphentheorie.- I. 3 Das lineare Komplementaritätsproblem (q|M).- I. 4 Der Lemke-Algorithmus.- I. 5 Spezielle Klassen von Matrizen.- I. 6 Anwendungen zum linearen Komplementaritätsproblem.- I. 7 Geometrische Interpretation des linearen Komplementaritätsproblems.- I. 8 Neuere Forschungsresultate.- I. 9 Das nichtlineare Komplementaritätsproblem.- I. 10 Technik der Triangulation.- I. 11 Der Markierungsprozess.- I. 12 Der Basisalgorithmus.- I. 13 Einige spezielle Klassen nichtlinearer Probleme und Existenzsätze.- I. 14 Anwendungen zum nichtlinearen Komplementaritätsproblem.- I. 15 Spezielle Triangulation von Rn.- I. 16 Die Verfeinerung.- II. Teil: Fixpunktalgorithmen.- II. 1 Einleitung.- II. 2 Der Fixpunktsatz von Brouwer.- II. 3 Der Fixpunktalgorithmus von H. Scarf.- II. 4 Bestimmung von Fixpunkten konvexer, obenhalbstetiger Korrespondenzen.- II. 5 Anwendung der Fixpunktalgorithmen.- II. 6 Komplementarität und Fixpunkte: Abschliessende Bemerkungen.