Lemat Farkasa

Szablon:Dopracować Lemat Farkasa, alternatywa Farkasa – twierdzenie z algebry liniowej, według którego w przestrzeni ${ℝ}^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 {ℝ}^n$ jest wektorem zapisywanym w kolumnie, zachodzi alternatywa wykluczająca:

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

$\{\genfrac{}{}{0ex}{}{y^{T}A⩾0}{y^{T}b<0}$

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

Interpretacja

Jeżeli równanie $Ax=b$ ma rozwiązanie $x⩾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:

$\{\genfrac{}{}{0ex}{}{y^{T}A⩾0}{y^{T}b<0}$

ma rozwiązanie $y\in {ℝ}^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