Vorlesungsplan Optimierung

Schauen Sie sich die Homepage zur Vorlesung an und verschaffen Sie sich einen Überblick über die dort angebotenen Materialien. Lesen Sie Kapitel 1 (Einleitung), Seiten 1–15 im Gerdts-Skript. Lassen Sie sich dabei auch etwas von den folgenden Kontrollfragen leiten. Welche Schreibweisen sind Ihnen nicht bekannt? Bereiten Sie Fragen vor, damit Sie sich selbst und dem Vorlesenden gegebenenfalls Lücken aufzeigen können. Nutzen Sie auch die Möglichkeit, Ihr bisheriges Mathematikwissen zu wiederholen. Beachten Sie auch, dass die Materialien Fehler enthalten können. Seien Sie kritisch und fragen Sie im Zweifel bitte nach!

Die Befehle für das Computer-Algebra-System Maple werden wir nicht weiter untersuchen.

• Was für Lehrmaterialien werden angeboten und wie können Sie diese für sich nutzen?
• Wie sieht ein Optimierungsproblem in allgemeiner Form aus? Nennen Sie Beispiele!
• Warum ist jedes Standard-Optimierungsproblem auch ein allgemeines Optimierungsproblem?
• Definieren Sie die Begriffe lokale und globale Optimallösung einer Optimierungsaufgabe! Was kann man sich anschaulich darunter vorstellen?
• Was meint man damit, eine Optimierungsaufgabe zu lösen?

• Wie kann man ein allgemeines Optimierungsproblem als Standard-Optimierungsproblem schreiben?

Wiederholen Sie Kapitel 1 (Einleitung), Seiten 1–15 im Gerdts-Skript. Achten Sie dabei besonders auf die Beispiele 1.0.7, 1.0.8 und 1.0.9.

• Worin unterscheiden sich verschiedene Klassen von Optimierungsaufgaben? Warum ist es wichtig, eine gegebene Optimierungsaufgabe einer Klasse zuordnen zu können?
• Nennen Sie ein oder zwei Beispiele von Klassen von Optimierungsaufgaben. Wodurch zeichnen sich diese aus?

• Nennen Sie Gründe, warum die Lösung des mathematischen Modellproblems das Anwendungsproblem nicht tatsächlich löst. Warum interessiert man sich trotzdem für dessen Lösung?

Lesen Sie im Kapitel 2 im Gerdts-Skript (mindestens)

• den Abschnitt 2.1 bis zur Ungleichung (2.2), Seiten 16–17, und
• den Abschnitt 2.2 bis vor den Satz 2.2.3 plus Bemerkung 2.2.6, Seiten 20–21, 24.

• Wann können Sie eine Anwendungsaufgabe mit Hilfe einer linearen Optimierungsaufgabe lösen? Wie gehen Sie vor?
• Wie können Sie eine lineare Optimierungsaufgabe mit Hilfe eines Computers lösen?
• Was sind Schlupfvariablen?
• Wie bringt man ein lineares Optimierungsproblem in Normalform?
• Wie bringt man ein lineares Optimierungsproblem in Standardform?
• Überlegen Sie sich ein praktisches Beispiel für eine lineare Optimierungsaufgabe, die keine zulässigen Punkte hat.

• Nennen Sie ein Beispiel für eine "lineare Optimierungsaufgabe" mit unendlich vielen Restriktionen. Was sind Probleme und Chancen solcher Darstellungen?

Lesen Sie nun den Rest von 2.1 und 2.2 (die Beweise dürfen Sie auslassen) sowie den Abschnitt 2.3 bis vor den Beginn von 2.3.1, Seiten 16–27 im Gerdts-Skript.

• Wie sieht die zulässige Menge einer linearen Optimierungsaufgabe geometrisch aus?
• Was muss erfüllt sein, damit man eine lineare Optimierungsaufgabe einfach geometrisch lösen kann?
• Was haben Optimallösungen mit Ecken zu tun?
• Wann bewerten wir eine Ecke besser als eine andere?

• Wie viele Ecken kann ein Polyeder höchstens haben?

Lesen Sie die Abschnitte 2.3.1–2.3.6, Seiten 27–40, im Gerdts-Skript.

• Was ist eine Basislösung und wie lässt sie sich beschreiben?
• Welche Wahlmöglichkeiten hat man beim Basisübergang?
• Was ist das Simplex-Tableau und welche Informationen enthält es?
• Wie kann man die Pivotzeile bestimmen? Und wie die Pivotspalte?
• Welche Formen kann das Ergebnis des Simplex-Algorithmus annehmen?
• Wie kann eine zulässige Basislösung gefunden werden um das Verfahren starten zu können?
• Erklären Sie die Begriffe Basis, Nichtbasis, Basisvektor und zulässiger Basisvektor für das Polyeder \(X = \{ x \in R^n : Ax = b, x \ge 0 \}\). Was haben diese Begriffe mit den Ecken des Polyeders zu tun?
• Erläutern Sie den grundsätzlichen Ablauf eines Schrittes im Simplex-Algorithmus. Wie kann man erkennen, ob das LP unbeschränkt ist?
• Wie kann man erkennen, ob das LP unzulässig ist?

Lesen Sie den Abschnitt 2.4, Seiten 40–44, im Gerdts-Skript.

• Was versteht man unter dem schwachen Dualitätssatz? Wie beweist man ihn?
• Was sind die Komplementaritätsbedingungen?
• Wie bilden Sie das duale lineare Optimierungsproblem?
• Welche Informationen bekommen wir aus dem dualen Optimalwert?
• Welche Informationen bekommen wir aus einer dualen Optimallösung?
• Was besagt der starke Dualitätssatz?

• Was ist der duale Simplex-Algorithmus? Wann ist dieser besser als das primale Simplexverfahren?

Lesen Sie den Anfang von Kapitel 3 vor Abschnitt 3.1, Seiten 45–49, im Gerdts-Skript.

• Beschreiben Sie das Rucksackproblem! Wie kann man es lösen?
• Beschreiben Sie das Problem des Handlungsreisenden (Traveling Salesman Problem) sowohl als praktisches Problem als auch als ILP.
• Was ist eine Relaxierung? Was sagt uns im allgemeinen die Lösung eines relaxierten Problems?
• Seien \(A \in Z^{m \times n}\) eine Matrix und \(b \in Z^m\) ein Vektor mit ganzzahligen Einträgen. Haben dann die Ecken des Polyeders \(X = \{ x \in R^n : x \ge 0, Ax = b \}\) immer ganzzahlige Koordinaten? Warum ist diese Fragestellung überhaupt wichtig?
• Nennen Sie Beispiele linearer Optimierungsaufgaben, die auf Graphen definiert sind. Warum spielt die Ganzzahligkeit der Lösung oft eine Rolle? Erläutern Sie eines der Beispiele genauer: Was sind die Matrix \(A\), rechte Seite \(b\), Kostenvektor \(c\), sonstige Beschränkungen an \(x\)?
• Was ist ein allgemeines Transportproblem?
• Wie kann man Transportprobleme lösen?
• Was ist das Heiratsproblem? Erläutern Sie die Begriffe bipartiter Graph und Matching.
• Wie kann man das Heiratsproblem als Optimierungsaufgabe formulieren? Welche Eigenschaften hat diese Aufgabe? Kann man sie mit dem Simplex-Verfahren lösen?

Lesen Sie die Abschnitte 3.1 und 3.2, Seiten 50–60, im Gerdts-Skript.

• Was ist eine Schnittebene?
• Was versteht man unter Branch-and-Bound?
• Was für untere Schranken für ein Minimierungsproblem kennen Sie?
• Was für obere Schranken für ein Minimierungsproblem kennen Sie?

• Wiederholen Sie den Begriff der partiellen Ableitungen von Funktionen mehrerer Veränderlicher, z.B. im ALA-Skript Abschnitt 7.1, Seiten 142–145.
• Wiederholen Sie den Abschnitt 7.2 aus dem ALA-Skript, Seiten 145–150.
• Lesen Sie den Anfang von Kapitel 4 inklusive 4.2, Seiten 61–73, im Gerdts-Skript. Auf Seite 68 können Sie den Text vor Satz 4.1.9 mit Eigenwerten gern auslassen. Wir werden uns auf die Charakterisierung der Definitheit aus dem ALA-Skript beschränken.

• Was ist der Gradient einer Funktion?
• Wie bestimmt man die Hessematrix einer Funktion?
• Hat jede Funktion einen Gradienten und eine Hessematrix?
• Was sind Gradient und Hessematrix einer Funktion f mit genau einer Veränderlichen?
• Was ist der Unterschied zwischen hinreichenden und notwendigen Bedingungen (z.B. für Optimalität)?
• Was sind konkrete hinreichende bzw. notwendige Bedingungen für lokale Minima für unrestringierte Optimierungsprobleme mit glatter Zielfunktion?
• Was verbirgt sich genauer hinter dem Begriff glatt?

Lesen Sie im ALA-Skript die Abschnitte 7.4 und 7.5, Seiten 153–160

• Nennen Sie eine Möglichkeit, Regularität für den Lagrange-Ansatz sicherzustellen.
• Was kann beim Lagrange-Ansatz schief gehen, wenn die Regularität verletzt ist?
• Welche Aussagen zur freien Optimierung übertragen sich dank der Lagrange-Methode auf Gleichungsnebenbedingungen?

Entfällt diesmal.

Lesen Sie Abschnitte 4.3 und 4.4, Seiten 73–78, im Gerdts-Skript.

• Wie lange benötigt das allgemeine Abstiegsverfahren, um ein Minimum exakt zu finden?
• Wie hängt das Ergebnis einer Optimierung mittels Abstiegsverfahren vom Startpunkt ab?
• Welches Verhalten eines Abstiegsverfahrens wünscht man sich (realistisch)?
• Können sich viele kleine Rechenfehler im Verlaufe eines Abstiegsverfahrens zu gravierenden großen Fehlern im Endergebnis auswirken?
• Was für Garantien bringt unsere mit Abstiegsverfahren berechnete Lösung mit?
• Was für Wahlmöglichkeiten haben Sie, um eine Abstiegsverfahren durchzuführen?
• Was besagt der Konvergenzsatz für das Gradientenverfahren mit Armijoregel?
• Welche Schrittweitenstrategien für das allgemeine Abstiegsverfahren kennen Sie?
• Was ist ein Orakel 2. Ordnung für Abstiegsverfahren?

Lesen Sie Abschnitte 4.5 bis 4.7, Seiten 78–88, im Gerdts-Skript.

• Was besagt der Konvergenzsatz für das lokale Newtonverfahren?
• Was besagt der Konvergenzsatz für das globale Newtonverfahren?
• Was ist lineare, superlineare und quadratische Konvergenz?
• Was kann in der Praxis die Anwendung des Newtonverfahrens schwierig machen?
• Welche Gestalt (Formel) hat eine lineare Funktion \(f : R^n \to R\)? Und eine quadratische Funktion?
• Was versteht man unter einem linearen bzw. einem quadratischen Modell einer Funktion \(f(x)\) in der Nähe eines Punktes \(\bar x\)?

• Schreibgeräte etc. (Wecker sind erlaubt sofern sie leise bleiben; nicht erlaubt: Handy, Smartphone und sonstige Kommunikationsgeräte)
• ausreichend eigenes unbeschriebenes Papier
• nicht programmierbarer Taschenrechner
• Tafelwerke ohne eigene Ergänzungen (im Zweifel melden Sie Ihr Tafelwerk beim Dozenten bitte an!)
• Vorlesungsmitschriften/Skript sind nicht direkt zugelassen.

Es wird eine vorlesungsspezifische Prüfungshilfe geben, die Sie selbst erarbeiten und den Klausuraufgaben beigefügt wird.

• Deren Umfang ist auf 2 Seiten A4 beschränkt.
• Sie reichen bei Dr. Düvelmeyer Vorschläge per Email ein, bis zum 18.7.2011 (Montag nach der letzten Vorlesung).
• Vorschläge können vom Dozenten ohne Grund abgewiesen werden.
• Keine Garantie für die Exaktheit der Notizen.
• Bekanntgabe der Klausurversion der Hilfe am 20.7.2011.

Ziel ist, dass Sie Standardtechniken der Optimierung erfolgreich auf praktische Probleme anwenden können. Um dies zu überprüfen, wird es Aufgaben aus drei Bereichen geben.

• Wissensfragen: Wiedergabe und Erklärungen zu theoretischen Aspekten.
• Modellierung: Aus Textbeschreibungen eines Problems soll eine mathematische Problemformulierung gewonnen werden.
• klassisches Rechnen: mathematische Probleme sollen rechnerisch gelöst werden.