Kuliah 7: Pemisahan, Hiperbidang Nonvertikal, dan Konjugasi

• Tinjauan pemisahan hiperbidang

• Hiperbidang nonvertikal

• Fungsi konjugat konveks

• Teorema konjugasi

• Contoh

Bacaan: Bagian 1.5 dan 1.6.

• Karakterisasi fundamental: Tutupan selubung konveks suatu himpunan $C\subset\mathbb R^n$ adalah irisan semua setengah ruang tertutup yang memuat $C$. (Buktinya memakai teorema pemisahan ketat.)

• Suatu hiperbidang memisahkan $C_1$ dan $C_2$ secara proper jika hiperbidang itu memisahkan $C_1$ dan $C_2$ serta tidak sepenuhnya memuat keduanya.

• Teorema pemisahan proper: Misalkan $C_1$ dan $C_2$ dua himpunan bagian konveks tak kosong dari $\mathbb R^n$. Ada hiperbidang yang memisahkan $C_1$ dan $C_2$ secara proper jika dan hanya jika

• Ingat bahwa dua himpunan konveks $C$ dan $P$ yang memenuhi

dapat dipisahkan secara proper, yaitu oleh hiperbidang yang tidak memuat $C$ dan $P$ sekaligus.

• Jika $P$ polihedral dan syarat yang sedikit lebih kuat

berlaku, hiperbidang pemisah proper dapat dipilih agar tidak memuat $C$, yang tidak harus polihedral, sedangkan hiperbidang itu boleh memuat $P$.

Di sebelah kiri, hiperbidang pemisah dapat dipilih agar tidak memuat $C$. Di sebelah kanan, ketika $P$ tidak polihedral, pilihan semacam itu tidak mungkin.

Hiperbidang di $\mathbb R^{n+1}$ dengan normal $(\mu,\beta)$ disebut nonvertikal jika $\beta\neq0$.

• Hiperbidang itu memotong sumbu ke-$(n+1)$ pada $\xi=(\mu/\beta)'\bar u+\bar w$, dengan $(\bar u,\bar w)$ sebarang vektor pada hiperbidang tersebut.

• Hiperbidang nonvertikal yang menempatkan epigraf suatu fungsi di setengah ruang “atas” memberikan batas bawah bagi nilai fungsi tersebut.

• Epigraf fungsi konveks proper tidak memuat garis vertikal dua arah yang lengkap. Karena itu, masuk akal bahwa epigraf tersebut termuat dalam setengah ruang “atas” suatu hiperbidang nonvertikal.

• Misalkan $C$ himpunan bagian konveks tak kosong dari $\mathbb R^{n+1}$ yang tidak memuat garis vertikal dua arah. Maka:

  1. $C$ termuat dalam setengah ruang tertutup suatu hiperbidang nonvertikal. Dengan kata lain, terdapat $\mu\in\mathbb R^n$, $\beta\in\mathbb R$ dengan $\beta\neq0$, dan $\gamma\in\mathbb R$ sedemikian sehingga

2. Jika $(\bar u,\bar w)\notin\operatorname{cl}(C)$, terdapat hiperbidang nonvertikal yang memisahkan $(\bar u,\bar w)$ dan $C$ secara ketat.

Bukti: Perhatikan bahwa $\operatorname{cl}(C)$ tidak memuat garis vertikal dua arah. Memang, $C$ tidak memuat garis demikian, $\operatorname{ri}(C)$ juga tidak, sedangkan $\operatorname{ri}(C)$ dan $\operatorname{cl}(C)$ mempunyai kerucut resesi yang sama. Jadi cukup ditinjau kasus ketika $C$ tertutup.

(a) Himpunan $C$ adalah irisan semua setengah ruang tertutup yang memuat $C$. Jika semuanya bersesuaian dengan hiperbidang vertikal, $C$ akan memuat garis vertikal dua arah.

(b) Ada hiperbidang yang memisahkan $(\bar u,\bar w)$ dan $C$ secara ketat. Jika hiperbidang itu nonvertikal, hasilnya langsung diperoleh. Jika vertikal, orientasikan fungsi afin pemisahnya $g_0$ sehingga $g_0\geq0$ pada $C$ dan $g_0(\bar u,\bar w)<0$. Dari bagian (a), orientasikan fungsi setengah ruang nonvertikal $h$ sehingga $h\geq0$ pada $C$. Untuk $\epsilon>0$, fungsi $g_\epsilon=g_0+\epsilon h$ tetap tak negatif pada $C$ dan nonvertikal. Karena $g_0(\bar u,\bar w)<0$ dan $h(\bar u,\bar w)$ berhingga, $g_\epsilon(\bar u,\bar w)<0$ tetap berlaku untuk $\epsilon>0$ yang cukup kecil. Jadi hiperbidang $g_\epsilon=0$ memberikan pemisahan ketat yang diminta.

Perhatikan fungsi $f$ dan epigrafnya. Hiperbidang nonvertikal yang memberi batas bawah pada $\operatorname{epi}(f)$ bersesuaian dengan titik potong pada sumbu vertikal; bila supremum berikut tercapai, hiperbidangnya benar-benar pendukung:

• Untuk sebarang $f:\mathbb R^n\to[-\infty,+\infty]$, fungsi konjugat konveksnya didefinisikan oleh

Ketiga contoh memakai definisi

• Dari definisi

tampak bahwa $f^*$ konveks dan tertutup.

• Alasan: $\operatorname{epi}(f^*)$ adalah irisan epigraf fungsi-fungsi afin terhadap $y$,

ketika $x$ merentang $\mathbb R^n$.

• Perhatikan konjugat dari konjugat:

• Fungsi $f^{**}$ konveks dan tertutup.

• Fakta penting / teorema konjugasi: Jika $f$ tertutup, proper, dan konveks, maka $f^{**}=f$.

Visualisasi mengulangi

dan

• Jika $f$ tertutup, konveks, dan proper, maka $f^{**}=f$.

• Misalkan $f:\mathbb R^n\to(-\infty,+\infty]$ suatu fungsi, misalkan $\check{\operatorname{cl}}f$ tutupan konveksnya, misalkan $f^*$ konjugat konveksnya, dan perhatikan konjugat dari $f^*$,

1. Kita mempunyai

2. Jika $f$ konveks, keproperan salah satu dari $f$, $f^*$, dan $f^{**}$ mengakibatkan keproperan dua yang lain.

3. Jika $f$ tertutup, proper, dan konveks, maka

4. Jika $\check{\operatorname{cl}}f(x)>-\infty$ untuk semua $x\in\mathbb R^n$, maka

• (a) Untuk semua $x,y$, berlaku $f^*(y)\geq y'x-f(x)$. Akibatnya, $f(x)\geq\sup_y\{y'x-f^*(y)\}=f^{**}(x)$.

• (c) Dengan kontradiksi, andaikan ada $(x,\gamma)\in\operatorname{epi}(f^{**})$ tetapi $(x,\gamma)\notin\operatorname{epi}(f)$. Ada hiperbidang nonvertikal bernormal $(y,-1)$ yang memisahkan $(x,\gamma)$ dari $\operatorname{epi}(f)$ secara ketat. (Komponen vertikal vektor normal dinormalkan menjadi $-1$.)

Sebuah kontra-contoh dengan fungsi $f:\mathbb R\to[-\infty,+\infty]$ yang tertutup dan konveks tetapi tak proper menunjukkan perlunya asumsi proper agar $f=f^{**}$:

Kita mempunyai

dan

Namun,