*Wissenschaftliches Programm*   *Liste der Vortragenden*

Sektion 9
Montag, 18.09.2000, 15.30–15.50 Uhr, WIL C 133

Die Level-Methode in der primalen Dekomposition

Klaus Beer, TU Chemnitz, Fakultät für Mathematik

Die Levelmethode (1) ist ein Lösungsverfahren vom Kelley’schen Schnittebenentyp für i. A. nichtdifferenzierbare konvexe Optimierungsaufgaben. In ihr wird die Güte (gemessen am Zielfunktionswert) des aktuell besten Punktes durch eine lineare Optimierungsaufgabe abgeschätzt und der nächste Iterationspunkt durch Projektion des letzten Iterationspunktes auf eine Niveaumenge der vorhandenen stückweise-affinlinearen unteren Approximation der Zielfunktion berechnet.

Im Vortrag geht es um die Erweiterung der Methode auf Aufgaben, in denen das Definitionsgebiet der Zielfunktion nicht der gesamte Raum ist und explizit nicht zur Verfügung steht (2), sondern nur für einen konkreten Versuchspunkt ermittelt werden kann, ob er zum Definitionsgebiet gehört oder nicht. Diese Situation liegt in der sogenannten primalen Dekomposition von Optimierungsaufgaben vor. Hier geht es um die Aufgabe der Minimierung einer Funktion f(x), die selbst Optimalwert einer anderen Aufgabe ist, bei der x sowohl in die Zielfunktion als auch in die Nebenbedingungen eingeht. Die Erprobung der Methode am Dekompositionszugang zu linearen Optimierungsaufgaben (2) mit blockangularer Verbundstruktur bestätigt ihre Robustheit (3) und zeigt eine wesentlich bessere Konvergenzgeschwindigkeit als die theoretische Aussage zur Konvergenzrate angibt.

Der Vortrag basiert auf einer gemeinsamen Arbeit mit E. G. Golstein, Chemnitz.

Literatur:

[1]
C. Lemarechal, A.S. Nemirovskij, Yu.E. Nesterov (1995): New variants of bundle methods, Mathematical Programming, 69, 111-147
[2]
K. Beer, E.G. Golshtein, N.A. Sokolov: Minimization of a nondifferentiable convex function, defined not everywhere, eingereicht zur Publikation in ”Optimization”, Preprint 1998-9 der Fakultät für Mathematik der Technischen Universität Chemnitz
[3]
E.G. Golstein, Th.Unger: Generalized Level Method with Approximated Data, eingereicht zur Publikation in ”Optimization”, Preprint 2000-5 der Fakultät für Mathematik der Technischen Universität Chemnitz.