Metode Steepest Descent

Menurut Rao (2020), algoritma metode steepest descent adalah sebagai berikut: Algoritma steepest descent

Sebagai ilustrasi, misalnya kita ingin mencari nilai optimum dari fungsi berikut: \[ f(x_1, x_2)=x_1-x_2+2{x_1}^2+2x_1x_2+{x_2}^2 \] dengan nilai awal \[ x_{(1)}=\biggl[\begin{matrix}0\\0\end{matrix}\biggr] \]

Sebelum melakukan perhitungan menggunakan fungsi-fungsi di dalam R, kita perlu menginstall terlebih dulu package numDeriv.

Selanjutnya, kita dapat menyusun fungsi untuk melakukan perhitungan nilai optimum, dengan mengacu pada algoritma steepest descent.

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) {
    # 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
    
    # Calculate function value and gradient at new x
    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))
}

Sebagai input dari fungsi yang telah kita tuliskan di atas, kita perlu menuliskan fungsi \(f(x_1, x_2)\) dalam R code, contohnya seperti yang dilakukan program di bawah ini.

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

Sesuai dengan instruksi pada ilustrasi ini, kita ingin mencari nilai optimum dengan menentapkan nilai awal \(x_{(1)}=\biggl[\begin{matrix}0\\0\end{matrix}\biggr]\).

x0<-c(0,0)

Setelah mempersiapkan semua input yang diperlukan, kita dapat menjalankan fungsi steepestDescent() untuk mencari nilai optimum dari \(f(x_1,x_2)\).

steepestDescent(f=f, x0=x0)
## $x
## [1] -0.9999998  1.4999997
## 
## $fx
## [1] -1.25
## 
## $iter
## [1] 20

Output di atas menunjukkan bahwa konvergensi tercapai pada iterasi ke-20, dan diperoleh nilai optimum \(f(x_1,x_2)\) tercapai pada titik \(x^*=\biggl[\begin{matrix}-1\\1.5\end{matrix}\biggr]\).

Metode Gradien Konjugat

Metode ini merupakan pengembangan dari metode steepest descent sehingga optimisasi dapat dilakukan dengan iterasi yang lebih cepat. Algoritma metode gradien konjugat (Fletcher-Reeves) adalah sebagai berikut: Algoritma Fletcher-Reeves

Sebagai ilustrasi, kita akan menggunakan fungsi \(f(x_1,x_2)\) yang sama seperti sebelumnya. Berikut ini adalah fungsi yang dapat kita gunakan untuk melakukan optimisasi dengan algoritma Fletcher-Reeves.

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) {
    # 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))
  
}

Dengan memasukkan input berupa fungsi \(f(x_1,x_2)\), gradien \(\nabla f\), serta nilai awal \(x_{(1)}\) ke dalam fungsi conjugateGradientFR(), kita dapat memperoleh nilai optimum yang diinginkan.

conjugateGradientFR(f=f,x0=x0) 
## $x
## [1] -1.0  1.5
## 
## $fx
## [1] -1.25
## 
## $iter
## [1] 4

Output di atas memperlihatkan bahwa nilai optimum tercapai pada iterasi ke-4, jauh lebih sedikit dibandingkan dengan metode sebelumnya.

Sebagai tambahan, metode optimisasi dengan pendekatan gradien konjugat dapat pula dilakukan menggunakan fungsi optim(),dengan menuliskan argumen method="CG seperti contoh berikut ini.

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

Latihan

  1. Tentukan \(x\) yang meminimumkan fungsi \(f(x)=x^2\), gunakan nilai awal \(x_{(1)}=5\). Lakukan perhitungan secara manual, lalu bandingkan hasilnya dengan output fungsi R.

  2. Tentukan \(x_1\) dan \(x_2\) yang meminimukan fungsi \(f(x_1, x_2)=100{(x_2-{x_1}^2)}^2+{(1-x_1)}^2\) dengan nilai awal \(x_{(1)}=\biggl[\begin{matrix}-1.2\\1\end{matrix}\biggr]\). Bandingkan hasilnya dengan hasil perhitungan secara manual (cukup gunakan dua iterasi).

Referensi

Rao, S.S. (2020). Engineering Optimization. New Jersey: John Wiley & Sons.

(Pustaka lain yang relevan)