Nama: Muhammad Haikal Fikri, NIM: 230605110067, Fakultas: Sains dan Teknologi, Program studi: Teknik Informatika, Universitas: Universitas Islam Negeri Maulana Malik Ibrahim Malang, Dosen pengajar: Prof. Dr. Suhartono, M.Kom, Tanggal kirim: 7 November 2023

Mengoptimalkan Pencarian Nol dalam Pelokalan Akar menggunakan Metode Gradient Descent

Metode Gradient Descent

Metode gradient descent adalah teknik optimasi terkenal yang digunakan untuk menemukan nilai minimum (atau maksimum) suatu fungsi. Metode ini sangat relevan ketika masalah pelokalan akar dikaitkan dengan meminimalkan (atau memaksimalkan) sebuah fungsi yang memiliki akar pada nilai minimum (atau maksimum).

Dalam konteks pencarian nol, Anda dapat melihat akar suatu fungsi sebagai titik di mana turunan (gradien) fungsi tersebut adalah nol. Dengan kata lain, akar adalah minimum atau maksimum dari turunan fungsi. Untuk menemukan titik ini, metode penurunan gradien dapat digunakan.

Metode ini dimulai dari tebakan awal, menghitung gradien pada titik tersebut (yang mengarah ke arah kenaikan paling curam), dan bergerak ke arah yang berlawanan untuk mencapai minimum (atau maksimum). Dengan memperbarui tebakan secara berulang-ulang berdasarkan gradien, metode ini dapat secara efektif menemukan akarnya.

Penting untuk dicatat bahwa metode gradient descent sangat berguna ketika berhadapan dengan fungsi non-linear atau fungsi dengan banyak akar, karena metode ini dapat menemukan akar terdekat berdasarkan tebakan awal dan tujuan optimasi.

Pilihan teknik optimasi tergantung pada masalah spesifik. Jika Anda tertarik dengan lokalisasi dan optimasi akar, metode gradient descent, bersama dengan algoritma optimasi lainnya, dapat menjadi alat yang berharga untuk mencapai kedua tujuan tersebut secara efisien.

Berikut adalah cara kerja Metode Gradient Descent dalam mengoptimalkan pencarian Zero Finding:

  1. Inisialisasi

Mulailah dengan memilih tebakan awal untuk solusi optimal atau minimum fungsi. Ini adalah titik awal Anda dalam mencari nilai minimum.

  1. Hitung Gradien

Hitung gradien (atau turunan) fungsi pada tebakan saat ini. Gradien menunjuk ke arah kenaikan paling curam dalam fungsi.

  1. Perbarui Tebakan

Sesuaikan tebakan Anda dengan bergerak ke arah yang berlawanan dengan gradien. Penyesuaian ini ditentukan oleh faktor yang disebut tingkat pembelajaran (α). Rumus untuk memperbarui tebakan adalah sebagai berikut:

Tebakan Baru = Tebakan Lama - (α * Gradien)

Laju pembelajaran mengontrol ukuran langkah dan mempengaruhi seberapa cepat metode ini konvergen. Memilih laju pembelajaran yang tepat sangatlah penting.

  1. Mengevaluasi Fungsi

Hitung nilai fungsi pada tebakan baru. Hal ini dilakukan untuk menentukan apakah nilai fungsi menurun, yang mengindikasikan kemajuan menuju nilai minimum.

  1. Periksa Konvergensi

Periksa konvergensi dengan memeriksa salah satu kondisi berikut: Jika perubahan nilai fungsi lebih kecil dari toleransi yang telah ditentukan (yaitu, |f(tebakan baru) - f(tebakan lama) < ε), Anda dapat berhenti. Metode ini telah mencapai titik minimum. Jika Anda telah mencapai jumlah iterasi maksimum, Anda juga dapat berhenti, bahkan jika kondisi konvergensi tidak terpenuhi.

  1. Ulangi atau Hentikan

Jika kondisi konvergensi tidak terpenuhi, kembali ke Langkah 2 dengan tebakan baru sebagai tebakan saat ini. Lanjutkan iterasi hingga konvergensi tercapai atau jumlah iterasi maksimum tercapai.

Representasi Visual dalam R - Metode Gradient Descent:

Saya akan memberikan contoh visual sederhana dari penggunaan Metode Gradient Descent untuk mencari nilai minimum dari sebuah fungsi f(x) = x^2 satu dimensi di R. Dalam kasus ini, kita akan mengoptimalkan fungsi untuk menemukan nilai minimumnya. Perhatikan bahwa ini adalah contoh langsung untuk mengilustrasikan konsep ini secara visual.

# Define the function to optimize (f(x) = x^2)
f <- function(x) {
  return(x^2)
}

# Gradient of the function (derivative)
gradient <- function(x) {
  return(2 * x)
}

# Gradient Descent Method
gradient_descent <- function(learning_rate, max_iterations, initial_guess) {
  history <- data.frame(iteration = numeric(), x = numeric(), f_x = numeric())
  x <- initial_guess
  
  for (i in 1:max_iterations) {
    f_x <- f(x)
    history <- rbind(history, data.frame(iteration = i, x = x, f_x = f_x))
    gradient_x <- gradient(x)
    x <- x - learning_rate * gradient_x
  }
  
  return(history)
}

# Set parameters
learning_rate <- 0.1
max_iterations <- 5
initial_guess <- 3

# Run the Gradient Descent Method
results <- gradient_descent(learning_rate, max_iterations, initial_guess)

# Plot the function and optimization path
library(ggplot2)

ggplot(data.frame(x = c(-2, 4)), aes(x)) +
  geom_function(fun = f, color = "blue", size = 1) +
  geom_segment(data = results, aes(xend = x, yend = f_x), x = results$x, y = results$f_x, color = "red", size = 1) +
  geom_point(data = results, aes(x, f_x), color = "red", size = 3) +
  labs(
    title = "Gradient Descent Method for f(x) = x^2",
    x = "x",
    y = "f(x)"
  )
## Warning: Using `size` aesthetic for lines was deprecated in ggplot2 3.4.0.
## ℹ Please use `linewidth` instead.
## This warning is displayed once every 8 hours.
## Call `lifecycle::last_lifecycle_warnings()` to see where this warning was
## generated.

Untuk lebih jelasnya kita visualisasikan dengan annotasi di setiap iterasinya

# Define the function to optimize (f(x) = x^2)
f <- function(x) {
  return(x^2)
}

# Gradient Descent Method
gradient_descent <- function(learning_rate, max_iterations, initial_guess) {
  history <- data.frame(iteration = numeric(), x = numeric(), f_x = numeric())
  x <- initial_guess
  
  for (i in 1:max_iterations) {
    f_x <- f(x)
    history <- rbind(history, data.frame(iteration = i, x = x, f_x = f_x))
    x <- x - learning_rate * 2 * x  # Gradient of f(x) = 2x
  }
  
  return(history)
}

# Set parameters
learning_rate <- 0.1
max_iterations <- 5
initial_guess <- 3

# Run the Gradient Descent Method
results <- gradient_descent(learning_rate, max_iterations, initial_guess)

# Annotate the plot with iteration and x values
annotation_text <- paste("Iteration ", results$iteration, "\n x = ", round(results$x, 2))

# Create the plot with annotations for each iteration
ggplot(data.frame(x = c(-2, 4)), aes(x)) +
  geom_function(fun = f, color = "blue", size = 1) +
  geom_point(data = results, aes(x, f_x), color = "red", size = 3) +
  geom_segment(data = results, aes(xend = x, yend = f_x), x = results$x, y = results$f_x, color = "red", size = 1, arrow = arrow(type = "closed", length = unit(0.03, "npc"))) +
  annotate("text", x = results$x, y = results$f_x, label = paste("Iteration ", results$iteration, "\n x = ", round(results$x, 2)), hjust = -0.2, size = 3) +
  labs(
    title = "Gradient Descent Method for f(x) = x^2",
    x = "x",
    y = "f(x"
  )

Jalur Optimisasi: Jalur merah mengilustrasikan langkah-langkah iteratif Metode Descent Gradien. Ini menunjukkan bagaimana algoritma dimulai dengan tebakan awal dan secara bertahap bergerak menuju minimum dengan mengikuti gradien negatif.

Anotasi: Setiap titik pada jalur optimisasi dianotasi dengan nomor iterasi yang sesuai dan nilai x. Ini memberikan perkembangan langkah demi langkah, memudahkan untuk memahami bagaimana metode ini berkembang dan konvergen.

Parameter: Parameter-parameter metode termasuk tingkat pembelajaran, jumlah iterasi maksimum, dan tebakan awal. Parameter-parameter ini memainkan peran penting dalam menentukan kecepatan dan akurasi proses optimisasi.

Referensi:

Jorge Nocedal, Stephen J. Wright.(2006).Numerical Optimization (2). United States of America. Springer Science+Business Media.