In den Übungen haben Sie in den letzten Wochen einige verschiedene Algorithmen kennengelernt, die Probleme auf die ein oder andere Art via Divide & Conquer in kleinere Teile zerlegen und damit lösen. Hier betrachten wir nun ein Beispiel für ein Problem, für das sich nur schwer eine systematische Lösung finden, aber das sich dafür recht einfach mit numerischer Optimierung lösen lässt. Sie haben in der Vorlesung kurz Optimierungsprobleme kennen gelernt und sollen nun Ihr erstes Optimierungsproblem auf naive Art und Weise lösen.

Gegeben ist eine Liste von n Punkten, repräsentiert als Tupel (xi, yi) R2, i ∈ {0, . . . , n 1}. Wir möchten nun die Gerade finden, die diese Punkte am besten beschreibt. Um dies zu errei- chen versuchen wir –wie in Optimierungsproblemen üblich– die sogenannte Kostenfunktion“ zu optimieren. Die Kostenfunktion ermöglicht es verschiedene Lösungen bezüglich ihrer Güte zu vergleichen. Für unser Problem wählen wir als Kostenfunktion die aufsummierte Abweichung der Punkte von der betrachteten Geraden y = mx + b. Findet man eine Gerade, für die die Abweichung bzw. die Kostenfunktion minimal ist, so hat man die Gerade gefunden, die die Punkte am besten beschreibt. 

1. Schreiben Sie ein Unterprogramm cost_function(a,m,b), dem eine Liste a von n Tupeln und die Parameter der betrachteten Geraden m und b übergeben werden und das die Kostenfunktion folgendermaßen berechnet und zurück gibt:

          ∑i=0n-1    |(mxi + b) yi|

2. Schreiben Sie ein Unterprogramm regression(a,m,b), das die Kostenfunktion minimiert, indem mit den übergebenen Werten m und b gestartet wird und dann in jedem Schritt abwechselnd m und b jeweils um 0,01 erhöht oder verringert werden, sodass die Kos- tenfunktion in jedem Schritt kleiner wird. Führen Sie das so lange durch, bis sich die Kostenfunktion nicht mehr verringern lässt und geben Sie dann m,b als Tupel zurück. Führen Sie die Optimierung für

[(0 , -0.302287) ,  (1 ,0.48864), (2 ,2.56601), (3,4.42318),  (4,2.57443),  (5, 4.38737), (6 ,5.71113), (7 ,7.58872) , (8 ,7.55638),  (9 ,9.48674)]

 mit den Startwerten m = 0, b = 1 durch und geben Sie das Ergebnis auf der Konsole aus.

Scaffold Head
Scaffold Foot
Start time:
Do 18 Jan 2018 14:00:03
End time:
Do 25 Jan 2018 14:00:03
General test timeout:
30.0 seconds

Tests

Comment prefix #
Given input
0, 1
2, 1
1, 0.5
1, -0.14
Expected output
38.1
55.5
7.7
6.4
#(0.8, 0.7)
#(0.9, -0.06)
#(0.8, 0.3)
#(0.9, -0.1)