Inhaltlich weitermachen, wir haben uns das letzte Mal, Schnittebenenverfahren hat mal abgeschlossen und haben uns mit Lagrange-Relaxierung beschäftigt. Die Idee im Unterschied zu Schnittebenenverfahren ist, dann nehmen wir ja die Ganzzahligkeitsbedingungen aus dem System und bringen die

Ganzzahligkeitsbedingungen wieder rein, indem wir Schnittebenen erzeugen, in der Hoffnung, dass man am Ende dann tatsächlich ganzzahlige Lösungen findet. Lagrange geht anders vor, da nimmt uns eine Teilmenge der Randbedingungen raus, bestraft diese Randbedingungen bei Verletzungen in der Zielfunktion, behält aber die Ganzzahligkeit im System. Und da haben wir das nächste Mal

nachgewiesen, da sind wir stehen geblieben, dass A, man dadurch eine Schranke hält, die mindestens so gut ist wie die LP-Relaxierung, aber natürlich auch nur höchstens so gut wie die Ganzzahlige Lösung und, dass es in der Regel irgendwo dazwischen liegt, das schauen wir uns in der Übung

an. Und das Zweite, was wir festgestellt haben, diese Lagrange-Funktion L von Lambda, also die Maximierung über diese Lagrange-Funktion, das ist ein Maximieren über eine stückweise linearen konkarfen Funktion. Das ist L von Lambda, stückweise linearen konkarfen, und da sind wir das letzte Mal stehen geblieben, das ist die Frage, wie kriegen wir jetzt ein

Maximum über eine stückweise linearen konkarfen Funktion raus. Das wollen wir uns heute anschauen und dann noch eine weitere, eine dritte Relaxierungsmöglichkeit kennenlernen, die sogenannte Danzig-Wulf-Dekomposition, also in dem Sinne mehr von Dekompositionsmethoden, wo wir dann hergehen wollen und auch wieder ein Teilsystem rausnehmen, aber dieses

Teilsystem reformulieren über die Idee, die wir schon hatten. Polyeder lassen sich entweder über durchschnittendlich viele Halbräume charakterisieren oder als konvexe Hülle der Ecken, wenn es den Ecken gibt, und der konischen Kombination der Extremalen. Und auf diese Art und

Weise, genau diese Tatsachen wollen wir ausnutzen, sozusagen dieses System über Ungleichung reformulieren in der anderen Darstellung und dann wieder ein System integrieren. Schauen wir mal, was da dabei rauskommt, da werden wir sehen, dass man im linearen Fall auf jeden Fall die Lösung kriegt, sogar in gewissen Fällen im Ganzzahligkeitsfall auch tatsächlich

sogar beweisbar die ganzzahlige Optimallösung findet. Gibt es aber erst mal noch zum letzten Mal noch Fragen bis dahin, was Lagrange- Relaxierung betrifft. Ist nicht der Fall. Wir sind also das letzte Mal genau an der Stelle stecken geblieben, dass also die Lagrange-Funktion so

aussieht, also vom Bild her ist das irgendwie so eine Funktion, Stückweise linear und konkar. Jetzt wollen wir dort das Maximum bestimmen,

also was wir tun wollen, ist maximiere Lambda größer gleich Null, dieses L von Lambda. So, also das heißt, die Frage ist, wir brauchen jetzt eine Bode, wie finden wir diesen Punkt? Okay. Was wird man denn normalerweise tun, wenn wir so eine Funktion haben, die glatt ist? Also in dem Sinne, wenn wir

sowas haben. Wenn wir sowas hätten, dann würden wir ganz klassisch einfach die Ableitung bestimmen und die Ableitung gleich Null setzen in einer Dimension. Wir haben hier noch eine Variable in einer Dimension und

dort, wo die Ableitung Null ist, haben wir potenzielle Kandidaten für Minima, Maxima oder Sattelpunkte. In dem Fall, wo wir wissen, dass es konkar ist, ja, ganz natürlich an der Stelle, wo, wenn es denn die Ableitung eine

Null-Stelle hat, müssten wir damit eigentlich die Optimallösung haben, auch das Extremum gefunden haben, das eindimensionale Analysis. Im eindimensionalen, wenn wir Lander jetzt im hörendimensionalen Fall haben, also in unserem Fall, wenn wir viele Ungleichungen relativieren, dann haben wir hier natürlich ein Vektor stehen, dann heißt natürlich Ableitung

Gradient, dann müssen wir Gradient gleich Null setzen, dann müssten wir die Hessische Matrix angucken und dergleichen mehr. Das denke ich, sind altbekannte Sachen. Das einzige Problem, was wir jetzt hier eben haben, ist, dass wir die Ableitung nicht haben, in unserem Fall. Genau an den Punkten ist unsere Funktion ja nicht ableitbar. Also können wir

diesen klassischen Ansatz so nicht wählen, dass wir einfach mal den Gradienten ausrechnen, weil den Gradienten gibt es nicht an diesen Stellen, weil dort die Funktion nicht differenzierbar ist. So, was macht man anstattdessen? Anstattdessen, man erweitert einfach diesen Begriff

des Gradienten und beschäftigt sich mit sogenannten Subgradienten. Also das ist eigentlich die Idee, was wir ja nur brauchen, ist folgendes. Wenn ich mir das im glatten Fall anschaue, wenn ich hier irgendwo an einem Punkt bin, dann berechne ich sozusagen die Ableitung. Das heißt, es gibt mir ja

der Gradient gibt mir eigentlich eine Richtung, in der ich sozusagen Richtung Maximum laufen kann. Und das ist ja nichts anderes als der Gradient von L, von Lambda, wenn ich ihn denn hätte. So, das habe ich hier aber nicht. Also hier hätte ich es, wenn ich an so einer

Stelle bin, bin ich natürlich glatt. Und dann kann ich natürlich auch diesen Vektor bestimmen. Das ist genau das gleiche, aber das Problem ist natürlich genau an diesen Eckfällen. Und naja, wenn man optimiert, landet man gern an solchen Eckfällen. Und jetzt in der Stelle gibt es ein Gradient. Aber in dem Fall muss ich ja auch nicht unbedingt, was heißt,

ich könnte jetzt, um weiter zu laufen, kann ich sowohl in die Richtung, könnte ich weiter laufen oder auch in die Richtung. Ja, sozusagen alles, was in diesem Bereich ist, ist ja für mich in Ordnung. Also in dem Fall gibt es einen größeren Bereich, der für mich in Ordnung ist. Und das

nennt man Subdifferential. Also die erfüllen natürlich dann nicht im Ableitungsfall, das mit Gleichheit, sondern nur mit kleiner gleich. Aber alles, was ich ja brauche, ist, ich möchte irgendwie weitermachen können. Und deswegen erweitert man diesen Begriff zu dem Subdifferential. Und dann schauen wir einfach, wie wir ganz konkret an jedem dieser Punkte so ein

Subdifferential ausrechnen können. Und dann müssen wir uns nur noch über die Schrittlänge Gedanken machen. Ja, diejenigen, die vielleicht schon nicht lineare Optimierung gehört haben, die klassischen nicht linearen Optimierungsverfahren sehen, oder eigentlich alle nicht linearen Optimierungsverfahren sehen so aus, man bestimmt eine Schrittrichtung,

also eine Richtung und eine Schrittlänge. Also man braucht so einen Vektor und da muss man noch überlegen, wie weit man läuft. Aber letztendlich alle nicht linearen Optimierungsprobleme basieren auf diesem System. Gut, also schauen wir uns das mal an. Also was

heißt Subdifferential? Das ist die nächste Definition. 3, 36 sei L vom R hoch M nach R konkav. Dann heißt U aus dem R hoch M mit heißt

U im Punkt lambda Null Subgradient, falls L von lambda minus L von

minus L von lambda Null kleiner gleich U transponiert lambda minus

lambda Null für alle lambda ist. So was steht hier, wenn wir ableiten könnten und wir würden das auf die andere Seite bringen, dann würde hier mit Gleichheit genauer Gradient stehen. Also eindimensional oder

höherdimensional dann auch. Entsprechend. Das heißt, was wir hier machen ist aus diesem Gleichheit ein kleiner Gleich, deswegen Sub anstatt Gradient. Und das ist genau das, was wir brauchen, nämlich genau an dieser Stelle. Wir erlauben sozusagen auch Richtung, die hier irgendwo dazwischen liegen und nicht nur genau eine dieser beiden hier sind. Gut.

So und jetzt ist die Frage natürlich, tun es diese Subgradienten? Also wenn wir diese haben, kommen wir mit denen tatsächlich hier zu dem lambda Stern und wenn ja, wie kriegen wir denn überhaupt so ein Subgradient

raus? So und ein Teil davon beantwortet der folgende Satz, das ist der Satz 337. Also einmal sei lambda Null aus dem R hoch M eins, jetzt in

dem Fall x Null eine Optimallösung für uns Optimierungsproblem. Ich schreibe

das mal noch mal hin. So gucken, wo ich es habe. 316. Also das ist sozusagen die

Bestimmung von L von lambda. Also sei x Null Optimallösung für Minimum C T x minus lambda Null B eins minus A eins x und x aus P Zwo. Ja also wir geben

uns das lambda Null vor und dann schauen wir uns dieses Teilproblem an, wo wir nur noch über die A Zwo x kleiner gleich B Zwo optimieren. Also das ist genau unser L von lambda und sei x Null so eine Optimallösung, können wir aus dieser Optimallösung direkt einen solchen Subgradient ausrechnen. Dann

folgt G Null gleich A eins x Null minus B eins ist Subgradient. Okay also

direkt aus der Bestimmung von L von lambda die Optimallösung, eine Optimallösung x Null, die das L von lambda Null bestimmt. Also das Ding ist

ja gerade L von lambda Null. Genau die liefert uns direkt so ein Subgradient. Und das ist genau dieser Vektor, der hier oben steht. Okay, so das ist die erste Aussage, die wir da stecken haben. Also das ist schon mal nett.

Ich meine das L von lambda Null müssen wir eh ausrechnen. Ja und wir kriegen zum Nulltarif sozusagen gleich ein Subgradienten geschenkt. Das ist das eine. Das zweite ist, wenn wir so ein Subgradient haben, also jetzt wissen wir ja, wir haben den. So jetzt können wir ja weiter Richtung Maximum marschieren. Die Frage

ist, wann wissen wir denn, wann wir aufhören sollen. Ja und aufhören können wir genauso wie im Fall, wenn es differenzierbar ist. Also lambda Stern maximiert die Funktion L genau dann, wenn Null ist Subgradient an L

in lambda Stern. Also sobald die Null da drin auftaucht, wissen wir, sind wir fertig. So jetzt müssen wir es natürlich noch beweisen. So die

einfach los, das sind mehr oder weniger Einsätzen. Also L von lambda minus L von lambda Null. So da setzen wir es einfach mal in die Definition ein. Also wenn

die zugehörige Lösung zu dem lambda sei x lambda, dann ist das ct x lambda minus lambda transponiert b 1 minus a 1 x lambda für den ersten Teil, minus ct

x Null, brauchen wir jetzt erst die Klammer, minus lambda Null transponiert b 1 minus a 1 x Null. Das ist einfach in die Definition eingesetzt. So jetzt machen

wir aus diesem lambda hier immer eine Null. Wenn wir hier anstatt diesem x lambda ein x Null setzen, dann wird das höchstens größer gleich, weil das x lambda ist

das Minimum hier über diese Funktion. Das heißt x lambda selber ist zulässig und x Null ist auch offensichtlich zulässig für x aus p 2, aber ist möglicherweise nicht die Optimallösung bezüglich lambda. Also können wir das hier abschätzen,

indem wir hier jeweils die Null oben hinschreiben, den Rest lassen. So und jetzt, wenn wir das uns anschauen, was bleibt noch stehen? So hier steht ct x Null, hier ziehen wir das ct x Null wieder ab. Hier steht ein b 1 minus a 1 x Null, das gleiche

steht hier hinten auch. Das ist genau unser g hier, minus g. Das heißt, das ganze hier ist, wenn wir das weiterschreiben, ist nichts anderes als g Null transponiert

mal lambda minus lambda Null. Also das ist wirklich kein Hexenwerk, was da dahinter steckt und wir haben genau diese Definition erfüllt, die wir hier stehen haben. L von lambda minus lambda Null ist kleiner gleich, g Null transponiert lambda minus

lambda Null. So das ist die eine Geschichte. So die zweite ist sozusagen, wann können wir aufhören? Also genau wenn Null ein Subdifferential ist, also zu b. Was haben

wir da zu tun? Ja das eine ist, also die eine Richtung, wenn Null ein Subdifferential ist, ja was steht dann da? Dann steht hier L von lambda minus L von lambda Null ist

kleiner gleich Null transponiert, also machen wir mit lambda Stern, so soll ich es natürlich schreiben, ist kleiner gleich lambda minus lambda Stern. Also wenn die Null ein Subdifferential

ist bezüglich lambda Stern, dann gilt offensichtlich die Beziehung, hier steht sie ja noch, bei der Definition, Null transponiert das, das ist gleich Null, das heißt daraus folgt L von lambda ist kleiner gleich L von lambda Stern für alle lambda, das

heißt lambda Stern maximiert die Funktion. So das ist die eine Richtung, ja die andere ist genau das gleiche, da nehme ich die Beziehung, ja aus dieser Beziehung folgt

natürlich das L von lambda minus L von lambda Stern ist kleiner gleich Null, das ist nichts anderes als, das kann ich jetzt ergänzen, wie ich lustig bin, ich ergänze es so, ist nichts anderes als Null transponiert lambda minus lambda Stern, also daraus

folgt Null, das ist Subgradient. Gut, so das heißt, damit haben wir jetzt aber auch schon eigentlich direkt ein Verfahren zur Hand, ja warum? Also der G Null,

der zeigt uns, wenn wir uns jetzt diesen G Null mal anschauen, also es gilt ja offensichtlich, G Null transponiert mal lambda minus lambda Stern, oder lambda Stern minus, machen wir es andersrum jetzt hier, lambda Stern minus lambda Null, ja ist

sicherlich größer gleich als L von lambda Stern minus L von lambda Null, und von dem wissen wir ja, dass das größer gleich Null ist. So das heißt unser G Null zeigt uns tatsächlich in die Richtung, wo wir wollen, also das einzige, also wir wissen,

wir sind an einem Punkt, wir wissen, G Null zeigt in die richtige Richtung, jetzt laufen wir einfach in diese Richtung. Die einzige Frage, die noch offen ist, wie weit laufen wir? Welche Schrittlänge nehmen wir? Und naja, da gibt uns der

folgende Satz dann eine Auskunft drüber, aber bevor wir den uns anschauen, schauen wir uns vielleicht das generelle Verfahren an, also wir fahren, wir laufen, wir machen so, wir lösen einfach für irgendein lambda, sage ich am Anfang, dieses Problem hier, was hier steht, das ist einfach über den P 2, da sind

allerdings die Ganzheitlichkeitsbedingungen dabei, dann kriegen wir daraus unser G Null, wenn zufällig die Null sozusagen, G Null die Null ist, oder größer, das kann man auch leicht erkennen an dieser Stelle, ob sozusagen

Null in dem Fall möglich wäre, dann sind wir fertig, wenn nicht, wenden wir einfach auf lambda das G Null an, addieren das drauf, kriegen neue Null an das, ja, und iterieren den ganzen Prozess. So, das ganze Verfahren,

wenn man das aufsetzt, nennt sich Subgradientenverfahren. Also ich schreibe das mal zusammen, Algorithmus 3, 38, Subgradientenverfahren, also Input ist,

Input, Output lasse ich mal, oder Input, Input, L aus dem R hoch M nach R von K, Output, Max, L von lambda, lambda größer gleich Null, so, was machen

wir, als ersten wähle irgendein lambda Null, wähle lambda Null beliebig,

setze unseren Laufindex K gleich Null, so einen Skript habe ich jetzt komischer, wo ist das lambda da unten stehen, das ist besser glaube ich oben, also wähle lambda Null aus beliebig, so das zweite ist bestimme L von

lambda K, ja, und sei x K die Optimallösung, sei x K Optimallösung

dazu, durchlösen von diesen Problemen, was wir hier oben haben, hier steht es nochmal, ja und dann, so jetzt kommen schon die Wagenformulierungen, wir wissen nämlich nicht genau wann wir aufhören, das müssen wir noch überprüfen,

also sage ich gleich noch was dazu, ist Stop Kriterium erfüllt, gut dann Stop,

fangen wir jetzt wirklich mal so allgemein, so und dann kommt der nächste Schritt, so wähle, ich schau mal hier hin, wähle lambda K plus eins durch lambda K plus

eins ist gleich das alte lambda K plus nu K mal gK, wobei nu K jetzt eine noch festzulegen, die Schrittlänge sei, ja nu K, also nu K aus dem R plus die

Schrittlänge und dann zählen wir noch den Zähler hoch, 5K wird zu K plus

eins und das war's, okay, also eigentlich ein ziemlich einfaches Verfahren, wenn wir jetzt mal angucken, ein paar Sachen habe ich jetzt offen gelassen, einmal das hier, da werde ich gleich noch was dazu sagen oder der nächste Satz sagt was dazu, dann das zweite ist hier dieser Punkt,

also ansonsten ist das Verfahren eigentlich festgelegt, weil das ist die Bestimmung von dem ist klar, das ist ein gemisch ganz zahliges lineares Programm, wir können jede beliebige Optimallösung nehmen, damit kriegen wir den Gradienten, das heißt das einzige, wo wir wirklich

noch wählen können, ist sozusagen hier an dieser Schrittlänge und so sehen auch typischerweise alle nicht-linearen Optimierungsverfahren aus, das sind so iterative Verfahren, wo man die Richtung hat plus die Länge und es gibt den neuen Punkt, den man überprüft.

So die Frage ist jetzt A, wie wählt man diese MyS und B, kann ich so wählen, dass ich hier ein vernünftiges Githem angeben kann, dass ich tatsächlich immer am Schluss die Optimallösung finde beziehungsweise sozusagen, dass am Schluss tatsächlich hier

das G0 der Nullvektor ist. Was für Voraussetzungen müssen wir denn an dieses Nüder stellen? Also was sind da so Vorschläge? Also typischerweise ist es ja so, dass man am Anfang, also man sitzt

an irgendeinem Punkt, man hat keine Ahnung sozusagen, wo das Maximum liegt. Was wird man am Anfang versuchen, sozusagen nach Möglichkeit in großen Schritten möglichst nah an das Ziel zu kommen? Man ist ja irgendwo, also versucht man am Anfang vielleicht mit großen Schritten erst mal in die richtige Richtung zu kommen. Das G zeigt ja in die richtige Richtung.

Die einzige Gefahr, die man mit großen Schritten hat, ist, dass man vielleicht drüber hinaus schießt. Also in unserem Bild hier oben, wenn ich hier links anfange, ich laufe in die gelbe Richtung. Wenn ich das Land jetzt zu groß wähle, dann laufe ich über den Hügel drüber und lande auf der anderen Seite. Am Anfang vom Prozess ist es vielleicht gar

nicht schlimm, dann laufe ich halt vom einen Hügel auf die andere Seite wieder hin und her, aber irgendwann sollte ich natürlich mal anfangen, sozusagen dieses Überspringen des Maximums aufzuhören. Also muss ich kontinuierlich diese Schrittweite reduzieren. Das ist das, was

man dann typischerweise macht, ist sozusagen, dass man sukzessive diese Nüs gegen null gehen lässt, damit das Verfahren überhaupt konvergiert. Also eine notwendige Voraussetzung ist, dass diese Nüs im Laufe der Zeit gegen null konvergieren. Wenn sie das nicht tun, kann ich immer oszillieren. Also das ist eine notwendige

Voraussetzung, die man an das Ding stellen muss. Muss ich noch eine stellen? Ich muss noch eine zweite stellen, wenn mir nämlich das Ding gegen null geht. Ich muss auch dafür sorgen, dass, egal wie weit ich weg bin, dass ich auf jeden Fall mein Ziel erreiche. Also wenn ich alle Schrittlängen aufaddiere,

dann muss ich auf jeden Fall zu dem Maximum kommen können. Also und ich weiß ja nicht, wo ich am Anfang starte. Mein erstes Land an null ist ja völlig willkürlich gewählt. Das heißt, ich muss eigentlich auch dafür sorgen, dass wenn ich alle Schrittlängen aufsumme, ich garantiert hinkomme. Das heißt, die Summe über alle Schrittlängen muss divergieren. Das sind

genau die zwei Voraussetzungen, die man braucht. Einmal die Summe muss divergieren und die Folge selbst muss zu null konvergieren. Wenn ich die zwei Voraussetzungen habe, dann konvergiert tatsächlich das Verfahren. Das sagt der folgende Satz. Das ist der Satz

339. Also ist L nach oben beschränkt und

gilt einmal der Liemes, nu von k ist gleich null, für k gegen unendlich. Und

plus unendlich, k gleich null bis unendlich. Dann folgt Liemes L von lambda k, ist gleich L von lambda Stern, für k gegen unendlich. Und das geht zurück auf Polyak

1967 hat er das bewiesen. Den Beweis schenken wir uns, dass die beiden Kriterien notwendig sind. Die haben wir uns gerade erarbeitet, dass sie auch hinreichend sind. Das ist

sozusagen der Beweis und deswegen ist auch dem Polyak das zugeschrieben. Ja, Beispiele für solche, gibt es überhaupt solche Folgen, die es erfüllen? Analysis 1. Wer

kennt noch eine aus Analysis 1? Ja, genau. Also die harmonische Reihe oder die Folge 1 durch n erfüllt dieses Kriterium. Also die Folge 1 durch n für n gegen unendlich

geht gegen null, aber die Summe 1 durch k war wahrscheinlich bei Ihnen auch eine nette Übungsaufgabe am Anfang, dass das Ding tatsächlich divergiert. Divergiert

ist natürlich, dass aus theoretischer Sicht, aus praktischer Sicht hilft das ehrlich gesagt nicht so wirklich, weil ich meine, hier steht limes k gegen unendlich. Wir wollen ja nicht unendlich lang auf das Ergebnis warten, zumal wir ja

eigentlich ein endliches Problem haben. Also unser Ausgangsproblem war ja die Lösung eines gemischt ganzzahligen linearen Programms. Auch wenn das NP schwer ist, so wissen wir doch zumindest, dass wir das in endlicher Zeit lösen

können, vorausgesetzt das Problem ist beschränkt und das haben wir ja hier auch vorausgesetzt. Also kommen wir eigentlich vom Regen in die Traufe. Aus dem Endlichkeitsresultat machen wir plötzlich ein Konvergenzresultat. Deswegen muss man eigentlich an dieser

Stelle, deswegen gibt es hier dieses Stop-Kriterium. Das heißt, man muss sich Gedanken machen, sozusagen wann höre ich diesen Prozess auf. Und das typische ist, also wenn man solche Verläufe anschaut von solchen Lagrange- Funktionen, man macht am Anfang unheimlich schnell einen Fortschritt und irgendwann tümpelt das so vor

sich hin. Wenn man diese Funktion L von lambda mal plotet, dann geht es relativ steil am Anfang hoch und dann tümpelt das so vor sich hin, macht es immer noch ein bisschen Fortschritt, aber relativ wenig. Und dann muss man halt irgendwann sagen, naja, breche ich einfach ab. Wobei irgendwann sagen, das muss man sich halt wirklich das Problem selber

angucken, wie gut man dann tatsächlich ist. Wir berechnen ja auch, das muss man auch sagen, letztendlich nur Schranken, also Relaxierungen. Ob ich jetzt aufs letzte Epsilon sozusagen diese untere Schranke am Schluss raus bekommen habe, ist vielleicht dann auch den Aufwand nicht wert am Ende. Gut, also die Frage ist, wann

wendet man denn sowas gerne an? Oder wenn wir jetzt ganz konkret vor so einem Problem stehen, ja, wann wird man denn jetzt diese Schnittebene machen oder wann wird man denn Lagrange machen? Und wenn wir jetzt sagen, wir machen Lagrange, wir haben uns dafür entschieden, welche Randbedingungen

schmeißen wir denn raus? Da sind sozusagen, wir pochen sozusagen zwei Herzen in einer Brust, wenn man so will, weil wenn ich möglichst viele Randbedingungen rausnähen, dann wird natürlich mein Restproblem, das P2, wird dann einfach. Ich kann ja auch,

der Ansatz funktioniert auch, wenn ich alle Randbedingungen rausnähe. Dann steht da einfach freies Optimierungsproblem oder wenn ich 0,1 Variabeln habe, 0x zwischen 0 und 1 und alle Randbedingungen a x kleiner gleich b schmeiß ich in die Zielfunktion. Das ist unsere Problem, kann ich super einfach lösen, das ist ein Würfel, da kann

ich locker mit Greedy oder einfach in der Zielfunktion gucken, sozusagen welche positiv sind, die packe ich alle, die anderen, die negativ sind, nehme ich nicht. Also je mehr ich nach oben packe, umso leichter wird eigentlich mein Teilproblem. Also schmeiß ich doch alles nach oben. Nein, weil

je mehr ich nach oben schmeiße, umso mehr Land das muss ich mich kümmern. Also die Dimension des konkarfen Optimierungsproblem wächst natürlich mit jeder Nebenbedingungen, die ich nach oben nehme. Und das heißt, mein Verfahren ist ein höherdimensionales Verfahren, also hier die lambda ks,

das heißt, das wird entsprechend auch länger brauchen. Also was ich zur Lösung des Teilsproblems an Zeit gewinne, büße ich eventuell wieder ein oben dann sozusagen beim Interationsprozess, wenn ich diese superhinten Verfahren anwende. Also deswegen muss man immer abwägen sozusagen,

was mache ich wo oder welche Teile nehme ich raus, welche nehme ich nicht raus. Und häufig ist es auch aus der Anwendung heraus schon so, dass man irgendwie ein klares Bild kriegt, wann man welche Bedingungen man rausnimmt. Also da möchte ich vielleicht noch zwei Beispiele kurz erwähnen,

wo dem so ist. Anwendungen, also die erste ist eigentlich das, wo das eigentlich das erste Mal richtig erfolgreich auch angewandt wurde, war das Traveling Salesman Problem.

Und also Traveling Salesman Problem, wem sagt das nichts, was Traveling Salesman Problem ist? Also wir haben eine gegebene Anzahl von Städten und wir möchten die kürzeste Rundreise durch diese Städte irgendwie finden. Das ist das Traveling Salesman Problem.

Wer kennt noch keine ganzzahlige Formulierung als ganzzahliges Programm vom Traveling Salesman Problem? Hände gehen hoch, gut, dann gucken wir uns das mal an, wie wird man denn so was machen? Also, wie wird man denn das Traveling Salesman Problem als ganzzahliges Programm formulieren? Also

wir haben die Städte, machen wir da einfach halber, wir haben vollständigen Graf, also G gleich V, E, vollständig. Es sind alle potenziellen Verbindungen da. Wenn einen nicht da wäre, können wir ja als Gewicht unendlich drauf geben oder eine ziemlich

große Zahl, dass die nicht gewählt wird. So, was müssen wir für Entscheidungen fällen? Also sind wir als erste, was für Variablen brauchen wir? Am Schluss haben wir einen Knoten I, hier haben wir einen Knoten J. Wir wollen

ja letztendlich wissen, sozusagen, welche Kanten wählen wir. Also brauchen wir sozusagen als Variablen Xij, ja, ist 1, falls ij aus E in

der Tour und 0 sonst. So, dann minimieren wir natürlich unsere Zielfunktion, also das heißt, wir minimieren somit

Cij Xij, ij aus E. Ja, wir haben natürlich als Randbedingungen, die schreibe ich gleich mal hier hin, die müssen alle aus 0, 1 sein, so was noch. Das allein

reicht ja noch nicht. Ja, genau, also in jedem Knoten muss einer rein, einer raus. Also Summe, ich schreibe das mal in Kurzform, ij aus Delta von

Vxiv muss gerade 2 sein. Das ist also für alle V aus V, okay, reicht es. Zusammenhang

brauchen wir noch, ja, also was jetzt mit diesen Bedingungen allein passieren kann, ist noch sowas, wenn das meine Knoten sind, ja, dann kann es solche Kotzzyklen geben. Also, ich habe zwar, jeder Knoten hat

genau, geht genau einer rein, einer raus, aber das sind halt nicht zusammenhängend. Das heißt, man muss jetzt hier noch diesen Zusammenhang modellieren. So, also, wie modelliert man Zusammenhang? Das heißt, über jeden Schnitt muss mindestens einer drüber. Ich habe hier einen Schnitt, das heißt, alle Kanten, die hier drüber laufen, davon muss ich

mindestens eine wählen. Ich gucke mal so hier alle Kanten da rüber an, das gleiche für den und von, eine von denen muss ich wählen. Das drückt man so aus, man schaut sich alle ij jetzt aus delta von

w an. xij ist größer gleich eins, für alle w Teilmenge von v und w ist ungleich v und ungleich der Lernmenge. So, die Bedingung kann ich ja noch ein bisschen

stärker machen, weil ich weiß, also, wenn ich auf die andere Seite gehe, muss ich auch wieder zurück. Ich habe eine Rundreise, das heißt, aus der eins kann ich auch eine zwei machen. So, brauchen wir noch was? Jetzt müssten wir

es eigentlich haben. Aber Romik, wie sehen wir das ein? Naja, das sehen wir genau über dieses Argument.

Erstens hier, wir wissen ja, in jedem geht einer rein und einer raus. Das heißt, ich fange an irgendeinem Knoten i an. Ich weiß, mit der Bedingung muss einer rausgehen. Bin ich am anderen Knoten, nachdem das nicht gleich zwei ist, muss wieder einer rausgehen. So,

jetzt laufe ich so weiter, muss wieder einer raus. Es gibt zwei Möglichkeiten. Entweder ich treffe, ich laufe über alle oder ich mach, ich laufe irgendwann zurück, aber ich habe einen Knoten vergessen. Das ist genau dort, wo ich hier zurück laufe. Das ist so ein W, was offensichtlich diese Bedingungen nicht erfüllt. Aber nachdem die erfüllt sein muss,

muss ich jeden Knoten mitgenommen haben. Das heißt, ich habe tatsächlich eine Tour. So, das ist tatsächlich eine ganzzahlige Formulierung für das Traveling Seismen Problem. So, jetzt schauen wir uns mal an, was würde Lagrange machen jetzt an dieser Stelle? Also,

jetzt sehen wir ja, jetzt sind wir ganz konkret. Und zum Beispiel, es bietet sich, es bieten sich eigentlich zwei Dinge an. Ich nehme die raus oder ich nehme diese Klasse von Bedingungen raus. So, wenn ich die rausnehme, dann kriege ich hier oben was, was, was kriege

ich hier für ein Problem? Ganzzahligkeitsbedingungen, Summe der xj gleich zwei. Das ist kombinatorisch ein zwei-matching-Problem. Also, matching, für die, die noch nicht grafen Algorithmen gehabt haben, das matching ist sozusagen, ich verbinde sozusagen Knoten paarweise, das ist ein Matching, daher der Name, ja,

und zwei-matching heißt, jeder Knoten ist genau mit zwei Kanten-Inzident. Das heißt zwei-matching. Ein normales, ein einfaches Matching heißt, jeder Knoten ist höchstens mit einer Kante-Inzident. Und zwei-matching heißt, genau mit zwei. Okay, also dieses Ding hier modelliert mir ein zwei-matching. Das lässt sich

kombinatorisch sogar lösen. Also, gibt es Algorithmen dafür, diejenigen, die sich für grafen Algorithmen interessieren, können da das mal nachlesen. Das heißt, wir kriegen, wenn ich das rausschmeiße, automatisch Ganzzahligkeit über diesen kombinatorischen Algorithmen. Das ist eigentlich auch die Idee von Lagrange zu sagen,

nimm einen Teil raus, sodass was bleibt, auch wenn ich die Ganzzahligkeit dabei habe, dass ich direkt exakt lösen kann oder vielleicht sogar nicht über LP-Methoden, sondern über kombinatorische Algorithmen. Und es geht in dem Fall. So der Nachteil von dem Verfahren ist

aber, wie viel Randbedingungen schmeiße ich denn da raus? Es gibt ja exponentiell viele Schnitte. Für jeden Schnitt, für jeden Schnitt gibt es hier eine Randbedingung. Für jeden einzelnen Schnitt gibt es eine. Wie die Zielfunktion packt, muss ich da in dem Verfahren exponentiell viele solche

Landas kontrollieren. Das ist ein bisschen aufwendig. Also das sieht man schon, wie gesagt, möglichst viel rausschmeißen, vereinfacht zwar mein Problem, aber bringt mir ein enormes Problem dann oben in der Zielfunktion, insbesondere beim Subgradientverfahren. So jetzt könnte man eigentlich das andere noch probieren. Wir

schmeißen die raus, lassen die drin. Was kriegen wir denn dann? Dann kriege ich im Wesentlichen aufspannendes Baumproblem. Wenn Sie sich erinnern, über jeden Schnitt muss mindestens einer

drüber gehen. Machen wir ruhig hier mal mit der Eins. Über jeden Schnitt muss mindestens einer drüber gehen. Das ist genau eine Formulierung für das aufspannende Baumproblem. Also Zusammenhang in einem Grafen, so wie es gerade gesagt wird. Damit modelliere ich Zusammenhang in einem Grafen. Und eine minimale Struktur, die zusammenhängt ist, ist ein Baum. Minimal

aufspannende Bäume kann man auch wieder super einfach berechnen. Diejenigen, die Grafen-Algorithmen schon mal gehört haben, gibt es verschiedene Gridi, eigentlich funktioniert da Gridi- Gruskal und Primes sind die zwei, die zwei Alternativen da vorgeschlagen haben, aber beide beruhen auf einer

Gridi-Idee. Also lässt sich es relativ einfach implementieren. Und man hat damit alle exponentielle vielen von diesen Randbedingungen kombinatorisch erschlagen. Man kann sozusagen dann dieses mit denen, obwohl es exponentiell viele Randbedingungen sind und diese 0,1-Bedingungen

polynomialer Zeit lösen. So damit, und jetzt hat man nur noch die Landas, nur noch Anzahl Knotenfiele. Wir haben quadratisch viele Variablen, aber nur Anzahl Knotenfiele Landas. Das heißt, dieser Ansatz scheint zumindest auf den ersten Blick deutlich vielversprechender als die

andere Klasse von Ungleichen hochzunehmen. Und der ist auch tatsächlich enorm gut, das muss man sagen. Also es gibt Implementierungen von diesem Verfahren rein kombinatorisch. Den Zusammenhang hat man eigentlich erst später gesehen. Es gab schon in den 50er, glaube ich, oder 60er gab es von Linn-Körnig im Verfahren, was genau auf dieser Idee

beruhte. Man nennt dann diese Relaxierung hier unten die Einsbaum genannt, weil es ein bisschen eine Erweiterung von einem aufspannenden Baum ist, was sich hier modellieren lässt. Aber letztendlich mit dieser Idee kann man rein auf kombinatorischer Ebene solche Schranken für das Traveling Salesman-Problem ausrechnen. Und die sind ziemlich gut. Also man kommt da bis auf ein, zwei Prozent in aller Regel bei

den praktischen Problemen mit dieser Schranke hin und kann rein kombinatorisch arbeiten. Also da ist ein Beispiel, wo Lagrange auf jeden Fall Sinn macht. Wenn wir das jetzt nochmal vergleichen, angenommen würden LP-Relaxierungen lösen. Das ist der erste Ansatz, zu sagen, lasst

uns die Ganzzeitigkeitsbedingungen rausschmeißen. Können wir überhaupt dieses LP hier lösen? Mit Lagrange haben wir ja gerade gesehen, kriegen wir polynomial hin, Lagrange. Und wir wissen, Lagrange hat einen

Zielfunktionswert, der mindestens so gut ist wie die LP-Relaxierungen. Also kriegen wir hier, und jetzt umgekehrt die Frage, kriegen wir denn wenigstens, wenn ich den anderen Ansatz hier fahre, kriegen wir denn wenigstens die LP-Relaxierungen hier gelöst? Ich habe ein exponentiell großes LP. Ich

habe hier die, hier N-Viele und hier habe ich exponentiell viele. Das heißt, ich kann das Ding maximal höchstens gelöst kriegen, weil ich nicht explizit all diese hier aufführe. Nur dann funktioniert es. Wenn ich die alle einmal aufschreiben muss, habe ich schon ein exponentiell großes LP. Und selbst wenn ich dann das in linearer Zeit lösen

könnte, hätte ich schon verloren. Also ich muss das LP lösen, ohne dass ich explizit alle Ungleichungen auflässt. Geht das? Noch mal zurück in die Einführung der Optimierung. Da haben wir diesen dicken Satz bewiesen, separieren ist gleich

optimieren. Das heißt, wir können, und was hat dieser Satz gesagt? Also ein Optimierungsproblem ist polynomial äquivalent zum Separierungsproblem. Das heißt, ich kann über so ein Problem optimieren, genau dann, wenn ich separieren kann. Also muss ich mir jetzt eigentlich nur überlegen, könnte ich über diesen Problem separieren. Ja, das können wir uns überlegen.

Können wir das? Ja, wir können es. Also die können wir einfach expliziter zunehmen. Das sind innerlinear viele. Da können wir auch einfach separieren. Wir überprüfen alle linear vielen, ob die Gleichung erfüllt ist. Was ist mit denen hier? Das ist nichts anderes als eine Schnittbedingung. Ja, wir müssen nur schauen, ob es einen Schnitt gibt, dessen Wert kleiner ist als zwei. Also

was tun wir? Wir rechnen minimalen Schnitt aus. Wenn der minimale Schnitt kleiner ist als zwei, dann gibt es offensichtlich eine verletzte Ungleichung. Einen verletzten Schnitt, den nehmen wir dazu. Wenn das Minimum größer gleich zwei ist, wissen wir, es gibt keinen verletzten Schnitt. Also haben wir damit, voraussichtlich, wir können einen minimalen Schnitt berechnen, können wir das Separierungsproblem lösen. Und

nachdem wir das Separierungsproblem lösen können, sagt uns der dicke Satz über separieren gleich optimieren. Wir können auch über diesem Linienprogramm optimieren, obwohl es exponentiell viele Ungleichungen gibt. So, minimale Schnitte können wir ausrechnen. Das haben wir uns entweder in graven Algorithmen oder aber auch in der Vorlesung angeguckt. Denn minimale Schnitte, dazu

gehört ein maximaler Fluss. Ein maximaler Fluss, wusste man, die Matrix ist total unimodular. Da kriegen wir automatisch ganzzeige Lösungen geschenkt. Also haben wir damit sozusagen implizit auch ein polynomiales Verfahren, um wenigstens die LP-Relaxierung auszurechnen. Trotzdem ist Lagrange natürlich erstmal mindestens

genauso gut auch. Also da sieht man schon an diesem konkreten Beispiel, dass es viele Varianten gibt, um ganzzeige Programme zu lösen und es nicht immer nur die eine richtige gibt, aber dass man zumindest auch verschiedene oder unterschiedliche Einsicht in so ein Problem braucht, um

überhaupt das beurteilen zu können. Was ist denn ein gutes Verfahren, was nicht? Vielleicht noch als zweites. Ich habe hier als erstes geschrieben. Eine zweite klassische Anwendung von solchen Verfahren sind Matrizen mit Blockstruktur. Also wenn meine Matrix A, meine Nebenbedingung so irgendwie

aussieht. Ja, ich habe hier verschiedene einzelne Blöcke, ziemlich viele. Und dann habe ich hier unten einen größeren Satz von Randbedingungen, der die miteinander verbindet. Also Beispiel mal die Commodity Flow-Probleme. Sie haben Netzwerk. Sie möchten von A

nach B etwas transportieren. Das maximale Flussproblem ist so eins, aber da haben wir nur eine Commodity. Also nehmen wir mal an, in jedem diesem Block gesteckten Flussproblem. Es gibt hier ein S und ein T. Und ich möchte hier möglichst viel von S

nach T transportieren. Jetzt habe ich jetzt vier S1 und T1. Hier habe ich aber ein S2 und ein T2 und so weiter. Und hier habe ich ein SK und ein TK. Ich habe ein und denselben Graphen. Ich möchte gleichzeitig Güter von S1 nach T1 transportieren, von S2 nach T2. Und die dürfen wir nicht miteinander mischen, sondern

ich muss die Commodities voneinander unterscheiden. Aber die müssen natürlich alle durchs gleiche Netzwerk laufen. Das heißt, es gibt für jede Kante eine Kapazitätsbeschränkung, wie viel diese Kante maximal gleichzeitig aufnehmen kann. Also sind diese einzelnen Commodities jeweils über die Kapazität auf dem

Graphen gekoppelt. Und wenn man sich diese Matrix anschaut, dann hat die genauso eine Struktur. So eigentlich könnte man es schnell lösen. Ein Commode, die können wir lösen. Maximales Flussproblem wissen wir, wie wir das schnell lösen. Das Dumme ist nur, dass das hier gekoppelt ist. Na ja, und da bietet sich eben genau Lagrange an. Die Dinge stecken wir hoch in

die Zielfunktion. Dann kriegen wir hier plötzlich unabhängige Probleme, die wir alle hintereinander oder auf einem Parallelrechner gleichzeitig ausrechnen können und können damit dieses komplette, eigentlich riesige Problem, man muss sich mal überlegen. Also nur als Beispiel zu nennen, vor zwei,

drei Jahren kam mal SAP und hat gefragt, ob wir so mal die Commodity Flow Problem lösen könnten für eineinhalb Milliarden Variablen und eine Milliarde Nebenbedingungen. Das war genau von so einem Typ. Wenn Sie sich die großen Distributionscenter angucken wie EDEKA oder REWE, da müssen Sie

Commodities transportieren. Das sind die Commodities hier mit Milchflaschen, Brot und was weiß ich nicht, Eier. Und hier unten haben Sie die Trucks, die LKWs, die zur Verfügung stehen, die auch noch beschränkte Kapazitäten haben. Und die Frage ist, wie packen Sie jetzt die LKWs voll, sodass Sie möglichst viel oder möglichst

kostengünstig, können Sie auch als Minimiumsproblem auffassen, die Dinge transportieren, sodass sie beim Endkunden auftauchen. Wenn Sie mal schauen, so immer ein Großes wie Aldi, REWE oder sonst jemand, wie viele Filialen die rumstehen haben, welcher organisatorischer Aufwand dahinter ist und sozusagen welches Logistikproblem, dann stecken letztendlich solche Probleme dahinter. Und solche

Probleme kann man nur lösen, wenn man sie dekomponiert. Sie schaffen es einfach nicht eineinhalb Milliarden Variablen und Randbedingungen. Allein das Problem einzulösen, brauchen Sie schon mehrere Gigabyte an einer Platte überhaupt, um das einzulösen, geschweige denn, dass Sie das in Ihren RAM oder Cache reinbringen, um überhaupt etwas optimieren zu können. Um solche Dinge, also

wir konnten das Problem nicht lösen, sage ich heute schon, sage ich an der Stelle dazu. Ich habe gesagt, da müssen wir noch ein bisschen warten. Im Millionenbereich trauen wir es uns heute schon zu, aber im Milliardenbereich, so weit sind wir mit den Toten dann doch noch nicht. Also da liegt es irgendwie auf der Hand, Lagrange-Ansatz zu

machen, wenn man so eine Struktur gegeben hat. Gut, soweit zu Lagrange, gibt es da noch, gibt es da noch Fragen dazu. Wenn das nicht der Fall ist, schauen wir uns noch eine Variante, noch zwei Varianten

eigentlich an, die aber sehr ähnlich sind. Eine ist, geht auf Danzig und Wolf zurück, deswegen heißt sie auch Danzig-Wolf, die Komposition und die macht eigentlich,

benutzt die gleiche Idee wie Lagrange, nimmt eine Menge von Landbedingungen raus, nur packt sie nicht in die Zielfunktion, sondern reformuliert sie und steckt sie wieder in das Problem selber rein.

Also Danzig-Wolf, die Komposition ist dann, also erst mal 3-3 ist die Kompositionsmethoden, 3-3-1

ist erst mal Danzig-Wolf, das geht zurück auf ein Paper von den

beiden, muss ich nachgucken, von 1960, also wir schauen uns genau das

gleiche Szenario an wie vorher, wie Lagrange, also minimiere, CTx, a1x kleiner gleich b1, a2x kleiner gleich b2 und x aus z hoch n oder z

hoch n minus p kreuz, r hoch p und andersrum, ich jetzt hier, hier war

das p und hier war das n minus p. Ich fange mal an das Problem zu erklären für p gleich 0, also wir tun erst mal so, als wären keine ganzzahligen Variablen da und schauen uns erst mal das Prinzip an und dann überlegen wir uns was geht an dem Vorgehen schief, wenn wir plötzlich ganzzahlige

Variablen dabei haben. So, jetzt haben wir immer, also genau das gleiche, so hier, wir nehmen uns diesen Teil hier her, wir nehmen einen Teil raus, wir wissen ja, dieser Teil für sich beschreibt uns auch wieder ein Polyeder, also wir können, wir wissen,

nennen wir das wieder p2, ist die Menge aller x mit a2x kleiner gleich b2 ist ein Polyeder. Von diesem Polyeder wissen wir, wir können das schreiben als Konvexel Hülle von einer Menge von, von einer endlichen Menge

von Vektoren plus einer chronischen Kombination, ebenfalls einer endlichen Menge. So, wenn das Polyeder eine Ecke hat, dann sind das genau die Ecken, wenn es nicht, sind es halt entsprechend Punkte auf dem

minimalen Seitenflächen. Also der Einfachheithalter sagen wir, ist die konvexel Kombination der Ecken plus die chronische Kombination der Extremalen. So, also das heißt, wenn wir uns das hier anschauen, jedes x, was das erfüllt, lässt sich so beschreiben. Also ich kann jetzt einfach schreiben, x aus p2, kann ich

schreiben, x ist nichts anderes als die Summe Landa i V i plus Summe Nü j E j. Und ich fordere noch, dass die Summe der Landa i gleich eins ist. Damit habe ich das hier modelliert. So, und jetzt setze ich

das hier wieder da ein. So, was kriegen wir dann? Also hier eingesetzt, kriegen wir folgendes Minimiere. So, ct setzt jetzt

einfach für das x das hier ein, Summe Landa i V i plus Summe Nü j E j. Unter der Nebenbedingung a1 soll jetzt wieder das gleiche hier, kleiner gleich b1. Und das Einzige, was ich mir noch eingehandelt habe,

ist, dass die Summe der Landa i gleich eins ist. So, und Landa und Landa und das Nü, beide müssen größer gleich Nü sein. So, und wenn

wir das jetzt umschreiben, das können wir ein bisschen anders schreiben. Schreiben wir das jetzt mal in unseren Variablen. Was sind jetzt unsere neuen Variablen? Die Variablen des x ist jetzt verschwunden. Unsere Variablen sind jetzt das Landa und das Nü. Das

und das. Das sind jetzt unsere Variablen. So, das heißt, wenn wir das jetzt mal aus Sicht unserer Variablen schreiben, was kriegen wir dann? Schreiben wir das da vollständigkeit halber hin. Dann kriegen wir hier Summe ct V i mal

Landa i plus Summe ct E j mal Nü j. Und wir haben als Randbedingung Summe so a 1.

V i mal λ i plus Summe a 1 e j mal nu j kleiner gleich b 1 und wir haben immer noch Summe der λ i gleich 1. So, wenn wir die beiden jetzt mal

vergleichen, also wir haben nichts gemacht außer umformuliert bislang, hier ist unser Originalproblem jetzt mit x aus R hoch N und das ist unser

Alternativmodell. Welches finden Sie sympathischer? Welches von beiden würden

Sie versuchen zu lösen? Also wäre es für die linke Seite 1, 2, wäre es für die

oder gibt es Vor- oder Nachteile für das eine oder andere? Die kennen wir nicht, das ist richtig. Nehmen wir mal an, wir würden sie kennen oder wir könnten sie einfach

bestimmen, nicht unbedingt kennen. Also was könnte überhaupt ein Vorteil sein rechts? Also bislang haben wir ja immer über die Seite diskutiert, wenn man

Einführung, Optimierung haben wir nur in dieser Welt diskutiert. Warum sollte es überhaupt Sinn machen, jetzt auf diese rechte Seite zu gucken? Richtig, ja die haben wir aber hier jetzt auch erstmal weggelassen. Bislang sind wir ja noch nicht, also im Moment habe ich ja gesagt P soll gleich Null sein, also im

Moment sind wir auch hier im R hoch N. Also jetzt erstmal für die Diskussion. Wenn du das andere dann reinbringst, sehen wir gleich noch. Also müssen wir ein bisschen die Analyse geben, angenommen würden wir das jetzt mit dem

Simplex-Verfahren lösen wollen. Was wäre denn der Vorteil hier drüben? Also wenn wir mal schauen, was sind denn die teuren Schritte beim Simplex-Verfahren? Da müssen wir eigentlich, der erste Schritt ist ein Gleichungssystem lösen, dieses b dran. Da müssen wir ausrechnen, y transponiert, y transponiert

ab gleich cb transponiert. Da müssen wir ein Gleichungssystem lösen, dann machen wir so eine Minimumsbildung über das Pricing. Also gucken, gibt es denn nicht Basisvariable, die vielleicht noch attraktiv sein können? Also rechnen wir erstmal die reduzierten Kosten aus. Dann schauen wir, ob da eine

noch negativ ist von denen. Und wenn wir jetzt eine solche haben, dann müssen wir sozusagen den Basisaustausch machen. Da müssen wir wieder ein Gleichungssystem lösen und das Minimum und Minimumsbildung. Das ist eigentlich alles. Was jetzt beim Simplex drin steht, ist einmal, zweimal ein Gleichungssystem lösen, einmal Minimum bilden und ja, das war's

eigentlich. Und das Pricing ist eigentlich auch nur Matrix mal Vector. Das heißt, die teuren Operationen im Simplex-Verfahren sind diese Gleichungssysteme lösen. Zweimal ein Gleichungssystem lösen. So und wenn man überlegt, Gleichungssystem lösen hängt ab, eigentlich im schlimmsten

Fall ist es Kubisch oder 1 hoch 2 plus, ich weiß nicht, was gerade die beste Schranke ist, um Gleichungssysteme zu lösen. Aber ich sage mal, im Normalfall, wenn wir eine Chaos-Elimination machen, hat man da ein N hoch 3 Algorithmus drin, wenn man es ungeschickt macht. Das heißt, N hoch 3, Anzahl der Nebenbedingungen. So und jetzt kommt der erste

Vorteil. Hier haben wir einen ganzen Packen rausgeschmissen. Wir leben nur noch in der A1-Welt. Also hier haben wir noch als Randbedingungen, hier haben wir ein M1 und hier haben wir ein M2. Und das haben wir hier drüben

reduziert auf ein M1 plus eine 1. Das heißt, die Anzahl Randbedingungen haben wir, je nachdem, jetzt haben wir natürlich wieder die gleiche Problematik, je mehr ich hier rausschmeiße, umso kleiner wird mein System hier drüben. Das heißt, umso schneller wird vermutlich mein

Simplex-Verfahren laufen. Nachteil allerdings, ich handle mir hier neue Probleme ein, nämlich es kann sein, ich kriege enorm viele Zeilen und Spalten, enorm viele Spalten. Das einfachste Beispiel ist immer der Würfel. Wenn ich hier angenommen, mein M2 wäre ein Würfel, da steht nur

0 kleiner gleich x kleiner gleich 1. Wie viele VIs kriege ich denn da drüben? Jeder 0,1 Vektor ist einer. Das heißt, ich kriege exponentiell viele VIs da

drüben. Das heißt, aus eigentlichen linear vielen Ungleichungen kriege ich plötzlich drüben exponentiell viele Variablen. Es kann aber auch der umgekehrte Fall sein. Exponentiell viel hier kann, wenn ich mir das Kreuz-Politop anschaue als Beispiel, dann ist es so, dass ich

exponentiell viele Randbedingungen habe und aber nur polynomial viele oder linear viele Ecken. Also da ist in beiden Richtungen möglich, aber im Allgemeinen, wenn man von dieser Formulierung ausgeht, ist es tendenziell schon so, dann hat man hier eine kompakte Formulierung und die

Anzahl Ecken kann dann potenziell, tatsächlich exponentiell wachsen. Die Frage ist, ist es wirklich schlimm, dass die Anzahl Ecken exponentiell wachsen kann? Exponentiell an sich holt uns es nicht vom Stuhl in der diskreten Optimierung oder

kombinatorischen Optimierung. Da haben wir ständig mit exponentiellen Größen zu tun. Für uns ist ja nur entscheidend, ob man über diese exponentiellen Größen in vernünftiger Zeit optimieren können. Also gerade hat man es ja auch bei Lagrange, da standen zwar exponentiell viele Schnitte, aber das hat uns eigentlich nicht gejuckt, weil minimalen Schnitt können wir

in polynomialer Zeit ausrechnen, also können wir auch über diese exponentiellen Klasse von Ungleichungen separieren und damit auch optimieren. Also erstmal die Tatsache, dass es exponentiell viele gibt, die macht uns das Leben noch nicht schwer und deshalb steckt da drin jetzt auch wieder ein Kern für einen vernünftigen Ansatz, weil was wir jetzt

hier wieder genauso machen können, wir müssen ja diese Variable nicht alle explizit auf einmal modellieren und formulieren und dann einen riesen LP aufstellen, sondern es reicht ja, wenn wir die sozusagen wieder on demand berechnen können. Und wenn wir nochmal in Simplex-Verfahren gucken, wo

brauchen wir denn wirklich nur alle Spalten? Die brauchen wir nur beim Pricing. Am Anfang haben wir gerade gesagt, wir lösen ein Gleichungssystem, dann müssen wir die reduzierten Kosten überprüfen der Nichtbasisvariabeln, das ist genau der Schritt. Wir müssen die reduzierten Kosten aller Nichtbasisvariabeln,

das können hier viele sein. Und wenn es keine Spalte gibt mit negativen reduzierten Kosten, dann wissen wir, wir haben die optimal Lösung gefunden. Und wenn es so eine gibt, dann nehmen wir genau die eine rein, lösen wieder ein Gleichungssystem, machen den Basisaustausch

und iterieren. Das heißt, wir brauchen nur genau an dieser einen Stelle, dass beim Pricing müssen wir über alle Spalten gehen. Und wenn wir das wieder als Optimierungsproblem formulieren können, was vielleicht sogar in polynomialer Zeit lösbar ist, dann sind wir wieder im Geschäft. Und genau das funktioniert in dem Fall. Und das schauen wir uns jetzt mal an, wie das

geht. Also ich schreibe dazu vielleicht, dieses Problem, was wir hier haben, schreibe ich mal in Kurzform. Also nennen wir das hier mal Stern. Stern in Kurzform.

Lässt sich das so schreiben, minimiere Omega mal Eta unter der Randbedingung

D gleich D und das Eta soll größer gleich Null sein. In dem Eta habe ich jetzt die Landas und die Nüs versteckt und in dem D habe ich das a1vi und

die a1ej versteckt. So und wie schon gesagt, hier im Simplex, die Basismatrix hat hier eine Größe von m1 plus 1 in dem System, wenn sie hier noch die Größe m1 plus m2 hat. So wie sieht jetzt das Pricing aus?

Also schauen wir uns das mal an. Wie sieht das Pricing aus in dem System hier? Also Pricing, sprich Bestimmung der reduzierten Kosten.

Die bestimmen sich wie folgt. Das ist dann über die nicht basisvariablen Minus. Ich schreibe sie hin. Y-Schlange transponiert dN mit einem Y-Schlange kleiner gleich Null und das Y-Schlange ist genau die Lösung des

Gleichungssystems mit Y-Schlange transponiert dB gleich Omega B. Nur zur Erinnerung, das war genau der erste Schritt im Simplex- Be-B dran, wo wir das Y ausrechnen. Das setzen wir dann hier ein, um die

reduzierten Kosten auszurechnen. Wenn die alle größer gleich Null sind, wissen wir, sind optimal. So das Ding kriegen wir jetzt einfacher als dort, weil das System ist nur Größe m1 plus 1. Also das kriegen wir deutlich schneller als noch hier. So bleibt die Frage, können wir das hier ausrechnen?

Können wir entscheiden, ob dieser Vektor größer gleich Null ist oder kleiner gleich Null? Was müssen wir dazu tun? Dazu müssen wir eigentlich nur über diesem System hier rechnen. Aber jetzt gucken wir wieder in die normale Darstellung.

Also um das auszurechnen, nehmen wir jetzt nicht diese Darstellung, sondern gehen wir wieder zurück und nehmen die. Also zur Berechnung, also zur eigentlich Berechnung, zur Bestimmung, zur Entscheidung, ob dieser

Vektor hier, Omega N minus Y Schlange transponiert D N größer gleich Null,

gilt Bestimme zur Minimiere. Ich schreibe das erstmal hin. CT minus Y quer A 1 X

unter der Randbedingung A 2 X ist kleiner gleich B 2 X aus dem A hoch N.

So warum? Warum reicht das? Schauen wir uns das mal an, was passiert denn hier, wenn wir das ausrechnen. Nehmen wir mal den einfachen Fall an, alles ist beschränkt, wir haben da ein Politop stehen, dann wissen wir, wenn wir ein

Optimallösung immer an der Ecke angenommen. Das heißt, wenn wir dieses LP lösen, kriegen wir eine Optimallösung, die zu einer Ecke gehört. Naja, das muss aber offensichtlich einer von diesen VIs sein.

So haben wir es ja gerade geschrieben. P 2, wir optimieren hier genau über P 2. Die Konvexhöhe der Ecken plus der chronische Kombination der Extremalen. Also wir kriegen automatisch eine Ecke damit geschenkt. Es muss jetzt nicht endlich sein, das Ding hier. Es kann auch unbeschränkt sein.

Wenn es unbeschränkt ist, dann kriegen wir halt genau so ein E. So und das ist ein lineares Programm. Lineare Programme können wir in polynomialer Zeit lösen, wissen wir. Also können wir übersetzen, wenn diese Größe hier, die VJs und die EJs und die VIs alle exponentielle Größe haben, wir

können in polynomialer Zeit einen von denen bestimmen. Und mehr brauchen wir ja nicht. Und was jetzt noch dazukommt, dieses lineare Programm ist auch noch deutlich kleiner. Also dieses lineare Programm kriegen wir deutlich schneller gelöst als das. Da fehlen ja die ganzen a 1 x kleiner

B 1 Bedingungen. Okay. Also und damit ist eigentlich das Verfahren, jetzt können wir es noch genau auswerten. Also die drei Fälle, die passieren können, dass wir da tatsächlich dann einkriegen mit negativen reduzierten Kosten. Aber das ist, das ist irgendwo offensichtlich, dass dem so ist.

Aber schauen wir uns mal, also werten wir das mal aus. Also sei x Schlange optimal Lösung von diesem Problem. So was kann passieren? Also im Moment,

Schmarrn, das war Quatsch. Das ist der erste Fall. Ja, es kann ja sein, das Ding ist unbeschränkt. Also erster Fall, es gibt eine endliche Optimallösung. So was, was gilt dann mit, also mit der, mit der

Bedingung, dass dies, dass die Z-Funktion negativ ist, also c t minus y quer a 1 x quer ist kleiner 0. So was gilt dann für unsere reduzierten

Kosten? Ja, schauen wir uns das mal hier an. Also dieses x Schlange gehört zu einem V i, ja, weil x, dieses x Schlange ist eine

Optimallösung, damit muss es eine optimale Ecklösung sein und damit muss das x Schlange 1 von diesen V i sein. Und wenn wir jetzt die reduzierten Kosten genau für, für dieses V i hier anschauen, was steht dann da, für diese Komponente W i minus y quer transponiert. D Punkt i

ist da nichts anderes als, so jetzt schauen wir uns, ich schreibe es minus y transponiert a 1 V i 1. So, warum ist das der Fall? Schauen wir

uns das nochmal an. Wo haben wir unsere abkürzende Schreibweise? Hier. So, das muss eins von diesen V i sein. Wie sehen die V i aus? Die sehen genau so aus. Da steht hier a 1 V i und an dieser Stelle steht noch die 1. Das ist die 1, was zum Lambda gehört. Das ist genau dieses D i und

das W i, die Zielfunktion, ist ja nichts anderes als das entsprechende C T V i, was hier steht. Das ist genau das. So, wenn wir das jetzt hier ausrechnen, dann kriegen wir da raus, das ist C T V i minus y

quer transponiert a 1 V i minus y quer und jetzt die M plus, M 1 plus erste Komponente. Und wenn wir uns das hier angucken, habe ich das jetzt falsch gemacht, hier oben habe ich es falsch gemacht, nicht kleiner Null,

sondern kleiner diesen Y M 1 plus 1 quer, was diese, was dieser Lösung entspricht, wobei die Quers alle Schlange sein sollen, Entschuldigung, also diese Y, das sind natürlich genau das hier drüben, die Lösung von dem

Ding hier. So, und damit angenommen, wir haben eine optimale Lösung mit dieser Eigenschaft, dann heißt dieser Vektor ist kleiner Null. So und

damit haben wir, also wir lösen das Ding, wir kriegen eine endlich optimale Lösung, die diese Eigenschaft hat, wenn sie die hat, dann kriegen wir sofort eine Nichtbasisvariable in dem System, dessen reduzierte Kosten

negativ sind und die Spalte nehmen wir dann dazu. So und jetzt gibt es noch den zweiten Fall und den dritten und dann haben wir es eigentlich vollständig analysiert. So bleibt noch, bleibt noch als Überbleib sozusagen der

zweite Fall, das Ding ist unbeschränkt, also dieses Problem ist unbeschränkt, also jetzt habe ich leider keinen Mager gesetzt, also ich schreibe

mal so kurz, rechts oben, ist unbeschränkt, dann muss dazu ein E Stern, dann gehört dazu ein EJ, existiert dieses EJ, was wir auch

ausrechnen mit, CT minus Y Schlange transponiert A1, E Stern, EJ ist ein kleiner Null. Also erst mal es gibt einen Extremalstrahl oder ein

Extremale, so dass sozusagen, wenn ich mir das anschaue, die Zielfunktion ich beliebig verbessern kann, nachdem die alle Extremalstrahlen ich in meiner Menge EJ habe, muss eins von diesen EJ auch diese Bedingungen erfüllen. So und genau dieses muss dieses sein, die Spalte, die dazu gehört in

unserem System sieht dann so aus, also wenn ich die negativen, wenn ich die reduzierten Kosten anschaue, minus DK plus eins an dieser Stelle, ist dann nichts anderes als CT EJ minus Y Schlange transponiert A1, jetzt steht

hier an dieser Stelle eine Null, weil in unserem Problem, was wir zusätzlich hatten, stand ja sozusagen nur Summe lambda i gleich eins über die Ny J hat man keine zusätzlichen Einschränkungen mehr, ja und wenn wir das auflösen, ist es dann CT EJ minus Y Schlange transponiert A1, EJ und das

Ding hier ist echt kleiner Null nach dieser Bedingung, damit wissen wir, haben auch in dem Fall eine Spalte gefunden mit negativen reduzierten Kosten und können die entsprechend dazu nehmen. So und im dritten Fall, das Ding ist praktisch die selbe Rechnung wie hier, also der dritte Fall

hat optimal Lösung mit genau diesem Wert, was hier rechts steht, größer gleich, also mit CT minus Y Schlange A1, X Schlange ist größer gleich Y

M1 plus 1 Schlange, ja dann wissen wir daraus folgt Stern ist optimal. Warum?

Weil wenn weder der erste Fall noch dieser Fall zutrifft, dann können wir mit dieser Aussage wissen wir sofort alle reduzierten Kosten sind nicht negativ und dann wissen wir nach dem Simplex-Fahren oder nach dem Dualitätssatz, dass dieses lineare Programm hier optimal

gewesen ist, optimalität hat. So und wenn wir uns das jetzt nochmal anschauen, wenn wir uns das gesamte Verfahren nochmal anschauen, wir haben einmal das ursprüngliche Problem, wenn man das mal vergleichen ist, wir

müssen, das Originalproblem löst immer ein Problem M1 plus M2 Brandbedingungen, dann wenn ich jetzt vergleiche mit Danzig-Wulf, was auch Danzig-Wulf, Danzig-Wulf hat ein Problem, was nur M1 viele Brandbedingungen hat, dafür aber sozusagen das Pricing-Verfahren etwas teurer ist, was

heißt teurer, jedes diese Pricing-Auswertung bedarf des Lösen eines linearen Programms, was hier rechts oben an der Tafel steht. Dieses lineare Programm ist aber wieder kleiner als das Originalproblem, nämlich hat nur M2 viele Brandbedingungen und somit haben wir

sozusagen unser Gesamtproblem reduziert von entweder ständig lösen oder berechnen von Gleichungssystemen der Größe M1 plus M2 auf ein Problem des iterativen Lösens der Größe M1 und M2. Und unter dem Aspekt, wenn wir das mal sehen, dass das Lösen von Gleichungssystem der teure Anteil ist,

kann es an verschiedenen Stellen durchaus Sinn machen, diesen der Kompositionsansatz zu wählen. Es zeigt sich nur, dass lineare Programme, also bislang haben wir den Fall ja nur für lineare Programme angeguckt. Für lineare Programme ist es nicht ganz so essentiell, weil lineare Programme können heute oft mal sogar im Minusbereich mit mehreren

hunderttausenden oder Millionen von Brandbedingungen gelöst werden. Dort noch mal zu dekomponieren macht häufig wenig Sinn, wobei man das in den 60er, 70ern doch häufiger gemacht hat, weil damals konnte man große lineare Programme noch nicht lösen. Heute ist natürlich dieser Ansatz relevant, wenn man Ganztaglichkeitsbedingungen dabei haben und ob

man diesen Ansatz so übertragen können auf Ganztaglichkeitsbedingungen, das schauen wir uns dann am Mittwoch an. Vielen Dank.