12 Hessian Matris ve Subdiferansiyel
Geçen hafta konveks fonksiyonları epigrafları üzerinden tanımlamış ve genişletilmiş reel değerlere — yani \(\overline{\mathbb{R}}\) kümesine — izin vermiştik; bu hafta aynı çerçevede devam ediyoruz. Bir fonksiyonun konveks olup olmadığını kiriş eşitsizliğinden okumak çoğu zaman zordur. Bu haftada iki kez türevlenebilen fonksiyonlar için konveksliği tek bir matrisin işaretine indirgiyor, ardından türevin var olmadığı noktalarda onun yerini alan subgradient kavramını kuruyoruz. Bölüm, konveks analizin üç temel fonksiyonuyla kapanıyor: destek fonksiyonu, indikatör fonksiyonu ve pozitif homojen fonksiyonlar.
12.1 Konveksliğin Hessian ile Belirlenmesi
Tek değişkende konveksliğin ölçütü herkesin bildiği bir şeydir: \(f'' \ge 0\). Grafik her yerde yukarı bükülüyorsa kiriş grafiğin üstünde kalır. Çok değişkende aranan şey tam olarak aynıdır; tek fark, “ikinci türev”in artık bir sayı değil bir matris olmasıdır.
Bunu görmek için \(x\) noktasından \(d\) yönünde çıkan doğru üzerinde \(f\)’yi izleyelim:
\[g(t) = f(x + t d).\]
\(g\) tek değişkenli bir fonksiyondur ve zincir kuralı iki kez uygulanınca
\[g''(0) = \langle d, H(x)\, d \rangle, \qquad H(x) = \left( \frac{\partial^2 f}{\partial x_i \partial x_j}(x) \right)\]
çıkar; buradaki simetrik \(H(x)\) matrisine \(f\) fonksiyonunun Hessian matrisi denir. Yani \(\langle d, H(x)\, d \rangle\) sayısı, \(f\)’nin \(x\) noktasında \(d\) yönündeki ikinci türevinden başka bir şey değildir.
Bir fonksiyonun konveks olması, üzerinden geçen her doğru parçasında konveks olması demektir. O hâlde aranan koşul kendiliğinden ortaya çıkıyor: hiçbir yönde ikinci türev negatif olmasın. Bu koşulun matrislerde hazır bir adı vardır.
Tanım 12.1 (Pozitif Tanımlı ve Pozitif Yarı-Tanımlı Matris) Simetrik bir \(Q_{n \times n}\) reel matrisine, eğer her \(x \in \mathbb{R}^n\) için \(\langle x, Qx \rangle \ge 0\) ise pozitif yarı-tanımlı matris, eğer her \(x \in \mathbb{R}^n \setminus \{0\}\) için \(\langle x, Qx \rangle > 0\) ise pozitif tanımlı matris denir; \(\langle x, Qx \rangle\) ifadesine de sırasıyla pozitif yarı-tanımlı form ve pozitif tanımlı form denir.
Sezgisel karşılıkları şudur: yarı-tanımlı “hiçbir yönde aşağı bükülmüyor”, tanımlı ise “her yönde gerçekten yukarı bükülüyor”.
Teorem 12.1 (Hessian Kriteri) \(f : C \subset \mathbb{R}^n \to \mathbb{R}\) fonksiyonu açık konveks bir \(C\) kümesi üzerinde reel değerli ve ikinci mertebeden sürekli türevlenebilir bir fonksiyon olsun. Bu durumda \(f\) fonksiyonunun \(C\) üzerinde konveks olabilmesi için gerek ve yeter koşul,
\[H(x) = \left( \frac{\partial^2 f}{\partial x_i \partial x_j}(x) \right), \qquad i, j = 1, \dots, n\]
Hessian matrisinin her \(x \in C\) için pozitif yarı-tanımlı olmasıdır.
Eğer \(H(x)\) matrisi her \(x \in C\) için pozitif tanımlı ise o zaman \(f\) kesin konveks fonksiyondur.
- \(n = 1\) durumunda \(H(x)\) tek elemanlı bir matristir ve teorem tanıdık \(f''(x) \ge 0\) koşuluna iner. Hessian, ikinci türevin çok değişkenli hâlidir.
- Hessian tek bir noktada bile pozitif yarı-tanımlı değilse fonksiyon konveks değildir.
- Pozitif tanımlılık kesin konveksliği getirir, ama tersi doğru değildir: \(f(x) = x^4\) kesin konvekstir, buna karşılık \(f''(0) = 0\)’dır.
12.2 Kontrol Reçetesi: Esas Minörler
Tanım “her \(x\) için” dediğinden doğrudan kullanışlı değildir; sonsuz çok vektör tek tek denenemez. Neyse ki işi sonlu sayıda determinant hesabına indiren kriterler vardır. Bu kriterleri kullanırken doğru yapılması gereken tek bir ayrım var — karışan yer tam olarak burasıdır.
Tanım 12.2 (Esas Minör ve Öncü Esas Minör) \(Q\) simetrik bir \(n \times n\) matris ve elemanları \(a_{ij}\) olsun.
Esas minör: aynı numaralı satır ve sütunlar birlikte seçilerek elde edilen alt matrisin determinantı. Örneğin \(3 \times 3\) bir matriste \(\{2\}\) seçimi \(a_{22}\) sayısını, \(\{1, 3\}\) seçimi ise \(\begin{vmatrix} a_{11} & a_{13} \\ a_{31} & a_{33} \end{vmatrix}\) determinantını verir. Boş olmayan her seçim bir minör verdiğinden toplam \(2^n - 1\) tanedir.
Öncü esas minör: yalnızca \(\{1\}, \{1,2\}, \dots, \{1, \dots, n\}\) seçimlerinden gelenler, yani sol üst köşeden başlayıp büyüyen kareler:
\[\Delta_1 = a_{11}, \qquad \Delta_k = \begin{vmatrix} a_{11} & \cdots & a_{1k} \\ \vdots & \ddots & \vdots \\ a_{k1} & \cdots & a_{kk} \end{vmatrix}, \qquad k = 2, 3, \dots, n.\]
Toplam \(n\) tanedir.
Her öncü esas minör aynı zamanda bir esas minördür; tersi doğru değildir.
Kriterler bu iki listeyi şöyle kullanır:
| Aranan | Koşul | Bakılacak minörler | Kaç tane |
|---|---|---|---|
| pozitif tanımlı (\(\Rightarrow\) kesin konveks) | hepsi \(> 0\) | yalnızca öncü esas minörler | \(n\) |
| pozitif yarı-tanımlı (\(\Leftrightarrow\) konveks) | hepsi \(\ge 0\) | bütün esas minörler | \(2^n - 1\) |
Lemma 12.1 (Sylvester Kriteri) Simetrik bir \(A_{n \times n}\) matrisin pozitif tanımlı olması için gerek ve yeter koşul, tüm öncü esas minörlerinin pozitif olmasıdır; yani her \(k = 1, \dots, n\) için \(\Delta_k > 0\) gerçeklenmesidir.
Pozitif yarı-tanımlılık kriteri. Simetrik bir \(A_{n \times n}\) matrisin pozitif yarı-tanımlı olması için gerek ve yeter koşul, \(2^n - 1\) tane olan esas minörlerinin hepsinin negatif olmamasıdır.
\(A = \begin{pmatrix} 0 & 0 \\ 0 & -1 \end{pmatrix}\) matrisinde \(\Delta_1 = 0 \ge 0\) ve \(\Delta_2 = \det(A) = 0 \ge 0\)’dır: öncü minörlerin ikisi de negatif değil. Buna karşılık \(x = (0, 1)\) için
\[\langle x, Ax \rangle = -1 < 0\]
olduğundan \(A\) pozitif yarı-tanımlı değildir. Gözden kaçan minör sağ alt köşedeki \(-1\)’dir; o da bir esas minördür ama öncü değildir. Kısacası: kesin konvekslik ararken öncü minörler yeter, düz konvekslik ararken yetmez.
\(n = 2\) için tablo tamamen açılabilir. \(A = \begin{pmatrix} a & b \\ b & c \end{pmatrix}\) matrisinin öncü esas minörleri \(a\) ile \(ac - b^2\), bütün esas minörleri ise \(a\), \(c\) ve \(ac - b^2\) olduğundan:
- kesin konveks (pozitif tanımlı): \(a > 0\) ve \(ac - b^2 > 0\);
- konveks (pozitif yarı-tanımlı): \(a \ge 0\), \(c \ge 0\) ve \(ac - b^2 \ge 0\).
Aradaki tek fark ikinci listede \(c\)’nin de ayrıca kontrol edilmesidir; yukarıdaki tuzak tam olarak bu unutulan \(c\)’den doğar.
\(n = 3\) durumunda \(A = \begin{pmatrix} a & b & c \\ b & d & e \\ c & e & f \end{pmatrix}\) matrisinin yedi esas minörü \(a\), \(d\), \(f\), \(ad - b^2\), \(af - c^2\), \(df - e^2\) ve \(\det(A)\) değerleridir; hepsi negatif değilse \(A\) pozitif yarı-tanımlıdır. Daha büyük \(n\) için de durum aynıdır.
Örnek 12.1 (Kesin Konveks Bir Kuadratik Form) \(f(x, y, z) = x^2 + 2y^2 + 3z^2 + 2xy + 2xz\) fonksiyonunun \(\mathbb{R}^3\)’te konveksliğini inceleyiniz.
Çözüm
Kuadratik bir formda Hessian sabittir, dolayısıyla tek bir matris hesabı bütün noktalar için yeter. Tablonun birinci satırından, yani Sylvester kriterinden başlayalım: yalnızca öncü esas minörlere bakacağız; hepsi pozitif çıkarsa fonksiyon kesin konvekstir.
Birinci mertebeden türevler
\[f_x = 2x + 2y + 2z, \qquad f_y = 4y + 2x, \qquad f_z = 6z + 2x\]
olduğundan ikinci mertebeden türevler
\[f_{xx} = 2,\quad f_{xy} = 2,\quad f_{xz} = 2, \qquad f_{yx} = 2,\quad f_{yy} = 4,\quad f_{yz} = 0, \qquad f_{zx} = 2,\quad f_{zy} = 0,\quad f_{zz} = 6\]
olur ve
\[H(x, y, z) = \begin{pmatrix} 2 & 2 & 2 \\ 2 & 4 & 0 \\ 2 & 0 & 6 \end{pmatrix}\]
elde edilir. Şimdi öncü esas minörlerini hesaplayalım:
\[\Delta_1 = 2 > 0, \qquad \Delta_2 = \begin{vmatrix} 2 & 2 \\ 2 & 4 \end{vmatrix} = 4 > 0, \qquad \Delta_3 = \begin{vmatrix} 2 & 2 & 2 \\ 2 & 4 & 0 \\ 2 & 0 & 6 \end{vmatrix} = 8 > 0.\]
Her \(x \in \mathbb{R}^3\) için \(\Delta_1, \Delta_2, \Delta_3 > 0\) gerçeklendiğine göre Lemma 12.1 nedeniyle Hessian matrisi pozitif tanımlı bir matristir. Dolayısıyla Teorem 12.1 nedeniyle \(f\) fonksiyonu \(\mathbb{R}^3\) üzerinde kesin konveks bir fonksiyondur.
Hessian burada sabittir; kuadratik formlarda durum daima böyledir ve konvekslik tek bir matris hesabına iner.
Örnek 12.2 (Küpsel Terim Konveksliği Bozar) \(f(x, y, z) = x + y^2 + z^3 - xy - 3z\) fonksiyonunun \(\mathbb{R}^3\)’te konveksliğini inceleyiniz.
Çözüm
Birinci mertebeden türevler
\[f_x = 1 - y, \qquad f_y = 2y - x, \qquad f_z = 3z^2 - 3\]
olduğundan ikinci mertebeden türevler
\[f_{xx} = 0,\quad f_{xy} = -1,\quad f_{xz} = 0, \qquad f_{yx} = -1,\quad f_{yy} = 2,\quad f_{yz} = 0, \qquad f_{zx} = 0,\quad f_{zy} = 0,\quad f_{zz} = 6z\]
olur ve
\[H(x, y, z) = \begin{pmatrix} 0 & -1 & 0 \\ -1 & 2 & 0 \\ 0 & 0 & 6z \end{pmatrix}\]
elde edilir. Öncü esas minörler
\[\Delta_1 = 0, \qquad \Delta_2 = \begin{vmatrix} 0 & -1 \\ -1 & 2 \end{vmatrix} = -1 < 0, \qquad \Delta_3 = \begin{vmatrix} 0 & -1 & 0 \\ -1 & 2 & 0 \\ 0 & 0 & 6z \end{vmatrix} = -6z\]
biçimindedir. Bu kez sorulan konvekslik olduğu için tablonun ikinci satırındayız: her esas minör negatif olmamalı. Oysa \(\Delta_2 = -1 < 0\)’dır ve \(\Delta_2\) de bir esas minördür. Bu tek başına, Hessian’ın hiçbir noktada pozitif yarı-tanımlı olmadığını gösterir.
Aynı sonuç \(z\) üzerinden de okunabilir: \(6z\) bir esas minördür ve \(z < 0\) için negatiftir. Nitekim konveksliği bozan asıl terim \(z^3\)’tür; tek değişkenli \(z^3 - 3z\) fonksiyonunun ikinci türevi \(6z\) olup \(z < 0\) bölgesinde negatiftir.
Dolayısıyla \(f\) fonksiyonu \(\mathbb{R}^3\) üzerinde konveks bir fonksiyon değildir.
12.3 Seviye Kümeleri
Tanım 12.3 (Seviye Kümesi) \(\alpha \in \mathbb{R}\), \(C\) konveks bir küme ve \(f : C \subseteq \mathbb{R}^n \to \mathbb{R}\) olmak üzere
\[L_f(\alpha) = \{x \in \mathbb{R}^n : f(x) \le \alpha\}\]
kümesine \(f\) fonksiyonunun \(\alpha\) seviye kümesi denir.
Lemma 12.2 (Seviye Kümeleri Konvekstir) \(C\) konveks bir küme olmak üzere \(f : C \subseteq \mathbb{R}^n \to \mathbb{R}\) fonksiyonu konveks ise, her \(\alpha \in \mathbb{R}\) için \(L_f(\alpha)\) seviye kümeleri konvekstir.
İspat
\(\alpha \in \mathbb{R}\), \(x_1, x_2 \in L_f(\alpha)\) ve \(0 < \lambda < 1\) olsun. \(f\) konveks olduğu için
\[f\big( \lambda x_1 + (1 - \lambda)x_2 \big) \le \lambda f(x_1) + (1 - \lambda)f(x_2) \le \lambda \alpha + (1 - \lambda)\alpha = \alpha\]
yani \(f\big( \lambda x_1 + (1 - \lambda)x_2 \big) \le \alpha\) gerçeklenir. Bu ise \(\lambda x_1 + (1 - \lambda)x_2 \in L_f(\alpha)\), dolayısıyla \(L_f(\alpha)\) kümelerinin konveks olması demektir.
\(\blacksquare\)
Yukarıdaki lemmanın tersi her zaman doğru değildir. Örneğin \(\mathbb{R}\)’de tanımlanmış \(f(x) = x^3\) fonksiyonunun her \(\alpha \in \mathbb{R}\) için
\[L_f(\alpha) = \{x : x^3 \le \alpha\} = \big( -\infty,\ \sqrt[3]{\alpha}\ \big]\]
seviye kümesi bir aralık, yani konvekstir; ancak \(f(x) = x^3\) fonksiyonu \(\mathbb{R}\) üzerinde konveks değildir — \(x < 0\) bölgesinde ikinci türev \(6x\) negatiftir ve kiriş grafiğin altına düşer.
Bütün seviye kümeleri konveks olan fonksiyonlar ayrı bir ad taşır.
Tanım 12.4 (Kuazikonveks Fonksiyon) \(C\) konveks bir küme ve \(f : C \subseteq \mathbb{R}^n \to \mathbb{R}\) olmak üzere, her \(\alpha \in \mathbb{R}\) için \(L_f(\alpha)\) seviye kümesi konveks ise \(f\) fonksiyonuna kuazikonveks denir.
Lemma 12.2 her konveks fonksiyonun kuazikonveks olduğunu söyler; \(x^3\) örneği ise tersinin doğru olmadığını gösterir. Kısacası konvekslik, kuazikonvekslikten kesin olarak daha güçlü bir koşuldur.
12.4 Yönlü Türev
Tanım 12.5 (Yönlü Türev) \(d \in \mathbb{R}^n\) olmak üzere
\[f'(x_0; d) = \lim_{\lambda \downarrow 0} \frac{f(x_0 + \lambda d) - f(x_0)}{\lambda}\]
limitine \(f\) fonksiyonunun \(x_0\) noktasındaki \(d\) yönündeki yönlü türevi denir.
Örnek 12.3 (Bir Yönlü Türev Hesabı) \(f(x, y) = xy\) şeklinde tanımlanmış \(f : \mathbb{R}^2 \to \mathbb{R}\) fonksiyonunun \(x_0 = (1, 1)\) noktasında \(d = (1, 2)\) yönündeki türevini hesaplayınız.
Çözüm
Önce \(x_0 + \lambda d\) noktasını yazalım:
\[x_0 + \lambda d = (1 + \lambda,\ 1 + 2\lambda).\]
Buradan
\[f(x_0 + \lambda d) = (1 + \lambda)(1 + 2\lambda) = 2\lambda^2 + 3\lambda + 1, \qquad f(x_0) = 1 \cdot 1 = 1\]
olur. Böylece
\[f'(x_0; d) = \lim_{\lambda \downarrow 0} \frac{2\lambda^2 + 3\lambda + 1 - 1}{\lambda} = \lim_{\lambda \downarrow 0} (2\lambda + 3) = 3.\]
Genel olarak konveks bir küme üzerinde tanımlanmış konveks bir fonksiyonun bir iç noktada diferansiyellenebilir olması gerekmez. Örneğin \(\mathbb{R}\) üzerinde tanımlanmış \(f(x) = |x|\) konveks fonksiyonu \(x = 0\) noktasında diferansiyellenebilir değildir. Buna karşılık yönlü türev her yönde vardır: konveks fonksiyonlarda fark bölümleri \(\lambda\) küçüldükçe azalır ve alttan sınırlıdır. Bu nedenle konveks fonksiyonlar için gradient kavramından daha genel olan subgradient kavramı verilmektedir.
12.5 Subgradient ve Subdiferansiyel
Tanım 12.6 (Subgradient) \(f : \mathbb{R}^n \to \overline{\mathbb{R}}\) bir has konveks fonksiyon olsun ve \(x_0 \in \operatorname{dom}(f)\) olmak üzere
\[\forall x \in \mathbb{R}^n \ \text{ için } \ f(x) - f(x_0) \ \ge\ \langle x^{*},\ x - x_0 \rangle\]
sağlayan \(x^{*} \in \mathbb{R}^n\) vektörüne \(f\) fonksiyonunun \(x_0\) noktasındaki bir subgradienti denir.
Eşitsizliğin anlamı geometriktir: \(x \mapsto f(x_0) + \langle x^{*}, x - x_0 \rangle\) afin fonksiyonu, grafiğe \(x_0\) noktasında değer ve her yerde grafiğin altında kalır. Düzgün noktalarda böyle tek bir doğru vardır — teğet; kırılma noktalarında ise bir doğru ailesi.
Tanım 12.7 (Subdiferansiyel) \(f\) fonksiyonunun \(x_0\) noktasındaki tüm subgradientlerinin kümesine \(f\)’in \(x_0\) noktasındaki subdiferansiyeli denir ve
\[\partial f(x_0) = \{x^{*} \in \mathbb{R}^n : f(x) - f(x_0) \ge \langle x^{*}, x - x_0 \rangle,\ \forall x \in \mathbb{R}^n\}\]
ile gösterilir.
Örnek 12.4 (Mutlak Değer Fonksiyonunun Subdiferansiyeli) \(\mathbb{R}\) üzerinde tanımlanmış \(f(x) = |x|\) fonksiyonu için \(\partial f(0)\) subdiferansiyel kümesini hesaplayınız.
Çözüm
Subdiferansiyel tanımı gereği, \(x_0 = 0\) ve \(f(0) = 0\) olduğundan her \(x \in \mathbb{R}\) için
\[|x| \ge x^{*} x\]
sağlayan \(x^{*}\) noktalarının kümesini hesaplamalıyız. Üç durumu ayrı ayrı ele alalım:
- \(x > 0\) için eşitsizlik \(x \ge x^{*}x\) hâlini alır; \(x > 0\) ile bölünürse \(1 \ge x^{*}\) bulunur.
- \(x < 0\) için eşitsizlik \(-x \ge x^{*}x\) hâlini alır; negatif olan \(x\) ile bölündüğünde yön değiştiği için \(-1 \le x^{*}\) bulunur.
- \(x = 0\) için eşitsizlik \(0 \ge 0\) olur ve her \(x^{*} \in \mathbb{R}\) bunu sağlar.
Üç koşul birlikte \(-1 \le x^{*} \le 1\) verir. Dolayısıyla
\[\partial f(0) = [-1, 1]\]
elde edilir. Sıfırdan farklı noktalarda ise fonksiyon türevlenebilir olduğundan subdiferansiyel tek noktalıdır: \(x > 0\) için \(\partial f(x) = \{1\}\), \(x < 0\) için \(\partial f(x) = \{-1\}\).
12.6 Destek, İndikatör ve Pozitif Homojen Fonksiyonlar
Tanım 12.8 (Destek Fonksiyonu) \(\varnothing \ne A \subset \mathbb{R}^n\) olmak üzere
\[S(x, A) = \sup_{a \in A} \{\langle x, a \rangle\}\]
fonksiyonuna \(A\) kümesinin destek fonksiyonu denir.
Destek fonksiyonu, bir kümeyi ölçtüğü yönler üzerinden kodlar: \(S(x, A)\) değeri, \(x\) yönüne dik olup \(A\)’yı destekleyen hiperdüzlemin konumunu verir. Teorem 11.3 nedeniyle destek fonksiyonu — lineer fonksiyonların supremumu olduğundan — her zaman konvekstir.
Tanım 12.9 (İndikatör Fonksiyonu) \(\varnothing \ne A \subset \mathbb{R}^n\) olmak üzere
\[\delta(x, A) = \begin{cases} 0, & x \in A \\ +\infty, & x \notin A \end{cases}\]
fonksiyonuna \(A\) kümesinin indikatör fonksiyonu denir.
İndikatör fonksiyonu, genişletilmiş reel değerli fonksiyonlarda \(+\infty\) değerine neden izin verdiğimizin cevabıdır: \(A\) üzerinde bir eniyileme problemi, \(f + \delta(\cdot, A)\) fonksiyonunun kısıtsız eniyilemesine dönüşür. \(A\) konveks ise \(\operatorname{epi}\big( \delta(\cdot, A) \big) = A \times [0, +\infty)\) olduğundan indikatör fonksiyonu da konvekstir.
Tanım 12.10 (Pozitif Homojen Fonksiyon) \(0 < \lambda < +\infty\) olmak üzere her \(x \in \mathbb{R}^n\) için \(f(\lambda x) = \lambda f(x)\) gerçekleyen \(f : \mathbb{R}^n \to \overline{\mathbb{R}}\) has fonksiyonuna pozitif homojen fonksiyon denir.
Pozitif homojenlik, epigrafın bir koni olmasıyla aynı şeydir: \((x, \alpha) \in \operatorname{epi}(f)\) ve \(\lambda > 0\) ise \(f(\lambda x) = \lambda f(x) \le \lambda \alpha\) olduğundan \((\lambda x, \lambda \alpha) \in \operatorname{epi}(f)\)’dir. Norm fonksiyonu ile destek fonksiyonu bu ailenin en tanıdık iki üyesidir; böylece koniler bölümünde kurduğumuz dualite dili, doğrudan fonksiyonlara taşınmış olur.