Що таке теорема відокремлення леми Фаркаша?

Узагальнену лему Фаркаша можна інтерпретувати геометрично так: або вектор знаходиться в заданому замкнутому опуклому конусі, або існує гіперплощина, що відділяє вектор від конуса; інших можливостей немає. Умова замкнутості є необхідною, дивіться Теорему відокремлення I у Теоремі відокремлення на гіперплощині.

Лема Фаркаша показує це нерозв'язність системи може бути «сертифікована»: розв’язок z (II) можна використовувати як «сертифікат», що систему (I) неможливо розв’язати. Такі довідки в математиці називаються обструкціями. Існує декілька узагальнень леми Фаркаша.

Таким чином, коротко, лема Мінковського-Фаркаса стверджує, що якщо l ·b ³ 0 для всіх l таких, що l A ³ 0 , то Ax = b має невід’ємний розв’язок x ³ 0. Застосування леми Мінковскі численні – до теорем подвійності в лінійному програмуванні, теореми Куна-Таккера та в іграх з нульовою сумою.

Теорема (альтернатива Фаркаса): один і тільки один із наступних двох випадків завжди вірний: Ax = b має розв’язок x ∈ Rn, x ≥ 0, xабо існує y ∈ Rm такий, що AT y ≥ 0 і y · b < 0.

Мета цієї короткої замітки — представити гарний доказ леми Фаркаса, яка це стверджує якщо C є опуклим конусом, натягнутим на скінченну множину, і якщо x не входить до C, то існує лінійний функціонал α, який є невід’ємним на C з α(x) < 0. Це означає, зокрема, що опуклий конус C є замкнутим.

Правдиве твердження, яке є менш важливим і використовується для підтвердження істинності іншого важливого твердження. Можна також сказати, що лема — це невелика підтеорема, яку необхідно довести в процесі доведення більшого результату.