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ổ đề

sửa

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

Đặ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

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[1]. (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

sửa
  • Berkovitz, Leonard D. (2001), Convexity and Optimization in  , 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ú

sửa
  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