Lemat Farkasa

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Lemat Farkasa, alternatywa Farkasa - twierdzenie z algebry liniowej, według którego w przestrzeni albo punkt należy do stożka, albo można go oddzielić od stożka płaszczyzną.

Wypowiedź[edytuj]

Jeżeli jest macierzą rzeczywistą o wierszach i kolumnach oraz jest wektorem zapisywanym w kolumnie, zachodzi alternatywa wykluczająca:

  • albo równanie ma rozwiązanie ,
  • albo układ nierówności:

ma rozwiązanie ze względu na .

Interpretacja[edytuj]

Jeżeli równanie ma rozwiązanie , wtedy istnieje kombinacja stożkowa kolumn macierzy dająca wektor , czyli punkt należy do stożka wyznaczonego przez kolumny macierzy .

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

ma rozwiązanie , wtedy wektor tworzy z każdą z kolumn macierzy kąt mniejszy bądź równy od (bo wszystkie iloczyny skalarne są większe od 0), a z wektorem kąt rozwarty. Zatem płaszczyzna prostopadła do wektora oddziela stożek od punktu .

Zastosowanie[edytuj]

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[edytuj]