Dieser Audiobeitrag wird von der Universität Erlangen-Nürnberg präsentiert.

Wir haben jetzt soweit das Simplex-Verfahren besprochen, auch in einer Form, dass es wirklich

richtig algorithmisch durchführbar ist, nicht nur sozusagen konzeptionell geometrisch oder tatsächlich geometrisch für kleine Probleme.

Und wollen jetzt im Abschluss noch uns mit etwas beschäftigen, was jetzt den Titel hat,

Optimalitätsbedingungen und Dualität. Das ist uns beide schon begegnet bei der quadratischen Optimierung.

Bei der quadratischen Optimierung hatten wir auch schon Optimalitätsbedingungen hergeleitet, also Bedingungen,

die in einem allgemeinen Fall, in einem Fall allgemeiner Optimierungsaufgaben, dann tatsächlich notwendige Bedingungen für ein Optimumsinnen

und in unserem Fall der quadratischen Optimierung sich sogar als äquivalent herausgestellt haben.

Das war eben die Existenz der Multiplikatoren und darauf aufbauend, Stichwort Dualität,

dann die Formulierung von dualen Problemen und den Zusammenhang der Lösungen des primalen und des dualen Problems.

Das möchten wir jetzt hier für die lineare Optimierung auch sozusagen nachmachen,

wobei jetzt hier zwei wesentliche Unterschiede sind.

Der eine ist, das Zielfunktional wird ein Stück weit einfacher natürlich,

bedeutet aber, wie wir jetzt mehr als genug diskutiert haben, dass ein lineares Funktional zu minimieren

nur unter Ungleichungsnebenbedingungen wirklich einen Sinn macht.

Wenn wir Gleichungsnebenbedingungen haben, so wie wir das in dieser Situation der quadratischen Optimierung hatten,

dann heißt das im Wesentlichen, man hat eine triviale Situation in der linearen Optimierung.

Nichtsdestotrotz werden wir mit dieser Situation erstmal anfangen, mit der Situation,

das Funktional ist konstant auf dem ganzen Unterraum oder aber es ist unbeschränkt,

es sei denn der Schnitt, jetzt die zulässige Menge reduziert sich auf einen Punkt.

Während im quadratischen Fall, je nachdem, ob wir sozusagen eine nach oben oder nach unten geöffnete Parabel haben,

haben wir eben auch im unbeschränkten Fall, sagen wir, wir machen Minimierung mit der nach oben geöffneten Parabel,

dann eine eindeutige Lösung.

Gleichungsnebenbedingungen in dem Sinne sind sozusagen gar keine richtigen Nebenbedingungen,

denn es heißt ja einfach nur, wir beziehen uns dann auf einen affinen Unterraum,

das heißt also, wenn wir den parametrisieren, entweder eben indirekt, indem wir das beschreibende Gleichungssystem angeben,

oder direkt, indem wir eben uns in einer Basis des Lösungsraums bewegen,

heißt das, wir haben dann damit diese Einschränkung wieder aufgehoben.

Bei Ungleichungsnebenbedingungen ist das ein bisschen was anderes, die werden dann interessanter,

da fängt die Optimierung eigentlich dann erst an, denn die können eben aktiv oder inaktiv sein.

Wenn ich mich im Inneren des Polyedas an einer Stelle befinde, dann merke ich sozusagen die Einschränkung lokal zumindest,

dann merke ich lokal die Einschränkungen, die das im Polyeda sein bedeutet gar nicht.

Ich kann mich immer noch ein bisschen bewegen, es gibt eine Umgebung, das ist eben eine offene Menge,

es gibt eine Umgebung, die genauso zu der Menge gehört.

Anders ist, wenn ich auf dem Rand bin, wenn die Einschränkung aktiv wird.

Und diesen Unterschied werden wir jetzt ein neues Phänomen in die Optimalitätsbedingungen hineinbekommen,

das sind die sogenannten Komplementaritätsbedingungen,

und dann im Nachgang können wir schauen, naja, wie ist das mit anderen Zielfunktionalen.

Wir werden sehen, bei der quadratischen Optimierung ist das genauso.

Und ein Stück weit, wenn wir hinreichend viel Analysis können, wobei das hinreichend gar nicht so viel ist,

was man da braucht, dann kann man das dann auch auf allgemeine nicht-linare Funktionale übertragen.

Das ist jetzt ein bisschen das Programm.

Ok, fangen wir an. Also wir fangen sozusagen mit der Trivialsituation an,

nur um es nochmal die Situation zu vergegenwärtigen.

Wir haben also unser lineares Zielfunktional und wir haben Einschränkungen nur durch Gleichungen gegeben.

die Notation ist jetzt ein bisschen anders als in den vorherigen Abschnitten.

Ich versuche in der Notation so eine Art Kompromiss herzustellen.

Warum sieht das so komisch aus?

Oh, der Beamer ist wieder da.

Ist ja schon mal.