AG Numerik UniLogo

Optimierung

Zeit und Ort der Vorlesung: Montag, 8:15-9:45 Uhr, Raum R512

Zeit und Ort der Übungsgruppe 1: Montag, 10:00-11:30 Uhr, Raum D 436

Übungstermine: 07.05.; 21.05.; 04.06.; 18.06.; 02.07.; 16.07.

Homepage der Vorlesung: www.math.uni-konstanz.de/numerik/personen/junk/teaching/Vorlesungen/optimization/SS12/

Inhalt: In dieser zweistündigen Veranstaltung soll eine Einführung in die Theorie und Numerik von Optimierungsproblemen gegeben werden. Im Zentrum stehen unrestringierte Optimierungsprobleme, d.h. die Suche nach den Minimal- oder Maximalstellen einer reellwertigen Funktion f, die auf ganz Rn definiert ist. Vorgestellt werden das Abstiegsverfahren und das Newton-Verfahren zum Aufspüren von Extremstellen. Ergänzt wird die Vorlesung durch Theorie- und Programmierübungen.

Ziel des Abstiegsverfahren ist es, von einem grundsätzlich beliebigen (aber günstigerweise nahe eines lokalen Minimums liegenden) Startpunktes x0 aus einen neuen Punkt zu bestimmen, der einen kleineren Funktionswert liefert. Meist verwenden wir als Richtung d den steilsten Abstieg der Funktion von x0 aus, d.h. den (normierten) negativen Gradienten. Nach Wahl einer geeigneten Schrittweite t finden wir so einen Punkt p=x0+td mit f(p)<f(x0). Iterieren wir dieses Vorgehen, so erhalten wir eine Folge pn+1=pn+tndn, so dass die zugehörige Folge der Funktionswerte monoton fällt. Unter geeigneten Voraussetzungen konvergiert die Folge (pn) und der Grenzwert ist eine lokale Minimalstelle von f.

Beim Newtonverfahren ersetzen wir die zu minimierende Zielfunktion f durch ein quadratisches Modell, d.h. wir führen eine Taylor-Entwicklung der Ordnung 2 an einem Startpunkt nahe des gesuchten Minimalpunktes durch (und vernachlässigen den Restterm). Die notwendige Bedingung erster Ordnung, Gradient=0, der Modellfunktion liefert ein lineares Gleichungssystem, dessen Lösung diese unter geeigneten Voraussetzungen minimiert und einen neuen Startpunkt liefert. Wir konstruieren auf diese Weise wieder eine Iterationsfolge, die (hoffentlich) gegen die gesuchte lokale Minimalstelle von f konvergiert.

Vorkenntnisse in den Bereichen Analysis, Lineare Algebra und Numerik (Matlab) werden vorausgesetzt.

Material für die Übungen: G L S E1 E2 P1 E3 E4 P2 E5 E6 P3