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

Learn & Enjoy …

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

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

Định nghĩa (siêu phẳng đỡ): Nếu tập S lồi và điểm x\in\partial S, siêu phẳng \Pi qua x và phân tách S,\{x\} gọi là siêu phẳng đỡ S tại x.

Nhận xét: Nếu x\in\mathrm{rint}S thì không thể có siêu phẳng đỡ S tại xx\cap \mathrm{rint}S\neq\emptyset.

Định lý (giao của siêu phẳng đỡ và tập lồi): Nếu x\in\partial S thì

  1. Tồn tại siêu phẳng \Pi đỡ S tại x.
  2. \dim(\Pi\cap S) < \dim S.

Chứng minh (1): Hiển nhiên vì \{x\}\cap \mathrm{rint} S=\emptyset khi x\in\partial S.

Chứng minh (2): Giả sử ngược lại \dim(\Pi\cap S) = \dim S. Ta thấy \Pi\cap S\subset S, tức là \mathrm{Aff}\left(\Pi\cap S\right)\subset \mathrm{Aff}S. Nhưng \dim(\Pi\cap S) = \dim S nên \mathrm{Aff}\left(\Pi\cap S\right)= \mathrm{Aff}S. Mặt khác vì \Pi\cap S\subset \Pi\cap\mathrm{Aff}S nên \mathrm{Aff}\left(\Pi\cap S\right)\subset \Pi\cap\mathrm{Aff}S\subset\mathrm{Aff}S. Tức là \Pi\cap\mathrm{Aff}S=\mathrm{Aff}S, suy ra \Pi\supset\mathrm{Aff}S\supset S. Mâu thuẫn vì như vậy \Pi\supset S\cup \{x\} và như vậy không thể là siêu phẳng đỡ (theo định nghĩa siêu phẳng phân cách).

Định nghĩa (điểm cực biên): Điểm cực biên x\in S của tập đóng, lồi S có thể được định nghĩa bằng các cách tương đương sau:

  1. Không tồn tại hai điểm y,z\in S0<\lambda<1 sao cho x=\lambda y+(1-\lambda)z.
  2. Không tồn tại véc tơ h\neq 0 sao cho x-h,x+h\in S.
  3. Tập S\setminus\{x\} lồi.

Kí hiệu tập các điểm cực biên của S\mathrm{Ext}S .
Chứng minh:

1\Rightarrow 2: Hiển nhiên vì x =\displaystyle \frac{1}{2}(x+h)+ \frac{1}{2}(x-h).

2\Rightarrow 3: Giả sử S\setminus\{x\} không lồi, suy ra tồn tại đoạn thẳng (y,z)\in S chứa x, tức là có một đoạn thẳng có x là trung điểm, trái với giả thiết.

3\Rightarrow 1: Hiển nhiên vì nếu tồn tại y,z\in S0<\lambda<1 sao cho x=\lambda y+(1-\lambda)z thì S\setminus\{x\} không thể lồi.

Định lý: Nếu siêu phẳng \Pi=\{x:f^Tx=a\} đỡ tập lồi S thì các điểm cực biên của \Pi\cap S cũng là điểm cực biên của S.

\mathrm{Ext}(\Pi\cap S)\subset \mathrm{Ext}S

Chứng minh: Nếu x là điểm cực biên của \Pi\cap S nhưng không phải là điểm cực biên của S, tức là có h\neq 0 sao cho x+h,x-h\in S. Ta có \displaystyle \max(f^T(x+h),f^T(x-h))\geq f^Tx\geq\sup_{y\in S}f^Ty. Suy ra f^T(x+h)=f^T(x-h)=f^Tx, tức là x+h,x-h\in\Pi. Nói cách khác x cũng không là điểm cực biên của \Pi\cap S, mâu thuẫn.

Định nghĩa (đỉnh): Đỉnh x\in S của tập đóng, lồi S có thể định nghĩa bằng các cách tương đương sau:

  1. Tồn tại siêu phẳng \Pi đỡ S tại x\Pi\cap S=\{x\} .
  2. Tồn tại dạng tuyến tính f^Txđạt giá trị cực đại duy nhất trên S tại x.

Chứng minh: Hiển nhiên vì siêu phẳng chỉ giao với S tại x nên giá trị của dạng tuyến tính tại các điểm khác f^Ty,y\in S, y\neq x trong S không thể bằng giá trị của f^Tx.

Định lý: Điểm x là điểm cực biên của S nếu nó là đỉnh của S.

Chứng minh: Vì tồn tại dạng tuyến tính f^Tx đạt giá trị cực đại duy nhất tại x nên không thể tồn tại véctơ h\neq 0 sao cho x+h,x-h\in S do \displaystyle\max(f^T(x+h),f^T(x-h))\geq f^Tx.

Định lý Krein-Milman (điều kiện tồn tại điểm cực biên): Nếu tập S là tập đóng, lồi thì:

  1. S có điểm cực biên nếu và chỉ nếu S không chứa đường thẳng.
  2. Nếu S giới nội thì S chính là bao lồi của các điểm cực biên của nó.

Chứng minh (1):

\Rightarrow“: Giả sử S không chứa đường thẳng. Chọn điểm x\in S bất kì. Nếu x là điểm cực biên, ta có điều phải chứng minh. Ngược lại, nếu x không phải là điểm cực biên, chọn một đường thẳng bất kì qua x. Đường thẳng này phải thoát ra khỏi S ở một điểm x_1\in\partial S nào đó (vì S không chứa đường thẳng). Vì x_1\in\partial S, ta có mặt phẳng \Pi_1 đỡ S tại x_1. Đặt S_1=\Pi_1\cap S, ta có \dim S_1<\dim S. Nếu x_1 không phải là điểm cực biên của S_1 ta lại lập luận như trên và giảm được \dim S_1S_1 cũng không chứa đường thẳng. Quá trình lập luận này phải dừng ở bước k nào đó mà x_k là điểm cực biên của S_k. Theo định lý trên ta có \mathrm{Ext}S_k\subset\ldots\mathrm{Ext}S_1 \subset\mathrm{Ext}S, tức là x_k là điểm cực biên của S.

\Leftarrow“: Giả sử S có điểm cực biên x và đường thẳng \{y(t):y(t)=y+th, h\neq 0,t\in \mathbb{R} \} . Rõ ràng, đường thẳng này không thể đi qua x vì đây là điểm cực biên. Ta sẽ chứng minh x+h\in S. Thật vậy, với nếu ta chọn điểm z(t) nằm giữa x,y+th,t>0 sao cho

z(t)=\displaystyle \frac{1}{t}(y+th)+(1-\frac{1}{t})x, t>0

thì \displaystyle \lim_{t\rightarrow\infty}z(t)=x+h. Hơn nữa, ta lại có z(t)\in S,\forall t, và S đóng nên x+h\in S. Tương tự x-h\in S. Suy ra x không phải là điểm cực biên.

Chứng minh (2): Rõ ràng \mathrm{Conv} \mathrm{Ext}S\subset SS lồi. Ta sẽ chứng minh S\subset\mathrm{Conv} \mathrm{Ext}S bằng quy nạp theo n=\dim S.

Cơ sở: Định lý đúng với n=0, hay S=\{X\}.

Quy nạp: Giả sử định lý đúng với mọi n<k, ta sẽ chứng minh định lý cũng đúng với n=k. Thật vậy, xét điểm x\in S, một đường thẳng bất kì qua x phải thoát ra khỏi S tại hai điểm x^+,x^-\in\partial S vì nếu không S sẽ chứa đường thẳng hoặc chứa tia, tức là S không bị giới nội. Như vậy có 2 siêu phẳng \Pi^+,\Pi^- đỡ S lần lượt ở x^+,x^-. Ta có

x^+\in\mathrm{Conv} \mathrm{Ext}(\Pi^+\cap S)

x^-\in\mathrm{Conv} \mathrm{Ext}(\Pi^-\cap S)

theo giả thiết quy nạp do \dim(\Pi^+\cap S)<\dim S\dim(\Pi^-\cap S)<\dim S. Như vậy,

x\in \mathrm{Conv}\{x^+,x^-\} \subset\mathrm{Conv}(\mathrm{Ext}(\Pi^+\cap S)\cup\mathrm{Ext}(\Pi^-\cap S))

\subset \mathrm{Conv}\mathrm{Ext}S

\mathrm{Ext}(\Pi^+\cap S)\subset\mathrm{Ext}S\mathrm{Ext}(\Pi^-\cap S)\subset\mathrm{Ext}S.

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: