Farkas' lemma

Farkas' lemma is a mathematical statement about systems of inequalities. It says that for any set of linear inequalities, either there is a solution that makes all inequalities true simultaneously, or there exists a specific combination of these inequalities—called a certificate—that proves no such solution can exist. Essentially, it provides a way to verify if a system is feasible or impossible by either finding a solution or identifying a proof of inconsistency, but not both. This principle is fundamental in optimization and linear programming, ensuring the decision process about system feasibility is well-defined.