Bổ đề Farkas

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  (1894, 1902). 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ổ đề

Giả sử A là một ma trận m × n và b 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ơ x ∈ Rⁿ sao cho Ax = b và x ≥ 0.
2. Tồn tại y ∈ R^m sao cho A^Ty ≥ 0 và b^Ty < 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

Đặt a₁, …, a_n ∈ R^m 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ố x₁, …, x_n ∈ R, x₁, …, x_n ≥ 0, sao cho b = x₁a₁ + ··· + x_na_n.
2. Tồn tại vectơ y ∈ R^m sao cho a_i · y ≥ 0 với i = 1, …, n và b · y < 0.

Các vectơ x₁a₁ + ··· + x_na_n với hệ số không âm tạo thành một nón lồi sinh bởi tập hợp {a₁, …, a_n} 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ơ a_i 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, a_i 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 {a₁, …, a_n} và vectơ b.

Để minh họa, xét n,m=2 và a₁ = (1,0)^T và a₂ = (1,1)^T. Nón lồi sinh bởi a₁ và a₂ 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 a₁x₁+a₂x₂. Do đó, tồn tại siêu phẳng chia cắt chúng. Đặt y = (1,−1)^T. Ta nhận thấy a₁ · y = 1, a₂ · 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 a₁x₁+a₂x₂ và b.

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ể

Có nhiều biến thể của bổ đề Farkas như định lý Gordan: hoặc ${\displaystyle Ax<0}$ có nghiệm x, hoặc ${\displaystyle 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 ${\displaystyle Ax}$ ≤ ${\displaystyle b}$ vô nghiệm thì ${\displaystyle y^{T}A=0}$, ${\displaystyle y^{T}b=-1}$, ${\displaystyle y}$ ≥ ${\displaystyle 0}$ có nghiệm^[1]. (ghi chú ${\displaystyle y^{T}A}$ là một tổ hợp tuyến tính của vế trái, ${\displaystyle 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)

Tham khảo

• Berkovitz, Leonard D. (2001), Convexity and Optimization in ${\displaystyle \mathbb {R} ^{n}}$, New York: John Wiley & Sons, ISBN 978-0-471-35281-5.
• Farkas, Gyula (1894), “A Fourier-féle mechanikai elv alkamazásai”, Mathematikai és Természettudományi Értesítő, 12: 457–472, reference from Schrijver's Combinatorial Optimization textbook.
• Farkas, Julius (Gyula) (1902), “Über die Theorie der Einfachen Ungleichungen”, Journal für die Reine und Angewandte Mathematik, 124 (124): 1–27, doi:10.1515/crll.1902.124.1.
• Rockafellar, R. T. (1979), Convex Analysis, Princeton University Press, tr. 200
• Gale; Kuhn; Tucker (1951), “Linear Programming and the Theory of Games - Chapter XII”, trong Koopmans (biên tập), Activity Analysis of Production and Allocation (PDF), Wiley. Xem bổ đề 1 ở trang 318.
• Kutateladze, S. (2010), “The Farkas Lemma Revisited” (PDF), Siberian Mathematical Journal, 51 (1): 78–87, doi:10.1007/s11202-010-0010-y.

Ghi chú

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