Optimierung 1 Übungsblatt 4 Laurent Pfeiffer, Universität Graz 15. April 2016 N.B. Die Aufgaben 4 und 5 vom Blatt 3 sind wieder ankreuzbar. Aufgabe 1 (Simplex-Algorithmus). Lösen Sie das folgende Problem mit dem Simplex-Algorithmus:    −x1 + x2 + x3 = 1 x ≥ 0. min −2x1 − x2 , u.d.N. x1 + x2 + x4 = 3  x∈R5  2x1 − x2 + x5 = 3, Beweisen Sie auch, dass die zulässige Menge beschränkt ist. Aufgabe 2 (Simplex-Algorithmus). 1. Seien A ∈ Rm×n und b ∈ Rm , b ≥ 0. Wir betrachten n die Menge M = {x ∈ R | Ax = b, x ≥ 0}. Zeigen Sie die folgende Äquivalenz: ⊤ M ist nicht leer ⇐⇒ inf e y, u.d.N. Ax + y = b, x ≥ 0, y ≥ 0 = 0, n m x∈R , y∈R wobei e = [1, ..., 1]⊤ ∈ Rm . 2. Zeigen Sie mit Hilfe des Simplex-Algorithmus, dass die folgende Menge nicht leer ist: {x ∈ R3 | x1 + x2 + x3 = 2, 2x1 − 2x2 − x3 = −1, x ≥ 0}. Aufgabe 3 (Anwendungsproblem). |x| = inf (y1 ,y2 )∈R2 1. Zeigen Sie, dass für alle x ∈ R gilt: y1 + y2 , u.d.N. x = y1 − y2 , y1 ≥ 0, y2 ≥ 0. 2. Ein Signal, das aus N reellen nicht-negativen Zahlen besteht wird gemessen. Wir bezeichnen mit y = [y1 , ..., yN ]⊤ die Messungen. Da die Messungen unpräzise sind, muss das Signal entrauscht werden. Zu diesem Zweck kann man das folgende Problem lösen: min x∈RN N X i=1 |xi − yi | + α N −1 X |xi+1 − xi |, u.d.N.x ≥ 0, i=1 P PN −1 wobei α > 0. Erkären Sie die Rolle der Terme N i=1 |xi − yi | und i=1 |xi+1 − xi |. Bringen Sie das Problem auf ein lineares Problem in kanonischer Form (gemäss der Definition der Aufgabe 2.2) und beweisen Sie, dass eine optimale Lösung existiert. 3. Ein Schwarz-Weiss Foto besteht aus N × M Zahlen yij in [0, 1]. Man kann das folgende Problem lösen: min x∈RNM N M X X i=1 j=1 N M −1 X −1 M N i hX X X |xi+1,j − xi,j | , |xi,j+1 − xi,j | + |xi,j − yi,j | + α i=1 j=1 u.d.N. 0 ≤ x ≤ 1, 1 i=1 j=1 um das Foto zu entrauschen. Bringen Sie das Problem auf ein lineares Problem in kanonischer Form. Die Koordinaten müssen auf folgende Weise zugeordnet werden: ⊤ x = x1,1 , x2,1 , ..., xM,1 , x1,2 , x2,2 , ..., xM,2 , ..., x1,N , x2,N , ..., xM,N . 2