Linear Programming Duality

Linear duality deals with the relationship between two complementary orthogonal subspaces L and L ^⊥ of Kⁿ. The main theorem of linear duality, FARKAS’ Lemma, will be presented in Chapter 4. In this chapter we will derive FARKAS’ Lemma only for a special class of complementary pairs (L, L^⊥) arising from directed graphs.

Many problems in the real world (and in mathematics) can be formulated in the following way: .

The result mentioned at the end of Section 3.2, which relates the emptiness of a given polyhedron to the nonemptiness of a certain other polyhedron is wellknown as the FARKAS Lemma. We will state this theorem in a more precise form in this section. Moreover, we shall give several equivalent formulations of the FARKAS Lemma, which we derive from each other by introducing standard techniques in polyhedral theory. In particular, we will show that the FARKAS Lemma can be seen as a theorem relating a subspace L of Kⁿ to its orthogonal complement L ^⊥ in the sense of Theorem 2.10.

In Chapter 4 we learned about at least five versions of FARRAS’ Lemma. Is there any one which is more “natural” than the others? We propagate that the “linear subspace version” (Theorem 4.6) is the most natural one: It is both simple and “selfdual”, i.e. both alternatives a) and b) arise from each other by simply replacing L by L ^⊥ . If we agree that Theorem 4.6 is the most natural way to state FARKAS’ Lemma, the next question that arises is: Are dual pairs of vector spaces the most natural structures for stating Theorem 4.6? More precisely, given two sets of vectors, say, S and S ¹ such that an analogue of Theorem 4.6 holds (with L and L ^⊥ replaced by S an S ¹ , resp.), is it true then that S and S give rise to a dual pair of vector spaces in some way? As one might guess, the answer is no (for otherwise we would probably not have written this book). In fact, a systematic analysis of those properties of vector spaces which make L and L ^⊥ satisfy FARKAS’ Lemma will lead us to discover more general structures, called “oriented matroids”. These are, as we will see, the most general (and hence the most simple or “natural”) structures satisfying an analogue of FARKAS’ Lemma.

After this “tour de force” in abstract duality theory, the reader — if there still is any — will probably be glad to learn that we are now coming back to Kⁿ, in order to have a short break there and solve our optimization problems from Chapter 4. Our main object however will be to show that linear programming essentially is an oriented matroid problem.

As we have seen, oriented matroids provide a natural way to study linear programming in an abstract setting. A major second field of “application” is to study the structure of polyhedra in the general framework of oriented matroids. This will be our main object in the following. Our investigation starts with the present chapter, introducing some basic notions and results from polyhedral theory.

In Chapter 6 we have analyzed the structure of an oriented matroid O, considered as a system of sign vectors. Here we will investigate its structure as a poset. These two points of view are strongly related, of course, though the relationship is not as clear as one might expect at the first glance. For example, if a set of sign vectors is given and we are to decide whether this is an OM, then we may simply check the axioms in order to find out the answer. On the other hand, if we are given a poset (P, ⪳), there is no obvious way to decide wether it is an OM-poset or not, except by “brute force”, i.e. by trying all possible OMs up to a certain size and each time comparing their posets to the given one. [21] and [48] provide a more clever way of computing a set O of sign vectors such that (O, ⪳) equals the given poset (P,⪳). But nonetheless, the final check whether or not (O, ⪳) is an OM poset has to be done by checking the sign vector axioms. The reason is that, so far, there is no neat characterization of OMs in terms of their posets.

Let B ∈ ^RE×n and let O = σ(imB) denote the corresponding OM. Suppose for simplicity that B has no zero rows, thus every H _e ⁰ ={x ∈ R ⁿ |B _e x=0} is a hyperplane in Rⁿ. This family of hyperplanes (H _e | e ∈ E) subdivides Rⁿ into the family of polyhedral cones definable from Bx ≤ 0.