Tập lồi (5) – Phân cách 2 tập lồi bằng siêu phẳng « CS Study Fun

Tháng Hai 2008
T2	T3	T4	T5	T6	T7	CN
		Tháng 3 »
	1	2	3
4	5	6	7	8	9	10
11	12	13	14	15	16	17
18	19	20	21	22	23	24
25	26	27	28	29

Tập lồi (5) – Phân cách 2 tập lồi bằng siêu phẳng

Đăng bởi tqlong on Tháng Hai 12, 2008

Định nghĩa (siêu phẳng): Tập $X$ là siêu phẳng trong $\mathbb{R}^n$ nếu $X$ là không gian affine $n-1$ chiều.

Định lý (dạng tuyến tính của siêu phẳng): Tập $X$ là siêu phẳng nếu và chỉ nếu $X$ có thể biểu diễn dưới dạng

$X=\{x:f^Tx=a,f\neq 0\}$ .

Chứng minh: Hiển nhiên vì không gian con $L$ gắn với $X$ có $n-1$ chiều.

Như vậy, siêu phẳng $X=\{x:f^Tx=a,f\neq 0\}$ chia $\mathbb{R}^n$ thành 2 phần

$M_-=\{x:f^Tx\leq a\}, M_+=\{x:f^Tx\geq a\}$

Định nghĩa (phân cách bằng siêu phẳng): Ta nói siêu phẳng $X=\{x:f^Tx=a,f\neq 0\}$ phân cách hai tập $S,T\neq\emptyset$ nếu

$S\subset M_-, T\subset M_+$ .
$S\cup T\nsubseteq X$ .

Nhận xét: Ta cũng nói dạng tuyến tính $f^Tx,f\neq 0$ phân cách được $S,T$ nếu tồn tại $a$ sao cho siêu phẳng tương ứng phân cách $S,T$ .

Định lý: Dạng tuyến tính $f^Tx$ phân cách được $S,T$ nếu và chỉ nếu

$\displaystyle\sup_{x\in S}f^Tx\leq \inf_{y\in T}f^Ty$ .
$\displaystyle\inf_{x\in S}f^Tx < \sup_{y\in T}f^Ty$ .

Chứng minh:

“ $\Rightarrow$ “: Nếu $f^Tx$ phân cách được $S,T$ , tồn tại $a$ sao cho siêu phẳng $X=\{x:f^Tx=a,f\neq 0\}$ phân cách $S,T$ , tức là

$\forall x\in S: f^Tx\leq a\Rightarrow \displaystyle\sup_{x\in S}f^Tx\leq a$

$\forall y\in T: f^Ty\geq a\Rightarrow \displaystyle\inf_{y\in T}f^Ty\geq a$

tức là $\displaystyle\sup_{x\in S}f^Tx\leq \inf_{y\in T}f^Ty$ .

Hơn nữa, ta phải có $\displaystyle\inf_{x\in S}f^Tx < \sup_{y\in T}f^Ty$ vì nếu $\displaystyle\inf_{x\in S}f^Tx = \sup_{y\in T}f^Ty$ thì $f^Tx=f^Ty,\forall x\in S, y\in T$ , tức là $S\cup T\subset X$ .

“ $\Leftarrow$ “: Chọn $a$ sao cho $\displaystyle\sup_{x\in S}f^Tx\leq a\leq\inf_{y\in T}f^Ty$ , rõ ràng siêu phẳng $X=\{x:f^Tx=a,f\neq 0\}$ phân cách $S,T$ .

Định lý (phân cách 2 tập lồi): Điều kiện cần và đủ để hai tập lồi $S,T\neq\emptyset$ phân cách được là phần trong tương đối của $S,T$ không giao nhau.

$\mathrm{rint}S\cap\mathrm{rint}T=\emptyset$ .

Chứng minh:

Bổ đề: Nếu dạng tuyến tính $f^Tx$ đạt giá trị cực đại (hoặc cực tiểu) trên tập lồi $X$ tại một điểm $x\in\mathrm{rint}X$ thì $f^Tx$ là hằng số trên $X$ .

Chứng minh: Ta chỉ cần chứng minh cho trường hợp cực đại, trường hợp cực tiểu là hệ quả nếu ta xét dạng tuyến tính $-f^Tx$ . Xét $y\in X$ , vì $x\in\mathrm{rint}X$ nên với $\epsilon>0$ đủ nhỏ ta có $z=x-\epsilon(y-x)\in X$ . Ta có

$x=\displaystyle \frac{1}{1+\epsilon}z+\frac{\epsilon}{1+\epsilon}y$

$\Rightarrow f^Tx=\displaystyle\frac{1}{1+\epsilon}f^Tz+\frac{\epsilon}{1+\epsilon}f^Ty$ .

Vì $f^Tz\leq f^Tx$ nên $f^Ty\geq f^Tx$ nếu không vế phải sẽ nhỏ hơn vế trái, suy ra $f^Ty=f^Tx,\forall y\in X$ .

“ $\Rightarrow$ “: Giả sử ngược lại, tức là tồn tại $a\in \mathrm{rint}S\cap\mathrm{rint}T$ và có dạng tuyến tính $f^Tx$ phân cách $S,T$ , ta có

$f^Ta\leq \displaystyle \sup_{x\in S}f^Tx\leq\inf_{y\in T}f^Ty\leq f^Ta$ .

Nghĩa là $f^Tx$ đạt cực tiểu trên $T$ tại $a\in \mathrm{rint}T$ , và $f^Tx$ đạt cực đại trên $S$ tại $a\in \mathrm{rint}S$ . Theo bổ đề trên, $f^Tx$ là hằng số trên $S,T$ :

$f^Tx=f^Ty=f^Ta,\forall x\in S,y\in T$ .

Như vậy, $f^Tx$ không phân cách được $S,T$ , mâu thuẫn.

“ $\Leftarrow$ “: Ta sẽ chứng minh theo thứ tự sau

(i) Trường hợp $S=\mathrm{Conv}\{x_1,\ldots,x_n\} , T=\{x\}, x\notin S$ .

(ii) Trường hợp $S$ là tập lồi bất kì, $T=\{x\}, x\notin S$ .

(iii) Trường hợp $S,T$ là hai tập lồi bất kì và $S\cap T=\emptyset$ .

(iv) Trường hợp $S,T$ là hai tập lồi bất kì và $\mathrm{rint}S\cap \mathrm{rint}T=\emptyset$ .

Chứng minh (i): Đặt

$\beta_i=\left[\begin{array}{c}x_i\\1\end{array}\right],i=1,\ldots,n,\beta=\left[\begin{array}{c}x\\1\end{array}\right]$ .

Ta thấy $\beta$ không thể là tổ hợp nón của $\beta_i, i=1,\ldots,n$ vì nếu vậy

$\left[\begin{array}{c}x\\1\end{array} \right]=\displaystyle \sum_{i=1}^n\lambda_i\left[\begin{array}{c}x_i\\1\end{array} \right],\lambda_i\geq 0$ .

Tức là $x= \displaystyle \sum_{i=1}^n\lambda_i x_i,\sum_{i=1}^n\lambda_i=1,\lambda_i\geq 0$ hay $x\in S$ .

Theo định lý Farkas thuần nhất, phải tồn tại véctơ $h$ sao cho

$h^T\beta_i\leq 0,i=1,\ldots,n$ nhưng $h^T\beta > 0$ .

trong đó $h=\left[\begin{array}{c}f\\c\end{array} \right]$ .

Nghĩa là $f^Tx_i+c\leq 0< f^Tx+c$ hay $f^Tx_i<f^Tx,i=1,\ldots,n$ . Mặt khác, nếu $y\in S, y=\displaystyle \sum_{i=1}^n\lambda_i x_i, \sum_{i=1}^n\lambda_i=1,\lambda_i\geq 0$ thì

$f^Ty= \displaystyle \sum_{i=1}^n\lambda_i f^Tx_i\leq\max_i f^Tx_i<f^Tx$ .

Tức là dạng tuyến tính $f^Tx$ phân cách hai tập $S=\mathrm{Conv}\{x_1,\ldots,x_n\} , T=\{x\}, x\notin S$ .

Bổ đề 1: Nếu tập $S\subset\mathrm{R}^n, S\neq\emptyset$ thì tồn tại chuỗi $\{x_i\}_{i=1}^\infty, x_i\in S$ trù mật trong $S$ , nghĩa là với mọi điểm $x\in S$ , có một chuỗi con $\{x_{i_k}\}_{k=1}^\infty\rightarrow x$ .

Chứng minh: Đặt chuỗi $\{r_i\}_{i=1}^\infty, r_i\in\mathrm{R}^n$ là chuỗi tất cả các véctơ hữu tỉ trong $\mathrm{R}^n$ (lưu ý: tập các véctơ hữu tỉ trong $\mathrm{R}^n$ là tập đếm được). Ta xây dựng chuỗi $\{x_i\}_{i=1}^\infty, x_i\in S$ như sau

Với mọi $t=1,2,\ldots$ , với mọi $i=1,2,\ldots$ , đưa một điểm $z\in S$ sao cho $||z-r_i||<\displaystyle\frac{1}{t}$ vào tập $X_t$ nếu có $z$ như vậy. Chuỗi $\{r_i\}_{i=1}^\infty$ trù mật trong $\mathrm{R}^n$ nên với mọi $x\in S$ , có một điểm $r_i$ nào đó sao cho $||x-r_i||<\displaystyle\frac{1}{t}$ . Vì thế $X_t\neq \emptyset$ , đồng thời $X_t$ là tập đếm được (do với mỗi $i$ chỉ có nhiều nhất một điểm $z\in S$ được đưa vào $X_t$ ).
Tập $X=\displaystyle \cup_{i=1}^\infty X_i$ là tập đếm được (hợp đếm được các tập đếm được) nên có thể viết thành chuỗi $\{x_i\}_{i=1}^\infty, x_i\in S$ .

Ta sẽ chứng minh $X$ trù mật trong $S$ . Thật vậy, với mọi $x\in S$ , với mọi $t=1,2,\ldots$ , ta có một điểm $r_i$ sao cho $||x-r_i||<\displaystyle\frac{1}{t}$ . Trong quá trình xây dựng $X_t$ , ta đã đưa vào $X_t$ một điểm $z\in S$ sao cho $||z-r_i||<\displaystyle\frac{1}{t}$ nên $||x-z||<\displaystyle\frac{2}{t}$ . Tức là, với mọi $x\in S$ , với mọi $t=1,2,\ldots$ , ta luôn tìm được một điểm $z\in X$ sao cho $||x-z||<\displaystyle\frac{2}{t}$ , nói cách khác $X$ trù mật trong $S$ .

Bổ đề 2: Hai tập $S,T$ phân cách được nếu và chỉ nếu tồn tại dạng tuyến tính $f^Tx$ phân cách $S,T$ với $f\in\mathrm{Lin}(S\cup T)$ .

Chứng minh:

“ $\Rightarrow$ “: hiển nhiên.

“ $\Leftarrow$ “: Nếu $S,T$ phân cách được thì tồn tại dạng tuyến tính $f^Tx, f\in\mathrm{R}^n,f\neq 0$ phân cách $S,T$ . Chiếu $f$ xuống $\mathrm{Lin}(S\cup T)$ ta được

$f=f_1+f_2, f_1\in \mathrm{Lin}(S\cup T), f_2\in\mathrm{Lin}(S\cup T)^\perp$ .

Ta thấy $f_1\neq 0$ vì nếu $f_1=0$ thì $f^Tx=f_2^Tx=0,\forall x\in S\cup T$ và dạng tuyến tính $f_1^Tx$ cũng phân cách $S,T$ vì $f^Tx=(f_1+f_2)^Tx=f_1^Tx,\forall x\in S\cup T$ .

Chứng minh (ii): Xét 2 tập lồi $\widehat S=S-x, \widehat T=\{0\}$ , rõ ràng $0\notin S$ vì nếu không $x\in S$ . Theo bổ đề 1 có chuỗi $\{x_i\}_{i=1}^\infty, x_i\in \widehat S$ trù mật trong $\widehat S$ , đồng thời theo (i) hai tập lồi $\mathrm{Conv}\{x_i\}_{i=1}^n$ và $\widehat T$ phân cách được với mọi $n$ . Như vậy, theo bổ đề 2, tồn tại dạng tuyến tính $f_n^Tx$ với $f_n\in \mathrm{Lin}(\widehat S)$ sao cho

$\displaystyle f_n^T0=0\geq \max_{i=1}^n f_n^T x_i,\forall n$ .

Không mất tính tổng quát, giả sử $||f_n||=1$ . Như vậy, chuỗi $\{f_n\}_{n=1}^\infty$ phải chứa một chuỗi con $\{f_{n_k}\}_{k=1}^\infty$ hội tụ đến $f\in \mathrm{Lin}(\widehat S)$ nào đó với $||f||=1$ và đương nhiên $f^Tx_i\leq 0,i=1,2,\ldots$ do hàm $f^Tx$ liên tục. Mặt khác, do $\{x_i\}_{i=1}^\infty$ trù mật trong $\widehat S$ nên

$\displaystyle \sup_{x\in\widehat S}f^Tx = \sup_i f^Tx_i\leq 0$

Ta sẽ chứng minh $\displaystyle \inf_{x\in\widehat S}f^Tx<0$ . Thật vậy, nếu ngược lại $\displaystyle \inf_{x\in\widehat S}f^Tx\geq 0$ , nghĩa là $f^Tx=0,\forall x\in\widehat S$ . Do $f\in\mathrm{Lin}(\widehat S)$ nên chỉ có một khả năng là $f=0$ , mâu thuẫn vì $||f||=1$ . Như vậy $\widehat S=S-x, \widehat T=\{0\}$ phân cách được bằng dạng tuyến tính $f^Tx$ . Từ đó dễ dàng suy ra $f^Tx$ cũng phân cách $S,T$ vì $S,T$ là ảnh của phép tịnh tiến $S=\widehat S+x, T=\widehat T+x$ .

Chứng minh (iii): Xét 2 tập lồi $\widehat S=S-T, \widehat T=\{0\}$ . Rõ ràng $\widehat S$ lồi vì nó là tổ hợp tuyến tính của hai tập lồi, đồng thời $0\notin \widehat S$ vì nếu không $S\cap T\neq\emptyset$ . Theo (ii), phải có dạng tuyến tính $f^Tx$ phân cách $\widehat S, \widehat T$ . Tức là

$\begin{cases}\displaystyle \sup_{u\in \widehat S}f^Tu\leq\inf_{v\in \widehat T}f^Tv\\\displaystyle \inf_{u\in \widehat S}f^Tu<\sup_{v\in \widehat T}f^Tv\end{cases}$

$\Leftrightarrow \begin{cases}\displaystyle \sup_{x\in S,y\in T}(f^Tx-f^Ty)=\sup_{x\in S}f^Tx-\inf_{y\in T}f^Ty\leq 0\\\displaystyle \inf_{x\in S,y\in T}(f^Tx-f^Ty)=\inf_{x\in S}f^Tx-\sup_{y\in T}f^Ty<0\end{cases}$

$\Leftrightarrow \begin{cases}\displaystyle \sup_{x\in S}f^Tx\leq\inf_{y\in T}f^Ty\\\displaystyle \inf_{x\in S}f^Tx<\sup_{y\in T}f^Ty\end{cases}$

Tức là $f^Tx$ phân cách $S,T$ .

Chứng minh (iv): Xét 2 tập lồi $\widehat S=\mathrm{rint}S, \widehat T=\mathrm{rint}T$ , theo giả thiết $\widehat S\cap \widehat T\neq\emptyset$ nên theo (iii) tồn tại dạng tuyến tính $f^Tx$ phân cách $\widehat S, \widehat T$ . Tức là

$\begin{cases}\displaystyle \sup_{u\in \widehat S}f^Tu\leq\inf_{v\in \widehat T}f^Tv\\\displaystyle \inf_{u\in \widehat S}f^Tu<\sup_{v\in \widehat T}f^Tv\end{cases}$

Vì phần trong tương đối trù mật trong bao đóng và hàm $f^Tx$ liên tục nên

$\displaystyle\sup_{u\in \widehat S}f^Tu=\sup_{x\in S}f^Tx, \inf_{u\in \widehat S}f^Tu=\inf_{x\in S}f^Tx$

$\displaystyle\sup_{v\in \widehat T}f^Tv=\sup_{y\in T}f^Ty, \inf_{v\in \widehat T}f^Tv=\inf_{y\in T}f^Ty$ ,

như vậy, $f^Tx$ cũng phân cách $S,T$ .

Định nghĩa (phân cách chặt): Hai tập $S,T$ phân cách chặt nếu tồn tại dạng tuyến tính $f^Tx$ sao cho

$\displaystyle\sup_{x\in S}f^Tx < \inf_{y\in T}f^Ty$ .

Nhận xét:

$S,T$ phân cách chặt thì cũng phân cách được.
$S,T$ phân cách chặt thì rời nhau: $S\cap T=\emptyset$ nhưng điều ngược lại không đúng (kể cả khi hai tập lồi).

Định lý (phân cách chặt hai tập lồi): Điều kiện cần và đủ để hai tập lồi $S,T\neq\emptyset$ phân cách chặt là khoảng cách giữa chúng lớn hơn 0.

$d=\displaystyle \inf_{x\in S,y\in T}||x-y||>0$ .

Chứng minh:

“ $\Rightarrow$ “: Giả sử hai tập lồi $S,T\neq\emptyset$ phân cách chặt và tồn tại dạng tuyến tính $f^Tx$ sao cho

$\displaystyle\sup_{x\in S}f^Tx < \inf_{y\in T}f^Ty$ .

Ta sẽ chứng minh

$d=\displaystyle \inf_{x\in S,y\in T}||x-y||>0$ .

Thật vậy, giả sử ngược lại $d=0$ , nghĩa là tồn tại hai chuỗi $\{x_i\}_{i=1}^\infty, x_i\in S, \{y_i\}_{i=1}^\infty, y_i\in T$ , sao cho

$\displaystyle \lim_{i=1}^\infty ||x_i-y_i||=0$

Vì hàm $f^Tx$ liên tục nên $\displaystyle\lim_{i=1}^\infty(f^Tx_i-f^Ty_i)=0$ . Ta lại có

$\displaystyle\lim_{i=1}^\infty(f^Tx_i-f^Ty_i)\leq \left(\sup_{x\in S}f^Tx - \inf_{y\in T}f^Ty\right) < 0$

suy ra mâu thuẫn.

“ $\Leftarrow$ “: Giả sử $d=\displaystyle \inf_{x\in S,y\in T}||x-y||>0$ . Xét $S_+$ là lân cận $\displaystyle \frac{d}{2}$ của S:

$S_+=S+\{r:||r||\leq\displaystyle \frac{d}{2}\}$

Vì $S$ lồi nên $S_+$ cũng lồi, đồng thời $S_+\cap T=\emptyset$ vì $d(S_+,T)\geq\displaystyle \frac{d}{2}$ . Theo định lý phân cách trên, ta có dạng tuyến tính $f^Tx$ phân cách $S_+, T$ . Tức là

$\displaystyle \sup_{x\in S_+}f^Tx\leq\inf_{y\in T}f^Ty$

$\displaystyle \sup_{x\in S,||r||<\frac{d}{2}}f^T(x+r)\leq\inf_{y\in T}f^Ty$

Tức là $\displaystyle\sup_{x\in S}f^Tx+\frac{d}{2}||f||\leq\inf_{y\in T}f^Ty$ , suy ra $\displaystyle\sup_{x\in S}f^Tx<\inf_{y\in T}f^Ty$ .

Bài viết này được đăng vào Tháng Hai 12, 2008 lúc 8:39 sáng và tập tin được lưu ở Giải tích lồi. Tagged: cực tiểu, cực đại, dãy con, dạng tuyến tính, farkas, liên tục, phân cách, phần trong, siêu phẳng, tập lồi, tổ hợp nón, tổ hợp tuyến tính, trù mật. Bạn có thể theo dõi các phản hồi của bài viết này thông qua RSS 2.0 dòng thông tin. Bạn có thể Để lại lời nhắn, hoặc trackback từ trang của bạn.

Để lại hồi âm

« Tập lồi (4) – Tính chất tôpô

Tập lồi (6) – Siêu phẳng đỡ và điểm cực biên »

	Khuyen Nguyen trong bài Phân lớp bằng siêu phẳng (1) …
	tqlong trong bài Phân lớp bằng siêu phẳng (1) …
	Khuyen Nguyen trong bài Phân lớp bằng siêu phẳng (1) …
	tqlong trong bài Bất đẳng thức xác suất (1) …
	H.T.D. trong bài Bất đẳng thức xác suất (1) …

CS Study Fun – Khoa học máy tính

Learn & Enjoy …

Phân loại

Lưu trữ

Thống kê

Bài gần đây

Lời bình gần đây

Trang

Blogroll

Quản trị

Lịch

Theo dõi

Blog D.Q. Huy

Các phương pháp điểm trong

Xem nhiều nhất

Từ khóa

Tập lồi (5) – Phân cách 2 tập lồi bằng siêu phẳng

Để lại hồi âm