Optimization

Optimasi adalah jantung banyak masalah teknik: biaya produksi diturunkan, galat model diperkecil, energi sistem diminimalkan — semuanya bermuara pada satu pertanyaan, di titik mana fungsi mencapai nilai terkecilnya? MATLAB membawa tiga penjawab: fminbnd untuk fungsi satu variabel pada rentang terbatas, fminsearch untuk fungsi banyak variabel tanpa batasan, dan fmincon untuk masalah ber-constraint (Optimization Toolbox). Sebelum memakainya, kita perlu paham satu konsep yang sering menjebak: local minimum.

Local Minimum vs Global Minimum #

Fungsi multimodal punya banyak lembah. Lembah terdalam di seluruh wilayah disebut global minimum; lembah lain disebut local minimum — turunannya nol, tetapi bukan titik terendah keseluruhan. Contoh klasik: g(x) = (x^2 - 1)^2 + 0.3x, fungsi dua sumur dengan dasar sumur kiri (dekat x = -1) lebih dalam daripada sumur kanan (dekat x = +1).

Algoritma minimisasi hanya melihat sekeliling titik yang sedang dievaluasi. Akibatnya, bracket pencarian menentukan lembah mana yang ditemukan:

g = @(x) (x.^2 - 1).^2 + 0.3*x;
[xKanan, fKanan] = fminbnd(g, 0.4, 1.5);
[xKiri,  fKiri]  = fminbnd(g, -1.5, -0.4);
fprintf('bracket kanan : x = %.6f, f = %.6f  (local)\n', xKanan, fKanan);
fprintf('bracket kiri  : x = %.6f, f = %.6f  (global)\n', xKiri, fKiri);

Output yang Dihasilkan:

bracket kanan : x = 0.960155, f = 0.294146  (local)
bracket kiri  : x = -1.035579, f = -0.305428  (global)

Bracket [0.4, 1.5] hanya memuat sumur kanan, sehingga algoritma melaporkan x = 0.96 dengan nilai 0.294 — padahal sumur kiri lebih dalam (-0.305). Tidak ada galat di sini; pembatasan rentanglah yang memutuskan jawaban. Strategi praktisnya: jalankan pencarian dari beberapa bracket atau titik awal yang berbeda, lalu bandingkan nilai f pada masing-masing hasil.

fminbnd: Minimum Satu Variabel pada Bracket #

Panggilan dasarnya: [xmin, fmin] = fminbnd(f, a, b) dengan f function handle dan [a, b] bracket pencarian. Di balik layar, fminbnd menggabungkan golden section search dengan successive parabolic interpolation: algoritma mengecilkan bracket secara terarah sambil memanfaatkan informasi kelengkungan parabola dari tiga titik terbaik. Konvergensi dikontrol toleransi TolX (default sekitar 1e-4).

f = @(x) (x - 2).^2 + 3;
[xmin, fmin, exitflag] = fminbnd(f, 0, 10);
fprintf('fminbnd   : x* = %.6f, f(x*) = %.6f, exitflag = %d\n', ...
        xmin, fmin, exitflag);

opt = optimset('TolX', 1e-8);            % perketat toleransi
xketat = fminbnd(f, 0, 10, opt);
fprintf('TolX 1e-8 : x* = %.9f\n', xketat);

Output yang Dihasilkan:

fminbnd   : x* = 2.000000, f(x*) = 3.000000, exitflag = 1
TolX 1e-8 : x* = 2.000000000

Mari kita bedah baris-baris kode di atas:

1. Baris 2 ([xmin, fmin, exitflag] = fminbnd(f, 0, 10)): tiga keluaran — titik minimum, nilai fungsi di titik itu, dan exitflag; nilai 1 berarti algoritma konvergen sesuai toleransi.
2. Baris 7 (xketat = fminbnd(f, 0, 10, opt)): struct opsi hasil optimset('TolX', 1e-8) diberikan sebagai argumen keempat; bracket berhenti mengecil ketika lebarnya di bawah TolX, sehingga hasil ketat memuat lebih banyak digit benar.

fminsearch: Nelder-Mead untuk Banyak Variabel #

Fungsi banyak variabel tidak punya “bracket”. fminsearch(f, x0) memulai dari titik awal x0 (vektor) lalu berjalan dengan algoritma Nelder-Mead: algoritma memelihara simplex — segitiga pada dua dimensi, tetrahedron pada tiga dimensi — dan menggesernya lewat operasi refleksi, ekspansi, dan kontraksi sampai simplex mengecil di sekitar minimum. Keunggulan besar: Nelder-Mead tidak membutuhkan turunan, cocok untuk fungsi yang mahal atau tidak mulus.

h = @(v) (v(1) - 1).^2 + 2*(v(2) + 3).^2 + 7;   % mangkuk elips
v0 = [0 0];
[vA, fA] = fminsearch(h, v0);
[vB, fB] = fminsearch(h, v0, optimset('TolX', 1e-9));
fprintf('fminsearch default   : x = %.6f, y = %.6f, f = %.6f\n', ...
        vA(1), vA(2), fA);
fprintf('fminsearch TolX 1e-9 : x = %.6f, y = %.6f, f = %.6f\n', ...
        vB(1), vB(2), fB);

Output yang Dihasilkan:

fminsearch default   : x = 1.000025, y = -2.999986, f = 7.000000
fminsearch TolX 1e-9 : x = 1.000000, y = -3.000000, f = 7.000000

Jawaban sebenarnya adalah (1, -3) dengan nilai 7. Dengan toleransi default, fminsearch berhenti di 1.000025 dan -2.999986 — cukup dekat, tetapi empat digit terakhirnya belum benar; memperketat TolX merapikannya. Inilah sifat algoritma iteratif: presisi akhir adalah pilihan kita, bukan kebetulan.

Grid Search: Brute Force yang Selalu Tersedia #

Sebelum optimasi cerdas, ada senjata paling sederhana: evaluasi fungsi pada grid titik-titik rapat, lalu ambil yang terkecil dengan min. Grid search tidak mengenal local minimum sepanjang grid menutupi seluruh wilayah pencarian, dan kodenya berjalan di lingkungan MATLAB mana pun.

xg = linspace(-2, 2, 4001);
fg = g(xg);
[fm, idx] = min(fg);
fprintf('grid search 4001 titik: x = %.6f, f = %.6f\n', xg(idx), fm);

Output yang Dihasilkan:

grid search 4001 titik: x = -1.036000, f = -0.305428

Grid 4001 titik menemukan sumur dalam (-1.036, -0.305) tanpa perlu memilih bracket — resolusinya 4/4000 = 0.001. Biayinya: jumlah evaluasi fungsi sama dengan jumlah titik grid, mahal untuk fungsi yang lambat atau dimensi banyak; di situ fminbnd/fminsearch jauh lebih hemat.

Constraint dan fmincon #

Dunia nyata memasang pagar: modal terbatas, dimensi komponen harus di antara batas manufaktur, total berat tidak boleh melebihi kapasitas. Constraint linear ditulis sebagai A*x <= b. Solver toolbox untuk masalah semacam ini:

% MATLAB Optimization Toolbox (tidak tersedia di Octave)
x = fmincon(fun, x0, A, b, Aeq, beq, lb, ub);

Baris tersebut mencari minimum fun mulai dari x0 dengan constraint pertidaksamaan A*x <= b, kesamaan Aeq*x = beq, dan batas variabel lb <= x <= ub. Tanpa toolbox, constraint sering bisa diakali: hukum penalti menambahkan konstanta besar ke fun saat constraint dilanggar, mengubah wilayah terlarang menjadi lembah tinggi yang dihindari fminsearch.

Mengevaluasi Hasil Optimasi #

Algoritma minimisasi bisa berhenti karena konvergen — atau karena kehabisan langkah. Tiga pemeriksaan penutup:

1. Baca exitflag: nilai positif berarti konvergen sesuai toleransi; nilai 0 atau negatif berarti iterasi berhenti prematur.
2. Cek titik stasioner: turunan numerik di sekitar x* harus mendekati nol. Untuk fungsi satu variabel, central difference cukup: (f(x*+h) - f(x*-h))/(2h).
3. Uji dari beberapa titik awal: hasil yang sama dari berbagai titik awal adalah bukti kuat minimum global; hasil yang berbeda-beda berarti fungsi multimodal.

Potongan berikut memakai f dan xketat — hasil fminbnd dengan TolX 1e-8 dari bagian sebelumnya:

hh = 1e-6;
turunan = (f(xketat + hh) - f(xketat - hh))/(2*hh);
fprintf('turunan numerik di x*: %.2e\n', turunan);

Output yang Dihasilkan:

turunan numerik di x*: 0.00e+00

Turunan bernilai nol persis di titik hasil — pemeriksaan stasioner lolos untuk parabola uji kita.

Berkas contoh.m pada bagian bawah halaman merangkai seluruh bab: fminbnd dengan exitflag dan toleransi ketat, perbandingan local/global minimum, fminsearch dua dimensi, grid search, dan pemeriksaan turunan.

Ringkasan #

fminbnd(f, a, b) mencari minimum fungsi satu variabel di dalam bracket; bracket menentukan lembah mana yang dilaporkan pada fungsi multimodal. fminsearch(f, x0) menjelajah fungsi banyak variabel dengan Nelder-Mead tanpa turunan; presisi dikendalikan TolX lewat optimset. Grid search adalah padanan brute force yang kebal local minimum tetapi mahal evaluasi. Constraint formal diserahkan pada fmincon (Optimization Toolbox, MATLAB-only) atau penalti manual. Setiap hasil optimasi diverifikasi dengan exitflag, cek turunan di titik minimum, dan pengulangan dari beberapa titik awal.