10 I. Convex Sets at Large Remark: We prove this in Chapter II see Corollary II.4.3. 7∗. Prove that a bounded polyhedron P Rd is also a polytope. Remark: We prove this in Chapter IV see Corollary IV.1.3. It seems intuitively obvious that in the space of a small dimension, to represent a given point x from the convex hull of a set A as a convex combination, we would need to use only a few points of A, although their choice will, of course, depend on x. For example, in the plane, to represent x as a convex combination, we need to use only three points see Figure 4. a b c d e u Figure 4. Example: to represent u as a convex combination of a, b, c, d and e, we need only three points, for instance b, e and d. The general fact is known as Carath´ eodory’s Theorem, which was proved by C. Carath´ eodory around 1907. (2.3) Carath´ eodory’s Theorem. Let S Rd be a set. Then every point x conv(S) can be represented as a convex combination of d + 1 points from S: x = α1y1 + . . . + αd+1yd+1, where d+1 i=1 αi = 1, αi 0 and yi S for i = 1, . . . , d + 1. Proof. Every point x conv(S) can be written as a convex combination x = α1y1 + . . . + αmym of some points y1,... , ym S. We can assume that αi 0 for all i = 1, . . . , m. If m d+1, we can add terms 0y1, say, to get a convex combination with d+1 terms. Suppose that m d + 1. Let us show that we can construct a convex combination
Previous Page Next Page