GRADIENT DESCENT (ASCENT)

By Eni Sumarminingsih, SSi, MM

Gradient descent (ascent) adalah algoritma optimasi orde pertama.

Untuk menemukan minimum lokal dari fungsi menggunakan gradien descent, diambillangkah sebanding dengan negatif dari gradien (atau perkiraan gradien) dari fungsi pada titik sekarang.

Jika diambil langkah sebanding dengan gradien positif, maka akan didapatkanmaksimum lokal fungsi tersebut; prosedur ini kemudian dikenal sebagai gradient ascent

Gradient descent juga dikenal sebagai steepest descent, sedangkan gradient ascent dikenaldengan steepest ascent.

ALGORITMA (MAKSIMISASI) Mulai dari titik awal v0 Bergerak dari v0 ke v1 dengan arah f(v0) :

v1 = v0 + t0 f(v0) dengan t0 adalah solusi dari masalah optimisasiberikut:

max f(v0 + t0 f(v0) )s.t t0 ≥ 0

Langkah – langkah tersebut diulangi sampaididapat nilai vi dan vi+1 yang cukup dekat

ALGORITMA (MINIMISASI) Mulai dari titik awal v0 Bergerak dari v0 ke v1 dengan arah f(v0) :

v1 = v0 - t0 f(v0) dengan t0 adalah solusi dari masalah optimisasiberikut:

min f(v0 - t0 f(v0) )s.t t0 ≥ 0

Langkah – langkah tersebut diulangi sampaididapat nilai vi dan vi+1 yang cukup dekat

ILUSTRASI

CONTOH SOAL

Gunakan metode steepest ascent untukaproksimasi solusi dari

max 푧 = − 푥 − 3 − 푥 − 2s.t 푥 , 푥 ∈ 푅

Dengan titik awal v0 = (1,1)Jawab: f(x1, x2) = (– 2(x1 – 3), – 2(x2 – 2))

f(v0) = f(1,1) = (4,2)Pilih t0 yang memaksimumkanf(v0 + t0 f(v0) ) max f[(1,1)+t0(4,2)]

max f[1+4t0 , 1+2t0]max 푧 = − 1 + 4푡0 − 3 − (1 + 2푡0 −

2)

max 푧 = − 1 + 4푡0 − 3 − 1 + 2푡0 − 2max 푧 = − −2 + 4푡0 − −1 + 2푡0

f ‘(t0)=0 - 2(-2+4t0)4 -2(-1+2t0)2 = 020 – 40 t0 = 0t0 = 0.5

v1 = [(1,1)+0.5(4,2)] = (3,2)Karena f(3, 2) = (0,0) maka iterasi dihentikanKarena f(x1, x2) adalah fungsi konkaf, maka (3,2) adalah solusi yang dicari

SOAL -SOAL

1. Gunakan metode gradient ascent untukmenduga solusi optimal dari

max 푧 = − 푥 − 2 − 푥 − 푥mulai dari titik awal (2.5, 1.5)

2. Gunakan metode gradient descent untukmenduga solusi optimal darimin 푧 = 푥 − 푥 + 푥 − 푥 푥