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 . 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:
 Tồn tại vectơ x ∈ Rn sao cho Ax = b và x ≥ 0.
 Tồn tại y ∈ Rm 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 .

Ý nghĩa hình học 

Đặt a1, …, an ∈ Rm là các cột của A. Bổ đề Farkas khẳng định rằng một trong hai mệnh đề sau là đúng:
 Tồn tại các hệ số x1, …, xn ∈ R, x1, …, xn ≥ 0, sao cho b = x1a1 + ··· + xnan.
 Tồn tại vectơ y ∈ Rm sao cho ai · y ≥ 0 với i = 1, …, n và b · 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)T và a2 = (1,1)T. Nón lồi sinh bởi a1 và a2 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+a2x2 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  có nghiệm x, hoặc  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  ≤  vô nghiệm thì , ,
 ≥  có nghiệm. (ghi chú  là một tổ hợp tuyến tính của vế trái,  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
 .
 .
 .
 
 .  Xem bổ đề 1 ở trang 318.

Ghi chú

Tối ưu toán học
Bổ đề
Giải tích lồi
Quy hoạch tuyến tính
Tối ưu hóa (toán học)