Optimisasi Statistika - Metode Steepest Descent dan Gradien Konjugat

Video Pembelajaran - P6

Video Pembelajaran dapat diakses melalui link berikut : https://ipb.link/materiopstat

Metode Steepest Descent (Metode Cauchy)

Metode Steepest Descent adalah metode optimasi yang paling sederhana dan intuitif. Pada dasarnya, metode ini meminimalkan fungsi \(f(x)\) dengan bergerak ke arah gradien negatif dari fungsi tersebut, yang menunjukkan arah tercepat penurunan nilai fungsi. Metode ini sangat cocok untuk masalah optimasi yang tidak terlalu besar dan lebih mudah untuk diterapkan, meskipun memiliki kekurangan dalam hal kecepatan konvergensi, terutama pada fungsi yang memiliki bentuk yang rumit atau datar.

Langkah-Langkah

  1. Menentukan titik awal \(x_0\): Titik awal \(x_0\) adalah titik pertama dari mana kita mulai mencari solusi. Pemilihan titik awal ini dapat mempengaruhi laju konvergensi. Titik awal yang lebih dekat dengan solusi optimal cenderung mempercepat konvergensi.

  2. Menghitung gradien fungsi \(\nabla f(x_i)\): Gradien fungsi \(\nabla f(x_i)\) pada titik \(x_i\) dihitung dengan menghitung turunan parsial dari fungsi \(f(x)\) terhadap setiap variabel \(x_1, x_2, ..., x_n\). Gradien ini menunjukkan arah pertumbuhan tercepat dari fungsi, dan kita bergerak ke arah negatif gradien untuk meminimalkan fungsi.

    \[ \nabla f(x_i) = \left( \frac{\partial f}{\partial x_1}, \frac{\partial f}{\partial x_2}, \dots, \frac{\partial f}{\partial x_n} \right) \]

    Dalam kasus dua dimensi, gradien dapat ditulis sebagai:

    \[ \nabla f(x_i) = \left( \frac{\partial f}{\partial x}, \frac{\partial f}{\partial y} \right) \]

  3. Menentukan panjang langkah optimal \(\alpha\): Pencarian garis dilakukan untuk menentukan panjang langkah optimal \(\alpha\), yaitu nilai yang meminimalkan fungsi \(f(x)\) sepanjang arah gradien negatif. Proses pencarian ini dapat dilakukan menggunakan metode numerik seperti metode kuadrat terkecil atau pencarian garis satu dimensi. Biasanya kita mencari \(\alpha\) yang meminimalkan fungsi berikut:

    \[ \alpha = \arg \min_{\alpha} f(x_i - \alpha \nabla f(x_i)) \]

  4. Memperbarui titik \(x_{i+1}\): Setelah mendapatkan \(\alpha\), titik berikutnya \(x_{i+1}\) diperoleh dengan mengurangi gradien dari titik saat ini \(x_i\), dikalikan dengan panjang langkah \(\alpha\).

    \[ x_{i+1} = x_i - \alpha \nabla f(x_i) \]

    Proses ini menggeser titik ke arah yang mengurangi nilai fungsi.

  5. Kondisi penghentian: Iterasi dilanjutkan sampai norma gradien \(||\nabla f(x_i)||\) lebih kecil dari suatu toleransi \(\epsilon\) yang telah ditentukan, atau jumlah iterasi melebihi batas maksimum. Jika kondisi ini terpenuhi, maka iterasi dihentikan.

    \[ ||\nabla f(x_i)|| < \epsilon \]

Kelebihan dan Kekurangan

  • Kelebihan:

    • Konsep yang sederhana dan mudah diterapkan.
    • Sangat baik untuk fungsi yang tidak terlalu kompleks dan memiliki gradien yang jelas.

  • Kekurangan:

    • Kecepatan konvergensi yang lambat, terutama pada fungsi dengan gradien yang sangat kecil atau jika bentuk fungsinya tidak memiliki struktur yang baik.
    • Tergantung pada pemilihan titik awal, yang bisa sangat mempengaruhi hasil akhirnya.

Sintaks R

steepestDescent <- function(f, x0, tol = 1e-6, maxIter = 1000) {
  # Initialize variables
  x <- x0
  fx <- f(x)
  gradx <- numDeriv::grad(func=f, x=x)
  iter <- 0
  
  # Iterate until convergence or maximum number of iterations reached
  while (iter < maxIter && norm(as.matrix(gradx)) > tol) {
    cat("Iterasi ke-", iter, "\n", "x1 =", x[1], "; x2 =", x[2], "; fx =", fx, "\n")
    
    # Calculate step size using line search
    alpha <- optimize(function(a) f(x - a * gradx), interval = c(0, 1))$minimum
    
    # Update x
    x <- x - alpha * gradx
    
    # Update function value and gradient
    fx <- f(x)
    gradx <- numDeriv::grad(func=f, x=x)
    
    # Update iteration count
    iter <- iter + 1
  }
  
  # Return the final solution and function value
  return(list(x = x, fx = fx, iter = iter))
}

# Definisi fungsi
f <- function(x) {
  x1 <- x[1]; x2 <- x[2];
  x1 - x2 + (2 * x1^2) + (2 * x1 * x2) + (x2^2)
}

# Titik awal
x0 <- c(0, 0)

# Panggil fungsi
steepestDescent(f = f, x0 = x0)
## Iterasi ke- 0 
##  x1 = 0 ; x2 = 0 ; fx = 0 
## Iterasi ke- 1 
##  x1 = -0.9999339 ; x2 = 0.9999339 ; fx = -1 
## Iterasi ke- 2 
##  x1 = -0.799955 ; x2 = 1.199939 ; fx = -1.199979 
## Iterasi ke- 3 
##  x1 = -0.9999868 ; x2 = 1.399944 ; fx = -1.239992 
## Iterasi ke- 4 
##  x1 = -0.9599741 ; x2 = 1.439962 ; fx = -1.247997 
## Iterasi ke- 5 
##  x1 = -0.9999974 ; x2 = 1.47998 ; fx = -1.249599 
## Iterasi ke- 6 
##  x1 = -0.9919914 ; x2 = 1.487987 ; fx = -1.24992 
## Iterasi ke- 7 
##  x1 = -0.9999995 ; x2 = 1.495994 ; fx = -1.249984 
## Iterasi ke- 8 
##  x1 = -0.9983976 ; x2 = 1.497596 ; fx = -1.249997 
## Iterasi ke- 9 
##  x1 = -0.9999999 ; x2 = 1.499199 ; fx = -1.249999 
## Iterasi ke- 10 
##  x1 = -0.9996794 ; x2 = 1.499519 ; fx = -1.25 
## Iterasi ke- 11 
##  x1 = -1 ; x2 = 1.49984 ; fx = -1.25 
## Iterasi ke- 12 
##  x1 = -0.9999359 ; x2 = 1.499904 ; fx = -1.25 
## Iterasi ke- 13 
##  x1 = -1 ; x2 = 1.499968 ; fx = -1.25 
## Iterasi ke- 14 
##  x1 = -0.9999872 ; x2 = 1.499981 ; fx = -1.25 
## Iterasi ke- 15 
##  x1 = -1 ; x2 = 1.499994 ; fx = -1.25 
## Iterasi ke- 16 
##  x1 = -0.9999974 ; x2 = 1.499996 ; fx = -1.25 
## Iterasi ke- 17 
##  x1 = -1 ; x2 = 1.499999 ; fx = -1.25 
## Iterasi ke- 18 
##  x1 = -0.9999995 ; x2 = 1.499999 ; fx = -1.25 
## Iterasi ke- 19 
##  x1 = -0.9999999 ; x2 = 1.5 ; fx = -1.25
## $x
## [1] -0.9999998  1.4999997
## 
## $fx
## [1] -1.25
## 
## $iter
## [1] 20

Metode Gradien Konjugat (Fletcher-Reeves)

Metode Gradien Konjugat adalah metode yang lebih canggih dan lebih efisien dibandingkan dengan Steepest Descent, terutama pada masalah optimasi yang besar dan linear. Metode ini sangat berguna dalam memecahkan masalah dengan fungsi kuadrat yang besar, yang sering ditemui dalam teknik dan ekonomi.

Keunggulan utama dari metode Gradien Konjugat adalah kemampuannya untuk mempercepat konvergensi dengan menggunakan informasi gradien dari iterasi sebelumnya. Alih-alih hanya mengarah ke gradien negatif, metode ini memperbarui arah pencarian dengan cara yang lebih efektif dan terstruktur.

Langkah-Langkah

  1. Menentukan nilai awal \(x_0\), gradien \(\nabla f(x_0)\), dan arah awal \(d_0\): Titik awal \(x_0\) dipilih, kemudian dihitung gradiennya \(\nabla f(x_0)\). Arah pencarian pertama \(d_0\) diatur sebagai negatif gradien pada titik \(x_0\).

    \[ d_0 = -\nabla f(x_0) \]

  2. Iterasi kedua dan seterusnya:

    • Hitung gradien \(\nabla f(x_i)\): Pada setiap iterasi, hitung gradien pada titik \(x_i\) yang baru.

    • Menentukan panjang langkah optimal \(\alpha\): Sama seperti pada metode Steepest Descent, kita menentukan panjang langkah \(\alpha\) yang meminimalkan fungsi \(f(x)\) sepanjang arah \(d_i\).

      \[ \alpha = \arg \min_{\alpha} f(x_i + \alpha d_i) \]

    • Memperbarui titik \(x_{i+1}\): Titik berikutnya \(x_{i+1}\) diperoleh dengan menambahkan \(\alpha d_i\) pada titik \(x_i\).

      \[ x_{i+1} = x_i + \alpha d_i \]

    • Menghitung koefisien \(\beta\): Koefisien \(\beta\) dihitung untuk memperbarui arah pencarian. Nilai \(\beta\) dihitung berdasarkan perbandingan antara gradien pada iterasi saat ini dan iterasi sebelumnya.

      \[ \beta = \frac{\|\nabla f(x_{i+1})\|^2}{\|\nabla f(x_i)\|^2} \]

    • Menentukan arah baru \(d_{i+1}\): Arah pencarian berikutnya \(d_{i+1}\) diperbarui dengan menggabungkan gradien negatif pada titik \(x_{i+1}\) dan informasi dari arah pencarian sebelumnya \(d_i\) yang terkonjugasi oleh koefisien \(\beta\).

      \[ d_{i+1} = -\nabla f(x_{i+1}) + \beta d_i \]

  3. Kondisi penghentian: Iterasi dihentikan jika norma gradien \(||\nabla f(x_{i+1})||\) lebih kecil dari toleransi \(\epsilon\), atau jika jumlah iterasi melebihi batas maksimum.

    \[ ||\nabla f(x_{i+1})|| < \epsilon \]

Kelebihan dan Kekurangan

  • Kelebihan:

    • Lebih efisien daripada Steepest Descent, terutama untuk masalah yang lebih besar dan lebih kompleks.
    • Kecepatan konvergensi yang lebih baik, terutama pada fungsi kuadrat besar.
    • Tidak memerlukan matriks Hessian, membuatnya lebih hemat memori.

  • Kekurangan:

    • Masih dapat mengalami kesulitan pada fungsi non-kuadrat atau tidak terstruktur.
    • Lebih kompleks dalam implementasi dibandingkan dengan Steepest Descent.

Sintaks R

conjugateGradientFR <- function(f, x0, tol = 1e-6, maxIter = 1000) {
  # Initialize variables
  x <- x0
  fx <- f(x)
  gradx <- numDeriv::grad(func=f, x=x)
  d <- -gradx
  iter <- 0
  
  # Iterate until convergence or maximum number of iterations reached
  while (iter < maxIter && norm(as.matrix(gradx)) > tol) {
    cat("Iterasi ke-", iter, "\n", "x1 =", x[1], "; x2 =", x[2], "; fx =", fx, "\n")
    
    # Calculate step size using line search
    alpha <- optimize(function(a) f(x + a * d), interval = c(0, 1))$minimum
    
    # Update x and gradient
    x <- x + alpha * d
    gradx_new <- numDeriv::grad(func=f, x=x)
    
    # Calculate beta using Fletcher-Reeves formula
    beta <- norm(as.matrix(gradx_new))^2 / norm(as.matrix(gradx))^2
    
    # Update direction
    d <- -gradx_new + beta * d
    
    # Update function value and gradient
    fx <- f(x)
    gradx <- gradx_new
    
    # Update iteration count
    iter <- iter + 1
  }
  
  # Return the final solution and function value
  return(list(x = x, fx = fx, iter = iter))
}

# Definisi fungsi
f <- function(x) {
  x1 <- x[1]; x2 <- x[2];
  x1 - x2 + (2 * x1^2) + (2 * x1 * x2) + (x2^2)
}

# Titik awal
x0 <- c(0, 0)

# Panggil fungsi
conjugateGradientFR(f = f, x0 = x0)
## Iterasi ke- 0 
##  x1 = 0 ; x2 = 0 ; fx = 0 
## Iterasi ke- 1 
##  x1 = -0.9999339 ; x2 = 0.9999339 ; fx = -1 
## Iterasi ke- 2 
##  x1 = -0.9999339 ; x2 = 1.499934 ; fx = -1.25 
## Iterasi ke- 3 
##  x1 = -0.999967 ; x2 = 1.499934 ; fx = -1.25
## $x
## [1] -1.0  1.5
## 
## $fx
## [1] -1.25
## 
## $iter
## [1] 4
# Alternatif menggunakan fungsi optim
optim(par = x0, fn = f, method = "CG")
## $par
## [1] -0.999999  1.499999
## 
## $value
## [1] -1.25
## 
## $counts
## function gradient 
##       39       17 
## 
## $convergence
## [1] 0
## 
## $message
## NULL