1 · Konsep dasar
- Unimodal: fungsi punya satu puncak atau satu lembah (asumsi metode numerik)
- Interval ketidakpastian: interval tempat optimum berada; dipersempit sampai panjang akhir l
- Bila tidak unimodal (mis. dua lembah) → sebagian interval bisa dibuang salah → hanya optimal lokal
2 · Peta & perbandingan metode
| Metode | Basis | Input | f baru |
|---|---|---|---|
| Direct search tak berpembatas | nilai f | x(1), l | 1 |
| Newton tak berpembatas | f′, f″ | x(1), ε | – |
| Dichotomous a≤x≤b | nilai f | [a,b], ε, l | 2 |
| Fibonacci a≤x≤b | nilai f | [a,b], ε, l | 1 |
| Golden section a≤x≤b | nilai f | [a,b], l | 1 |
| Bisection a≤x≤b | f′ | [a,b], ε | – |
Direct search & Newton butuh titik awal; metode lain butuh interval [a,b].
3 · Direct search
- Langkah λ = l/2; arah d=+1 (kanan) / −1 (kiri)
- Mulai x(1): bila f(x+λd) membaik → maju; jika memburuk → balik d=−1; jika sama → berhenti
- x(k+1)=x(k)+λd selama membaik; berhenti saat f(x+λd) tak lebih baik
Slide: min (x−1)², l=0,01 (λ=0,005), x(1)=3: f(3,005)=4,020 > f(3)=4 → d=−1; 401 iterasi; berhenti di x=1,000 → interval [0,995; 1,005] (panjang 2λ=l)
† (x−2)², x(1)=5, λ=0,05: x=5−0,05k; berhenti di x=2,00 (k=60), interval [1,95; 2,05].
4 · Newton (optimisasi)
Pendekatan kuadratik di x(k):
Syarat: f dapat diturunkan 2×, titik awal; f″(x(k))=0 → pembagian nol (mis. x⁴−2x di x=0)
Slide: min (x−1)², f′=2(x−1), f″=2, x(1)=0: x(2)=0−(−2)/2=1; x(3)=1 → stop
† 3x²−6x+2 dari 10: 10−54/6=1 (kuadrat: 1 langkah). x³ di x=1: f=1, f′=3, f″=6 → x=1−3/6=0,5
Newton optimisasi: f′/f″. Newton-Raphson akar: f/f′.
5 · Dichotomous search
Slide: min (x−1)², [−1,2], ε=0,0001, l=0,01
| k | u | v | f(u) | f(v) |
|---|---|---|---|---|
| 1 | 0,5 | 0,5001 | 0,25005 | 0,24995 |
| 2 | 1,2499 | 1,25 | 0,062463 | 0,062513 |
k=1 [−1;2]: f(u)>f(v) → [u,b]=[0,5;2]. k=2: f(u)=0,062463 ≤ f(v)=0,062513 → [a,v]=[0,5;1,25]. 10 iterasi: [0,9980; 1,0039]. † maks −(x−3)², [0,4], ε=0,02: u=1,99, v=2,01; f(u)<f(v) → [1,99;4].
6 · Fibonacci search
F0=F1=1, Fn=Fn−1+Fn−2: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987 (n=0..15)
- min: f(u)≤f(v) → b=v, v←u lama, hitung u baru. Else a=u, u←v lama, hitung v baru (1 evaluasi baru)
- Iterasi k=n: u=v → pakai v=u+ε (itulah fungsi ε)
Slide: [−1,2], l=0,01: (b−a)/l=300 → F12=233<300<F13=377 → n=13. u1=0,1459, v1=0,8541 → akhir [0,9973; 1,0053]
[−2,8], l=0,1: 100 → n=11 (F10=89<100). b−a=10, l=0,01: 1000 → n=16 (F15=987).
7 · Golden section
- min: f(u)≤f(v) → a tetap, b=v, v←u lama, u baru = a+(1−γ)(b−a)
- f(u)>f(v) → a=u, b tetap, u←v lama, v baru = a+γ(b−a)
- Titik lama dipakai ulang → 1 evaluasi baru/iterasi
Slide: [−1,2]: u1=0,1460, v1=0,8540, f=0,7293 > 0,0213 → a=0,146, u2=0,8542 (=v1), v2=1,2918. 13 iterasi: [0,9969; 1,0062]
[0,5]: u=0,382×5=1,910; v=0,618×5=3,090.
8 · Bisection (turunan)
Contoh slide: min (x−1)², [−1,2], ε=0,001, f′=2(x−1)
| k | a | b | m | f′(m) |
|---|---|---|---|---|
| 1 | −1 | 2 | 0,5 | −1,0 |
| 2 | 0,5 | 2 | 1,25 | 0,5 |
| 3 | 0,5 | 1,25 | 0,875 | −0,25 |
12 iterasi → [0,9995; 1,0010]. Panjang setelah k pembagian = (b−a)/2k; † [−1,2], ≤0,01: 3/2k≤0,01 → k=9. † x⁴−4x pada [0,3]: [0;1,5], [0,75;1,5], [0,75;1,125].
9 · Aturan arah update (min vs maks)
| Min | Maks | |
|---|---|---|
| buang kanan → [a,v] | f(u) ≤ f(v) | f(u) ≥ f(v) |
| buang kiri → [u,b] | f(u) > f(v) | f(u) < f(v) |
| bisection → [a,m] | f′(m) > 0 | f′(m) < 0 |
| bisection → [m,b] | f′(m) < 0 | f′(m) > 0 |
| direct search: lanjut d=+1 | f(x+λ) < f(x) | f(x+λ) > f(x) |
| direct search: balik d=−1 | f(x+λ) > f(x) | f(x+λ) < f(x) |
f′(m)=0 → berhenti. Min: f′>0 berarti f naik di m → minimum di kiri. Maks: f′>0 berarti masih naik → maksimum di kanan: −(x−1)² pada [−1,2], m=0,5, f′=1 → [0,5;2]. Min pada [0,4], m=2, f′=3>0 → [0;2].