next up previous contents
Next: Numerische Lösung von Up: Previous: Rekonstruktion stochastischer Prozesse

Effizienz stochastischer Verfahren der globalen Optimierung

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:

  1. E. H. L. AARTS AND P. J. M. LAARHOVEN, Simulated Annealing: Theory and Applications, Reidel, Dordrecht, 1987.
  2. P. DIACONIS, Group Representations in Probability and Statistics, IMS-Lecture Notes, 11, 1988.
  3. P. MATHÉ, Approximation Theory of Stochastic Numerical Methods, Habilitationsschrift, FU Berlin, 1994.



Group_of_Office
Mon May 13 20:25:53 MET DST 1996