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

In der jetzigen Vorlesung geht es um etwas, was wir hatten und zwar über die Anzahl

der Augmentierungsschritte bis zum Optimum. Und da haben wir ja gesehen, wenn wir diesen

Graver-Best-Verbesserungsschritt suchen, dann brauchen wir nur polynomial viele Schritte.

Das hat uns dann geholfen für dieses n-fache IP, da ein polynomialer Algorithmus jetzt entfiegt.

So, jetzt machen wir was anderes. Jetzt machen wir einen steilsten Abstieg.

Und wir machen es uns einfach. Wir gucken uns ein lineares, ganz steiliges Optimierungsproblem an.

Also minimiere C transponiert Z, A Z gleich B.

Zu viel Schreibarbeit. Also einfach nur nicht Negativität. Das aber auch für

unteren Oberschranken gehen. Weil die Graver-Base da ja ein Optimum ist.

Weil die Graver-Base dafür ein Optimitätszertifikat ist, könnte man eigentlich auch unteren Oberschranken

annehmen. Aber sparen wir jetzt das hier mal. Gut, also wir haben jetzt ein Optimierungsproblem

und normalerweise starten wir von der Lösung Z0, Z1 und so weiter, bis wir irgendwann mal zu Zmin kommen.

Und wir addieren da alpha 1, g1, alpha 2, g2 und so weiter. Addieren wir hier drauf.

Und kommen von einem Punkt zum nächsten. Und die Frage ist, wie finden wir diesen Punkt?

Den einen haben wir gehabt, den Graver-Best. Also die Kombination alpha g, die den meisten

Fortschritt macht. Und jetzt wollen wir aber steilster Abstieg machen.

Steilster Abstieg unter allen, machen T aus dem ganzteiligen Kern

von A, wähle ein T. Wir sind noch nicht in der Graver-Base, da kommen wir gleich noch hin.

Unter allen T aus dem Kern, wähle ein T mit Z0 plus T. Z0 plus T ist gültig.

Und der Fortschritt, den T macht, das sollte erst mal,

das heißt also C transponiert, T sollte kleiner 0 sein.

Mit dem Minus ist es jetzt größer 0. Und wir wählen den, der den meisten Fortschritt macht,

in Bezug auf seine 1-Norm.

Wir wählen wirklich hier einen steilsten Abstieg, aber nicht bezüglich der ökidischen Norm,

sondern bezüglich der L1-Norm, der Manhattan-Metri.

So, ja dann ist es schlecht. Wir können aus diesen ganz vielen Vektoren,

können wir schlecht auswählen. Deswegen wäre hier mal eine kleine Übungsaufgabe fällig.

Fakt, das ist Übungsaufgabe 17. Gar nicht so schwer.

Unter allen steilsten Abstiegsrichtungen, da muss es ja nicht nur eine geben,

existiert auch eine aus G von A.

Das heißt wir brauchen gar nicht außerhalb der Grave Up Basis schauen.

Wenn wir die insgesamt steilste Abstiegsrichtung wählen wollen,

dann brauchen wir nur eine der Grave Up Basis suchen, da ist eine drin.

Es gibt vielleicht auch noch andere, aber in der Grave Up Basis gibt es eine, die ist drin.

Genauso steil wie die steilste, die es maximal gibt.

So, aber wie könnten wir das beweisen?

Muss ich vorstellen.

Ich bin hier in Z0.

Ich kann jetzt Z0 plus T hingehen. Ich bin gültig hier und das ist wirklich so steil wie fast nirgendwo anders.

Wie können wir zeigen, dass es dann noch in der Grave Up Basis ist?

Wie können wir zeigen, dass es dann auch ein Grave Up Basis Element gibt,

das ich anwenden kann, gültig bleibe, aber genauso steil ist?

So, 5 Minuten zu überlegen.

Einfach nur mal brainstorming.

Mittlerweile solltet ihr ein paar Fakten wissen über Grave Up Basis, Repräsentationseigenschaft und mehr gibt es eigentlich nicht.

Ich hätte mal gesagt, dass die Repräsentationseigenschaft genau das ist, was die Grave Up Basis so stark macht.

Das heißt, nutzt die Repräsentationseigenschaft irgendwo aus.

Und das zweite, was es gibt, ist wir haben ein lineares Optimierungsproblem mit linearen Nebenbedingungen.

Belegt mal, wie ihr anfangen könntet.