Skip to main content
main-content

Inhaltsverzeichnis

Frontmatter

Chapter 1. Prerequisites

Abstract
This chapter introduces some notation and reviews basic facts from different fields. The reader is assumed to be familiar with the very elementary concepts in linear algebra and topology of Euclidean n- space as summarized in Section 1.2 and 1.3. Apart from these, the book is essentially selfcontained (with a minor exception of Chapter 9). Section 1.1 introduces the notion of partially ordered sets which is not treated in depth anywhere in this book, but is used to simplify the notation only. Section 1.4 introduces some notions from polyhedral theory.
Achim Bachem, Walter Kern

Chapter 2. Linear Duality in Graphs

Abstract
Linear duality deals with the relationship between two complementary orthogonal subspaces L and L of Kn. 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.
Achim Bachem, Walter Kern

Chapter 3. Linear Duality and Optimization

Abstract
Many problems in the real world (and in mathematics) can be formulated in the following way:
$$ Let\;f:{K^n} \to K\;be\;a\;function,\;and\;let\;S \subseteq {K^n}.$$
.
Achim Bachem, Walter Kern

Chapter 4. The FARKAS Lemma

Abstract
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 Kn to its orthogonal complement L in the sense of Theorem 2.10.
Achim Bachem, Walter Kern

Chapter 5. Oriented Matroids

Abstract
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 1 such that an analogue of Theorem 4.6 holds (with L and L replaced by S an S 1 , 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.
Achim Bachem, Walter Kern

Chapter 6. Linear Programming Duality

Abstract
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 Kn, 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.
Achim Bachem, Walter Kern

Chapter 7. Basic Facts in Polyhedral Theory

Abstract
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.
Achim Bachem, Walter Kern

Chapter 8. The Poset (O, ≼)

Abstract
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.
Achim Bachem, Walter Kern

Chapter 9. Topological Realizations

Abstract
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 0 ={x ∈ R n |B e x=0} is a hyperplane in Rn. This family of hyperplanes (H e | eE) subdivides Rn into the family of polyhedral cones definable from Bx ≤ 0.
Achim Bachem, Walter Kern

Backmatter

Weitere Informationen