GRADIEN DESCENT
(Metode Optimasi)
PENDAHULUAN
Gradient merupakan nilai kemiringan atau kecondongan suatu garis yang
membandingkan antara komponen y (ordinat) dengan komponen x
(absis).
Gradient disini merupakan nilai kemiringan suatu fungsi, yaitu tingkat
perubahan parameter terhadap jumlah parameter lain.
Secara matematis, gradient dapat digambarkan sebagai turunan parsial
dari serangkaian parameter terhadap inputnya.
Semakin besar gradient maka semakin curam lerengnya
METODE STEEPEST ASCENT /DESCENT
Merupakan jenis metode gradien yang paling sederhana.
Terminologi:
o steepest ascent untuk pencarian maksimum fungsi
o steepest descent untuk pencarian minimum fungsi
Prinsip pencarian optimum:
Dilakukan serangkaian proses transformasi untuk mengubah sebuah
fungsi dengan banyak variabel (multi-dimensional function) menjadi
sebuah fungsi dengan variabel tunggal (one-dimensional function),
berdasarkan gradien arah pencarian.
Langkah pencarian optimum ini selanjutnya dilakukan secara
berulang-ulang (iteratif), hingga diperoleh tingkat konvergensi yang
diinginkan.
Gradient descent (ascent) adalah algoritma optimasi
orde pertama.
Untuk menemukan minimum lokal dari fungsi
menggunakan gradien descent, diambil langkah
sebanding dengan negatif dari gradien (atau
perkiraan gradien) dari fungsi pada titik sekarang.
Jika diambil langkah sebanding dengan gradien
positif, maka akan didapatkan maksimum lokal fungsi
tersebut; prosedur ini kemudian dikenal sebagai
gradient ascent
Gradient descent juga dikenal sebagai steepest
descent, sedangkan gradient ascent dikenal dengan
steepest ascent.
Fungsi Variabel Banyak
Steepest Descent: Penyelesaian Geometri
Model matematika :
f (X0)
Min 𝑓 𝑥 , 𝑥 adalah vektor
X0
Proses pencarian titik minimum dilakukan secara rekursif
sebagai berikut:
Dari suatu titik yang diketahui (x0), gerak berlawanan X1
arah dengan gradien fungsi pada titik tersebut sampai
didapat titik baru (x1) yang memiliki nilai 𝑓 𝑥 terkecil
sepanjang garis −𝛻𝑓 𝑥 0 . - f (X0)
Ulangi proses tersebut sampai tidak dapat memperoleh
titik baru lagi
Titik Min
Fungsi Variabel Banyak
Steepest Descent: Penyelesaian Geometri
Gradien 𝛻𝑓(𝑥 0 ) merupakan arah penambahan f (X0)
terbesar dari nilai 𝑓 𝑥 pada 𝑥 = 𝑥 0 .
X0
Sehingga −𝛻𝑓(𝑥 0 ) adalah arah penurunan terbesar
nilai 𝑓(𝑥) pada 𝑥 = 𝑥 0 . Untuk mencari titik minimum
sebaiknya bergerak sepanjang −𝛻𝑓(𝑥 0 )
X1
X0
- f (X0) = d 0
X ' X d
- f (X0)
X1
Untuk menentukan jauhnya, cari 𝜆 yang meminimumkan 𝑓 𝑥 0 + 𝜆𝑑 0 = 𝑓(𝜆) yaitu
fungsi variable tunggal sehingga dapat dicari dengan metode yang telah dijelaskan
Fungsi Variabel Banyak
Steepest Descent: Penyelesaian Geometri
𝑥 𝑛 = 𝑥 𝑛;1 − 𝜆𝑛 𝛻𝑓 𝑥 𝑛;1 𝑥 1 = 𝑥 0 − 𝜆1 𝛻𝑓 𝑥 0
𝑓 𝑥 𝑛 = 𝑓(𝑥 𝑛;1 − 𝜆𝑛𝛻𝑓(𝑥 𝑛;1 ) 𝑥 2 = 𝑥 1 − 𝜆2 𝛻𝑓 𝑥 1 ,
= 𝑓(𝜆𝑛 ) dan seterusnya
Definisikan:
𝑑𝑛 = steepest descent direction (arah penurunan paling tajam)
pada titik 𝑥 𝑛
𝑑𝑛 = −𝛻𝑓 𝑥 𝑛
𝑥 𝑛:1 = 𝑥𝑛 + 𝜆𝑛:1 𝑑𝑛
Fungsi Variabel Banyak
Steepest Descent: Penyelesaian Geometri
Sifat dari 𝑑𝑛 : 𝑑1 ⊥ 𝑑2
min
𝑑3 ⊥ 𝑑2
…..
𝑑𝑛:1 ⊥ 𝑑𝑛
x3 d2 x2
Berlaku: 𝑑1 . 𝑑2 = 0 d1
𝑑3 . 𝑑2 = 0 x1 d0 x0
…..
𝑑𝑛:1 . 𝑑𝑛 = 0
Mengapa? Coba buktikan!
Fungsi Variabel Banyak
Steepest Descent: Penyelesaian Geometri
Pseudocode:
1. Take 1 titik sembarang sebagai 𝑥 0 . Set 𝑛 = 1
2. Find 𝛻𝑓(𝑥 0 )
3. Calculate 𝑥 𝑛 = 𝑥 𝑛;1 − 𝜆𝑛 𝛻𝑓(𝑥 𝑛;1 ), nyatakan dengan 𝜆𝑛
4. Expres 𝑓 𝑥 𝑛 = 𝑓(𝑥 𝑛;1 − 𝜆𝑛 𝛻𝑓 𝑥 𝑛;1 ) sebagai 𝑓(𝜆𝑛 ) (karena 𝑓(𝑥 𝑛;1 ) dan
𝛻𝑓(𝑥 𝑛;1 ) dapat dihitung, 𝑓 𝑥 𝑛 = 𝑓(𝜆𝑛 ) adalah merupakan fungsi skalar)
5. Calculate 𝜆𝑛 yang meminimumkan 𝑓(𝜆𝑛 )
6. If 𝛻𝑓(𝑥 𝑛 ) > ∈, then set 𝑛 = 𝑛 + 1. Go to 3
7. Else, 𝑥 𝑛 adalah titik minimum dengan nilai minimum sebesar 𝑓(𝑥 𝑛 ). Stop
Fungsi Variabel Banyak
Steepest Descent: Contoh Fungsi Kuadrat (2 Variabel)
Contoh
min 3𝑥1 2 + 2𝑥2 2 + 4𝑥1 𝑥2 − 6𝑥1 − 8𝑥2 + 6
Dengan Steepest Descent mulai dari (1,1)
6𝑥1 + 4𝑥2 − 6
𝛻𝑓 𝑥 =
4𝑥1 + 4𝑥2 − 8
Iterasi 1
0 1 0 4
𝑥 = 𝛻𝑓(𝑥 ) =
1 0
0 −4 1 1 −4 1 − 4𝜆
𝑑 = 𝑥 = +𝜆 =
0 1 0 1
Fungsi Variabel Banyak
Steepest Descent: Contoh Fungsi Kuadrat (2 Variabel)
𝑓 𝜆 = 3(1 − 4𝜆)2 + 2 + 4 1 − 4𝜆 − 6 1 − 4𝜆 − 8 + 6
= 48𝜆2 − 24𝜆 + 3 + 2 + 4 − 16𝜆 − 6 + 24𝜆 − 2
= 48𝜆2 − 16𝜆 + 1
Cari 𝜆 yang meminimumkan 𝑓 𝜆 :
𝛻𝑓 𝜆 = 96𝜆 − 16 = 0
16 1
𝜆𝑚𝑖𝑛 = = 𝛻𝑓(𝑥 0 ) = 4 > 𝜀 (Terus)
96 6
Fungsi Variabel Banyak
Steepest Descent: Contoh Fungsi Kuadrat (2 Variabel)
Iterasi 2
1 1 1 −4 1/3 Iterasi 1
𝑥 = + =
1 6 0 1
0 0
𝛻𝑓(𝑥 1 ) = 𝑑1 = (1,1)
−8/3 8/3
(1/3,1)
1
2 1/3 0 3
𝑥 = +𝜆 =
1 8/3 8
1+ 𝜆
3
Fungsi Variabel Banyak
Steepest Descent: Contoh Fungsi Kuadrat (2 Variabel)
1 2 8 2 1 8 1 8
𝑓 𝜆 = 3 3 + 2 1 − 3𝜆 + 4 3 1 +3𝜆 −6 3
−8 1+ 3
𝜆 +6
1 32 128 2 4 32 64
= 3
+2+ 3 𝜆+ 9 𝜆 +3+ 9 𝜆 −2−8 − 3𝜆 +6
128 2 64 1
= 𝜆 − 𝜆+
9 9 3
Cari 𝜆 yang meminimumkan 𝑓 𝜆 :
256 64
𝛻𝑓 𝜆 = 𝜆 − =0
9 9
1 8
𝜆𝑚𝑖𝑛 = 𝛻𝑓(𝑥 ) = (Terus)
1
4 3
Fungsi Variabel Banyak
Steepest Descent: Contoh Fungsi Kuadrat (2 Variabel)
1 1 1 Iterasi 2
3 3 3
𝑥2 = 8 = 2 = 5
1+ 𝜆 1+ (1/3,5/3)
3 3 3
(1/3,1)
Fungsi Variabel Banyak
Steepest Descent: Contoh Fungsi Kuadrat (2 Variabel)
1 8 1 − 8𝜆
𝑥3 = 3 −𝜆 3 = 3 3
5 0 5
Contoh 3 3
2 (16𝜆)
Iterasi ketiga 𝑓 𝜆 = 3 8𝜆 3 − 1 3 −
1 9
8
2
𝑥 = 3 2
𝛻𝑓 𝑥 = 3 − 14 9
5 0
3 agar diperoleh λ minimum maka
2 2
8 𝛻𝑓 𝜆 = 0
𝑑 = −𝛻𝑓 𝑥 = 3 (128𝜆)
0 − 64 = 0
3 9
𝜆=1 6
Iterasi berlanjut
1 − 8𝜆 −1
karena 𝛻𝑓(𝑥 2 ) > 0 3 3 = 9
𝑥3 =
𝑥 3 = 𝑥 2 + 𝜆𝑑2 5 5
3 3
Fungsi Variabel Banyak
Steepest Descent: Contoh Fungsi Kuadrat (2 Variabel)
min min
Iterasi ketiga Iterasi ke-40
Fungsi Variabel Banyak
Steepest Descent
Contoh dengan Fungsi Pangkat 2
2𝑥12 − 4𝑥11 + 𝑥22 − 4𝑥2 mulai dari titik (−1,0)
𝑖 𝑥1 𝑥2 𝑓(𝑥)
0 -1 0
1 1.2222 1.1111 -5.1111
2 0.85185 1.85185 -5.934156
3 1.01646 1.93415 -5.995123
6 0.99918 1.99918 -5.999998
10 0.9999955 1.9999955 -6.000000
20 0.9999999 1.99999999 -6.000000
26 1.0000000 1.9999999 -6.000000
Fungsi Variabel Banyak
Steepest Descent: Contoh Fungsi Kuadrat (2 Variabel)
Tidak cocok
dengan
perhitungan
analitis.
Dimana letak
kesalahannya?
Mungkinkah
dibuat menjadi
konvergen ke
titik minimum
yang dicari?
Latihan
Selesaikan model matematika berikut dengan metode
stepeest descent (3 iterasi) dimulai dari titik (1,1)
Min 3𝑋12 + 2𝑋22 + 4𝑋1 𝑋2 − 6𝑋1 − 8𝑋2 + 6