Bearbeiter: P. Mathé
Kooperation: U. Voll, FU Berlin
Beschreibung der Forschungsarbeit:
Wenn es darum geht, komplexe Optimierungsprobleme zu behandeln, die mit den herkömmlichen Verfahren (lineare, konvexe ...) nicht angegangen werden können, dann gibt es verschiedene Möglichkeiten, durch Einführen zufälliger Parameter akzeptable Näherungslösungen zu erhalten. Einer der vielversprechendsten Ansätze verbirgt sich hinter dem Konzept des Simulated Annealing, siehe [1]. Für viele Anwendungsbereiche (insb. hochparametrische Traveling-Salesman-Probleme) hat sich diese Klasse von stochastischen Optimierungsverfahren bewährt.
Mathematische Resultate, die das Phänomen Simulated Annealing annähernd erklären können, sind rar. Die einfache Frage, wie eine zu minimierende Funktion beschaffen sein muß, damit das Verfahren effektiv eine Näherungslösung findet, ist weitgehend ungeklärt. Derartige grundlegende mathematische Fragestellungen sind Gegenstand des Projekts.
Der approximationstheoretische Apparat (vgl. [3]) zur Untersuchung der Effizienz stochastischer numerischer Verfahren kann hier eingesetzt werden, um vertiefte Kenntnisse über die Wirksamkeit derartiger stochastischer Suchverfahren zu gewinnen.
Bei der Anwendung des Simulated Annealing gilt es, zwei Parameter
geeignet zu
steuern:
-- die Geschwindigkeit der Abkühlung
-- die Relaxationzzeit der Metropolisschritte.
Die letzte Frage ist im Rahmen eines Teilprojekts mit Herrn U.
Voll bearbeitet worden.
Aufbauend auf [2] konnten grundlegende Zusammenhänge zwischen
gruppentheoretischen Eigenschaften des Grundbereichs und der
Konvergenzgeschwindigkeit darauf agierender (schnellmischender)
Markovketten erarbeitet werden.
Wegen seiner großen Bedeutung für praktische Anwendungen ist dieses Projekt langfristig angelegt.
Projektliteratur: