8 Konveks Örtü ve Carathéodory Teoremi
Konveks olmayan bir kümeyi konveks yapmanın en ekonomik yolu, onu kapsayan en küçük konveks kümeyi almaktır. Bu haftada konveks örtüyü tanımlıyor, onun tam olarak kümenin elemanlarının konveks kombinasyonlarından oluştuğunu gösteriyor ve Carathéodory teoremiyle bu kombinasyonlarda kaç noktanın yettiğini belirliyoruz: uzayın boyutu \(n\) ise \(n + 1\) nokta her zaman yeter.
8.1 Konveks Örtü
Konveks kümelerin kesişimi yine konveks olduğundan, bir kümeyi kapsayan bütün konveks kümeleri kesiştirmek anlamlı bir işlemdir; sonuç, o kümeyi kapsayan en küçük konveks küme olur.
Tanım 8.1 (Konveks Örtü) Bir \(A \subseteq \mathbb{R}^n\) kümesini kapsayan tüm konveks kümelerin kesişimine, yani \(I\) herhangi bir indis kümesi olmak üzere
\[\bigcap_{i \in I} \{A_i : \text{her } i \in I \text{ için } A_i \text{ konveks ve } A \subseteq A_i\}\]
kesişim kümesine \(A\) kümesinin konveks örtüsü veya konveks zarfı denir ve bu küme \(\operatorname{conv}(A)\) ile gösterilir.
Teorem 6.2 nedeniyle \(\operatorname{conv}(A)\) konvekstir; dolayısıyla \(A\) kümesini kapsayan en küçük konveks kümedir. Daima \(A \subseteq \operatorname{conv}(A)\) geçerlidir; \(A\) konveks bir küme ise \(\operatorname{conv}(A) \subseteq A\) gerçekleneceğinden \(\operatorname{conv}(A) = A\) elde edilir.
Teorem 8.1 (Konveks Kümeler Bütün Konveks Kombinasyonları İçerir) \(C \subset \mathbb{R}^n\) kümesinin konveks olması için gerek ve yeter koşul, elemanlarının tüm konveks kombinasyonlarını içermesidir.
İspat
İspat, Teorem 4.1 ile birebir aynı tümevarımdır; tek fark katsayıların negatif olmamasının korunmasıdır.
Yeterlilik yönü açıktır. Gereklilik için \(C\) konveks olsun ve \(C\)’nin \(m - 1\) tane elemanının konveks kombinasyonlarını içerdiğini kabul edelim. \(x_1, \dots, x_m \in C\), \(\lambda_i \ge 0\), \(\sum_{i=1}^{m}\lambda_i = 1\) verilsin. Eğer \(\lambda_m = 1\) ise diğer katsayılar sıfırdır ve toplam \(x_m \in C\)’ye eşittir. Aksi hâlde \(1 - \lambda_m > 0\) olup
\[\sum_{i=1}^{m} \lambda_i x_i = (1 - \lambda_m) \underbrace{\left( \sum_{i=1}^{m-1} \frac{\lambda_i}{1 - \lambda_m} x_i \right)}_{=: \, y} + \lambda_m x_m\]
yazılır. Burada \(\lambda_i / (1 - \lambda_m) \ge 0\) ve bunların toplamı \(1\) olduğundan \(y\), \(C\)’nin \(m-1\) elemanının bir konveks kombinasyonudur; hipotez gereği \(y \in C\)’dir. \(C\) konveks ve \(0 \le \lambda_m \le 1\) olduğundan \((1 - \lambda_m)y + \lambda_m x_m \in C\) bulunur.
\(\blacksquare\)
Bundan sonra bir \(A \subset \mathbb{R}^n\) kümesinin elemanlarının tüm konveks kombinasyonlarının kümesini \(K(A)\) ile göstereceğiz. \(K(A)\) konvekstir ve \(A \subseteq K(A)\)’dır; bir \(A\) kümesinin konveks olması için gerek ve yeter koşul \(A = K(A)\) olmasıdır.
Teorem 8.2 (Konveks Örtünün İçeriği) \(A \subset \mathbb{R}^n\) için \(\operatorname{conv}(A) = K(A)\) geçerlidir.
İspat
İspat Teorem 4.2 ile aynı akışı izler. \(K(A)\) konveks ve \(A\)’yı kapsayan bir küme olduğundan \(\operatorname{conv}(A) \subseteq K(A)\) olur. Tersine \(\operatorname{conv}(A)\) konveks olduğundan Teorem 8.1 nedeniyle elemanlarının tüm konveks kombinasyonlarını içerir; \(A \subseteq \operatorname{conv}(A)\) olduğundan özel olarak \(K(A) \subseteq \operatorname{conv}(A)\) elde edilir.
\(\blacksquare\)
Böylece bir kümenin konveks olması için gerek ve yeter koşul \(A = \operatorname{conv}(A)\) olmasıdır.
Örnek 8.1 (İki Konveks Örtü) Aşağıdaki konveks örtüleri belirleyiniz: (1) \(\mathbb{R}^2\)’de aynı doğru üzerinde bulunmayan üç noktanın konveks örtüsü, (2) birim çemberin konveks örtüsü.
Çözüm
1. Teorem 8.2 gereği \(\operatorname{conv}\{v_1, v_2, v_3\}\) kümesi, \(\lambda_i \ge 0\) ve \(\sum \lambda_i = 1\) olmak üzere \(\sum \lambda_i v_i\) noktalarının kümesidir. Katsayılar afin örtüdekilerle aynıdır, üstelik negatif olmama koşuluyla sınırlanmıştır; bu da afin örtü olan düzlemden yalnızca köşeleri \(v_1, v_2, v_3\) olan kapalı üçgensel bölgeyi seçer.
2. \(S = \{x \in \mathbb{R}^2 : \|x\| = 1\}\) olsun. Kapalı birim yuvar konveks olduğundan ve \(S\) kümesini kapsadığından \(\operatorname{conv}(S) \subseteq \overline{B(0,1)}\) geçerlidir. Ters yönde, \(\|x\| \le 1\) olan bir \(x\) noktasından geçen herhangi bir doğru çemberi iki noktada keser ve \(x\) bu iki noktanın konveks kombinasyonudur; dolayısıyla \(x \in \operatorname{conv}(S)\) olur. Sonuçta
\[\operatorname{conv}(S) = \overline{B(0,1)}\]
elde edilir. Dikkat edilirse burada Carathéodory teoreminin izin verdiği \(n + 1 = 3\) nokta yerine \(2\) nokta yetmiştir: teorem bir üst sınır verir, her noktada gerçekten gereken sayıyı değil.
Tanım 8.2 (Kapalı Konveks Örtü) \(\varnothing \ne C \subset \mathbb{R}^n\) kümesini kapsayan tüm kapalı ve konveks kümelerin kesişimine \(C\) kümesinin kapalı konveks örtüsü denir ve bu küme \(\overline{\operatorname{conv}}(C)\) ile gösterilir.
Önerme 8.1 (Kapalı Konveks Örtü ile Kapanış) \(\varnothing \ne C \subset \mathbb{R}^n\) için \(\overline{\operatorname{conv}}(C) = \overline{\operatorname{conv}(C)}\) geçerlidir.
İspat
\(\overline{\operatorname{conv}(C)}\) kümesi \(C\) kümesini içeren kapalı ve konveks bir kümedir — konvekslik Teorem 7.6’ten gelir. Dolayısıyla \(\overline{\operatorname{conv}}(C) \subseteq \overline{\operatorname{conv}(C)}\) kapsaması geçerlidir.
Öte yandan, tanımı gereği \(\overline{\operatorname{conv}}(C)\) kümesi \(C\)’yi kapsayan bir konveks küme olduğundan \(\operatorname{conv}(C) \subseteq \overline{\operatorname{conv}}(C)\) kapsaması geçerlidir. Bu kapsamada her tarafın kapanışı alınırsa ve \(\overline{\operatorname{conv}}(C)\) kümesinin kapalı olduğuna dikkat edilirse
\[\overline{\operatorname{conv}(C)} \subseteq \overline{\overline{\operatorname{conv}}(C)} = \overline{\operatorname{conv}}(C)\]
elde edilir.
\(\blacksquare\)
8.2 Carathéodory Teoremi
Konveks örtü, tanımı gereği sonsuz çok noktanın kombinasyonlarını içerebilir. Carathéodory teoremi, uzayın boyutunun bu sayıya kesin bir üst sınır koyduğunu söyler.
Teorem 8.3 (Carathéodory Teoremi) \(A \subset \mathbb{R}^n\) herhangi bir küme olsun. \(\operatorname{conv}(A)\) kümesinin herhangi bir elemanı, \(A\) kümesinin \(n + 1\)’den daha fazla olmayan sayıdaki elemanının konveks kombinasyonu şeklinde yazılabilir.
İspat
\(x \in \operatorname{conv}(A) = K(A)\) olsun; dolayısıyla \(\lambda_i \ge 0\), \(\sum_{i=1}^{m} \lambda_i = 1\) sayıları ve \(x_i \in A\) noktaları için \(x = \sum_{i=1}^{m} \lambda_i x_i\) yazılabilir. Bu yazılışta \(m > n + 1\), dolayısıyla \(m - 1 > n\) olsun.
\(\mathbb{R}^n\) uzayında en fazla \(n\) tane vektörün lineer bağımsız olabileceği bilgisi kullanılırsa, \(m - 1\) tane olan
\[x_1 - x_m,\ x_2 - x_m,\ \dots,\ x_{m-1} - x_m\]
vektörlerinin lineer bağımlı olmak zorunda olduğu sonucu elde edilir. Bu ise hepsi birden sıfır olmayan \(\alpha_1, \dots, \alpha_{m-1} \in \mathbb{R}\) sayıları için
\[\alpha_1 (x_1 - x_m) + \dots + \alpha_{m-1}(x_{m-1} - x_m) = 0 \tag{$*$}\]
eşitliğinin sağlanmasını gerektirir. \(\alpha_m := -\sum_{i=1}^{m-1} \alpha_i\) denirse \((*)\) eşitliğinden
\[\sum_{i=1}^{m-1} \alpha_i x_i - \left( \sum_{i=1}^{m-1} \alpha_i \right) x_m = \sum_{i=1}^{m-1} \alpha_i x_i + \alpha_m x_m = \sum_{i=1}^{m} \alpha_i x_i = 0, \qquad \sum_{i=1}^{m} \alpha_i = 0\]
elde edilir. Böylece her \(t \in \mathbb{R}\) için
\[x = \sum_{i=1}^{m} \lambda_i x_i - t \sum_{i=1}^{m} \alpha_i x_i = \sum_{i=1}^{m} (\lambda_i - t\alpha_i)x_i\]
yazılabilir. Şimdi amacımız, her \(i\) için \(\lambda_i - t_0\alpha_i \ge 0\) ve \(\sum_{i=1}^{m}(\lambda_i - t_0\alpha_i) = 1\) olacak, üstelik en az bir katsayıyı sıfır yapacak bir \(t_0 \in \mathbb{R}\) bulmaktır.
\(\alpha_i\)’lerin hepsi birden sıfır değil ve \(\sum_{i=1}^{m} \alpha_i = 0\) olduğundan, \(\alpha_i\)’lerden en az biri pozitiftir; böylece \(I := \{i : \alpha_i > 0\}\) indis kümesi boş değildir. Dolayısıyla
\[t_0 := \frac{\lambda_{i_0}}{\alpha_{i_0}} := \min\left\{ \frac{\lambda_i}{\alpha_i} : i \in I \right\} \ \ge 0\]
sayısı iyi tanımlıdır. Bu şekilde belirlenen \(t_0\) için:
- \(i \in I\) ise \(\lambda_i - t_0\alpha_i = \alpha_i \big( \tfrac{\lambda_i}{\alpha_i} - t_0 \big) \ge 0\); özel olarak \(i = i_0\) için \(\lambda_{i_0} - t_0 \alpha_{i_0} = 0\),
- \(i \notin I\) ise \(\alpha_i \le 0\) ve \(t_0 \ge 0\) olduğundan \(\lambda_i - t_0 \alpha_i \ge 0\) olur.
Ayrıca
\[\sum_{i=1}^{m} (\lambda_i - t_0\alpha_i) = \sum_{i=1}^{m} \lambda_i - t_0 \sum_{i=1}^{m} \alpha_i = 1 - t_0 \cdot 0 = 1\]
gerçeklenir. Sonuçta \(x = \sum_{i=1}^{m} (\lambda_i - t_0\alpha_i)x_i\) noktası, \(A\) kümesinin noktalarının bir konveks kombinasyonudur ve en az bir \(i_0\) için katsayı sıfır olduğundan \(x\) noktası \(A\) kümesinin \(m - 1\) tane elemanının konveks kombinasyonu şeklinde yazılmış olur.
Eğer \(m - 1 = n + 1\) ise ispat biter; \(m - 1 > n + 1\) ise ispatın başındaki \(m\) yerine \(m - 1\) yazılarak aynı işlemler tekrar edilir. Bu indirgeme, konveks kombinasyondaki eleman sayısı \(n + 1\) olana kadar devam ettirilebilir.
\(\blacksquare\)
Teorem 8.4 (Kompakt Kümenin Konveks Örtüsü) \(C \subset \mathbb{R}^n\) kümesi kompakt ise \(\operatorname{conv}(C)\) kümesi de kompakttır.
İspat
\(C\) kompakt, yani kapalı ve sınırlı bir küme ve \(x \in \operatorname{conv}(C)\) olsun.
Sınırlılık. Carathéodory teoremi nedeniyle \(x = \sum_{i=1}^{n+1} \alpha_i x_i\) olacak biçimde \(x_i \in C\) noktaları ve \(\sum_{i=1}^{n+1} \alpha_i = 1\) sağlayan \(0 \le \alpha_i \le 1\) sayıları vardır. \(C\) sınırlı olduğundan her \(i\) için \(\|x_i\| \le M\) olacak biçimde bir \(M > 0\) vardır. Böylece
\[\|x\| \le \sum_{i=1}^{n+1} \alpha_i \|x_i\| \le M \sum_{i=1}^{n+1} \alpha_i = M\]
nedeniyle \(\operatorname{conv}(C)\) kümesi sınırlı olur.
Kapalılık. \(\operatorname{conv}(C)\) kümesinden yakınsak bir \(\{x_k\}\) dizisi alalım ve \(x_k \to x_0\) olsun. Carathéodory teoremi nedeniyle her \(k \in \mathbb{N}\) için
\[x_k = \sum_{i=1}^{n+1} \alpha_{ki} x_{ki} \tag{2}\]
olacak biçimde \(x_{k1}, \dots, x_{k(n+1)} \in C\) noktaları ve \(\sum_{i=1}^{n+1} \alpha_{ki} = 1\) sağlayan \(\alpha_{ki} \ge 0\) sayıları vardır. \(\{\alpha_{ki}\}\) dizileri \([0,1]\) aralığında, \(\{x_{ki}\}\) dizileri ise sınırlı \(C\) kümesinde kaldıklarından sınırlıdırlar; Bolzano-Weierstrass teoremi nedeniyle yakınsak alt dizilere sahiptirler. Genelliği bozmaksızın bu yakınsak dizileri elimizdeki diziler olarak alalım. \(C\) kompakt, dolayısıyla kapalı olduğundan \(x_{ki} \to x_{0i}\) olacak şekilde \(x_{0i} \in C\) noktaları vardır; ayrıca \(\alpha_{ki} \to \alpha_{0i} \ge 0\) ve limitte \(\sum_{i=1}^{n+1} \alpha_{0i} = 1\) olur. Şimdi \((2)\) eşitliğinde \(k \to \infty\) için limite geçilirse
\[x_0 = \sum_{i=1}^{n+1} \alpha_{0i} x_{0i}\]
elde edilir. Böylece \(x_0\) noktası \(C\) kümesindeki \(n + 1\) tane noktanın bir konveks kombinasyonu olarak yazılabildiğinden \(\operatorname{conv}(C)\) kümesine aittir; yani \(\operatorname{conv}(C)\) kapalıdır.
Hem sınırlı hem kapalı olduğundan \(\operatorname{conv}(C)\) kompakttır.
\(\blacksquare\)
Carathéodory teoremi, görünüşte sonsuz bir işlemi sonlu bir işleme indirger. Aynı sonlu boyut fikrinin iki güçlü akrabası — Radon ve Helly teoremleri — bir sonraki haftanın konusudur.