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

Guten Morgen, wir waren letztes Mal so weit gekommen, dass wir gesehen haben,

will man ein quadratisches Minimierungsproblem, insbesondere mit Ungleichungsnebenbedingungen,

lösen muss man ein oder kann man äquivalent ein Komplementaritätsproblem lösen und für das

hatten wir uns jetzt schon etwas auf das Verfahren der aktiven Mengen, die aktive Mengenstrategie,

aktive Mengenverfahren, das alles das gleiche hin bewegt. Das möchte ich jetzt mal vollständig

aufschreiben. Grundlage dieses Verfahrens ist also die Beobachtung, dass wenn man die aktive

Menge sozusagen richtig treffen würde, des Optimums, dass man dann das reduzierte Gleichungsproblem

lösen könnte und daraus wird ein iteratives Verfahren, in dem man sozusagen eine Näherung für

die aktive Menge sich wie auch immer verschafft, das reduzierte Gleichungssystem löst und dann

feststellt, ob man im Optimum ist und das sind zwei Dinge nötig. Zum einen muss der vollständige

Satz von Ungleichungsbedingungen erfüllt sein und zum anderen muss die Vorzeichenbedingung für den

zugehörigen Lagrange-Modiplikator gelten. Wir gehen also mal, das Verfahren ist ein zulässiges

Verfahren, das heißt es produziert eine Folge von zulässigen Punkten, die alle also in der

Einschränkungsmenge uat liegen. Wir starten also mit so einem zulässigen Punkt, den muss man sich

verschaffen, das heißt natürlich insbesondere, dass es einen geben muss. Genauso geben wir uns

sozusagen einen in Anführungszeichen Lagrange-Modipikatoren-Vektor vor, für die

Gleichungsnebenbedingungen und analog für die Ungleichungsnebenbedingungen und wenn wir diese

drei Größen gegeben haben, dann definiert dann das Maß der Erfülltheit der Ungleichungsnebenbedingungen

unsere Menge der aktiven Einschränkungen für dieses x0, das heißt also wir können insbesondere

uns eine Menge a0 Teilmenge von a x0 wählen. Das ist unser Startversuch für das Auffinden der

aktiven Menge für das letztendlich zu findende Optimum. Das Verfahren besteht nun aus folgender

Schleife. Wenn wir in einer Stelle sind, wo alle Bedingungen erfüllt sind, also erfüllen xk zusammen

mit den Multiplikatoren yk und zk, ich sage es mal jetzt so, die KKT-Bedingungen, die Karuskuntaka-Bedingungen,

dann sind wir, das ist äquivalent dazu, dass wir im Optimum sind, dann bricht das Verfahren

nach endlich vielen Schritten ab. Das ist die eine Möglichkeit nach endlich vielen Schritten im Optimum

abzubrechen, die das Verfahren hat. Der Normalfall wird das nicht sein, sondern wir werden also jetzt

versuchen auf der Basis der Kenntnis des zk und der zugänglichen approximativen Multiplikatoren und

des ak uns die nächste iterierte zu verschaffen. Dazu setzen wir erstmal zur Notationsvereinfachung

ik als die Menge der inaktiven Einschränkungen und jetzt lösen wir, dass diese Notation hatte

ich letztes Mal eingeführt, das QBAK. Das ist also jetzt das eingeschränkte quadratische

Minimierungsproblem, was nur noch die Gleichungsnebenbedingungen hat und von den

Ungleichungsnebenbedingungen die aktiven in Form von Gleichungsnebenbedingungen. Äquivalent heißt,

dass man löse ein lineares Gleichungssystem und bekommt dann zu einer Lösung, diese Lösung

nennen wir mal die eindeutige Lösung davon, die also algorithmisch gut zugänglich ist,

die nennen wir mal x quer k. Das ist also noch nicht notwendigerweise die nächste iterierte.

Und dazu haben wir auch eben über den KKT-Wegmultiplikatoren ausgerechnet

y quer und z quer k. So, dieses xk ist jetzt sozusagen der erste Kandidat für die Lösung.

Das heißt, wir müssen diese beiden Dinge prüfen. Wir müssen prüfen, ob xk quer zulässig ist,

sprich die vollen Satz von Ungleichungsnebenbedingungen erfüllt, also zulässig für QP. Alles an die

Gleichungsnebenbedingungen sind ja sowieso erfüllt. Das war die eine Bedingung und wir müssen die

Vorzeichenbedingung, Moment, jetzt habe ich was vergessen. Jetzt setzen wir diese Multiplikatoren,

die wir jetzt erhalten haben, die nutzen wir jetzt zum Teil aus. Wir setzen zi k plus eins für die

nächste iterierte gleich zi quer k für die aktive Menge und zi k plus eins gleich null sonst. Und das

y, das ist unkritisch, das yk plus eins, da kann ja sozusagen nicht schiefgehen, was Vorzeichenbedingungen

und Nullzeilen und solche Dinge betrifft. Dann nehmen wir einfach das, was wir gerade ausgerechnet

haben. So, okay. Jetzt müssen wir zwei Dinge überprüfen, um zu schauen, ob wir im Ziel sind.

Wir müssen die Zulässigkeit jetzt erst mal dieser Lösung überprüfen, wenn dem so ist und wenn

zusätzlich jetzt der gerade definierte Multiplikatorenweckler das richtige Vorzeichen

haben, dann sind wir natürlich fertig. Die Lösung ist dieses xk quer. Wenn man will, ist das sozusagen