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

Wir haben gesehen, dass für diese n-fachen IPs diese Grave-up-Basen nicht komplizierter werden.

Sie werden zwar größer, die Vektoren werden länger, aber was wir jetzt eigentlich nachgewiesen

haben ist, dass die Einsnorm, die Einsnorm eines Element aus der Grave-up-Basis von A, B, N,

die ist beschränkt, wodurch? Durch konstant viele Blöcke. Diese konstant vielen Blöcke,

die kommen alle aus der Grave-up-Basis, das sind also konstant viele Möglichkeiten,

wenn A und B konstant sind. Wir haben also eigentlich nichts anderes nachgewiesen,

dass die Einsnorm von Z beschränkt ist durch eine Konstante.

Jeder Vektor hat konstant viele, nicht null. Blöcke und diese Blöcke sind entweder selber

Grave-up-Basis-Elemente von A oder ich kann sie als Grave-up-Basis-Elemente von A

als Summe auseinanderziehen und die sind auch wieder selbst konstant. Das impliziert halt,

dass ich aus der Grave-up-Basis A, B, Grave-Komplexität von A, B, kann ich also die Grave-up-Basis von A, B,

hoch N konstruieren und die hat jetzt O von groß N über G von A, B, mal die Größe der Grave-up-Basis

von A, B, hoch G, A, B. So viele Elemente hat die höchstens. Aus jedem Element hier drin kann ich

durch Einfügen von entsprechend vielen Nullen höchstens so viele Elemente da länger groß N machen

und das ist halt O von N hoch G von A, B. Das hier hinten sieht gigantisch aus, ist bestimmt auch

gigantisch, ist aber letztendlich nur konstanter, wenn A und B konstant sind. Das ist also jetzt für

A, B konstant prolinomiell den N und demzufolge sind N-Fache, separabel-Kondekse

ganz zahlige Minimierungsprobleme

in polynomierter Zeit lösbar.

Das ist schon mal super und wir werden uns jetzt das Gleiche mal anschauen für Matrizen,

die jetzt eine andere Gestalt haben. Da haben wir jetzt eine Matrix W, die auf der Diagonal ist und

die Verbindung ist nicht horizontal, sondern vertikal. Gut, weiß jemand wo solche Matrizen vorkommen von

dieser Gestalt? Der Rest ist Null. Sie kommen vor bei der zweistufigen stochastischen Optimierung.

Ich will jetzt nicht so detailliert drauf eingehen, aber jetzt will ich die Grundidee erzählen.

So zweistufig heißt, ich habe hier eine erste Entscheidung zu treffen.

Ich will vielleicht ein Produkt verkaufen und habe die Möglichkeit, dass ich jetzt verschiedene

Shops öffnen kann. Wo positioniere ich die Shops? Dann haben wir hier so ein großes Fragezeichen.

Da gibt es ein zufälliges Ereignis. Das zufällige Ereignis könnte in dem Fall jetzt für das Beispiel sein,

ich kenne den Bedarf nicht. Den Bedarf, die Nachfrage sehe ich erst, wenn ich die Shops

irgendwo aufgemacht habe. Wenn ich das dann gesehen habe, kann ich im zweiten Schritt eine zweite

sogenannte Korrekturentscheidung treffen. Was habe ich jetzt hier? Ich habe jetzt hier sofort Kosten

für die erste Stufe. Ich habe dann Kosten später für die zweite Stufe, aber ich kann noch gar nicht

genau sagen, welche Kosten ich haben werde, weil ich ja gar nicht weiß, was diese zufällige Ereignis so macht.

Wenn ich nichts über dieses zufällige Ereignis weiß, also wirklich absolut nichts, dann kann ich

auch praktisch nichts Sinnvolles tun. Da gibt es verschiedene Ansätze, wenn ich doch ein bisschen

was weiß, man könnte robuste Optimierung machen, sich quasi gegen den schlimmstmöglichen Fall

hier wären oder gegen alle möglichen Fälle hier sozusagen wären und zweiter wäre, nehmen wir an,

ich hätte für dieses zufällige Ereignis irgendeine Verteilungsfunktion. Also ich wüsste irgendwas,

ich weiß, was passieren könnte oder auch so prima da mit welcher Wahrscheinlichkeit. Jetzt wissen,

eine gewisse Verteilungsfunktion über mögliche Ereignisse.

So, damit könnte ich jetzt zum Beispiel Folgendes machen, ich schiebe das dann gleich dann über die

andere Tafel. Also so einen Erwartungswertansatz, dass ich jetzt minimiere die sofortigen Kosten,

Kosten für die erste Entscheidung und dann plus die erwarteten Kosten für die zweite Entscheidung.

Das ist jetzt schon mal ein ordentlich gestelltes Optimierungsproblem, weil ich auch genau jetzt

sagen kann, ob ich so eine erste Entscheidung überhaupt treffen kann. Weil ich kann so eine

erste Entscheidung nur treffen, wenn ich dann auch für alle Ereignisse, die auftauchen könnte,

eine zweite treffen könnte. Also alles andere sollte ich gar nicht als erste zulassen und ja,

wie könnte das jetzt mal so in Zahlen, aber halt konkreter aussehen, könnte also aussehen,

wir wollen also minimieren die Kosten unserer Erststufenentscheidung x plus die erwarteten Kosten