(A) Convex Sets and Convex Hulls 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 unnecessary 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:
Now we turn to an often useful theorem:
Proof: If x, y Î Ç nXn then x, y Î Xn for all n. Since Xn is convex, then for any l Î (0, 1), we have l x + (1-l )y Î Xn for all n. Thus, for any l Î (0, 1), l x + (1-l )y Î Ç nXn.§ It is easy to show that È nXn is not convex.
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 å i l ixi where xi Î X and l i ³ 0 and å il i = 1.
Proof: Let {Xn} be the collection of all convex sets containing X, i.e. X Í Xn for all Xn. Since Rn is itself convex, then {Xn} is non-empty. From the earlier theorem, we know that the intersection is convex, thus Ç n Xn is convex and itself contains X. Thus, define co(X) = Ç nXn 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:
Thus, H(p, c) Í Rn is a linear subspace. A hyperplane divides the space into two closed "half-spaces" H³(p, c) = {x Î Rn | p·x ³ c} and H£(p, c) = {x Î Rn | p·x £ c} which are the spaces "above" and "below" the hyperplane respectively. These half-spaces are 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³.
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.
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|| = infxÎ 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 ||x0 - y|| £ ||x - y|| for all x Î cl(X), then ||x0 - y|| £ ||(x0 + l (x-x0)) - y|| or:
Thus squaring:
But as ||x||2 = x·x, then:
or:
thus:
Thus, it must be that (x - x0)·(x0 - y) ³ 0 which implies that x·(x0 - y) ³ x0·(x0 - y). But by the property of inner product, if x0 ¹ y, then (x0 - y)(x0 - y) > 0, and thus x0(x0 - y) > y(x0 - y), thus combining the two inequalities:
Define p = (x0 - y), then if p ¹ 0 then the inequalities imply:
thus, inf{x·p | x Î X} ³ x0·p > y·p. Thus, letting c = x0·p, then:
Thus, {y} and X are separated by the hyperplane H(p, c) = {x Î Rn | x·p = c}.§ The foregoing proof is illustrated in Figure 1 (where z = l x + (1-l )x0) for two-dimensional Euclidian space (R2).
We can now turn to the main Separating Hyperplane Theorem:
Proof: Define X - Y = {x - y Î Rn | 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 Î Rn 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.
Of course, there is also a "strict" SHT which is as follows:
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
Thus a convex cone is always convex always contains the origin. See the diagram below for an example in R2.
In Figure 3, X = C(Y), i.e. X is the convex cone spanned by Y.
An example of the dual X* of the convex cone X is shown in Figure 3, for two-dimensional Euclidian space.
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:
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 Î Rn 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.
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 a1, .., an of A, i.e.
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 Î Rm 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 ak such that y·ak < 0. Since X is a cone and ak Î X, then a ak Î X for all a > 0. Thus, for sufficiently large a , then y·(a ak) = a (y·ak) < y·b. But this contradicts separation. Thus, y·ai ³ 0 for all columns ai of A. Thus yA ³ 0. Thus, (ii) holds.§ The Minkowski-Farkas Lemma follows as a corrollary to the above. Namely: (Minkowski-Farkas Lemma) Let A be a m ´ n real matrix with column vectors a1, .., an Î Rm and b Î Rm. Then l ·b ³ 0 for all l Î Rm such that l A ³ 0 if and only if there exists non-negative vector x = (x1, ..., xn) such that Ax = b. Proof: Since l ·b ³ 0 for all l Î Rm 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 Î Rn.§ 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 a1, a2 and a3. The convex cone spanned by these vectors (i.e. matrix A) is represented by the shaded area X in the diagram.
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 ai. 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 Î Rn | 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
NextAll rights reserved, Gonçalo L. Fonseca