1 · Pembatas persamaan: Lagrange
Opt f(x), x ∈ Rn, dengan m pembatas gi(x)=0 (f dapat diturunkan 2×, gi dapat diturunkan)
Kondisi perlu: ∂L/∂xj=0 (j=1..n) dan ∂L/∂λi=−gi(x)=0 (i=1..m) → n+m persamaan untuk n+m variabel (x,λ)
Jika ditulis L=f+λg: x* tetap, hanya tanda λ berbalik.
2 · Contoh Lagrange
Slide: min x1²+x2²−2x1−2x2, x1+x2=1
2x1−2−λ=0; 2x2−2−λ=0; x1+x2=1 → x*=(½,½), λ=−1, f=−3/2
maks x1x2, x1+x2=10: x2−λ=0, x1−λ=0 → x1=x2=λ=5, f=25
min x1²+x2², 2x1+x2=5: x1=λ, x2=λ/2 → λ=2, x*=(2,1), f=5
maks x1+x2, x1²+x2²=2: x1=x2=1/(2λ), λ=±½ → (1,1) dan (−1,−1): dua titik stasioner, bedakan lewat kondisi cukup
4 variabel + 2 pembatas → 4+2 = 6 persamaan, 6 variabel.
3 · Hessian bordered
- Ukuran (m+n)×(m+n); evaluasi di (x*,λ*)
- P: ∂gi/∂xj (m×n); Q = Hessian L terhadap x (n×n)
- n=4, m=2 → 6×6, P 2×4, Q 4×4
4 · Kondisi cukup: Hessian bordered
Periksa determinan n−m minor prinsipal (LPM) terakhir HB, mulai dari orde 2m+1 sampai m+n.
| tanda det | |
|---|---|
| maksimum | berganti-ganti, mulai (−1)m+1 |
| minimum | semua (−1)m |
| n, m | orde | maks | min |
|---|---|---|---|
| 2, 1 | 3 | + | − |
| 3, 1 | 3, 4 | +, − | −, − |
| 4, 2 | 5, 6 | −, + | +, + |
min slide (n=2,m=1): det 011120102 = −4 <0 → min
maks x1x2: det 011101110 = 2 > 0 → maks
maks slide (n=3): −∑x²+2∑x, ∑x=1 → x*=(⅓,⅓,⅓), λ=4/3; orde 3 = 4, orde 4 = −12 (+,−) → maks
Maks −∑x² dg x1+2x2+3x3=14: x*=(1,2,3), λ=−2, orde 3=10, orde 4=−56 → maks.
5 · Kondisi cukup: metode Δ
| akar μ | x* adalah |
|---|---|
| semua negatif | maksimum |
| semua positif | minimum |
Contoh 1: det(Δ)=2μ−4=0 → μ=2 → min
Contoh 2 (maks): det(Δ)=−3μ²−12μ−12=0 → μ=−2 (dua kali) → maks
Hasil slide Contoh 3 (min, f=∑x²+2∑x): HB orde 3,4 = −4, −12; μ=2 (ganda) → min. Periksa lagi nilai x* dan λ di slide itu.
6 · Pembatas pertidaksamaan: KKT
Model: opt f(x) dengan gi(x) ≤ 0, i=1..m. L = f − Σλigi.
Bentuk standar: 2x1−x2≥4 → −2x1+x2+4 ≤ 0 (ruas ke kiri, kalikan −1 → tanda berbalik)
| Syarat KKT | bentuk |
|---|---|
| tanda λ | λi≥0 (maks); λi≤0 (min) |
| stasioner | ∂L/∂xj=0, j=1..n |
| complementary slackness | λigi(x)=0 |
| kelayakan | gi(x)≤0 |
Aktif: gi=0; tak aktif (gi<0) → λi=0. Jumlah syarat = m+n+m+m: n=3,m=4 → 15; slide n=2,m=3 → 11
7 · Prosedur kasus KKT
- Bagi 2m kasus: tiap λi=0 atau ≠0 (m=4 → 16; m=3 → 8)
- λi≠0 → gi=0 (aktif); λi=0 → abaikan gi
- Pecahkan x, λ dari stasioner + pembatas aktif
- Cek layak (semua g≤0) dan tanda λ
- Lolos keduanya = memenuhi kondisi perlu
| Soal | Kasus | x | λ | hasil |
|---|---|---|---|---|
| maks −(x1−3)²−(x2−3)², x1+x2≤5 | λ=0 | (3,3) | 0 | tak layak (6>5) |
| λ≠0 | (2½,2½) | 1 | lolos (≥0) | |
| maks −(x1−1)²−(x2−1)², sama | λ≠0 | (2½,2½) | −1 | tanda salah |
| λ=0 | (1,1) | 0 | lolos | |
| min x1+x2, x1≥1, x2≥1 | 1,1 aktif | (1,1) | −1,−1 | lolos (≤0) |
| maks −(x1−2)²−(x2−2)², x1+x2≤2 | λ≠0 | (1,1) | 2 | lolos |
| min (x1−3)²+(x2−1)², x1+x2≤2 | λ≠0 | (2,0) | −2 | lolos |
Slide 3 pembatas (8 kasus): maks −(x1−1)²−(x2−1)², x1+x2≤5, x≥0: hanya λ=(0,0,0) di (1,1) lolos; mis. (5,0) λ1=−8, λ3=−10 ditolak (maks butuh λ≥0); (0,0) λ=(0,−2,−2) ditolak.
8 · Kondisi cukup KKT & ringkasan
| Kasus | f | himpunan pembatas |
|---|---|---|
| maksimisasi | cekung | cembung |
| minimisasi | cembung | cembung |
Fungsi linier = cembung dan cekung. Min x1+x2, x≥1: f linier + S cembung → (1,1) minimum global.
| Persamaan | Pertidaksamaan | |
|---|---|---|
| pembatas | g=0 | g≤0 |
| λ | tanda bebas | ≥0 maks / ≤0 min |
| syarat | ∂L/∂λ=0 | λg=0, g≤0 |
| cukup | HB atau Δ | konveksitas f & S |