Detailansicht
COMPASS
a free solver for mixed complementarity problems
Stefan Schmelzer
Art der Arbeit
Diplomarbeit
Universität
Universität Wien
Fakultät
Fakultät für Mathematik
Betreuer*in
Arnold Neumaier
DOI
10.25365/thesis.22204
URN
urn:nbn:at:at-ubw:1-29113.19262.143765-2
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)
Abstracts
Abstract
(Deutsch)
Die vorliegende Arbeit präsentiert COMPASS, einen global konvergenten Lösungsalgorithmus für gemischte Komplementaritätsprobleme. Die zu Grunde liegende math ematische Theorie basiert auf dem PATH Solver, dem standard Lösungsalgorithmus für diese Art von Problemen. COMPASS ist unter der “GNU General Public License” Lizenz veröffentlicht und ist daher Freie Software.
Das Fundament von COMPASS ist eine stabilisierte Newton Methode: Das gemischte Komplementaritätsproblem wird in der Form der Normalgleichung (normal equation) reformuliert. Eine allgemeine Approximation erster Ordnung dieser Normalgleichung kann als lineares gemischtes Komplementaritätsproblem dargestellt und mit Hilfe einer Pivot Technik gelöst werden. Diese Lösung entspricht dem Newton Punkt im standard Newton Verfahren, und wird daher hier auch so bezeichnet. In der Pivot Technik wird neben der Lösung auch ein stückweise linearer Pfad generiert, der den letzten Iterationspunkt und den Newton Punkt verbindet. Ob dieser Punkt als nächster Iterationspunkt akzeptiert wird hängt von einem nicht-monotonen Stabilisierungsverfahren ab, das eine Watchdog Technik beinhaltet. Außerdem existiert eine glatte “merit” Funktion, basierend auf einer modifizierten Fischer-Burmeister Funktion, die den Erfolg des Fortschritt misst, und bei der Lösung des Komplementaritätsproblems eine Nullstelle besitzt. Gemäß der Verbesserung des Wertes dieser merit Funktion sind gewisse nicht monotone Abstiegskriterien definiert. Diese werden jedoch nicht in jedem Schritt getestet, um die Anzahl der Funktions- und Gradientenauswertungen zu minimieren.
Wenn die Lösung aus der Pivot Technik, also der Newton Punkt, diesen Abstiegskriterien genügt, wird er als neuer Iterationspunkt verwendet. Falls nicht, geht der Algorithmus zurück zum letzten “Checkpoint”, dem letzten Punkt, der dem Test mit dem Abstiegskriterium erfolgreich unterzogen wurde. Der Pfad zwischen diesem Checkpoint, und dem Newton Punkt nach diesem Checkpoint (der Newton Punkt wird nach jedem Checkpoint gespeichert) wird dann nach einem die Abstiegskriterien erfüllenden Punkt durchsucht. Sollte kein passender Punkt gefunden werden, geht der Algorithmus zurück zum “Bestpoint”, dem Punkt mit dem bisher niedrigsten Wert der merit Funktion, und macht einen projizierten Gradientenschritt.
Ein globaler Konvergenzbeweis dieser Theorie ist in der Arbeit enthalten. Der Algorithmus wurde im Zuge dieser Arbeit in MATLAB/Octave implementiert, und steht auf http://www.mat.univie.ac.at/~neum/software/compass/COMPASS.html zum Download und zur freien Benutzung zur Verfügung. Eine Simulation wurde anhand von zufällig generierten Problemen durchgeführt und dokumentiert das erfolgreiche Lösen von Problemen des Algorithmus zumindest bis zu einer Größenordnung
von 200 Variablen. Eine kurze geschichtliche Einführung über den Zusammenhang zwischen gemischten Komplementaritätsproblemen und ökonomischen Modellen ist in der Arbeit enthalten, sowie eine Anleitung anhand eines Beispiels, wie solche Modelle in der Form von Komplementaritätsproblemen forumliert werden können.
Abstract
(Englisch)
This thesis presents COMPASS, a globally convergent algorithm for solving the Mixed Complementarity Problem (MCP). The mathematical theory behind it is based on the PATH solver, the standard solver for complementarity problems. The fundament of COMPASS is a stabilized Newton method; the MCP is reformulated as the problem of finding a zero of a non-smooth vector valued function, the normal equation. A pivot technique is used to solve a general first order approximation of the normal equation at the current point in order to obtain a piecewise linear path connecting consecutive iterates. A general descent framework uses a smooth merit function establishing non-monotone descent criteria; a non-monotone stabilization scheme employs a watchdog technique and pathsearches reducing the number of function and gradient evaluations. An implementation in MATLAB/Octave was developed and is an integral part of this thesis. Simulation results on random problems, as well as a short course on economic models as an example of a field of application are included.
Schlagwörter
Schlagwörter
(Englisch)
Mixed Complementarity Problem solver stabilized Newton method, Pivot technique
Schlagwörter
(Deutsch)
gemischtes Komplementaritätsproblem Solver stabilisierte Newton Methode Pivot Verfahren
Autor*innen
Stefan Schmelzer
Haupttitel (Englisch)
COMPASS
Hauptuntertitel (Englisch)
a free solver for mixed complementarity problems
Paralleltitel (Deutsch)
COMPASS: Ein freier Solver für gemischte Komplementaritätsprobleme
Publikationsjahr
2012
Umfangsangabe
II, 88 S.
Sprache
Englisch
Beurteiler*in
Arnold Neumaier
AC Nummer
AC09387316
Utheses ID
19831
Studienkennzahl
UA | 405 | | |