(A) Convex Sets and Convex Hulls

(B) The Separating Hyperplane Theorem

(C) Convex Cones and Inequalities

(D) The Minkowski-Farkas Lemma

Appeals to convex stuctures in mathematics are few and far between. Rather than dealing
with the particular case of convex sets, much of mathematics prefers to concentrate on
more general linear subspaces. However, convex structures are central in modern economics
-- particularly with the development of linear programming and the discovery (by
economists) of the Separating Hyperplane Theorem in the 1940s - which allowed them to
reformulate much of the central tenets of Walrasian economics without unecessary and
restrictive differentiability assumptions. Convexity was the organizing principle of
mathematical economics - particularly as practiced by those associated with the Cowles Commission (Koopmans, Debreu,
Arrow, etc.) throughout the 1950s. *The*
crucial contribution to this transformation was John von
Neumann's 1937 paper written through the Vienna
Colloquium.

Most of the important mathematical arguments contained here and in the subsequent sections - axiomatic reasoning, convexity arguments, linear systems of inequalities, saddlepoints, programming and duality relationships and fixed-point theorems were all introduced to economics by John von Neumann (1937). Adoption and extension of these tools were relatively swift and revolutionized mathematical economics and drew it away from the "Paretian" use of differential calculus and into axiomatic reasoning. For more reflections on this transformation in mathematical approach, see Debreu (1984, 1986, 1991), Khan (1993), Mirowski and Weintraub (1994) and Weintraub (1985).

**(A) Convex Sets and Convex Hulls**

We begin with a simple definition:

Convex: the set X ﾍ R^{n}is a "convex set" if for every x, y ﾎ X and any l ﾎ (0, 1), then l x + (1-l)y ﾎ X.

Now we turn to an often useful theorem:

Theorem: Let {X_{n}} be a collection of convex sets. Then ﾇ_{n}X_{n}is a convex set.

Proof: If x, y ﾎ ﾇ _{n}X_{n}
then x, y ﾎ X_{n} for all n. Since X_{n} is
convex, then for any l ﾎ (0, 1), we
have l x + (1-l )y ﾎ X_{n} for all n. Thus, for any l
ﾎ (0, 1), l x + (1-l )y ﾎ ﾇ _{n}X_{n}.ｧ

It is easy to show that ﾈ _{n}X_{n} is *not*
convex.

Convex Hull: If the set co(X) ﾍ R^{n}is the smallest convex set in R^{n}containing X, then co(X) is the "convex hull" of X.

Thus, we can readily notice that co(X) is generated by all convex linear combinations
of elements of X, i.e. the convex hull of X merely equals all points ・/font>
_{i} l _{i}x_{i} where x_{i} ﾎ X and l _{i} ｳ 0 and ・/font> _{il
i} = 1.

Theorem: For every non-empty subset X ﾍ R^{n}, the convex hull of X, co(X), exists.

Proof: Let {X_{n}} be the collection of all convex sets containing X, i.e. X ﾍ X_{n} for all X_{n}. Since R^{n} is itself
convex, then {X_{n}} is non-empty. From the earlier theorem, we know that the
intersection is convex, thus ﾇ _{n} X_{n} is
convex and itself contains X. Thus, define co(X) = ﾇ _{n}X_{n}
which is the smallest convex set containing X.ｧ

**(B) The Separating Hyperplane Theorem (SHT)**

The Separating Hyperplane Theorem is merely a version of the Hahn-Banach Theorem for functional analysis - and really states nothing much more complicated than that two convex sets can be separated by a line ("hyperplane") with one of the convex sets lying on one side of it and the other set sitting on the other. However, the importance of the "discovery" of the SHT by economists in the 1940s and 1950s can hardly be overstressed - for in this "separating hyperplane", economists saw "price lines" and in the convex sets they saw the typical sets in economics on which these price lines would sit - those defined by indifference curves, budget constraints, production possibility frontiers, etc. What was merely a supposition before the 1950s - i.e. "there is a set of prices such that..." was now translated into "there is a separating hyperplane..." and thereby confirmed.

Generally, a hyperplane is a linear subspace of one dimension less than the space in which it sits (thus diagramatically, a "hyperplane" is a line drawn in a two-dimensional space or a plane drawn in three-dimensional space). It is defined as follows:

Hyperplane: A given non-zero vector p ﾎ R^{n}and a scalar c ﾎ R define a "hyperplane" H(p, c) in R^{n}where:

H(p, c) = {x ﾎ R

^{n}| pｷx = c}

Thus, H(p, c) ﾍ R^{n} is a linear subspace. A
hyperplane divides the space into two closed "half-spaces" H^{ｳ}(p, c) = {x ﾎ R^{n} |
pｷx ｳ c} and H^{｣}(p, c)
= {x ﾎ R^{n} | pｷx ｣ c}
which are the spaces "above" and "below" the hyperplane respectively.
These half-spaces are convex:

Theorem: (Convexity of Half-Spaces) For all non-zero p ﾎ R^{n}and c ﾎ R, the set H^{｣}= {x ﾎ R^{n}| pｷx ｣ c} is convex.

Proof: Let x, y ﾎ H^{｣}
. Then for all l ﾎ [0, 1], pｷ(l x + (1-l )y) = l
(pｷx) + (1-l )(pｷy). Since x, y ﾎ
H^{｣}, then pｷx ｣ c and
pｷy ｣ c thus, l (pｷx) + (1-l )(pｷy) ｣ l
c + (1-l )c = c and thus pｷ(l x +
(1-l )y) ｣ c. Thus, l x + (1-l )y ﾎ
H^{｣} .ｧ

And we can do the same for H^{ｳ}.

Supporting Hyperplane: A hyperplane H is said to be a "supporting hyperplane" to a convex set X if X is contained within one of the halfspaces of H and the boundary of X has points in comon with H, i.e. H is a supporting hyperplane to X if inf{pｷx | x ﾎ X} = c (thus X ﾍ Xｳ ) or sup{pｷx | x ﾎ X} = c (thus X ﾍ X｣ ).

Separating Hyperplane: Two convex sets, A and B, are "separable by a hyperplane" if there exists a hyperplane H(p, c) such that A and B belong to different half-spaces, i.e. such that A ﾍ {x ﾎ R^{n}| pｷx ｳ c} and B ﾍ {x ﾎ R^{n}| pｷx ｣ c}. They are "strictly separable" if either A ﾌ {x ﾎ R^{n}| pｷx > c} and/or B ﾌ {x ﾎ R^{n}| pｷx < c}.

This is easy to visualize diagramatically as in Figure 2. Let us now turn to the SHT. We first prove that we can separate a convex a point from a non-empty convex set, before proving we can separate two disjoint convex sets.

Theorem: (Separation of Pointfrom Convex Set) Let X be a non-empty and convex set in R^{n}. Let y ﾎ X^{c}. Then there exists a vector p ﾎ R^{n}where p ｹ 0 and inf{px | x ﾎ X} > py (i.e. the sets {y} and X are separable).

Proof: If X is convex, then its closure cl(X) is also convex. Let xｰ
be a boundary point of X such that ||xｰ - y|| = inf_{xﾎ X} ||x - y||, i.e. xｰ is the
point in cl(X) closest to y. As cl(X) is convex, then if x ﾎ
X, then l x + (1-l )xｰ ﾎ cl(X) for any l
ﾎ (0, 1] - or, simply, xｰ + l (x - xｰ ) ﾎ
cl(X). But as ||x^{0} - y|| ｣ ||x - y|| for all x ﾎ cl(X), then ||x^{0} - y|| ｣
||(x^{0} + l (x-x^{0})) - y||

or:

||x

^{0}- y|| ｣ ||(x^{0}- y) + l (x-x^{0})||

Thus squaring:

||x

^{0}- y||^{2}｣ ||(x^{0}- y) + l (x-x^{0})||^{2}

But as ||x||^{2} = xｷx, then:

(x

^{0 }- y)(x^{0}- y) ｣ [(x^{0}- y) + l (x - x^{0})]ｷ[(x^{0}- y) + l (x - x^{0})]

or:

(x

^{0 }- y)(x^{0}- y) ｣ (x^{0}- y)(x^{0}- y) + 2l (x - x^{0})ｷ(x^{0}- y) + l^{2}(x - x^{0})(x - x^{0})

thus:

2l (x - x

^{0})ｷ(x^{0}- y) + l^{2}(x - x^{0})(x - x^{0}) ｳ 0

Thus, it must be that (x - x^{0})ｷ(x^{0} - y) ｳ
0 which implies that xｷ(x^{0} - y) ｳ x^{0}ｷ(x^{0}
- y). But by the property of inner product, if x^{0} ｹ
y, then (x^{0} - y)(x^{0} - y) > 0, and thus x^{0}(x^{0}
- y) > y(x^{0} - y), thus combining the two inequalities:

xｷ(x

^{0}- y) ｳ x^{0}ｷ(x^{0}- y) > y(x^{0}- y)

Define p = (x^{0} - y), then if p ｹ 0 then the
inequalities imply:

xｷp ｳ x

^{0}ｷp > yｷp

thus, inf{xｷp | x ﾎ X} ｳ x^{0}ｷp
> yｷp. Thus, letting c = x^{0}ｷp, then:

(i) xｷp ｳ c for all x ﾎ X

(ii) c > yｷp for {y}.

Thus, {y} and X are separated by the hyperplane H(p, c) = {x ﾎ
R^{n} | xｷp = c}.ｧ

The foregoing proof is illustrated in Figure 1 (where z = l
x + (1-l )x^{0}) for two-dimensional Euclidian space (R^{2}).

Figure 1- Separation of Point from Set

We can now turn to the main Separating Hyperplane Theorem:

Theorem: (Separating Hyperplane Theorem) Let X and Y be two non-empty, convex sets in R^{n}with no interior point in common, then there exists a pair (p c) where p ﾎ R^{n}ｹ 0 and c ﾎ R such that:px ｳ c " x ﾎ X

py ｣ c " y ﾎ Y

i.e. there is a hyperplane H(p, c) which separates X and Y.

Proof: Define X - Y = {x - y ﾎ R^{n} | x ﾎ X, y ﾎ Y} which is convex. Then, 0 ﾏ int(X-Y) (if it was, i.e. if 0 ﾎ int(X
- Y), then there is an x ﾎ int(X) and y ﾎ
int(Y) such that x - y = 0, or simply x = y, i.e. there is an interior point in common).
Thus, we can separate 0 from X-Y, i.e. there exists a p ﾎ R^{n} where p ｹ 0 and a c ﾎ R such that pｷ(x-y) ｳ c and pｷ0 ｣ c. As pｷ0 = 0, then pｷ(x-y) ｳ 0,
thus px ｳ py for all x ﾎ A and y ﾎ B, or simply there is a c ﾎ R such
that px ｳ c for all x ﾎ X and py ｣ c for all y ﾎ Y for all y ﾎ Y. ｧ

An example of this in a two-dimensional space can be seen in Figure 2.

** **

Figure 2 -Separation of two convex sets

Of course, there is also a "strict" SHT which is as follows:

Theorem: (Strict SHT) Let X and Y be two closed, convex sets in R^{n}with no points in common and at least one of which is bounded, then there exists a pair (p c) where p ﾎ R^{n}ｹ 0 and c ﾎ R such that:px > c " x ﾎ X

py < c " y ﾎ Y

i.e. there is a hyperplane H(p, c) which strictly separates X and Y.

Proof: Now, X and Y are closed thus, if either X or Y is bounded, then X - Y is closed as well and, as they have no points in common, then 0 ﾏ X-Y. Consequently, the rest of the proof follows from the previous theorem on the separation of a point 0 from set X-Y.ｧ

**(C) Convex Cones and Inequalities**

Cone:X is a cone with vertex at the origin if for any x ﾎ X and any scalar a ｳ 0, then a x ﾎ X.

Convex Cone:X is a "convex cone" if for any x, y ﾎ X and any scalars a ｳ 0 and b ｳ 0, then a x + b y ﾎ X.

Thus a convex cone is always convex always contains the origin. See the diagram below
for an example in R^{2}.

Spanning: The "convex cone spanned by Y" is the smallest convex cone that contains the set Y, i.e.

C(Y) = {・/font>

_{i}l_{i}y_{i}ｽ for all i = 1, .., n, l_{i}ｳ 0, y_{i}ﾎ Y and n arbitrary}

In Figure 3, X = C(Y), i.e. X is the convex cone spanned by Y.

Dual Cone: The "dual" X* of a convex cone X is the set {p ﾎ R^{n}| pｷx ｣ 0 for all x ﾎ X}.

An example of the dual X* of the convex cone X is shown in Figure 3, for two-dimensional Euclidian space.

Figure 3- Convex Cones

The dual convex cone is always closed regardless of whether the original convex cone is closed or not. X** is the dual of the dual convex cone which, obviously, must be related to the original convex cone X. This is as follows:

Theorem: (Closedness of Dual Cone) If X is a convex cone, then X ﾍ X** (where X = X** if and only if X is closed).

Proof: By definition of X*, if x ﾎ X, then for all p ﾎ X*, pｷx ｣ 0. But pｷx = xｷp, so xｷp
｣ 0, thus x ﾎ X**. Thus, X ﾍ X**. If X is closed, we shall prove also that X** ﾍ X. Now, suppose x ﾏ X. Since X is
closed and convex, then by the Separating Hyperplane Theorem, there is a p ﾎ R^{n} such that pｷy ｣ pｷx
for all y ﾎ X. But since X is a cone, then pｷy ｣ 0 ｣ pｷx. Thus, xｷp ｳ 0. Thus, if p ﾎ X* (i.e. pｷy ｣ 0) then x ﾏ X** (as xｷp ｳ 0). Thus, x ﾏ X ﾞ
x ﾏ X**, thus X** ﾍ X. Thus,
combining with the first part, we see that X = X**.ｧ

**(D) The Minkowski-Farkas Lemma**

The Minkowski-Farkas Lemma - sometimes only referred to as "Farkas's Theorem" is a highly useful result- particularly in linear programming, where we define primal and dual problems. It is effectively a corrollary of a basic theorem of the "alternative" which is, in turn, based on the Separating Hyperplane Theorem.

Theorem: (Basic Theorem of the Alternative) Let A be a m ｴ n real matrix and b ﾎ R^{m}, then exactly one of the following alternatives is true (but not both). Either:(i) Ax = b has a non-negative solution x ｳ 0.

or

(ii) yA ｳ 0 and yｷb < 0 has a solution y.

Proof: We go through several steps.

(i) ﾞ not (ii): Suppose that Ax = b has a non-negative solution x (so (i) holds). Then premultiplying by y, then yAx = yb. Then (ii) cannot hold. If it did, i.e. if yA ｳ 0, then we see that yAx ｳ 0 because x ｳ 0 from (i). But, if so, then it must be that yb ｳ 0, which contradicts (ii). Thus, not (ii).

not (i) ﾞ (ii): Let X be the convex cone spanned by columns
a^{1}, .., a^{n} of A, i.e.

X = {a ﾎ R

^{n}| a = ・/font>_{i}l_{ i}a^{i}, l_{i}ｳ 0, i = 1, .., n}

Suppose that Ax = b has no non-negative solution. Then b ﾏ
X. Since X is closed, then by the Separating Hyperplane Theorem, there is a vector y ﾎ R^{m} such that yｷa > yｷb for all a ﾎ X. Since X contains the origin, then 0 = yｷ0 > yｷb. Supose
that not yA ｳ 0. Thus, there is a column in A, say a^{k}
such that yｷa^{k} < 0. Since X is a cone and a^{k} ﾎ
X, then a a^{k} ﾎ X for all
a > 0. Thus, for sufficiently large a
, then yｷ(a a^{k}) = a
(yｷa^{k}) < yｷb. But this contradicts separation. Thus, yｷa^{i} ｳ 0 for all columns a^{i} of A. Thus yA ｳ
0. Thus, (ii) holds.ｧ

The Minkowski-Farkas Lemma follows as a corrollary to the above. Namely:

Theorem:(Minkowski-Farkas Lemma) Let A be a m ｴ n real matrix with column vectors a^{1}, .., a^{n}ﾎ R^{m}and b ﾎ R^{m}. Then l ｷb ｳ 0 for all l ﾎ R^{m}such that l A ｳ 0 if and only if there exists non-negative vector x = (x_{1}, ..., x_{n}) such that Ax = b.

Proof: Since l ｷb ｳ 0 for all l ﾎ R^{m} such that l A ｳ 0, then there can be no l such that l A ｳ
0 and l ｷb < 0. But then, by the previous theorem of the alternative, it must be that Ax = b for some
non-negative x ﾎ R^{n}.ｧ

Thus, in short, the Minkowski-Farkas Lemma states that if l ｷb ｳ 0 for all l such that l A ｳ 0 , then Ax = b has a non-negative solution x ｳ 0. The applications of the Minkowksi Lemma are numerous - to duality theorems in linear programming, the Kuhn-Tucker theorem and in zero-sum games.

This is, of course, merely a formal result - see Gale
(1960: p.44) or Takayama (1974: p.46-7) for the intuition behind these results, which can
be represented graphically in Figure 4 where we have, for illustration, decomposed matrix
A into columns with vectors a^{1}, a^{2} and a^{3}. The convex
cone spanned by these vectors (i.e. matrix A) is represented by the shaded area X in the
diagram.

Figure 4 -Minkowski-Farkas Lemma

Let us now see the basic theorem of the alternative. The
claim that Ax = b has *no* non-negative solution x implies that b does not lie in
this convex cone, i.e. b ﾏ X (as is seen in the figure). But
then the basic theorem of the alternative claims that this implies there is a y such that
yb < 0 and yA ｳ 0, i.e. there is a y that forms an obtuse
angle with b and an acute angle with every vector a^{i}. It is easy to notice
geometrically that this implies that there is a hyperplane H(y, 0) that is orthogonal to y
and has the cone X on one side and b on the other (thus H(y, 0) = {x ﾎ
R^{n} | yｷx = 0} is *separating hyperplane* we obtain with the SHT which separates the cone X and the point b. The Minkowski-Farkas Lemma
is merely the reverse of this.

Kim C. Border (1985) *Fixed Point Theorems with Applications to Economics and Game
Theory*. Cambridge, UK: Cambridge University Press.

Gerard Debreu (1959) *Theory of Value: An axiomatic analysis of economic equilibrium*.
New York: Wiley.

Gerard Debreu (1984) "Economic Theory in a Mathematical Mode", *American
Economic Review*, Vol. 74 (3) p.267-78.

Gerard Debreu (1986) "Theoretic Models: Mathematical form and economic
content", *Econometrica*, Vol. 54 (6), p.1259-70.

Gerard Debreu (1991) "The Mathematization of
Economic Theory", *American Economic Review*, Vol 81 (1), p.1-7.

David Gale (1960) *The Theory of Linear Economic Models*. New York: McGraw-Hill.

M. Ali Khan (1993) "The Irony In/Of Economic Theory", *MLN*, Vol. 108
(4), p.759-803.

Philip Mirowski and E. Roy Weintraub (1994) "The Pure and the Applied: Bourbakism
comes to America", *Science in Context*, Vol. 7 (2), p.245-72.

J. von Neumann (1937) "A Model of General Economic
Equilibrium", in K. Menger, editor, *Ergebnisse eines mathematischen Kolloquiums,
1935-36*. 1945 Translation, *Review of Economic Studies*, Vol. 13 (1), p.1-9.

Hukukane Nikaido (1968) *Convex Structures and Economic Theory*. New York:
Academic Press.

Herbert Scarf (1973) *The Computation of Economic Equilibria*. (with the
collaboration of Terje Hansen), New Haven: Yale University Press.

Akira Takayama (1974) *Mathematical Economics*. 1985 (2nd) edition, Cambridge, UK:
Cambridge University Press.

E. Roy Weintraub (1985) *General Equilibrium Analysis: Studies in appraisal*.
Cambridge, UK: Cambridge University Press.

Back | Top | Selected References | Next |