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

Learn & Enjoy …

Posts Tagged ‘farkas’

« Những bài viết trước

Phân tích các phương pháp điểm trong (1) – Bài toán gốc và bài toán đối ngẫu

Đăng bởi tqlong on Tháng Ba 13, 2008

Ta đã biết, các phương pháp điểm trong chú trọng vào việc giải bài toán QHTT ở dạng chuẩn tắc

\displaystyle \mathrm{Opt}(P)=\min_x \{c^Tx: Ax=b, x\geq 0\} ~~(P)

và bài toán đối ngẫu

\displaystyle \mathrm{Opt}(D)=\max_{\lambda,s} \{\lambda^Tb: A^T\lambda+s=c, s\geq 0\}~~(D)

Ta sẽ xem xét mối quan hệ giữa nghiệm \displaystyle x và \displaystyle (\lambda,s) của hai bài toán này.
Định lý (điều kiện của nghiệm tối ưu): \displaystyle (x^*,\lambda^*,s^*) là nghiệm tối ưu của \displaystyle (P),(D) nếu và chỉ nếu các điều kiện sau đồng thời thỏa mãn

  1. \displaystyle Ax^* = b.
  2. \displaystyle A^T\lambda^* + s^* = c.
  3. \displaystyle (x^*)^Ts^* = 0.
  4. \displaystyle (x^*,s^*)\geq 0.

Lưu ý: Điều kiện (3) và (4) đồng nghĩa với \displaystyle x_i^*s_i^* = 0,\forall i=1,\ldots,n.
Chứng minh:
“\displaystyle \Leftarrow“: Giả sử các điều kiện trên đều được thỏa mãn tại \displaystyle (x^*,\lambda^*,s^*), ta có

\displaystyle 0 = (s^*)^Tx^* = (c-A^T\lambda^*)^Tx^*=c^Tx^*-(\lambda^*)^Tb

Tức là giá trị hàm mục tiêu của hai bài toán \displaystyle (P),(D) tại \displaystyle x^* và \displaystyle (\lambda^*,s^*) bằng nhau. Mặt khác nếu \displaystyle (x,\lambda,s) là nghiệm chấp nhận được bất kì của \displaystyle (P),(D) thì

\displaystyle c^Tx-\lambda^Tb=(c-A^T\lambda)^Tx= s^Tx\geq 0 do \displaystyle (x,s)\geq 0

tức là giá trị hàm mục tiêu của bài toán gốc luôn lớn hơn giá trị hàm mục tiêu của bài toán đối ngẫu. Vì thế \displaystyle (x^*,\lambda^*,s^*) là nghiệm tối ưu của hai bài toán \displaystyle (P),(D).
“\displaystyle \Rightarrow“: Giả sử \displaystyle (x^*,\lambda^*,s^*) là nghiệm tối ưu của hai bài toán \displaystyle (P),(D). Các điều kiện (1),(2),(4) đã được thỏa mãn, ta chỉ cần chứng minh điều kiện (3). Đặt

\displaystyle \mathrm{Opt}(P) = c^Tx^*

là giá trị tối ưu của bài toán gốc. Như vậy bất đẳng thức \displaystyle c^Tx\geq \mathrm{Opt}(P) là hệ quả của hệ bất đẳng thức

\displaystyle \begin{cases}Ax=b\\x\geq 0\end{cases}

Áp dụng định lý Farkas không thuần nhất, ta có, tồn tại \displaystyle \lambda và \displaystyle s\geq 0 sao cho

\displaystyle \begin{cases}A^T\lambda+s=c\\s\geq 0\\\lambda^Tb\geq \mathrm{Opt}(P)\end{cases}

Nghĩa là \displaystyle (\lambda,s) là nghiệm chấp nhận được của của bài toán đối ngẫu \displaystyle (D) mà

\displaystyle \lambda^T b\geq \mathrm{Opt}(P)\geq \mathrm{Opt}(D)\geq \lambda^T b

Suy ra

\displaystyle \lambda^T b = \mathrm{Opt}(P) = \mathrm{Opt}(D) = (\lambda^*)^T b = c^Tx^*
\displaystyle \Rightarrow (s^*)^Tx^*=c^Tx^*-(\lambda^*)^T b = 0

Nhận xét:

  1. Các điều kiện (1), (2), (3), (4) còn có thể được suy ra từ việc áp dụng điều kiện KKT vào bài toán gốc hoặc vào bài toán đối ngẫu.
  2. Ngoài việc thỏa mãn các ràng buộc của bài toán QHTT, điều kiện độ vênh ở các ràng buộc bất đẳng thức bù nhau \displaystyle x_is_i = 0,\forall i=1,\ldots,n là điều kiện cần và đủ của nghiệm tối ưu. Như vậy, với các nghiệm chấp nhận được chưa phải là nghiệm tối ưu ta có \displaystyle x^Ts > 0. Các điểm \displaystyle (x,\lambda,s) mà \displaystyle x_is_i>0,\forall i=1,\ldots,n gọi là các điểm trong.
  3. Các phương pháp điểm trong đều tìm cách giảm đại lượng \displaystyle x^Ts trong quá trình tìm kiếm nghiệm tối ưu. Tức là tìm cách xóa dần tính “không tối ưu” của nghiệm hiện tại.
  4. Chứng minh trên tương tự như chứng minh trong bài Bài toán đối ngẫu nên định lý về tính đối ngẫu của hai bài toán \displaystyle (P),(D) vẫn đúng.

Định lý (điều kiện để tập nghiệm tối ưu bị chặn): Giả sử cả hai bài toán \displaystyle (P),(D) đều thỏa được. Khi đó tập các nghiệm tối ưu của bài toán gốc \displaystyle (P):

\displaystyle \Omega_P = \{x:c^Tx=\mathrm{Opt}(P), Ax=b,x\geq 0,\}

là tập khác rỗng và bị chặn nếu và chỉ nếu bài toán đối ngẫu \displaystyle (D) có điểm trong. Tức là

\displaystyle \exists\lambda, s>0: A^T\lambda+s=c.

Lưu ý: Bài toán đối ngẫu của bài toán đối ngẫu là bài toán gốc nên điều kiện đủ để tập các nghiệm tối ưu của bài toán đối ngẫu \displaystyle (D) là tập khác rỗng và bị chặn là bài toán gốc \displaystyle (P) có điểm trong, tức là

\displaystyle \exists x>0: Ax=b.

Chứng minh:
“\displaystyle \Leftarrow “: Giả sử bài toán đối ngẫu có điểm trong \displaystyle (\lambda,s), xét điểm \displaystyle x_0 là một nghiệm chấp nhận được của bài toán gốc. Xét tập các nghiệm chấp nhận được có giá trị hàm mục tiêu không lớn hơn \displaystyle c^Tx_0:

\displaystyle T = \{x:Ax=b, x\geq 0, c^Tx\leq c^Tx_0\}

Để ý rằng \displaystyle \Omega_P = \{x\in T: c^Tx\leq c^Ty,\forall y\in T\} . Nói cách khác, tập các cực tiểu của \displaystyle c^Tx trên \displaystyle T chính là \displaystyle \Omega_P – tập các nghiệm tối ưu của bài toán \displaystyle (P).Ta có

\displaystyle x\in T\Rightarrow s^Tx = c^Tx-\lambda^Tb\leq c^Tx_0 - \lambda^Tb=s^Tx_0

Do \displaystyle s>0,x\geq 0 nên

\displaystyle x_is_i\leq s^Tx_0,\forall i=1,\ldots,n\displaystyle \Rightarrow x_i\leq \frac{s^Tx_0}{\displaystyle \min_i s_i}, \forall i=1,\ldots,n\displaystyle \Rightarrow \max_i x_i\leq \frac{s^Tx_0}{\displaystyle \min_i s_i}

Tức là \displaystyle \forall x\in T, ||x||_{\infty} bị chặn. Như vậy \displaystyle T là tập khác rỗng (chứa \displaystyle x_0), đóng và bị chặn (compact). Vì thế hàm \displaystyle c^Tx đạt cực tiểu trên \displaystyle T và rõ ràng tập các cực tiểu này chính là \displaystyle \Omega_P. Nghĩa là \displaystyle \Omega_P khác rỗng và bị chặn.
“\displaystyle \Rightarrow“: Giả sử tập \displaystyle\Omega_P khác rỗng và bị chặn. Ta sẽ chứng minh tồn tại điểm trong \displaystyle (\lambda,s) thỏa mãn

\displaystyle \begin{cases}s>0\\A^T\lambda+s=c\end{cases}

Áp dụng định lý đảo tổng quát, ta có hệ bất phương trình trên có nghiệm tương đương với tính vô nghiệm của cả hai hệ bất phương trình sau

\displaystyle \mathcal{T}_1\begin{cases}\alpha\geq 0\\A\beta=0\\ \alpha+\beta=0\\ \displaystyle \sum_{i=1}^n\alpha_i>0\\ \displaystyle\sum_{i=1}^n\beta_ic_i\geq 0\end{cases} \displaystyle\mathcal{T}_2\begin{cases}\alpha\geq 0\\A\beta=0\\ \alpha+\beta=0\\ \displaystyle \sum_{i=1}^n\alpha_i=0\\ \displaystyle\sum_{i=1}^n\beta_ic_i>0\end{cases}

Hệ \displaystyle \mathcal{T}_2 rõ ràng vô nghiệm, còn hệ \displaystyle \mathcal{T}_1 thì tương đương với hệ

\displaystyle \mathcal{T}_1'\begin{cases}\beta\leq 0\\A\beta=0\\ \displaystyle \sum_{i=1}^n\beta_i<0\\c^T\beta\geq 0\end{cases}

Ta sẽ chứng minh khi \displaystyle \Omega_P khác rỗng và bị chặn thì \displaystyle\mathcal{T}_1' vô nghiệm. Thật vậy, giả sử có \displaystyle\beta thỏa mãn \displaystyle\mathcal{T}_1'. Suy ra, với mọi nghiệm tối ưu \displaystyle x\in\Omega_P, ta có \displaystyle x-t\beta\in\Omega_P với mọi \displaystyle t>0 vì

\displaystyle x-t\beta\geq 0 do \displaystyle \beta\leq 0
\displaystyle A(x-t\beta)=Ax-tA\beta=Ax=b
\displaystyle c^T(x-t\beta)=c^Tx-tc^T\beta\leq c^Tx

Mặt khác, \displaystyle \beta\neq 0 vì \displaystyle\sum_{i=1}^n\beta_i<0. Suy ra \displaystyle\Omega_P không bị chặn, mâu thuẫn. Vậy \displaystyle\mathcal{T}_1' vô nghiệm, hay tập nghiệm chấp nhận được của bài toán đối ngẫu chứa điểm trong \displaystyle (\lambda,s) nào đó.

Đăng trong Quy hoạch tuyến tính | Tagged: , , , , , | Leave a Comment »

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

  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.

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

  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,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:

  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}\}

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.

Đăng trong Giải tích lồi | Tagged: , , , , , , , , , , , , | Leave a Comment »

« Những bài viết trước