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

Learn & Enjoy …

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

Posted by Trần Quốc Long on Tháng Hai 12, 2008

Định nghĩa (siêu phẳng): Tập Xsiê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 Xn-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

  1. S\subset M_-, T\subset M_+.
  2. 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

  1. \displaystyle\sup_{x\in S}f^Tx\leq \inf_{y\in T}f^Ty.
  2. \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ạia 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.

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

  1. 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).
  2. 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,Tf^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\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,TS,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:

  1. S,T phân cách chặt thì cũng phân cách được.
  2. 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}\}

S lồi nên S_+ cũng lồi, đồng thời S_+\cap T=\emptysetd(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.

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

 
%d bloggers like this: