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

Learn & Enjoy …

Định lý Farkas thuần nhất

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

Định lý Farkas thuần nhất: Bất đẳng thức a^T x \geq 0 là hệ quả của hệ bất đẳng thức a_i^T x \geq 0, i=1,\ldots,n nếu và chỉ nếu a \in \mathrm{Cone}\{a_1, \ldots, a_n\}.

Chứng minh:

\Rightarrow“: Giả sử a \in \mathrm{Cone}\{a_1, \ldots, a_n\}, ta có a = \displaystyle \sum_{i=1}^n \lambda_i a_i, \lambda_i \geq 0. Suy ra

\displaystyle a^T x = \sum_{i=1}^n \lambda_i a_i^T x \geq 0

với mọi x sao cho a_i^T x \geq 0, i=1,\ldots,n.

\Leftarrow“: Giả sử a^T x \geq 0 với mọi x sao cho a_i^T x \geq 0, i=1,\ldots,n. Ta cần chứng minh a \in \mathrm{Cone}\{a_1, \ldots, a_n\}. Nhận xét rằng ta chỉ cần chứng minh cho a \neq 0.

Đặt A_i = \{x \in \mathbb{R}^n: a^T x = -1, a_i^T x \geq 0\}, rõ ràng ta có \displaystyle \bigcap_{i=1}^n A_i = \emptyset. Gọi k là số tập nhỏ nhất giao nhau bằng rỗng. Nghĩa là, không mất tính tổng quát, \displaystyle \bigcap_{i=1}^k A_i = \emptyset nhưng giao của k-1 tập bất kì đều khác rỗng. Ta sẽ chứng minh ba mệnh đề sau đây:

(i) a \in \mathrm{Lin} \{a_1, \ldots, a_k\}.

(ii) \{a_1, \ldots, a_k\} độc lập tuyến tính.

(iii) a \in \mathrm{Cone}\{a_1, \ldots, a_k\}.

Chứng minh (i): Nếu a \notin \mathrm{Lin} \{a_1, \ldots, a_k\}, suy ra tồn tại h \neq 0 sao cho a^T h \neq 0, a_i^T h = 0, i=1,\ldots,k. Đặt x = -\frac{h}{a^T h}, ta có

\displaystyle a^T x = -\frac{a^T h}{a^T h} = -1, a_i^T x = -\frac{a_i^T h}{a^T h} = 0.

Nghĩa là x \in A_i, i=1,\ldots, k, mâu thuẫn với giả thiết \displaystyle \bigcap_{i=1}^k A_i = \emptyset.

Chứng minh (ii): (Sử dụng định lý Helley) Đặt E = \mathrm{Lin} \{a_1, \ldots, a_k\}.

Trường hợp k = 1, vì a \neq 0a \in \mathrm{Lin} \{a_1\} nên a_1 \neq 0.

Trường hợp k > 1, giả sử \dim E = r < k. Đặt

B_i=\{x \in E: a^T x = -1, a_i^T x \geq 0\}.

a \in E nên B_i là tập lồi nằm trong không gian affine r-1 chiều. Nhận xét rằng, giao của bất cứ r tập trong B_i, i=1,\ldots, k đều khác rỗng. Thật vậy, vì r<k nên A_1,\ldots,A_r có ít nhất một điểm chung x. Chiếu x lên E, ta được

x = y + h, y \in E, h \in E^\perp

\Rightarrow a^T y = a^T(x-h) = a^T x= -1, a_i^T y = a_i^T (x-h) = a_i^T x\geq 0.

Nghĩa là y \in B_i, i=1,\ldots,r. Theo định lý Helley, \displaystyle \bigcap_{i=1}^k B_i \neq \emptyset, nhưng do B_i \subset A_i nên \displaystyle \bigcap_{i=1}^k A_i \neq \emptyset, mâu thuẫn với giả thiết.

Chứng minh (iii): Giả sử \displaystyle a=\sum_{i=1}^k \lambda_i a_i và không mất tính tổng quát, giả sử \lambda_1 < 0. Vì \{a_1, \ldots, a_k\} độc lập tuyến tính nên tồn tại x sao cho

a_1^T x = 1, a_i^T x = 0, i = 2, \ldots, k.

Xét y = \displaystyle\frac{x}{|\lambda_1|}. Ta có

\displaystyle a^T y = \frac{a^T x}{|\lambda_1|} = \frac{\lambda_1}{|\lambda_1|} = -1

\displaystyle a_1^T y =  \frac{a_1^T x}{|\lambda_1|} > 0, a_i^T y =  \frac{a_i^T x}{|\lambda_1|} = 0, i = 2, \ldots, k

Nghĩa là y \in A_i, i = 1, \ldots, k, mâu thuẫn với giả thiết.

Nhận xét:

  1. Định lý Farkas là một kết quả rất sâu, có nhiều ứng dụng trong việc phân tích các hệ bất phương trình, đặc biệt trong việc phân tích tính chất nghiệm của các bài toán tối ưu có ràng buộc
  2. Ta sẽ gặp ứng dụng của định lý Farkas trong các bài Định lý đảo tổng quát, Bài toán đối ngẫu, Điều kiện của cực tiểu của hàm lồi.

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: