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 :)