Optimization

Mencari Maksimum, Minimum, dan Solusi Constrained

calculus

optimization

lagrange

KKT

First-order conditions, second-order conditions, Lagrange multipliers, KKT conditions, dan aplikasi dalam econometrics dan ML.

Why This Matters for Your Work

Optimization adalah inti dari hampir semua metode statistik dan ML: kita selalu mencari parameter yang meminimalkan suatu loss atau memaksimalkan suatu objective. Memahami matematika di balik optimization memberi kita pemahaman yang jauh lebih dalam tentang mengapa algoritma bekerja (atau tidak bekerja).

Contoh langsung: - OLS: meminimalkan $\sum (y_i - x_i'\beta)^2$ — unconstrained quadratic optimization - MLE: memaksimalkan $\sum \ln f(x_i; \theta)$ — unconstrained optimization - Regularized regression (Ridge/Lasso): minimisasi dengan penalty — constrained atau penalized optimization - Portfolio optimization: maximize return subject to variance constraint — Lagrange multipliers - SVM: maximize margin subject to classification constraints — KKT conditions

1 Setup: Terminologi Dasar

Kita mau mencari: \[\min_{\mathbf{x} \in \mathcal{X}} f(\mathbf{x}) \quad \text{atau} \quad \max_{\mathbf{x} \in \mathcal{X}} f(\mathbf{x})\]

di mana $f: \mathbb{R}^n \to \mathbb{R}$ adalah objective function dan $\mathcal{X}$ adalah feasible set.

Jenis optimization: - Unconstrained: $\mathcal{X} = \mathbb{R}^n$ - Equality constrained: $\mathcal{X} = \{\mathbf{x} : h_i(\mathbf{x}) = 0, i = 1, \ldots, m\}$ - Inequality constrained: $\mathcal{X} = \{\mathbf{x} : g_j(\mathbf{x}) \leq 0, j = 1, \ldots, k\}$

Local vs. Global: - Local minimum $\mathbf{x}^*$: $f(\mathbf{x}^*) \leq f(\mathbf{x})$ untuk semua $\mathbf{x}$ di sekitar $\mathbf{x}^*$ - Global minimum: $f(\mathbf{x}^*) \leq f(\mathbf{x})$ untuk semua $\mathbf{x} \in \mathcal{X}$

Jika $f$ convex dan $\mathcal{X}$ convex set, setiap local minimum adalah global minimum.

2 Unconstrained Optimization: First-Order Conditions (FOC)

First-Order Necessary Condition

Jika $\mathbf{x}^*$ adalah local minimum (atau maximum) dari $f$ yang differentiable, maka: \[\nabla f(\mathbf{x}^*) = \mathbf{0}\]

Titik yang memenuhi kondisi ini disebut critical points atau stationary points.

Penting: FOC hanya necessary, bukan sufficient! Critical point bisa jadi minimum, maximum, atau saddle point.

3 Second-Order Conditions (SOC)

Second-Order Sufficient Conditions

Misalkan $\mathbf{x}^*$ memenuhi FOC ($\nabla f(\mathbf{x}^*) = \mathbf{0}$). Maka:

Jika $H_f(\mathbf{x}^*)$ positive definite: $\mathbf{x}^*$ adalah local minimum
Jika $H_f(\mathbf{x}^*)$ negative definite: $\mathbf{x}^*$ adalah local maximum
Jika $H_f(\mathbf{x}^*)$ indefinite: $\mathbf{x}^*$ adalah saddle point

Kasus univariate ($n=1$): - $f'(x^*) = 0$ dan $f''(x^*) > 0$: local minimum - $f'(x^*) = 0$ dan $f''(x^*) < 0$: local maximum

Worked Example: OLS via FOC

Problem: Cari $\hat{\beta}$ yang meminimalkan $L(\beta) = \|y - X\beta\|^2$.

FOC: \[\nabla_\beta L(\beta) = -2X'y + 2X'X\beta = \mathbf{0}\] \[X'X\hat{\beta} = X'y\] \[\hat{\beta} = (X'X)^{-1}X'y \quad \text{(jika } X'X \text{ invertible)}\]

SOC: \[H_L(\beta) = 2X'X\]

Jika $X$ full column rank: $X'X$ positive definite → Hessian positive definite → $\hat{\beta}$ adalah global minimum (bukan hanya local!).

Ini konfirmasi formal bahwa OLS punya unique solution yang merupakan global minimizer.

4 Constrained Optimization: Lagrange Multipliers

Untuk problem dengan equality constraints: \[\min_{\mathbf{x}} f(\mathbf{x}) \quad \text{subject to} \quad h_i(\mathbf{x}) = 0, \quad i = 1, \ldots, m\]

Lagrangian dan Lagrange Conditions

Definisikan Lagrangian: \[\mathcal{L}(\mathbf{x}, \boldsymbol{\lambda}) = f(\mathbf{x}) + \sum_{i=1}^m \lambda_i h_i(\mathbf{x})\]

di mana $\lambda_i$ adalah Lagrange multipliers.

Necessary conditions (di titik optimal $\mathbf{x}^*$): \[\frac{\partial \mathcal{L}}{\partial \mathbf{x}} = \nabla f(\mathbf{x}^*) + \sum_{i=1}^m \lambda_i \nabla h_i(\mathbf{x}^*) = \mathbf{0}\] \[h_i(\mathbf{x}^*) = 0, \quad i = 1, \ldots, m\]

Interpretasi $\lambda_i$: shadow price — laju perubahan optimal value terhadap perubahan constraint level.

Worked Example: Lagrange Multipliers

Problem: Maksimalkan $f(x, y) = xy$ subject to $x + y = 10$.

Setup Lagrangian: \[\mathcal{L}(x, y, \lambda) = xy + \lambda(x + y - 10)\]

FOC: \[\frac{\partial \mathcal{L}}{\partial x} = y + \lambda = 0 \implies \lambda = -y\] \[\frac{\partial \mathcal{L}}{\partial y} = x + \lambda = 0 \implies \lambda = -x\] \[\frac{\partial \mathcal{L}}{\partial \lambda} = x + y - 10 = 0\]

Dari dua persamaan pertama: $-y = -x \implies x = y$. Substitusi ke constraint: $x + x = 10 \implies x = y = 5$.

Optimal: $f(5, 5) = 25$, dengan $\lambda = -5$.

Interpretasi $\lambda$: jika constraint berubah menjadi $x + y = 11$, optimal value akan naik sekitar $|\lambda| = 5$ menjadi $\approx 30$.

5 KKT Conditions (Inequality Constraints)

Untuk problem yang lebih umum dengan inequality constraints: \[\min_{\mathbf{x}} f(\mathbf{x}) \quad \text{s.t.} \quad g_j(\mathbf{x}) \leq 0, \; j = 1,\ldots,k \quad \text{dan} \quad h_i(\mathbf{x}) = 0, \; i = 1,\ldots,m\]

KKT Conditions (Karush-Kuhn-Tucker)

Lagrangian: $\mathcal{L}(\mathbf{x}, \boldsymbol{\mu}, \boldsymbol{\lambda}) = f(\mathbf{x}) + \sum_j \mu_j g_j(\mathbf{x}) + \sum_i \lambda_i h_i(\mathbf{x})$

Necessary conditions di $\mathbf{x}^*$:

Stationarity: $\nabla_\mathbf{x} \mathcal{L} = \nabla f(\mathbf{x}^*) + \sum_j \mu_j \nabla g_j(\mathbf{x}^*) + \sum_i \lambda_i \nabla h_i(\mathbf{x}^*) = \mathbf{0}$
Primal feasibility: $g_j(\mathbf{x}^*) \leq 0$ dan $h_i(\mathbf{x}^*) = 0$
Dual feasibility: $\mu_j \geq 0$ untuk semua $j$
Complementary slackness: $\mu_j g_j(\mathbf{x}^*) = 0$ untuk semua $j$

Complementary slackness artinya: $\mu_j > 0 \implies g_j(\mathbf{x}^*) = 0$ (constraint active) atau $g_j(\mathbf{x}^*) < 0 \implies \mu_j = 0$ (constraint inactive/slack).

Connection: SVM dan Lasso

SVM (Support Vector Machine): Formulasi primalnya adalah constrained optimization dengan KKT conditions. Dual problem (yang lebih mudah disolve) diturunkan langsung dari KKT. Support vectors adalah data points di mana complementary slackness active.

Lasso Regression: Meminimalkan $\|y - X\beta\|^2$ subject to $\|\beta\|_1 \leq t$. KKT conditions di sini menjelaskan mengapa Lasso menghasilkan sparse solution (banyak $\beta_j = 0$) — ini adalah properti geometri dari $\ell_1$ constraint.

Ridge Regression: Equivalent problem $\|y - X\beta\|^2 + \lambda\|\beta\|^2$ — di sini $\lambda$ adalah Lagrange multiplier!

6 Gradient Descent sebagai Iterative Optimization

Untuk unconstrained problem, gradient descent adalah algoritma iteratif: \[\mathbf{x}_{t+1} = \mathbf{x}_t - \alpha_t \nabla f(\mathbf{x}_t)\]

Convergence: Jika $f$ strongly convex dan $\alpha$ dipilih tepat, gradient descent converges ke global minimum.

Variants: - Newton’s method: menggunakan Hessian untuk curvature information \[\mathbf{x}_{t+1} = \mathbf{x}_t - [H_f(\mathbf{x}_t)]^{-1} \nabla f(\mathbf{x}_t)\] - Coordinate descent: update satu koordinat setiap iterasi — berguna untuk Lasso

7 Key Takeaways

7.1 Poin Utama

FOC: $\nabla f(\mathbf{x}^*) = \mathbf{0}$ — necessary untuk optimality (tapi tidak sufficient)
SOC: Hessian PD → local min; ND → local max; indefinite → saddle point
Lagrange multipliers: untuk equality constraints — $\nabla f = -\lambda \nabla h$ di optimal
KKT conditions: generalisasi ke inequality constraints — complementary slackness adalah kunci
Convex problem: setiap local optimum = global optimum
OLS: global minimum karena loss function strictly convex ($H = 2X'X$ PD)
SVM, Lasso: KKT conditions menjelaskan sifat sparsity dan support vectors

Sebelumnya: ← Multivariate Calculus | Selanjutnya: Taylor Series →

--- title: "Optimization" subtitle: "Mencari Maksimum, Minimum, dan Solusi Constrained" description: "First-order conditions, second-order conditions, Lagrange multipliers, KKT conditions, dan aplikasi dalam econometrics dan ML." categories: [calculus, optimization, lagrange, KKT] --- ::: {.callout-note title="Why This Matters for Your Work"} Optimization adalah inti dari hampir semua metode statistik dan ML: kita selalu mencari parameter yang meminimalkan suatu loss atau memaksimalkan suatu objective. Memahami matematika di balik optimization memberi kita pemahaman yang jauh lebih dalam tentang *mengapa* algoritma bekerja (atau tidak bekerja). Contoh langsung: - **OLS**: meminimalkan $\sum (y_i - x_i'\beta)^2$ — unconstrained quadratic optimization - **MLE**: memaksimalkan $\sum \ln f(x_i; \theta)$ — unconstrained optimization - **Regularized regression (Ridge/Lasso)**: minimisasi dengan penalty — constrained atau penalized optimization - **Portfolio optimization**: maximize return subject to variance constraint — Lagrange multipliers - **SVM**: maximize margin subject to classification constraints — KKT conditions ::: ## Setup: Terminologi Dasar Kita mau mencari: $$\min_{\mathbf{x} \in \mathcal{X}} f(\mathbf{x}) \quad \text{atau} \quad \max_{\mathbf{x} \in \mathcal{X}} f(\mathbf{x})$$ di mana $f: \mathbb{R}^n \to \mathbb{R}$ adalah **objective function** dan $\mathcal{X}$ adalah feasible set. **Jenis optimization:** - **Unconstrained**: $\mathcal{X} = \mathbb{R}^n$ - **Equality constrained**: $\mathcal{X} = \{\mathbf{x} : h_i(\mathbf{x}) = 0, i = 1, \ldots, m\}$ - **Inequality constrained**: $\mathcal{X} = \{\mathbf{x} : g_j(\mathbf{x}) \leq 0, j = 1, \ldots, k\}$ **Local vs. Global:** - **Local minimum** $\mathbf{x}^*$: $f(\mathbf{x}^*) \leq f(\mathbf{x})$ untuk semua $\mathbf{x}$ di sekitar $\mathbf{x}^*$ - **Global minimum**: $f(\mathbf{x}^*) \leq f(\mathbf{x})$ untuk semua $\mathbf{x} \in \mathcal{X}$ Jika $f$ convex dan $\mathcal{X}$ convex set, setiap local minimum adalah global minimum. ## Unconstrained Optimization: First-Order Conditions (FOC) ::: {.callout-important title="First-Order Necessary Condition"} Jika $\mathbf{x}^*$ adalah local minimum (atau maximum) dari $f$ yang differentiable, maka: $$\nabla f(\mathbf{x}^*) = \mathbf{0}$$ Titik yang memenuhi kondisi ini disebut **critical points** atau **stationary points**. **Penting:** FOC hanya *necessary*, bukan sufficient! Critical point bisa jadi minimum, maximum, atau saddle point. ::: ## Second-Order Conditions (SOC) ::: {.callout-important title="Second-Order Sufficient Conditions"} Misalkan $\mathbf{x}^*$ memenuhi FOC ($\nabla f(\mathbf{x}^*) = \mathbf{0}$). Maka: - Jika $H_f(\mathbf{x}^*)$ **positive definite**: $\mathbf{x}^*$ adalah **local minimum** - Jika $H_f(\mathbf{x}^*)$ **negative definite**: $\mathbf{x}^*$ adalah **local maximum** - Jika $H_f(\mathbf{x}^*)$ **indefinite**: $\mathbf{x}^*$ adalah **saddle point** ::: **Kasus univariate ($n=1$):** - $f'(x^*) = 0$ dan $f''(x^*) > 0$: local minimum - $f'(x^*) = 0$ dan $f''(x^*) < 0$: local maximum ::: {.callout-tip title="Worked Example: OLS via FOC" collapse="true"} **Problem:** Cari $\hat{\beta}$ yang meminimalkan $L(\beta) = \|y - X\beta\|^2$. **FOC:** $$\nabla_\beta L(\beta) = -2X'y + 2X'X\beta = \mathbf{0}$$ $$X'X\hat{\beta} = X'y$$ $$\hat{\beta} = (X'X)^{-1}X'y \quad \text{(jika } X'X \text{ invertible)}$$ **SOC:** $$H_L(\beta) = 2X'X$$ Jika $X$ full column rank: $X'X$ positive definite → Hessian positive definite → $\hat{\beta}$ adalah **global minimum** (bukan hanya local!). Ini konfirmasi formal bahwa OLS punya unique solution yang merupakan global minimizer. ::: ## Constrained Optimization: Lagrange Multipliers Untuk problem dengan equality constraints: $$\min_{\mathbf{x}} f(\mathbf{x}) \quad \text{subject to} \quad h_i(\mathbf{x}) = 0, \quad i = 1, \ldots, m$$ ::: {.callout-important title="Lagrangian dan Lagrange Conditions"} Definisikan **Lagrangian**: $$\mathcal{L}(\mathbf{x}, \boldsymbol{\lambda}) = f(\mathbf{x}) + \sum_{i=1}^m \lambda_i h_i(\mathbf{x})$$ di mana $\lambda_i$ adalah **Lagrange multipliers**. **Necessary conditions** (di titik optimal $\mathbf{x}^*$): $$\frac{\partial \mathcal{L}}{\partial \mathbf{x}} = \nabla f(\mathbf{x}^*) + \sum_{i=1}^m \lambda_i \nabla h_i(\mathbf{x}^*) = \mathbf{0}$$ $$h_i(\mathbf{x}^*) = 0, \quad i = 1, \ldots, m$$ **Interpretasi $\lambda_i$**: shadow price — laju perubahan optimal value terhadap perubahan constraint level. ::: ::: {.callout-tip title="Worked Example: Lagrange Multipliers" collapse="true"} **Problem:** Maksimalkan $f(x, y) = xy$ subject to $x + y = 10$. **Setup Lagrangian:** $$\mathcal{L}(x, y, \lambda) = xy + \lambda(x + y - 10)$$ **FOC:** $$\frac{\partial \mathcal{L}}{\partial x} = y + \lambda = 0 \implies \lambda = -y$$ $$\frac{\partial \mathcal{L}}{\partial y} = x + \lambda = 0 \implies \lambda = -x$$ $$\frac{\partial \mathcal{L}}{\partial \lambda} = x + y - 10 = 0$$ Dari dua persamaan pertama: $-y = -x \implies x = y$. Substitusi ke constraint: $x + x = 10 \implies x = y = 5$. **Optimal**: $f(5, 5) = 25$, dengan $\lambda = -5$. **Interpretasi $\lambda$**: jika constraint berubah menjadi $x + y = 11$, optimal value akan naik sekitar $|\lambda| = 5$ menjadi $\approx 30$. ::: ## KKT Conditions (Inequality Constraints) Untuk problem yang lebih umum dengan inequality constraints: $$\min_{\mathbf{x}} f(\mathbf{x}) \quad \text{s.t.} \quad g_j(\mathbf{x}) \leq 0, \; j = 1,\ldots,k \quad \text{dan} \quad h_i(\mathbf{x}) = 0, \; i = 1,\ldots,m$$ ::: {.callout-important title="KKT Conditions (Karush-Kuhn-Tucker)"} **Lagrangian**: $\mathcal{L}(\mathbf{x}, \boldsymbol{\mu}, \boldsymbol{\lambda}) = f(\mathbf{x}) + \sum_j \mu_j g_j(\mathbf{x}) + \sum_i \lambda_i h_i(\mathbf{x})$ **Necessary conditions** di $\mathbf{x}^*$: 1. **Stationarity**: $\nabla_\mathbf{x} \mathcal{L} = \nabla f(\mathbf{x}^*) + \sum_j \mu_j \nabla g_j(\mathbf{x}^*) + \sum_i \lambda_i \nabla h_i(\mathbf{x}^*) = \mathbf{0}$ 2. **Primal feasibility**: $g_j(\mathbf{x}^*) \leq 0$ dan $h_i(\mathbf{x}^*) = 0$ 3. **Dual feasibility**: $\mu_j \geq 0$ untuk semua $j$ 4. **Complementary slackness**: $\mu_j g_j(\mathbf{x}^*) = 0$ untuk semua $j$ Complementary slackness artinya: $\mu_j > 0 \implies g_j(\mathbf{x}^*) = 0$ (constraint *active*) atau $g_j(\mathbf{x}^*) < 0 \implies \mu_j = 0$ (constraint *inactive/slack*). ::: ::: {.callout-caution title="Connection: SVM dan Lasso"} **SVM (Support Vector Machine)**: Formulasi primalnya adalah constrained optimization dengan KKT conditions. Dual problem (yang lebih mudah disolve) diturunkan langsung dari KKT. Support vectors adalah data points di mana complementary slackness *active*. **Lasso Regression**: Meminimalkan $\|y - X\beta\|^2$ subject to $\|\beta\|_1 \leq t$. KKT conditions di sini menjelaskan *mengapa* Lasso menghasilkan sparse solution (banyak $\beta_j = 0$) — ini adalah properti geometri dari $\ell_1$ constraint. **Ridge Regression**: Equivalent problem $\|y - X\beta\|^2 + \lambda\|\beta\|^2$ — di sini $\lambda$ adalah Lagrange multiplier! ::: ## Gradient Descent sebagai Iterative Optimization Untuk unconstrained problem, gradient descent adalah algoritma iteratif: $$\mathbf{x}_{t+1} = \mathbf{x}_t - \alpha_t \nabla f(\mathbf{x}_t)$$ **Convergence:** Jika $f$ strongly convex dan $\alpha$ dipilih tepat, gradient descent converges ke global minimum. **Variants:** - **Newton's method**: menggunakan Hessian untuk curvature information $$\mathbf{x}_{t+1} = \mathbf{x}_t - [H_f(\mathbf{x}_t)]^{-1} \nabla f(\mathbf{x}_t)$$ - **Coordinate descent**: update satu koordinat setiap iterasi — berguna untuk Lasso ## Key Takeaways ::: {.key-takeaways} ### Poin Utama - FOC: $\nabla f(\mathbf{x}^*) = \mathbf{0}$ — necessary untuk optimality (tapi tidak sufficient) - SOC: Hessian PD → local min; ND → local max; indefinite → saddle point - Lagrange multipliers: untuk equality constraints — $\nabla f = -\lambda \nabla h$ di optimal - KKT conditions: generalisasi ke inequality constraints — complementary slackness adalah kunci - Convex problem: setiap local optimum = global optimum - OLS: global minimum karena loss function strictly convex ($H = 2X'X$ PD) - SVM, Lasso: KKT conditions menjelaskan sifat sparsity dan support vectors ::: **Sebelumnya:** [← Multivariate Calculus](04-multivariate-calc.qmd) | **Selanjutnya:** [Taylor Series →](06-taylor-series.qmd)