Lemat Farkasa

Lemat Farkasa, alternatywa Farkasa – twierdzenie z algebry liniowej, według którego w przestrzeni $\mathbb {R} ^{n}$ albo punkt należy do stożka, albo można go oddzielić od stożka płaszczyzną.

Wypowiedź

Jeżeli $A$ jest macierzą rzeczywistą o $n$ wierszach i $m$ kolumnach oraz $b\in \mathbb {R} ^{n}$ jest wektorem zapisywanym w kolumnie, zachodzi alternatywa wykluczająca:

• albo równanie $Ax=b$ ma rozwiązanie $x\geqslant 0,$
• albo układ nierówności:

$\left\{{y^{T}A\geqslant 0 \atop y^{T}b<0}\right.$

ma rozwiązanie ze względu na $y\in \mathbb {R} ^{n}.$

Interpretacja

Jeżeli równanie $Ax=b$ ma rozwiązanie $x\geqslant 0,$ wtedy istnieje kombinacja stożkowa kolumn macierzy $A$ dająca wektor $b,$ czyli punkt $b$ należy do stożka wyznaczonego przez kolumny macierzy $A.$

Jeżeli układ nierówności:

$\left\{{y^{T}A\geqslant 0 \atop y^{T}b<0}\right.$

ma rozwiązanie $y\in \mathbb {R} ^{n},$ wtedy wektor $y$ tworzy z każdą z kolumn macierzy $A$ kąt mniejszy bądź równy od $90^{o}$ (bo wszystkie iloczyny skalarne są większe od 0), a z wektorem $b$ kąt rozwarty. Zatem płaszczyzna prostopadła do wektora $y$ oddziela stożek od punktu $b.$

Zastosowanie

Lemat Farkasa służy do pokazania twierdzenia o dualności w programowaniu liniowym, a w szerszym ujęciu nieliniowym w dowodzie twierdzenia Karusha-Kuhna-Tuckera.

Linki zewnętrzne

• Skrypt dra Łukasza Kowalika z MIMUW