Kısıtları türevlenebilirleştirmece(!) numarası

Diyelim ki eşitsizlik biçiminde ifade edebildiğiniz bazı kısıtlarınız var ve bu eşitsizlikleri sağlayacak bir çözüm arayışındasınız. Bu yazıda bunu elde etmeyi sağlayacak bir numara göstereceğim.

Problemimizi daha iyi tanımlayalım: öyle bir $x$ arıyoruz ki $g(x) \le 0$ olsun. $g(x)$ sürekli ve türevlenebilir olsun bir de. Genelde elimizdeki eşitsizlikleri biraz cebirsel oynamayla $g(x) \le 0$ şeklinde yazabiliriz.

Şimdi, $t \le 0$ eşitsizliğini sağlayan bütün $t$ değerlerinin $\max(0, t) = 0$ eşitliğini de sağladığını farkedelim. Bu demek oluyor ki  $t \le 0$ gördüğümüz her şeyi $\max(0, t) = 0$ gibi değerlendirebiliriz.

Yalnız $\max(0, t)$ ifadesi pek yumuşak değil, o yüzden karesini alıp yumuşatalım. Gene $t \le 0$ eşitsizliğini sağlayan $t$ değerleri $\max(0, t)^2 = 0$ eşitliğini sağlar.

Geldik son adıma, yukarıda bahsettiğimiz ifadelerde $t$ yerine $g(x)$ koyup şu problemi çözelim:
$$
\text{minimize } \max(0,g(x))^2
$$
Yukarıdaki problemde hedef fonksiyonun değeri 0 olduğunda istedğimiz bir çözüm bulunmuş olur. Bunu bulmak için de en basitinden gradient descent gibi bir yöntem kullanabiliriz, ne de olsa hedef fonksiyonumuz mis gibi türevlenebilir. Elbette yerel minimalara takılma şansınız var, hatta çözüme hiç bir zaman ulaşamayabilirsiniz.

Özetle, elinizdeki eşitsizlikleri gösterdiğim numara ile türevlenebilir bir fonksiyon halinde yazabilirsiniz.

Örnek Uygulama

Tarif ettiğim numarayı oyuncak bir problem üzerinde göstereyim, biraz balyozla sinek avlamaya benzeyecek ama daha anlasilir olacak. Verilen bir alana, belli bir boyuttaki dikdörtgeni nasıl sığdırabileceğimize bakalım. Dikdörtgeni döndürmek serbest. Aşağıdaki çizimde problemi tarif etmeye çalıştım.

Diyelim ki elinizde $\Omega=\{x\in \mathbb{R}^2 \mid f_j(x)\le 0, j=1,\dots,m \}$ tanımlanmış bir alan olsun. Elimizde de $(c, w, h, \theta)$ ile parametrize ettiğimiz bir dikdörtgen olsun. $c$, dikdörtgenin merkezinin konumu, $w$ ve $h$ genişliği ve yüksekliği, $\theta$ da döndürme açısı olsun, ayrıca kolaylık olsun diye $w$ ve $h$ bize önceden verilmiş olsun. Problemi ben uydurduğum için buna hakkım olsun :)

Dikdörtgeni verilen alanın içine sığdıracak $(c, \theta)$ arıyoruz. Dikdörtgenin alanın içinde olabilmesi için, 4 köşesinin de alanın içinde olması lazım, yani:
$$
f_j(p^i) \le 0 \text{ for all } j=1,\dots\,m \text{ and } \\ i=\{\text{SOLÜST, SAĞÜST, SOLALT, SAĞALT}\}
$$
Dikdörtgenin bir köşesinin ifadesini yazalım, diğer köşeler de benzer şekilde yazılabilir:
$$
p^{\text{SOLÜST}}=c+R(\theta) \begin{bmatrix} -0.5 w \\ -0.5 h \end{bmatrix}
$$
Yukarıdaki ifadede $R(\theta)$ döndürme matrisi, yani $R(\theta) = \left[\begin{smallmatrix}
cos(\theta) & -sin(\theta) \\ sin(\theta) & cos(\theta)
\end{smallmatrix} \right]$.

Şimdi, en başta bahsettiğim dönüşüm numarasını uygularsak problemimiz şu biçime dönüşür:
$$
\text{minimize} \sum_j \sum_i \max(0,f_j(p^i))^2
$$
Ben örneğimiz için döndürülmüş bir elips olan tek bir $f(\cdot)$ seçtim ve gradient descent ile çözdüm:
$$
f(x, y) = \frac{((x-2)\cos(\alpha) + (y-4)\sin(\alpha))^2}{4} + \frac{((x-2)\sin(\alpha) - (y-4)\cos(\alpha))^2}{16} - 1;
$$
Türevleri almak için MATLAB'ın sembolik kütüphanesini kullandım, bu işi ilk defa yaptığım için çok iğrenç bir kod oldu. Kötü kodlarımı paylaşmaya utandığımdan buraya koymadım. Aşağıda gradient descent algoritmasının bazı adımlarını görebilirsiniz:


Yazdığım yazılarda gittikçe anlaşılma derdimi yitirdiğimi görüyorum. Umarım oralarda hala beni anlayan birileri vardır :)

Lagrange Çarpanı - Değişik bir bakış

Lagrange Çarpanı yöntemi genelde 2 fonksiyonun gradyanlarının birbirine paralel olmasıyla açıklanır. Bu yazıda maksimizasyon/minimizasyon problemlerinde Lagrange Çarpanları kullanımının biraz daha garip fakat daha kolay bir çıkarımından bahsedeceğim.

Diyelim ki elimizde bir $f(x, y)$ fonksiyonu var ve bu fonksiyonun aldığı en büyük değeri bulmaya çalışıyoruz. Matematiksel olarak ifade edecek olursak:
$$
\max\limits_{x,y} f(x,y)
$$
Ve diyelim ki çözümün $g(x, y)=c$ gibi bir koşulu da sağlaması gereksin. Eğer böyle bir kısıtımız olmasaydı $f()$in kısmi türevlerini alıp sıfıra eşitlerdik ve çözüme ulaşırdık (fonksiyon limitlerde sonsuza büyümüyorsa tabi).

Şimdi bu kısıtımızı denkleme yedirelim. Maximize edeceğimiz fonksiyona $0$ değerini eklemek ya da çıkartmak ifadeyi maximize eden değerleri değiştirmeyecektir. Yani:
$$
\max\limits_{x,y} f(x,y) = \max\limits_{x,y}  \left[ f(x,y) + 0 \right]
$$
Aynı şekilde sıfırın herhangi bir katını da ekleyip çıkarmam sonucu değiştirmeyecektir:
$$
\max\limits_{x,y} f(x,y) = \max\limits_{x,y}  \left[ f(x,y) + k\cdot 0 \right]
$$
$g(x, y)=c$ olan kısıtımızı da düzenlersek  $0=g(x, y)-c$ elde ederiz. Sıfırı yerine koyarsak üstteki denklemde:
$$
\max\limits_{x,y} f(x,y) = \max\limits_{x,y}  \left[ f(x,y) + k(g(x, y)-c) \right]
$$
Elde ettiğimiz ifade Lagrange Çarpanları ifadesi; $k$lar da Lagrange Çarpanı denilen şeyler. Kısıtmızı esas başladığımız maksimizasyon problemine Lagrange Çarpanlarını kullanarak yedirmiş olduk. Şimdi bu elde ettiğimiz yeni denklemin x'e ve y'ye göre kısmı türevini alıp sıfıra eşitleyip kısıtımıza göre en büyük aldığı değeri bulabiliriz.