Farkas’ Lemma, Gale’s Theorem, and Linear Programming: the Infinite Case in an Algebraic Way

Abstract

We study a problem of linear programming in the setting of a vector space over a linearly ordered (possiblyskew) field. The dimension of the space may be infinite. The objective function is a linear mapping into another linearlyordered vector space over the same field. In that algebraic setting, we recall known results: Farkas’ Lemma, Gale’sTheorem of the alternative, and the Duality Theorem for linear programming with finite number of linear constraints.Given that “semi-infinite” case, i.e. results for finite systems of linear inequalities in an infinite-dimensional space, weare motivated to consider the infinite case: infinite systems of linear inequalities in an infinite-dimensional space. Givensuch a system, we assume that only a finite number of the left-hand sides is non-zero at a point. We shall also assumea certain constraint qualification (CQ), presenting counterexamples violating the (CQ). Then, in the described setting,we formulate an infinite variant of Farkas’ Lemma along with an infinite variant of Gale’s Theorem of the alternative.Finally, we formulate the problem of an infinite linear programming, its dual problem, and the Duality Theorem for theproblems.