Bổ đề Farkas

Bách khoa toàn thư mở Wikipedia
Bước tới: menu, tìm kiếm

Bổ đề Farkas là một kết quả toán học phát biểu như sau: một vectơ hoặc nằm trong một nón lồi hoặc tồn tại một siêu phẳng sao cho vectơ nằm ở một phía của siêu phẳng và nón lồi nằm ở phía kia. Nó được chứng minh đầu tiên bởi nhà toán học người Hungary Gyula Farkas Bản mẫu:Harvs. Nó có nhiều ứng dụng, chẳng hạn như trong chứng minh của định lý Karush–Kuhn–Tucker trong quy hoạch phi tuyến.

Phát biểu bổ đề[sửa | sửa mã nguồn]

Giả sử A là một ma trận m × nb là một vectơ m chiều. Đúng một trong hai trường hợp sau xảy ra:

  1. Tồn tại vectơ xRn sao cho Ax = bx ≥ 0.
  2. Tồn tại yRm sao cho ATy ≥ 0 và bTy < 0.

Ở đây kí hiệu x ≥ 0 có nghĩa là mọi tọa độ của x đều không âm.

Có nhiều phát biểu tương đương của bổ đề này. Phiên bản trên là của Gale, Kuhn & Tucker (1951).

Ý nghĩa hình học[sửa | sửa mã nguồn]

Đặt a1, …, anRm là các cột của A. Bổ đề Farkas khẳng định rằng một trong hai mệnh đề sau là đúng:

  1. Tồn tại các hệ số x1, …, xnR, x1, …, xn ≥ 0, sao cho b = x1a1 + ··· + xnan.
  2. Tồn tại vectơ yRm sao cho ai · y ≥ 0 với i = 1, …, nb · y < 0.

Các vectơ x1a1 + ··· + xnan với hệ số không âm tạo thành một nón lồi sinh bởi tập hợp {a1, …, an} nên mệnh đề thứ nhất nghĩa là b nằm trong hình nón này.

Theo mệnh đề thứ hai, tồn tại y sao cho góc giữa y và các vectơ ai là không quá 90° trong khi góc giữa y và vectơ b là lớn hơn 90°. So với siêu phẳng vuông góc với y, ai nằm ở một phía và vectơ b nằm ở phía kia. Do đó siêu phẳng này chia cắt nón lồi sinh bởi tập hợp {a1, …, an} và vectơ b.

Để minh họa, xét n,m=2 và a1 = (1,0)Ta2 = (1,1)T. Nón lồi sinh bởi a1a2 là một góc nhọn trong góc phần tư thứ nhất của mặt phẳng Oxy. Giả sử b = (0,1). Khi đó, b không nằm trong nón lồi a1x1+a2x2. Do đó, tồn tại siêu phẳng chia cắt chúng. Đặt y = (1,−1)T. Ta nhận thấy a1 · y = 1, a2 · y = 0, và b · y = −1. Do đó siêu phẳng với vectơ pháp tuyến y chia cắt nón lồi a1x1+a2x2b.

Do đó có thể diễn đạt bổ đề Farkas dưới dạng hình học như sau: cho một nón lồi và một vectơ, hoặc vectơ nằm trong nón lồi hoặc tồn tại một siêu phẳng chia cắt vectơ và nón lồi, nhưng không thể cả hai.

Biến thể[sửa | sửa mã nguồn]

Có nhiều biến thể của bổ đề Farkas như định lý Gordan: hoặc Ax < 0 có nghiệm x, hoặc A^T y = 0 có nghiệm khác không y với y ≥ 0.

Một phiên bản dễ nhớ là như sau: nếu một hệ bất phương trình không có nghiệm thì tồn tại một chứng minh phản chứng dưới dạng một tổ hợp tuyến tính với các hệ số không âm. Dưới dạng công thức: nếu Axb vô nghiệm thì y^T A = 0, y^T b = -1, y0 có nghiệm[1]. (ghi chú y^T A là một tổ hợp tuyến tính của vế trái, y^T b là tổ hợp tuyến tính tương ứng của vế phải các bất phương trình. Do tổ hợp tuyến tính không âm tạo ra vectơ không ở vế trái và −1 ở vế phải, hệ bất phương trình rõ ràng vô nghiệm)

Tài liệu tham khảo[sửa | sửa mã nguồn]

Ghi chú[sửa | sửa mã nguồn]

  1. ^ Boyd, Stephen P.; Vandenberghe, Lieven (2004), “Phần 5.8.3” (pdf), Convex Optimization, Cambridge University Press, ISBN 9780521833783, truy cập 15 tháng 10, 2011