Bab 7: Optimasi Kontinu

Mencari Solusi Terbaik: Minima, Maxima, dan Konstrain

Tujuan Utama

Hampir semua algoritma Machine Learning bermuara pada satu hal: Meminimalkan Error (Loss Function) atau Memaksimalkan Likelihood. Optimasi adalah alat untuk mencapai tujuan tersebut.

Peta Konsep

                            graph TD
                                A[Masalah Optimasi] --> B[Unconstrained]
                                A --> C[Constrained]
                                B --> D[Gradient Descent]
                                B --> E["Stochastic Gradient Descent (SGD)"]
                                B --> F[Newton Method]
                                C --> G[Lagrange Multipliers]
                                C --> H[Dualitas]
                                A --> I[Convex Optimization]
                                I --> J[Global Minimum Guaranteed]

1. Gradient Descent

Bayangkan Anda berada di pegunungan yang berkabut dan ingin turun ke lembah terdalam. Strategi paling sederhana adalah melihat ke sekeliling dan melangkah ke arah yang paling curam menurun. Ini adalah intuisi dari Gradient Descent.

Untuk meminimalkan fungsi $f(\boldsymbol{x})$, kita memperbarui parameter $\boldsymbol{x}$ secara iteratif:

\boldsymbol{x}_{t+1} = \boldsymbol{x}_t - \gamma \nabla f(\boldsymbol{x}_t)

$-\nabla f(\boldsymbol{x}_t)$: Arah turunan tercuram (negatif gradien).
$\gamma$: Step size atau Learning Rate (seberapa besar langkah yang diambil).

Contoh Perhitungan: Gradient Descent

Kita ingin meminimalkan $f(x) = x^2$. Turunannya adalah $f'(x) = 2x$.

Misalkan kita mulai di $x_0 = 3$ dengan learning rate $\gamma = 0.1$.

Iterasi 1:

x_1 = x_0 - \gamma f'(x_0) = 3 - 0.1(2 \times 3) = 3 - 0.6 = 2.4

Iterasi 2:

x_2 = x_1 - \gamma f'(x_1) = 2.4 - 0.1(2 \times 2.4) = 2.4 - 0.48 = 1.92

Kita lihat nilai $x$ semakin mendekati 0 (minimum global).

2. Optimasi Terkendala (Constrained Optimization)

Seringkali kita ingin mencari nilai optimal, tapi dengan batasan (constraint). Contoh: "Minimalkan biaya produksi, TAPI kualitas tidak boleh di bawah standar X".

Masalah ini diformulasikan sebagai:

\begin{align*} \min_{\boldsymbol{x}} \quad & f(\boldsymbol{x}) \\ \text{subject to} \quad & g_i(\boldsymbol{x}) \le 0 \quad \text{(pertidaksamaan)} \\ & h_j(\boldsymbol{x}) = 0 \quad \text{(persamaan)} \end{align*}

Lagrange Multipliers

Kita bisa mengubah masalah terkendala menjadi tak terkendala dengan menggunakan Lagrangian:

\mathcal{L}(\boldsymbol{x}, \boldsymbol{\lambda}, \boldsymbol{\nu}) = f(\boldsymbol{x}) + \sum \lambda_i g_i(\boldsymbol{x}) + \sum \nu_j h_j(\boldsymbol{x})

Variabel baru $\lambda_i$ dan $\nu_j$ disebut Lagrange Multipliers. Solusi optimal berada di titik sadel (saddle point) dari Lagrangian.

Contoh Konsep: Lagrange Multiplier

Minimalkan $f(x, y) = x^2 + y^2$ dengan kendala $x + y = 1$ (atau $x + y - 1 = 0$).

Lagrangian:

\mathcal{L}(x, y, \nu) = x^2 + y^2 + \nu(x + y - 1)

Cari turunan parsial dan samakan dengan 0:

\begin{align*} \frac{\partial \mathcal{L}}{\partial x} &= 2x + \nu = 0 \implies x = -\nu/2 \\ \frac{\partial \mathcal{L}}{\partial y} &= 2y + \nu = 0 \implies y = -\nu/2 \\ \frac{\partial \mathcal{L}}{\partial \nu} &= x + y - 1 = 0 \end{align*}

Substitusi $x$ dan $y$ ke persamaan kendala: $(-\nu/2) + (-\nu/2) - 1 = 0 \implies -\nu = 1 \implies \nu = -1$.

Maka $x = 1/2, y = 1/2$. Ini adalah titik minimum pada garis kendala.

3. Convex Optimization

Kelas masalah optimasi yang paling "enak". Jika fungsi tujuan $f(\boldsymbol{x})$ adalah Convex (cembung, berbentuk mangkuk) dan himpunan kendalanya juga convex, maka:

Setiap Local Minimum adalah Global Minimum.
Kita bisa menjamin bahwa kita akan menemukan solusi terbaik.

Banyak metode ML (seperti Support Vector Machines, Linear Regression, Logistic Regression) adalah masalah optimasi konveks. Namun, Deep Learning (Neural Networks) umumnya Non-Convex, yang membuatnya jauh lebih sulit secara teoritis, meski Gradient Descent sering berhasil dengan baik secara praktis.

Bab 6: Probabilitas Kembali ke Menu Utama