Lagrange Çarpanı yöntemi sadece eşitlik kısıtları ($g(x)=0$) için çalışır. Ancak gerçek dünya problemlerinde kısıtlar genellikle eşitsizlik şeklindedir ($g(x) \le 0$ veya $g(x) \ge 0$). Örneğin:
Karush-Kuhn-Tucker (KKT) koşulları, Lagrange Çarpanı yönteminin eşitsizlik kısıtlarını da kapsayacak şekilde genelleştirilmiş halidir. 1950'lerde Karush, Kuhn ve Tucker tarafından geliştirilmiştir.
Standart formda bir optimizasyon problemi:
KKT koşulları (1. mertebe gerekli koşullar):
$\nabla f + \sum \lambda_j \nabla g_j = 0$
(Lagrange'deki gradyan koşulu)
$g_j(x) \le 0$
(Kısıtların sağlanması)
$\lambda_j \ge 0$
(Lagrange'den farklı: çarpanlar negatif olamaz!)
$\lambda_j g_j(x) = 0$
(Aktif/pasif kısıt ayrımı)
| Özellik | Lagrange Çarpanı | KKT |
|---|---|---|
| Kısıt Türü | Eşitlik ($g=0$) | Eşitsizlik ($g \le 0$) |
| Çarpan İşareti | Serbest ($\lambda \in \mathbb{R}$) | Pozitif ($\lambda \ge 0$) |
| Tamamlayıcı Gevşeklik | Yok | Var ($\lambda g = 0$) |
| Aktif/Pasif Kısıt | Yok (tümü aktiftir) | Var (gevşek kısıtlar pasif) |
$\lambda_j g_j(x) = 0$ koşulu, şu anlama gelir:
Sezgi: Eğer bir kısıt zaten sağlanıyorsa (gevşekse), o kısıtın çözüm üzerinde etkisi yoktur, bu nedenle $\lambda_j = 0$ olur. Eğer bir kısıt aktifse ($g_j=0$), o zaman çarpan pozitif olabilir ve kısıtın marjinal etkisini gösterir.
$f(x)=x^2$'yi $x \le 1$ kısıtı altında minimize edelim.
1. Problem: $\min x^2$ kısıt: $g(x)=x-1 \le 0$
2. KKT Koşulları:
Durağanlık: $2x + \lambda \cdot 1 = 0 \Rightarrow 2x + \lambda = 0$
Uygunluk: $x - 1 \le 0$
Çarpan: $\lambda \ge 0$
Tamamlayıcı: $\lambda(x-1) = 0$
3. Durum Analizi:
Durum 1: $x=1$ (aktif kısıt). O zaman $\lambda = -2x = -2$. Ama $\lambda \ge 0$ olmalı! $\lambda = -2 < 0$ olduğu için geçersiz.
Durum 2: $\lambda = 0$ (pasif kısıt). O zaman $2x = 0 \Rightarrow x=0$. Uygunluk: $0-1=-1 \le 0$ sağlanır. $\lambda=0 \ge 0$ sağlanır. Tamamlayıcı: $0 \cdot (-1)=0$ sağlanır.
4. Sonuç: $x=0$ çözümdür. Kısıt pasiftir ($x=0 < 1$), bu nedenle $\lambda=0$'dır. Kısıt çözümü etkilememiştir.
Kısıt $x \le 1$, $x=0$ çözümünde pasif'tir (gevşek), çünkü $0 < 1$. Bu nedenle $\lambda=0$'dır. Kısıt çözümü etkilememiştir.
1. Problem: $\min x^2$ kısıt: $g(x)=1-x \le 0$ (standart forma çevrildi)
2. KKT Koşulları:
Durağanlık: $2x + \lambda \cdot (-1) = 0 \Rightarrow 2x - \lambda = 0 \Rightarrow \lambda = 2x$
Uygunluk: $1-x \le 0 \Rightarrow x \ge 1$
Çarpan: $\lambda \ge 0$
Tamamlayıcı: $\lambda(1-x) = 0$
3. Durum Analizi:
Durum 1: $x=1$ (aktif kısıt). O zaman $\lambda = 2x = 2$. $\lambda=2 \ge 0$ sağlanır. Tamamlayıcı: $2(1-1)=0$ sağlanır.
Durum 2: $\lambda = 0$ (pasif kısıt). O zaman $2x = 0 \Rightarrow x=0$. Uygunluk: $1-0=1 \le 0$ sağlanmaz! Geçersiz.
4. Sonuç: $x=1$ çözümdür. Kısıt aktif'tir ($x=1$), $\lambda=2 > 0$'dır. Kısıt çözümü etkilemiştir.
Kısıt $x \ge 1$, $x=1$ çözümünde aktif'tir. $\lambda=2 > 0$ olup, kısıtın çözümü etkilediğini gösterir. $\lambda$, kısıttaki 1 birimlik gevşemenin (örneğin $x \ge 0.99$ yapmak) amaç fonksiyonuna marjinal etkisini gösterir.
KKT koşulları, Lagrange Çarpanı yönteminin eşitsizlik kısıtlarına genelleştirilmiş halidir. Dört temel koşulu vardır: (1) Durağanlık, (2) Uygunluk, (3) Çarpan pozitifliği ($\lambda \ge 0$), (4) Tamamlayıcı gevşeklik ($\lambda g = 0$). Aktif kısıtlarda $\lambda > 0$, pasif kısıtlarda $\lambda = 0$'dır. KKT, optimizasyonun en önemli teorik araçlarından biridir.
KKT koşullarını öğrendik. Bir sonraki modülde "Çözümlü Örnekler" başlığı altında bugüne kadar öğrendiğimiz tüm kavramları pekiştirecek 20 adet çözümlü problem göreceğiz.