Optimasi

Dosen : Prof. Dr. Suhartono, M.Kom

Lembaga : Universitas Islam Negeri Maulana Malik Ibrahim Malang

Jurusan : Teknik Informatika

Fakultas : Sains dan Teknologi

library(Ryacas)

## 
## Attaching package: 'Ryacas'

## The following object is masked from 'package:stats':
## 
##     integrate

## The following objects are masked from 'package:base':
## 
##     %*%, det, diag, diag<-, lower.tri, upper.tri

## Error in get(genname, envir = envir) : object 'testthat_print' not found

library(optimization)

## Loading required package: Rcpp

Optimasi adalah suatu proses untuk mencari kondisi yang optimum atau kondisi paling menguntungkan. Optimasi dapat berupa nilai maksimum ataupun nilai minimum tergantung pada penggunaannya.
Jika berkaitan dengan masalah keuntungan, maka keadaan optimum adalah keadaan yang memberikan keuntungan maksimum (maksimasi). Jika berkaitan dengan masalah pengeluaran/pengorbanan, maka keadaan optimum adalah keadaan yang memberikan pengeluaran/pengorbanan minimum (minimasi).

---

Fungsi yang akan diminimumkan atau dimaksimumkan disebut fungsi objektif (objective function). Secara umum, mencari nilai maksimum dan minimum dari suatu fungsi adalah dengan mencari titik-titik kritis dari fungsi, kemudian mensubstitusikan titik kritis tersebut ke turunan pertama dari fungsi. Nilai terbesar adalah nilai maksimum dan nilai terkecil adalah nilai minimum dari fungsi tersebut.

---

Nilai maksimum dan minimum ada yang bersifat global dan lokal. Secara umum, suatu nilai optimum merujuk pada nilai yang bersifat global yaitu nilai maksimum dan minimum dalam suatu fungsi di dalam suatu selang. Namun bisa jadi dalam selang tersebut, terdapat titik-titik kritis lainnya yang membuat nilai menjadi maksimum dan minimum di dalam bagian dari selang. Itulah yang disebut nilai maksimum dan minimum lokal. 

**Optimasi Numerik

Optimasi satu variabel digunakan saat fungsi objektif hanya memiliki 1 variabel penjelas.

Metode yang digunakan :

• Metode golden section • Metode Newton

Metode Golden Section

Golden section merupakan salah satu cara atau metode optimasi numerik yang dapat diterapkan untuk fungsi yang bersifat unimodal.

Ide dasar metode ini adalah memanfaatkan nilai yang lama sebagai nilai yang baru, secara iteratif. Sebagai akibatnya, rentang/ interval awal variabel yang dipilih semakin lama akan semakin menyempit, karena ada sebagian sub-interval variabel yang dieliminasi, hingga diperoleh tingkat konvergensi yang diinginkan.

Algoritma Golden Section (Untuk nilai minimum)

1. Tentukan selang [a, b] yang memuat nilai minimum. Dapat dilihat dengan menggunakan grafik fungsi

2. Perkecil selang menjadi [a’, b’] yang memuat nilai minimum atau maksimum. Kriteria pemilihan a’ dan b’ adalah nilai diantara a dan b, sesuai dengan golden ratio

a’ = a + d b’ = a - d

dengan d = R (b-a)

Tentukan x1 dan x2 x1 = b - (b-a)/R x2 = a + (b-a)/R

Hitung f(x1) dan f(x2)

Jika f(x1) > f(x2) maka [a’,b’]=[x1,b] Jika f(x1) < f(x2) maka [a’,b’]=[a,x2]

3. Iterasi sampai |b’-a’| lebih kecil dari nilai tolerans

Catatan : Untuk nilai maksimum, gunakan algoritma kebalikannya.

Metode Golden Section untuk nilai minimum

goldenMin <- function (f, a, b,tol = 0.0000001) {
ratio <- 2 / ( sqrt (5) +1)
x1 <- b - ratio * (b - a)
x2 <- a + ratio * (b - a)
f1 <- f(x1)
f2 <- f(x2)

while (abs (b - a) > tol ) {
if (f2 > f1) {
b <- x2
x2 <- x1
f2 <- f1
x1 <- b - ratio * (b - a)

f1 <- f(x1)
} else {
  a <- x1
  x1 <- x2
  f1 <- f2
  x2 <- a + ratio * (b - a)
  f2 <- f(x2)
  }
  }
return ((a + b) / 2)
}

Metode golden section untuk nilai maksimum

goldenMax <- function (f, a, b,tol = 0.0000001) {
ratio <- 2 / ( sqrt (5) +1)
x1 <- b - ratio * (b - a)
x2 <- a + ratio * (b - a)
f1 <- f(x1)
f2 <- f(x2)

while (abs (b - a) > tol ) {
if (f2 < f1) {
b <- x2
x2 <- x1
f2 <- f1
x1 <- b - ratio * (b - a)

f1 <- f(x1)
} else {
  a <- x1
  x1 <- x2
  f1 <- f2
  x2 <- a + ratio * (b - a)
  f2 <- f(x2)
  }
  }
return ((a + b) / 2)
}

Contoh :

Mencari nilai minimum dari f(x)=|x−3.5|+(x−2)2

f <- function (x) { abs(x -3.5) + (x -2) ^2}
curve(f)

goldenMin (f ,1 ,2)

---

## [1] 2

---

goldenMin (f ,1 ,5)

---

## [1] 2.5

---

goldenMin (f ,3 ,5)

---

## [1] 3

Mencari nilai maksimum dari f(x)=2sinx−x210

di dalam interval 0 sampai 4

g <- function (x) { 2 * sin(x) - (x^2/10)}
curve(g)

goldenMax (g ,0 ,4)

---

## [1] 1.427552

Metode Newton Metode Newton Raphson lebih cepat dibanding Golden Section Search. Jika suatu fungsi memiliki turunan pertama dan kedua, maka nilai minimum dapat menggunakan metode Newton Raphson:

Xn=Xn−1−f′(Xn−1)f′′(Xn−1)

Iterasi berhenti jika f’(xn-1) dekat dengan 0 atau lebih kecil dari nilai tolerans.

newtonr <- function (fx , x0 =1){
fx1 <- deriv (fx ,"x") # turunan pertama
fx2 <- deriv (D(fx ,"x"),"x") # turunan kedua
er <- 1000
while(er > 1e-6){
x <- x0
f1 <- attr ( eval (fx1),"gradient")[1]
f2 <- attr ( eval (fx2),"gradient")[1]
er <- abs(f1) # bisa juga e <- abs (x1 -x0)
x1 <- x0 - f1/f2
x0 <- x1
}
return (x1)
}

Contoh :

Hitung nilai minimum untuk fungsi f(x)=4x2−3x−7

fx <- expression (4*x^2 - 3*x - 7)
newtonr (fx ,3)

---

## [1] 0.375

Hitung nilai minimum untuk fungsi f(x)=exp(−x)+x4

fx <- expression ( exp(-x) + x^4)
newtonr (fx)

---

## [1] 0.5282519

Hitung nilai minimum untuk fungsi f(x)=x2−x

fx <- expression (x^2 - x)
newtonr (fx)

---

## [1] 0.5

Referensi https://rpubs.com/annebel/optimasi