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

David Bartl

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.

Full Text:

PDF

References


E. J. Anderson and P. Nash, Linear Programming in Infinite-Dimensional Spaces, Wiley, Chichester, 1987.

D. Bartl, Farkas’ Lemma, other theorems of the alternative, and linear programming in infinite-dimensional spaces:

a purely linear-algebraic approach, Linear and Multilinear Algebra, 55 (2007) 327–353.

D. Bartl, A Short Algebraic Proof of the Farkas Lemma, SIAM Journal on Optimization, 19 (2008) 234–239.

D. Bartl, A note on the short algebraic proof of Farkas’ Lemma, Linear and Multilinear Algebra, 60 (2012) 897–901.

D. Bartl, A very short algebraic proof of the Farkas Lemma, Mathematical Methods of Operations Research, 75

(2012) 101–104.

D. Bartl, Separation theorems for convex polytopes and finitely-generated cones derived from theorems of the alternative,

Linear Algebra and its Applications, 436 (2012) 3784–3789.

P. M. Cohn, Skew fields: Theory of general division rings, Cambridge University Press, 1995.

K. Fan, On Systems of Linear Inequalities. In: H.W. Kuhn and A.W. Tucker (eds.), Linear Inequalities and Related

Systems, Princeton University Press, Princeton, 1956, 99–156.

J. Farkas, Theorie der einfachen Ungleichungen, Journal f¨ur die reine und angewandte Mathematik, 124 (1902)

–27.

D. Gale, The Theory of Linear Economic Models, McGraw-Hill, New York, 1960.

D. Gale, H. W. Kuhn, and A. W. Tucker, Linear Programming and the Theory of Games. In: T. C. Koopmans (ed.),

Activity Analysis of Production and Allocation, Wiley, New York, 1951, 317–329.

M. A. Goberna and M. A. L´opez, Linear Semi-Infinite Optimization, Wiley, Chichester, 1998.

T. Y. Lam, A First Course in Noncommutative Rings, Springer, New York, Berlin, 1991.


Refbacks

  • There are currently no refbacks.