1. Search with Fixed Step Size

Metode ini merupakan teknik pencarian minimum dari sebuah fungsi dengan menggunakan titik awal dan ukuran langkah yang tetap. Metode ini mengasumsikan fungsi tersebut unimodal pada interval pencarian.

Algoritma:

1. Mulai dengan titik tebakan awal, misalnya \(x_1\).
   
2. Hitung \(f_1 = f(x_1)\).
   
3. Asumsikan ukuran langkah \(s\), temukan \(x_2 = x_1 + s\).
   
4. Hitung \(f_2 = f(x_2)\).
   
5. Jika \(f_2 < f_1\), dan karena kita mencari minimum, maka lanjutkan pencarian ke arah \(x_2\) dengan mengevaluasi \(x_3, x_4,\) dan seterusnya, sampai \(f_i > f_{i-1}\).
   
6. Jika \(f_2 > f_1\), arahkan pencarian ke arah berlawanan dengan mengevaluasi \(x_{-1}, x_{-2},\) dan seterusnya.
   
7. Jika \(f_2 = f_1\), maka minimum dianggap berada di antara \(x_1\) dan \(x_2\).
   
8. Proses pencarian dihentikan ketika nilai fungsi mulai meningkat, dan titik minimum diperkirakan berada di antara \(x_{i-1}\) dan \(x_i\) atau di antara \(x_{-j+1}\) dan \(x_{-j}\) tergantung arah yang diambil.

Contoh dan Kode R:

Misalkan kita ingin mencari minimum fungsi \(f(x) = x^2 + 4x + 6\) dengan titik awal \(x_1 = 0\) dan ukuran langkah \(s = 0.001\).

f <- function(x) x^2 + 4*x + 6
x1 <- 0
s <- 0.001
f1 <- f(x1)
x2 <- x1 + s
f2 <- f(x2)

# Menentukan arah pencarian
if (f2 > f1) {
  s <- -s
  x2 <- x1 + s
  f2 <- f(x2)
}

# Pencarian minimum
while(TRUE) {
  x_new <- x2 + s
  f_new <- f(x_new)
  if (f_new > f2) {
    break
  }
  x1 <- x2
  f1 <- f2
  x2 <- x_new
  f2 <- f_new
}

# Menentukan titik minimum
if (s > 0) {
  x_min <- (x1 + x2) / 2
} else {
  x_min <- (x1 + x2 - s) / 2
}

cat("Titik minimum diperkirakan berada di:", x_min, "dengan nilai f(x) =", f(x_min),"\n")

## Titik minimum diperkirakan berada di: -1.999 dengan nilai f(x) = 2.000001

2. Exhaustive Search

Pencarian eksaustif adalah metode untuk menyelesaikan masalah di mana interval di mana optimum dapat berada diketahui secara finite. Ini dilakukan dengan mengevaluasi fungsi tujuan pada sejumlah titik yang sama rata dalam interval dan mengurangi interval ketidakpastian.

Algoritma:

1. Tentukan titik awal \(x_s\) dan titik akhir \(x_f\) dari interval ketidakpastian.
   
2. Pilih \(n\) titik yang sama rata di dalam interval \([x_s, x_f]\).
   
3. Evaluasi fungsi \(f(x)\) pada ke-\(n\) titik tersebut.
   
4. Temukan pasangan titik di mana terjadi penurunan nilai fungsi dan kemudian peningkatan, yang menandakan bahwa interval minimum berada di antara mereka.
   
5. Perkecil interval ketidakpastian dengan memilih interval di antara titik-titik ini sebagai interval baru.
   
6. Panjang interval ketidakpastian akhir, \(L_n\), dapat dihitung sebagai \(L_n = \frac{2}{n+1} L_0\), di mana \(L_0 = x_f - x_s\).

Contoh:

Temukan minimum dari \(f = x(x - 1.5)\) di interval \([0.0, 1.0]\) hingga dalam 10% dari nilai eksak.

Untuk akurasi 10%, kita membutuhkan setidaknya \(n = 9\) titik evaluasi.

Kode R:

f <- function(x) x * (x - 1.5)

xs <- 0.0

xf <- 1.0

n <- 9 + 2 # nilai nol dan 1 dimasukan pada syntax, jadi n = 9 + 2

x_values <- seq(xs, xf, length.out = n)[c(-1,-n)]

f_values <- sapply(x_values, f)

# Cari interval dengan minimum
min_index <- which.min(f_values)

if (min_index > 1 && min_index < n) {
  interval <- c(x_values[min_index-1], x_values[min_index+1])
} else {
  interval <- c(xs, xf)
}

# Hitung panjang interval ketidakpastian
L0 <- xf - xs
Ln <- (interval[2] - interval[1])

cat("Interval ketidakpastian akhir: ", interval, "\n")

## Interval ketidakpastian akhir:  0.6 0.8

cat("Panjang interval ketidakpastian awal (L0): ", L0, "\n")

## Panjang interval ketidakpastian awal (L0):  1

cat("Panjang interval ketidakpastian akhir (Ln): ", Ln, "\n")

## Panjang interval ketidakpastian akhir (Ln):  0.2

cat("Rasio Ln/L0: ", Ln/L0, "\n")

## Rasio Ln/L0:  0.2

rbind(x_values,f_values)

##           [,1]  [,2]  [,3]  [,4] [,5]  [,6]  [,7]  [,8]  [,9]
## x_values  0.10  0.20  0.30  0.40  0.5  0.60  0.70  0.80  0.90
## f_values -0.14 -0.26 -0.36 -0.44 -0.5 -0.54 -0.56 -0.56 -0.54

Dapat terlihat bahwa nilai x7 dan x8 memiliki nilai f(x) yang sama. Artinya, kita bisa memilih nilai x optimum berada di 0.75.

3. Dichotomous Search

Pencarian Dikhotomis adalah metode pencarian sekuensial yang membagi interval ketidakpastian menjadi dua bagian yang hampir sama besar dengan melakukan eksperimen di dua titik yang sangat dekat dengan tengah interval. Berdasarkan nilai fungsi objektif di dua titik tersebut, setengah dari interval dieliminasi dari pertimbangan lebih lanjut.

Algoritma:

1. Tentukan interval awal ketidakpastian dengan titik awal \(x_s\) dan titik akhir \(x_f\), serta panjang interval \(L_0 = x_f - x_s\).
   
2. Pilih \(δ\), yang merupakan bilangan positif kecil, untuk menentukan seberapa dekat eksperimen akan dilakukan di tengah interval.
   
3. Hitung dua titik eksperimen \(x_1 = \frac{L_0}{2} - \frac{δ}{2}\) dan \(x_2 = \frac{L_0}{2} + \frac{δ}{2}\).
   
4. Evaluasi fungsi objektif \(f_1 = f(x_1)\) dan \(f_2 = f(x_2)\).
   
5. Jika \(f_1 < f_2\), maka interval baru akan menjadi \([x_s, x_2]\), jika tidak, interval baru akan menjadi \([x_1, x_f]\).
   
6. Ulangi langkah 2-5 pada interval baru hingga interval ketidakpastian mencapai ukuran yang diinginkan.

Contoh:
Cari minimum dari \(f = x(x - 1.5)\) dalam interval \([0.0, 1.0]\) hingga 10% dari nilai eksak.

Kode R:

f <- function(x) x * (x - 1.5)

xs <- 0.0

xf <- 1.0

L0 <- xf - xs

delta <- 0.001

n <- 6 # Karena n harus genap dan ≥ 5 sesuai perhitungan, kita menggunakan n=6

# Melakukan eksperimen
for (i in 1:(n/2)) {
  x1 <- (xs + xf)/2 - delta/2
  x2 <- (xs + xf)/2 + delta/2
  f1 <- f(x1)
  f2 <- f(x2)

  if (f1 < f2) {
    xf <- x2
  } else {
    xs <- x1
  }
}

# Titik tengah interval akhir diambil sebagai titik optimum
x_opt <- (xs + xf)/2
f_opt <- f(x_opt)

cat("Titik optimum diperkirakan: ", x_opt, "\n")

## Titik optimum diperkirakan:  0.8121875

cat("Nilai fungsi di titik optimum: ", f_opt, "\n")

## Nilai fungsi di titik optimum:  -0.5586327

4. Fibonacci Search Method

Metode Fibonacci adalah teknik pencarian minimum dari suatu fungsi satu variabel yang menggunakan deret Fibonacci untuk menentukan titik-titik eksperimen secara sekuensial. Ini memungkinkan pengurangan interval ketidakpastian dengan efisien.

Keterbatasan:

1. Interval awal ketidakpastian harus diketahui.
   
2. Fungsi harus unimodal di interval awal.
   
3. Optimum eksak tidak dapat ditentukan, hanya interval akhir ketidakpastian.
   
4. Jumlah evaluasi fungsi harus ditentukan sebelumnya.

Algoritma:

1. Tentukan interval awal ketidakpastian \([a, b]\) dan total jumlah eksperimen \(n\).
   
2. Gunakan deret Fibonacci untuk menghitung posisi eksperimen: \(F_0 = F_1 = 1\) dan \(F_n = F_{n-1} + F_{n-2}\).
   
3. Letakkan dua eksperimen pertama \(x_1\) dan \(x_2\) di dalam interval dengan menggunakan rasio Fibonacci.
   
4. Evaluasi fungsi di \(x_1\) dan \(x_2\), buang interval yang tidak mengandung minimum berdasarkan evaluasi tersebut.
   
5. Lanjutkan proses dengan menghitung posisi eksperimen baru dan mengurangi interval ketidakpastian.

Contoh:
Cari minimum dari \(f(x) = x(x - 1.5)\) dalam interval \([0,3]\) menggunakan metode Fibonacci dengan \(n = 6\).

Kode R:

# Fungsi Objektif
f <- function(x) x * (x - 1.5)

# Fungsi objektif tugas kuliah
# f <- function(x) {
#   return(0.65 - (0.75 / (1 + x^2)) - 0.65 * x * atan(1 / x))
# }

# Fungsi untuk menghasilkan n bilangan Fibonacci pertama
fibonacci <- function(n) {
  fn <- c(1, 1)
  for (i in 3:(n+1)) {
    fn <- c(fn, (fn[i-1] + fn[i-2]))
  }
  return(fn[-1])
}

# Metode Pencarian Fibonacci
fib_search <- function(f, xl, xr, n){
  F = fibonacci(n) # Call the fibonnaci number function
  L0 <<- xr - xl # Initial interval of uncertainty
  R1 = L0 # Initial Reduction Ratio
  Li = (F[n-2]/F[n])*L0
  xll <- c()
  xrr <- c()
  
  R = Li/L0
  Lb=c()
  
  for (i in 2:n)
  {
    if (Li > R1/2) {
      x1 = xr - Li
      x2 = xl + Li
    } else {
      x1 = xl + Li
      x2 = xr - Li
    }
    f1 = f(x1)
    f2 = f(x2)
    
    if (f1 < f2) {
      xr = x2
      
    } else if (f1 > f2) {
      xl = x1
    } else {
      xl = x1
      xr = x2
    }
    Li = (F[n - i]/F[n - (i - 2)])*R1 # New interval of uncertainty
    R1 = xr - xl
    R = c(R, Li/L0)
    Lb = c(Lb,Li)
    xll = c(xll,xl)
    xrr = c(xll,xr)
  }
  
  list1 <- list(x1, f(x1), R, Lb, xll, xrr) # Membuat sebagai list sehingga bisa dipanggil keluar dengan fungsi return.
  names(list1) <- c("x", "f(x)", "R", "L*", "a", "b") # Memberi nama pada elemen suatu list.
  list2 <- list(x2, f(x2), R, Lb, xll, xrr)
  names(list2) <- c("x", "f(x)", "R", "L*", "a", "b")
  if (f1 <= f2) {
    return(list1) # Final result
  } else {
    return(list2) # Final result 
  }
}

# Menjalankan pencarian Fibonacci
xl <- 0
xr <- 3
n <- 6
result <- fib_search(f, xl, xr, n)

# Menampilkan hasil
print(result)

## $x
## [1] 0.6923077
## 
## $`f(x)`
## [1] -0.5591716
## 
## $R
## [1] 0.38461538 0.38461538 0.23076923 0.15384615 0.07692308
## 
## $`L*`
## [1] 1.1538462 0.6923077 0.4615385 0.2307692
## 
## $a
## [1] 0.0000000 0.0000000 0.4615385 0.4615385 0.6923077
## 
## $b
## [1] 0.0000000 0.0000000 0.4615385 0.4615385 0.6923077 0.9230769

Kode R di atas menggunakan deret Fibonacci untuk mempersempit pencarian minimum fungsi. Pada setiap iterasi, kode menghitung dua titik eksperimen baru dan membandingkan nilai fungsi di titik-titik tersebut untuk menentukan interval mana yang akan dijaga. Proses ini diulangi sampai mencapai jumlah eksperimen yang diinginkan, yang pada akhirnya memberikan estimasi titik minimum fungsi.

5. Golden Section Method

Metode Golden Section adalah teknik pencarian minimum untuk fungsi satu variabel yang menggunakan golden ratio dalam pemilihan titik eksperimen. Berbeda dengan metode Fibonacci, jumlah total eksperimen tidak perlu ditentukan sebelumnya dan dapat diputuskan selama perhitungan.

Golden Ratio:
Golden Ratio (dilambangkan dengan \(\varphi\)) adalah nilai yang diperoleh dari persamaan kuadrat \(\varphi^2 - \varphi - 1 = 0\), yang memiliki solusi positif \(\varphi = \frac{1 + \sqrt{5}}{2} \approx 1.618\).

Algoritma:

1. Tentukan interval awal ketidakpastian \([a, b]\).
   
2. Hitung \(L_2 = \frac{b - a}{\varphi^2}\) dan letakkan dua eksperimen pertama \(x_1\) dan \(x_2\) menggunakan rasio ini.
   
3. Evaluasi fungsi di \(x_1\) dan \(x_2\), dan buang bagian interval yang tidak mengandung minimum.
   
4. Lanjutkan proses dengan memperbarui posisi eksperimen baru berdasarkan golden ratio.
   
5. Ulangi sampai interval ketidakpastian mencapai akurasi yang diinginkan.

Contoh:
Minimalkan fungsi \(f(x) = 0.65 - [0.75 / (1 + x^2)] - 0.65x \tan^{-1}(1/x)\) menggunakan metode Golden Section dengan \(n = 20\).

Kode R:

f <- function(x) {
  return(0.65 - (0.75 / (1 + x^2)) - 0.65 * x * atan(1 / x))
}

# Konstanta golden ratio
phi <- (1 + sqrt(5)) / 2

# Metode Golden Section
golden_section_search <- function(f, a, b, n) {
  # Menentukan interval awal ketidakpastian
  L0 <- b - a
  # Menghitung titik eksperimen pertama
  L2 <- L0 / phi^2
  x1 <- a + L2
  x2 <- b - L2
  f1 <- f(x1)
  f2 <- f(x2)
  
  for (i in 1:(n-1)) {
    if (f1 > f2) {
      a <- x1
      x1 <- x2
      L2 <- L0 / phi^(i+1)
      x2 <- b - L2
      f1 <- f2
      f2 <- f(x2)
    } else {
      b <- x2
      x2 <- x1
      L2 <- L0 / phi^(i+1)
      x1 <- a + L2
      f2 <- f1
      f1 <- f(x1)
    }
  }
  
  # Menentukan titik terakhir dan nilai fungsi
  x_final <- (a + b) / 2
  f_final <- f(x_final)
  
  return(list(x = x_final, f_x = f_final))
}

# Menjalankan metode Golden Section
a <- 0
b <- 3
n <- 20
result <- golden_section_search(f, a, b, n)

# Menampilkan hasil
print(result)

## $x
## [1] 0.480781
## 
## $f_x
## [1] -0.3100205

1. Interpolasi Kuadratik

Metode Interpolasi Kuadratik adalah teknik optimisasi satu dimensi yang tidak memerlukan turunan fungsi. Metode ini menggunakan nilai-nilai fungsi untuk menentukan langkah yang meminimalkan fungsi dengan cara mendekati fungsi dengan polinomial kuadratik dan mencari minimum dari polinomial tersebut.

Algoritma:

1. Tentukan tiga titik, \(\lambda = A\), \(\lambda = B\), dan \(\lambda = C\) di mana \(A < B < C\), dan hitung nilai fungsi di ketiga titik tersebut, \(f_A\), \(f_B\), dan \(f_C\).
   
2. Gunakan nilai fungsi yang dihitung untuk menyelesaikan koefisien \(a\), \(b\), dan \(c\) dari polinomial kuadratik yang mendekati fungsi \(f(\lambda)\):
   \[ h(\lambda) = a + b\lambda + c\lambda^2 \]
   
3. Cari minimum kuadratik dengan rumus:
   \[ \lambda^* = -\frac{b}{2c} \]
   
4. Periksa kondisi kecukupan \(c > 0\). Jika \(\lambda^*\) cukup dekat dengan minimum, proses selesai; jika tidak, ulangi dengan memperbarui titik \(A\), \(B\), dan \(C\).

Contoh:
Minimalkan fungsi \(f(x) = 0.65 - \left[ \frac{0.75}{(1 + x^2)} \right] - 0.65x \tan^{-1}(1/x)\) dalam interval \([0, 10]\).

Kode R:

# Fungsi objektif yang akan diminimalkan
phi.f <- function(x) {
  return(0.65 - (0.75 / (1 + x^2)) - 0.65 * x * atan(1 / x))
}

# Implementasi metode interpolasi kuadratik
quadraticinterpolation <- function(phi.f, l = 0, u = 1, eps = 1e-6)
{
  #polynomials evaluated at 3 points(l, m, u) for interpolation: phi_fl, phi_fm, phi_fu
  if(l == u)
  {
    l <- 0
  }
  m <- (l + u)/2
  phi.fl <- phi.f(l)
  phi.fm <- phi.f(m)
  phi.fu <- phi.f(u)


  #a, b and c are coefficients of the polynomial (hx)
  y <- ((l - m)*(m - u)*(u - l))
  a <- (phi.fl*m*u*(u - m) + phi.fm*u*l*(l - u) + phi.fu*l*m*(m - l))/y
  b <- (phi.fl*(m^2 - u^2) + phi.fm*(u^2 - l^2) + phi.fu*(l^2 - m^2))/y
  c <- -(phi.fl*(m - u) + phi.fm*(u - l) + phi.fu*(l - m))/y

  alpha <- -b/(2*c)
  falpha <- phi.f(alpha)

  ncf <- 4

  hx <- function(x)  c*x^2 + b*x + a #environment global

  while((abs((hx(alpha) - falpha)) > eps))
  {
    #choice of l, m and C new values
    if(alpha <= m)
    {
      if(phi.fm >= falpha){
        u <- m; phi.fu <- phi.fm
        m <- alpha; phi.fm <- falpha
      }else{
        l <- alpha; phi.fl <- falpha
      }
    }else{
      if(phi.fm >= falpha){
        l <- m; phi.fl <- phi.fm
        m <- alpha; phi.fm <- falpha
      }else{
        u <- alpha; phi.fu <- falpha
      }

    }

    #refitting the function
    y <- ((l - m)*(m - u)*(u - l))
    a <- (phi.fl*m*u*(u - m) + phi.fm*u*l*(l - u) + phi.fu*l*m*(m - l))/y
    b <- (phi.fl*(m^2 - u^2) + phi.fm*(u^2 - l^2) + phi.fu*(l^2 - m^2))/y
    c <- -(phi.fl*(m - u) + phi.fm*(u - l) + phi.fu*(l - m))/y

    #quadratic interpolation

    alpha <- -b/(2*c)
    falpha <- phi.f(alpha)
    ncf <- ncf + 1

  }
  message("Method: Quadratic Interpolation. Number of calls of the objective function: ", ncf)
  return(alpha)
}

# Menentukan interval awal dan ketelitian
l <- -3
u <- 5
eps <- 1e-4

# Mencari minimum fungsi menggunakan metode interpolasi kuadratik
alpha_min <- quadraticinterpolation(phi.f, l, u, eps)

# Hasil
cat("Nilai alpha yang meminimalkan fungsi adalah:", alpha_min, "\n")

## Nilai alpha yang meminimalkan fungsi adalah: -0.4856592

cat("Nilai minimum fungsi adalah:", phi.f(alpha_min), "\n")

## Nilai minimum fungsi adalah: -0.3100079

2. Newton-Raphson

Metode Newton-Raphson adalah teknik optimisasi yang menggunakan pendekatan kuadratik untuk menemukan titik minimum atau akar dari suatu fungsi. Ini didasarkan pada ekspansi seri Taylor dari fungsi dan menggunakan turunan pertama dan kedua.

Algoritma:

1. Mulai dengan tebakan awal \(\lambda_1\).
   
2. Hitung nilai fungsi \(f(\lambda)\), turunan pertama \(f'(\lambda)\), dan turunan kedua \(f''(\lambda)\).
   
3. Gunakan rumus:
   \[ \lambda_{i+1} = \lambda_i - \frac{f'(\lambda_i)}{f''(\lambda_i)} \]
   
4. Ulangi hingga \(|f'(\lambda)|\) cukup kecil.

Contoh:
Cari minimum dari \(f(\lambda) = 0.65 - \frac{0.75}{1 + \lambda^2} - 0.65\lambda \tan^{-1}\left(\frac{1}{\lambda}\right)\) dengan \(\lambda_1 = 0.1\) dan \(\epsilon = 0.01\).

Kode R:

# Memuat paket numDeriv
library(numDeriv)

newton.raphson <- function(f, a, b, tol = 1e-5, n = 1000) {
  x0 <- a # Nilai awal diatur ke batas bawah yang diberikan
  k <- numeric(n) # Inisialisasi untuk menyimpan hasil iterasi
  
  # Periksa batas atas dan bawah untuk melihat apakah pendekatan menghasilkan 0
  fa <- f(a)
  if (fa == 0.0) {
    return(a)
  }
  
  fb <- f(b)
  if (fb == 0.0) {
    return(b)
  }
  
  for (i in 1:n) {
    # Turunan pertama f'(x0)
    dx <- genD(func = f, x = x0)$D[1]
    # Menghitung nilai berikutnya x1
    x1 <- x0 - (f(x0) / dx)
    k[i] <- x1 # Menyimpan x1
    # Jika perbedaan antara x0 dan x1 cukup kecil, keluarkan hasilnya.
    if (abs(x1 - x0) < tol) {
      root.approx <- tail(k, n=1)
      res <- list('root approximation' = root.approx, 'iterations' = i)
      return(res)
    }
    x0 <- x1 # Jika Newton-Raphson belum mencapai konvergensi, tetapkan x1 sebagai x0 dan lanjutkan
  }
  warning('Too many iterations in method')
}

# Fungsi objektif yang ingin kita temukan akarnya
f <- function(x) {
  0.65 - 0.75 / (1 + x^2) - 0.65 * atan(1 / x)
}

# Menjalankan Metode Newton-Raphson
result <- newton.raphson(f, a = 0, b = 1, tol = 1e-5, n = 1000)

# Menampilkan hasil
print(result)

## $`root approximation`
## [1] 0
## 
## $iterations
## [1] 2