Kuliah 6: Irisan Himpunan Tertutup, Ketertutupan, dan Hiperbidang

• Ketakkosongan irisan himpunan tertutup

  • Versi sederhana
  • Versi yang lebih kompleks

• Keberadaan solusi optimal

• Pelestarian ketertutupan di bawah transformasi linear

• Hiperbidang

Pertanyaan mendasar: Diberikan barisan himpunan tertutup tak kosong $\{C_k\}$ di $\mathbb R^n$ dengan $C_{k+1}\subset C_k$ untuk setiap $k$, kapan

tak kosong?

• Teorema irisan himpunan penting setidaknya dalam tiga konteks utama yang akan dibahas berikut ini:

  Apakah fungsi $f:\mathbb R^n\to(-\infty,\infty]$ mencapai nilai minimum pada suatu himpunan $X$?

  Hal ini benar jika dan hanya jika

Jika $C$ tertutup dan $A$ sebuah matriks, apakah $AC$ tertutup?

• Jika $C_1$ dan $C_2$ tertutup, apakah $C_1+C_2$ tertutup?

  • Ini merupakan kasus khusus.
  • Tuliskan

• Misalkan $C$ adalah himpunan konveks tertutup tak kosong dan $A$ adalah matriks dengan ruang nol $N(A)$. Maka $AC$ tertutup jika $R_C\cap N(A)=\{0\}$.

  Bukti (langkah bersarang diperbaiki): Misalkan $\{y_k\}\subset AC$ dan $y_k\to\bar y$. Ambil $r_k=\sup_{j\geq k}\lVert y_j-\bar y\rVert$, lalu definisikan $C_k=C\cap N_k$, dengan

Karena $y_k\in W_k$, setiap $C_k$ tak kosong; karena $W_{k+1}\subset W_k$, barisan $\{C_k\}$ bersarang. Selain itu, $R_{N_k}=N(A)$, sehingga $R_{C_k}=R_C\cap N(A)=\{0\}$ dan $C_k$ kompak. Teorema irisan memberi $\bar x\in\bigcap_k C_k$; karena $r_k\to0$, berlaku $A\bar x=\bar y$. Jadi $\bar y\in AC$. Terbukti.

• Kasus khusus: $C_1+C_2$ tertutup jika $C_1,C_2$ tertutup dan salah satu di antaranya kompak. [Tuliskan $C_1+C_2=A(C_1\times C_2)$, dengan $A(x_1,x_2)=x_1+x_2$.]

• Teorema terkait: $AX$ tertutup jika $X$ polihedral. Hal ini akan ditunjukkan kemudian dengan metode yang lebih halus.

• Misalkan $F:\mathbb R^{n+m}\to(-\infty,\infty]$ adalah fungsi konveks tertutup proper, dan tinjau

• Jika $F(x,z)$ tertutup, apakah $f(x)$ tertutup?

  • Pertanyaan penting dalam teori dualitas.

• Fakta pertama: Jika $F$ konveks, maka $f$ juga konveks.

• Fakta kedua:

dengan $P(\cdot)$ menyatakan proyeksi ke ruang $(x,w)$; yaitu, untuk sebarang subhimpunan $S$ dari $\mathbb R^{n+m+1}$, $P(S)=\{(x,w)\mid\exists z\in\mathbb R^m:\ (x,z,w)\in S\}$.

• Jadi, jika $F$ tertutup dan terdapat struktur yang menjamin bahwa proyeksi mempertahankan ketertutupan, maka $f$ tertutup.

• … tetapi kekonveksan dan ketertutupan $F$ tidak menjamin ketertutupan $f$.

• Hubungan antara pelestarian ketertutupan di bawah minimisasi parsial dan ketercapaian infimum atas $z$ untuk $x$ tetap.

• $F$ konveks dan tertutup, tetapi

tidak tertutup.

Misalkan $F:\mathbb R^{n+m}\to(-\infty,\infty]$ adalah fungsi konveks tertutup proper, dan tinjau $f(x)=\inf_{z\in\mathbb R^m}F(x,z)$.

• Setiap teorema irisan himpunan menghasilkan suatu hasil ketertutupan. Kasus paling sederhana adalah sebagai berikut:

• Pelestarian Ketertutupan di Bawah Kekompakan: Jika terdapat $\bar{x}\in\mathbb R^n$ dan $\bar{\gamma}\in\mathbb R$ sedemikian sehingga himpunan

tak kosong dan kompak, maka $f$ konveks, tertutup, dan proper. Selain itu, untuk setiap $x\in\operatorname{dom}(f)$, himpunan titik peminimum $F(x,\cdot)$ tak kosong dan kompak.

• Kita telah mencatat bahwa tiga pertanyaan dasar berikut mempunyai akar matematis yang sama:

  • Keberadaan solusi masalah optimisasi konveks

  • Terpeliharanya ketertutupan himpunan konveks di bawah transformasi linear

  • Terpeliharanya ketertutupan fungsi konveks di bawah minimisasi parsial

• Akar bersama itu adalah pertanyaan tentang ketakkosongan irisan suatu barisan bersarang himpunan tertutup.

• Pembahasan sebelumnya dalam kuliah ini menyelesaikan pertanyaan tersebut dengan mengasumsikan bahwa semua himpunan dalam barisan itu kompak.

• Pembahasan yang lebih tajam sebagai gantinya membuat berbagai asumsi tentang arah resesi dan ruang kelinieran himpunan-himpunan dalam barisan tersebut.

• Setelah teori irisan himpunan yang cukup tajam dikembangkan, dapat diperoleh hasil-hasil yang lebih kuat mengenai ketiga pertanyaan itu.

• Slide-slide selanjutnya hingga pembahasan hiperbidang merangkum pengembangan ini sebagai bantuan belajar mandiri dengan menggunakan Bagian 1.4.2, 1.4.3, 3.2, dan 3.3.

• Diberikan suatu barisan bersarang $\{C_k\}$ dari himpunan-himpunan konveks tertutup. Barisan $\{x_k\}$ disebut barisan asimtotik jika

  $$x_k\in C_k, \qquad x_k\neq0, \qquad k=0,1,\ldots$$

  dan

  $$\lVert x_k\rVert\to\infty, \qquad \frac{x_k}{\lVert x_k\rVert}\to\frac{d}{\lVert d\rVert},$$

  dengan $d$ suatu arah resesi bersama tak nol dari himpunan-himpunan $C_k$.

• Sebagai kasus khusus, kita mendefinisikan barisan asimtotik dari suatu himpunan konveks tertutup $C$ dengan memakai $C_k\equiv C$.

• Setiap barisan tak terbatas $\{x_k\}$ dengan $x_k\in C_k$ mempunyai subbarisan asimtotik.

• Barisan $\{x_k\}$ disebut retraktif jika untuk suatu $\bar{k}$ berlaku

  $$x_k-d\in C_k, \qquad \forall k\geq\bar{k}.$$

• Barisan bersarang $\{C_k\}$ dari himpunan-himpunan konveks tertutup disebut retraktif jika semua barisan asimtotiknya retraktif.

• Setengah-ruang tertutup, jika dipandang sebagai barisan dengan semua komponen identik, bersifat retraktif.

• Irisan dan hasil kali Kartesius dari barisan-barisan himpunan retraktif bersifat retraktif.

• Himpunan polihedral bersifat retraktif. Selain itu, jumlah vektor dari suatu himpunan konveks kompak dan suatu himpunan konveks retraktif juga retraktif.

• Kerucut nonpolihedral dan himpunan sublevel fungsi kuadratik belum tentu retraktif.

• Proposisi. Jika $\{C_k\}$ retraktif, maka $\bigcap_{k=0}^{\infty}C_k$ tak kosong.

• Gagasan utama bukti:

  1. Irisan $\bigcap_{k=0}^{\infty}C_k$ kosong jika dan hanya jika barisan $\{x_k\}$ yang terdiri atas vektor bernorma minimum di $C_k$ tak terbatas (sehingga suatu subbarisannya asimtotik).

  2. Barisan asimtotik $\{x_k\}$ yang terdiri atas vektor bernorma minimum tidak mungkin retraktif, sebab pergeseran berlawanan dengan arah asimtotik pada akhirnya menghasilkan titik yang lebih dekat ke $0$.

• Proposisi. Misalkan $\{C_k\}$ adalah barisan bersarang dari himpunan-himpunan konveks tertutup tak kosong, dan $X$ adalah himpunan retraktif sedemikian sehingga semua himpunan $\bar C_k=X\cap C_k$ tak kosong. Andaikan

  $$R_X\cap R\subset L,$$

  dengan

  $$R=\bigcap_{k=0}^{\infty}R_{C_k}, \qquad L=\bigcap_{k=0}^{\infty}L_{C_k}.$$

  Maka

  $$\{\bar C_k\}\text{ retraktif}, \qquad \bigcap_{k=0}^{\infty}\bar C_k\neq\varnothing.$$

• Kasus-kasus khusus:

  • $X=\mathbb R^n$ dan $R=L$ (himpunan-himpunan $C_k$ “silindris”)

  • $R_X\cap R=\{0\}$ (tidak ada arah resesi bersama tak nol dari $X$ dan $\bigcap_k C_k$)

Bukti. Himpunan arah resesi bersama dari $\bar C_k$ adalah $R_X\cap R$. Untuk sebarang barisan asimtotik $\{x_k\}$ yang bersesuaian dengan $d\in R_X\cap R$:

(1)

(2)

Jadi $\{\bar C_k\}$ retraktif.

• Tinjau

  $$\bigcap_{k=0}^{\infty}\bar C_k, \qquad \bar C_k=X\cap C_k.$$

• Syarat $R_X\cap R\subset L$ terpenuhi.

• Pada gambar kiri, $X$ bersifat polihedral.

• Pada gambar kanan, $X$ bersifat nonpolihedral dan tak retraktif, serta

  $$\bigcap_{k=0}^{\infty}\bar C_k=\varnothing.$$

• Teorema. Misalkan

  $$f(x)=x'Qx+c'x, \qquad X=\{x\mid a_j'x+b_j\leq0,\ j=1,\ldots,r\},$$

  dengan $Q$ simetris semidefinit positif. Jika nilai minimum $f$ pada $X$ berhingga, terdapat titik peminimum $f$ pada $X$.

• Bukti (garis besar). Tuliskan

  $$\text{Himpunan Titik Peminimum} =\bigcap_{k=0}^{\infty} \left(X\cap\{x\mid x'Qx+c'x\leq\gamma_k\}\right)$$

  dengan

  $$\gamma_k\downarrow f^*=\inf_{x\in X}f(x).$$

  Verifikasikan syarat $R_X\cap R\subset L$ dari teorema irisan himpunan sebelumnya, dengan $R$ dan $L$ masing-masing merupakan himpunan arah resesi bersama dan arah kelinieran bersama dari himpunan-himpunan

  $$\{x\mid x'Qx+c'x\leq\gamma_k\}.$$

  Terbukti.

• Misalkan $C$ adalah himpunan konveks tertutup tak kosong dan $A$ adalah matriks dengan ruang nol $N(A)$.

  1. $AC$ tertutup jika $R_C\cap N(A)\subset L_C$.

  2. $A(X\cap C)$ tertutup jika $X$ adalah himpunan retraktif dan

  $$R_X\cap R_C\cap N(A)\subset L_C.$$

• Bukti (garis besar yang dilengkapi). Untuk bagian (a), misalkan $\{y_k\}\subset AC$ dan $y_k\to\bar y$. Tetapkan $r_k=\sup_{j\geq k}\lVert y_j-\bar y\rVert$, lalu definisikan $C_k=C\cap N_k$ dan

  $$N_k=\{x\mid Ax\in W_k\}, \qquad W_k=\{z\mid\lVert z-\bar y\rVert\leq r_k\}.$$

  Barisan $\{C_k\}$ kini tak kosong, tertutup, dan bersarang. Syarat $R_C\cap N(A)\subset L_C$ membuatnya retraktif melalui teorema irisan sebelumnya, sehingga $\bigcap_k C_k\neq\varnothing$ dan setiap titik irisannya dipetakan ke $\bar y$.

  Untuk bagian (b), mulai dengan $\{y_k\}\subset A(X\cap C)$ dan gunakan $\bar C_k=X\cap C\cap N_k$. Syarat $R_X\cap R_C\cap N(A)\subset L_C$ bersama sifat retraktif $X$ memberi $\bigcap_k\bar C_k\neq\varnothing$, sehingga lagi-lagi $\bar y$ mempunyai praimaji dalam $X\cap C$.

• Kasus khusus. $AX$ tertutup jika $X$ polihedral.

Perhatikan ketertutupan $A(X\cap C)$.

• Dalam kedua contoh, syarat

  $$R_X\cap R_C\cap N(A)\subset L_C$$

  dipenuhi.

• Namun, pada contoh di kanan, $X$ tidak retraktif dan himpunan $A(X\cap C)$ tidak tertutup.

• Misalkan $C_1,\ldots,C_m$ adalah himpunan bagian konveks tertutup tak kosong dari $\mathbb R^n$. Andaikan persamaan $d_1+\cdots+d_m=0$ untuk vektor-vektor $d_i\in R_{C_i}$ mengakibatkan $d_i=0$ bagi semua $i=1,\ldots,m$. Maka $C_1+\cdots+C_m$ adalah himpunan tertutup.

• Kasus Khusus: Jika $C_1$ dan $-C_2$ adalah himpunan konveks tertutup, maka $C_1-C_2$ tertutup jika $R_{C_1}\cap R_{C_2}=\{0\}$.

Bukti: Produk Kartesius

adalah himpunan konveks tertutup, dan kerucut resesinya adalah

Definisikan $A$ dengan

Maka

dan

Berdasarkan syarat yang diberikan, $R_C\cap N(A)=\{0\}$, sehingga $AC$ tertutup. Q.E.D.

• Hiperbidang adalah himpunan berbentuk $\{x\mid a'x=b\}$, dengan $a$ suatu vektor tak nol di $\mathbb R^n$ dan $b$ suatu skalar.

• Dua himpunan $C_1$ dan $C_2$ dikatakan dipisahkan oleh hiperbidang $H=\{x\mid a'x=b\}$ jika masing-masing terletak di setengah-ruang tertutup berbeda yang terkait dengan $H$, yaitu

  salah satu dari

  $$a'x_1\leq b\leq a'x_2, \qquad \forall x_1\in C_1,\quad \forall x_2\in C_2,$$

  atau

  $$a'x_2\leq b\leq a'x_1, \qquad \forall x_1\in C_1,\quad \forall x_2\in C_2.$$

• Jika $\bar{x}$ termasuk dalam penutupan suatu himpunan $C$, hiperbidang yang memisahkan $C$ dan himpunan singleton $\{\bar{x}\}$ disebut hiperbidang pendukung bagi $C$ di $\bar{x}$.

• Hiperbidang pemisah dan pendukung:

• Hiperbidang pemisah $\{x\mid a'x=b\}$ yang tidak beririsan dengan $C_1$ maupun $C_2$ disebut memisahkan secara ketat jika

  $$a'x_1<b<a'x_2, \qquad \forall x_1\in C_1,\quad \forall x_2\in C_2.$$

• Misalkan $C$ konveks dan $\bar{x}$ suatu vektor yang bukan titik interior $C$. Maka terdapat hiperbidang yang melalui $\bar{x}$ dan memuat $C$ di salah satu setengah-ruang tertutupnya.

Bukti: Ambil barisan $\{x_k\}$ di luar $\operatorname{cl}(C)$ yang konvergen ke $\bar{x}$. Misalkan $\hat{x}_k$ adalah proyeksi $x_k$ pada $\operatorname{cl}(C)$. Untuk semua $x\in\operatorname{cl}(C)$ berlaku

dengan

Misalkan $a$ suatu titik limit dari $\{a_k\}$, lalu ambil limit ketika $k\to\infty$. Q.E.D.

• Misalkan $C_1$ dan $C_2$ adalah dua himpunan bagian konveks tak kosong dari $\mathbb R^n$. Jika $C_1$ dan $C_2$ saling lepas, terdapat hiperbidang yang memisahkan keduanya; dengan kata lain, terdapat vektor $a\neq0$ sedemikian sehingga

  $$a'x_1\leq a'x_2, \qquad \forall x_1\in C_1,\quad \forall x_2\in C_2.$$

Bukti: Perhatikan himpunan konveks

Karena $C_1$ dan $C_2$ saling lepas, titik asal tidak termasuk dalam $C_2-C_1$. Menurut Teorema Hiperbidang Pendukung, terdapat vektor $a\neq0$ sedemikian sehingga

yang ekuivalen dengan relasi yang diinginkan. Q.E.D.

• Teorema Pemisahan Ketat: Misalkan $C_1$ dan $C_2$ dua himpunan konveks tak kosong yang saling lepas. Jika $C_1$ tertutup dan $C_2$ kompak, terdapat hiperbidang yang memisahkan keduanya secara ketat.

Bukti: (Garis besar) Perhatikan himpunan $C_1-C_2$. Karena $C_1$ tertutup dan $C_2$ kompak, $C_1-C_2$ tertutup. Karena

misalkan $\bar{x}_1-\bar{x}_2$ adalah proyeksi $0$ pada $C_1-C_2$. Hiperbidang pemisah ketat dikonstruksi seperti pada panel (b).

• Catatan: Sebarang syarat yang menjamin ketertutupan $C_1-C_2$ menjamin keberadaan hiperbidang pemisah ketat. Namun, hiperbidang pemisah ketat dapat saja ada meskipun $C_1-C_2$ tidak tertutup.