Optimierung

Prof. Thomas Brox

Bei Optimierungsverfahren handelt es sich um Algorithmen, denen eine konkrete Zielfunktion zugrunde liegt, die es zu optimieren gilt. Für fast alle mathematisch fundierten Algorithmen ist dies der Fall. Optimierungsprobleme lassen sich in verschiedene Kategorien einteilen, die unterschiedlich schwierig sind. Eine Unterscheidung basiert zum Beispiel darauf, ob das Problem auf kontinuierlichen oder diskreten Variablen definiert ist, eine andere darauf, ob es Nebenbedingungen gibt oder nicht. In dieser Vorlesung werden die grundlegenden Verfahren und Konzepte der Optimierung vorgestellt. Das Hauptaugenmerk liegt auf kontinuierlicher Optimierung, da die grundlegenden kombinatorischen Probleme bereits in anderen Informatikvorlesungen behandelt werden. Ziel ist, dass Sie nach der Vorlesung auch Literatur zu spezielleren Optimierungsverfahren verstehen. Die Vorlesung wird von größtenteils praktischen übungen begleitet. In Python können einfachere Verfahren selbst implementiert und komplexere Verfahren ausprobiert werden.

Die Vorlesung findet als Online-Kurs in Zoom statt. Neben vorgefertigten Lerneinheiten gibt es Online-Termine, zu denen Sie Fragen zu den Materialien stellen können (Inverted-Classroom-Prinzip). Auch die Übungen finden online statt. Über das Online-Forum können Sie Fragen stellen, die von den Mitarbeitern oder anderen Studenten beantwortet werden. Hier haben Sie auch die Möglichkeit, sich mit anderen Studenten zu vernetzen und Übungen gemeinsam zu bearbeiten.

Alle für den Kurs in HisInOne registrierten Studenten erhalten das Passwort für das Zoom meeting sowie für den Zugriff auf die Kursmaterialien und das Online-Forum per E-Mail zugesendet.

Vorlesung: (1 SWS)	Freitag, 10:30, Online
Übungen: (1 SWS)	via online forum Kontakt: Jan Bechtold, Yassine Marrakchi
Beginn:	Freitag, 6.11.2020 Sie müssen bis 2.11. den Kurs in HisInOne belegen, um das Passwort für das Meeting zu bekommen.
ECTS Credits:	3
Semester:	3
Voraussetzungen:	Grundvorlesungen in der Mathematik
Sprache und Prüfung:	Die Klausur findet am 26.3.2021 um 10:00 als normale Präsenzprüfung statt. Weitere Informationen zum genauen Ablauf erhalten Sie zu einem späteren Zeitpunkt, da sich die Lage immer wieder ändern kann. Bitte informieren Sie sich auch auf der Seite des Prüfungsamts über die aktuellen Hinweise. Die Prüfung findet in verschiedenen Hörsälen statt. Sie erhalten per Rundmail spätestens einen Tag vor der Klausur eine Nachricht, in welchen Hörsaal Sie kommen sollen. Wir empfehlen, dass Sie unter möglichst realen Bedingungen die Probeklausur durcharbeiten. Die Musterlösung dazu sollten Sie sich erst hinterher ansehen. Disclaimer: Die Klausur wird (natürlich) etwas anders aussehen.
Sonstige Hinweise:

Themen und Termine:

Datum gilt jeweils für Online Q&A. Die Online Lectures werden idealerweise vorher angeschaut.

Einführung

(6.11.)	Folien, Aufzeichnung	Online-Vorlesung in Zoom
	Übungsvorbereitung

Gradientenverfahren
(13.11.)	Folien
	Online Lecture 2a	× (1) Worauf lassen sich Gradientenverfahren besonders gut anwenden? Probleme mit diskreten Variablen Probleme mit kontinuierlichen Variablen Probleme mit Nebenbedingungen (2) Welche Bedingungen müssen erfüllt sein um ein globales Minimum sicherzustellen? Der Gradient muss 0 sein und die Funktion muss konvex sein Der Gradient muss 0 sein (3) Wie bestimmt sich die Richtung, in der man zum Minimum läuft? Es wird eine beliebige Richtung gewählt, in der die Funktion sinkt Durch den negativen Gradienten Durch die Ableitung des Gradienten
	Richtungsableitung
	Online Lecture 2b	× (1) Wofür ist die Schrittweitenbestimmung wichtig? Für die Konvergenz Für die Effizienz Für beides (2) Ist es ausreichend, wenn der Funktionswert in jedem Iterationsschritt kleiner wird? Ja Nein (3) Was leistet die Armijo-Bedingung? Sie stellt die Konvergenz sicher Sie erhöht die Wahrscheinlichkeit der Konvergenz Sie erhöht die Effizienz (4) Was leisten die Wolfe-Bedingungen? Sie stellen die Konvergenz sicher Sie stellen Konvergenz und Effizienz sicher (5) Welches Verfahren ist im allgemeinen Fall insgesamt am effizientesten? Backtracking Line Search Interpolationsverfahren Suche nach der optimalen Schrittweite
	Online Lecture 2c	× (1) Warum konvergiert das CG-Verfahren für n-dimensionale quadratische Funktionen in n Schritten? Alle Gradientenverfahren fÃ¼r quadratische Funktionen konvergieren in n Schritten Es verwendet die Eigenvektoren der Funktionsmatrix Alle verwendeten Richtungen sind zueinander orthogonal (2) Welche Schrittweite verwendet das CG-Verfahren im Fall quadratischer Funktionen? Das ist egal. Jede Schrittweite, die die Amijo Bedingungen erfüllt ist geeignet Man wählt immer die optimale Schrittweite um in n Schritten zu konvergieren Es gibt keine variable Schrittweite. Alle Schritte hängen nur vom Gradienten ab (3) Was drückt die Konditionszahl einer Matrix aus? Wie isotrop bzw. anisotrop eine quadratische Funktion ist Wie viele Dimensionen die Funktion hat (4) Warum konvergiert das CG-Verfahren für nicht-quadratische Funktionen nicht mehr garantiert in n Schritten? Weil sich die Schrittweite nicht optimal bestimmen lässt Weil die Korrektur der Abstiegsrichtung nur noch eine Approximation ist
	Übung, Musterlösung

Newton und Quasi-Newton-Verfahren
(27.11.)	Folien
	Online Lecture 3a	× (1) Welchen Vorteil hat das Newton-Verfahren gegenüber dem Gradientenabstieg? Es konvergiert schneller Es hat einen größeren Konvergenzradius Es ist universeller einsetzbar (2) Was passiert bei negativer Krümmung Das Newton-Verfahren divergiert Der Gradientenabstieg divergiert Beide konvergieren Beide divergieren (3) Was ist der aufwendigste Rechenschritt beim Newton-Verfahren? Die Berechnung der Hesse-Matrix Die Inversion der Hesse-Matrix
	Online Lecture 3b	× (1) Was ist ein Quasi-Newton-Verfahren? Die Hesse-Matrix im Newton-Verfahren wird durch die Einheitsmatrix ersetzt Es hat nichts mit den Newton-Verfahren zu tun Die Hesse-Matrix im Newton-Verfahren wird mit Ableitungen 1. Ordnung approximiert (2) Ist eine Schrittweitenbestimmung im Quasi-Newton-Verfahren wichtig? Ja Nein (3) Wie löst man bei der Approximation das Problem, dass die invertierte Hesse-Matrix benötigt wird? Man approximiert direkt die inverse Hesse-Matrix Die Inversion der approximierten Hesse-Matrix ist sehr effizient Es kommt keine inverse Matrix vor, da nur 1. Ableitungen genutzt werden
	Online Lecture 3c	× (1) Welche Problemstruktur wird für das Gauss-Newton-Verfahren benötigt? Die Zielfunktion muss quadratisch sein Die Zielfunktion muss aus einer Summe von Fehlertermen bestehen Die Zielfunktion muss konvex sein (2) Was ist in der Jacobi-Matrix enthalten Die Krümmung der Zielfunktion Die Ableitung der Residuen nach den Parametern Der Gradient der Zielfunktion (3) Was muss in jedem Iterationsschritt des Gauss-Newton-Verfahrens berechnet werden? Es muss ein lineares Gleichungssystem in der Abstiegsrichtung gelöst werden Die Jakobi-Matrix muss invertiert werden Es muss die zweite Ableitung approximiert werden
(4.12.)	Übung, Musterlösung
(11.12.)	Übung, Musterlösung

Optimierung mit Nebenbedingungen
(18.12.)	Folien
	Online Lecture 4a	× (1) Das Minimum einer Funktion mit Nebenbedingungen ist immer kleiner gleich oder größer gleich das Minimum der Funktion ohne Nebenbedingungen? Kleiner gleich Größer gleich (2) Können Gleichheitsbedingungen und Ungleichheitsbedingungen ineinander überführt werden? Ja Nein (3) Bringen Sie die Nebenbedingung -2x + 3y <= 6 in die Form c(x,y) >= 0 [ohne Auflösung]
	Online Lecture 4b	× (1) Bei Optimierung der Funktion f unter einer Gleichheitsbedingung c muss in einem Minimum: ... der Gradient von f gleich 0 sein. Der Rest ist egal. ... der Gradient von f senkrecht zum Gradient von c stehen oder der Gradient von f gleich 0 sein. ... der Gradient von f parallel zum Gradient von c stehen oder der Gradient von f gleich 0 sein. ... der Lagrange Multiplier gleich 0 sein. (2) Wie viele einzelne notwendige Optimalitätsbedingungen löst eine Ungleichheitsbedingung c aus? Eine Zwei Drei (3) Wann ist eine Nebenbedingung c aktiv? Wenn c=0 Wenn lambda=0 Wenn lambda>0 (4) Wenn es mehrere Nebenbedingungen gibt: ... müssen alle Nebenbedingungen im Optimum erfüllt sein. ... müssen nur die inaktiven Nebenbedingungen im Optimum erfüllt sein. (5) Die notwendigen Bedingungen für ein Optimum sind: Die Gleichheits- und die Ungleichheitsbedingungen Die Ableitung der Lagrange-Funktion muss null sein Sämtliche KKT Bedingungen
	Online Lecture 4c	× (1) Das duale Problem zu einem Optimierungsproblem mit Nebenbedingungen: ... optimiert die gleichen Variablen wie das ursprüngliche Problem. ... ist ein Optimierungsproblem ohne Nebenbedingungen. ... ist ein neues Optimierungsproblem über den Lagrange Multiplikatoren des ursprünglichen Problems. (2) Was gilt bei starker Dualität? Die Optima des dualen und des primalen Problems nehmen den gleichen Wert an Das primale und das duale Problem haben dieselbe Form Die primalen Variablen können analytisch eliminiert werden
(18.12.)	Übung, Musterlösung

Lineare Programmierung
(08.01.)	Folien
	Online Lecture 5a	× (1) Haben lineare Programme immer eine Lösung? Ja Nein (2) Die Standardform eines linearen Programms erhält man durch Ein paar Umformungen Die Einführung von zusätzlichen Variablen Die Aufspaltung in positive und negative Werte und die Einführung von zusätzlichen Variablen (3) Die KKT Bedingungen Spielen bei linearen Programmen keine Rolle Sind für lineare Programme auch hinreichende Bedingungen Enthalten bei linearen Programmen nur lineare Bedingungen (4) Wenn ein lineares Programm unbeschränkt ist Ist das duale Problem auch unbeschränkt Ist das duale Problem kein lineares Programm Ist das duale Problem ungültig
	Online Lecture 5b	× (1) In der Basis befinden sich so viele Elemente, dass die dazugehörige Matrix B quadratisch ist befinden sich alle Elemente x=0 befinden sich unterschiedlich viele Elemente (2) Die aktive Menge besteht aus einer variablen Menge an Elementen, für die die Nebenbedingung aktiv ist. besteht aus allen Elementen, die nicht in der Basis sind (3) Eine Basislösung ist eine optimale Lösung ist eine Lösung auf einer Ecke des Polytops ist eine Lösung, die alle KKT Bedingungen einhält (4) Wie kommt man von einer Ecke des Polytops zur nächsten? Indem ein Element der Basis auf 0 gesetzt wird Indem ein Element aus der aktiven Menge auf 0 gesetzt wird Indem ein Element der aktiven Menge solange erhöht wird bis ein Element der Basis 0 wird.
	Online Lecture 5c	× (1) Für die Initialisierung des Simplex-Verfahrens gilt: Jeder Wert aus der gültigen Menge kann verwendet werden. Es muss ein neues lineares Programm gelöst werden um eine Initialisierung zu finden (2) Unter Pivoting versteht man: Die auszutauschenden Elemente und ihre neuen Werte lassen sich analytisch bestimmen. Pivoting ist eine iteratives Verfahren, bei dem xq schrittweise erhöht wird bis ein Abbruchkriterium erfüllt ist. (3) Im Falle einer degenerierten Basis Konvergiert das Verfahren trotzdem, wenn man Zyklen verhindert Findet man keine Lösung Sind alle Basiselemente gleich groß (4) Die Komplexität des Simplexverfahrens ist in der Zahl der Nebenbedingungen Im schlimmsten Fall exponentiell Immer linear Normalerweise kubisch
(15.01.)	Übung, Musterlösung

Nichtlineare Optimierung (Moritz Diehl)
(22.01.)	Folien & Aufzeichnungen
(29.01.)	Folien & Aufzeichnungen

Kombinatorische Optimierung
(12.02.)	Folien
	Online Lecture 8a
	Online Lecture 8b
	Online Lecture 8c
	Online Lecture 8d

Optimierung

Themen und Termine:

Einführung

Gradientenverfahren

Newton und Quasi-Newton-Verfahren

Optimierung mit Nebenbedingungen

Lineare Programmierung

Nichtlineare Optimierung (Moritz Diehl)

Kombinatorische Optimierung