CIS677: Notes for lecture 7: Convexity

CIS677
Notes for lecture 7: Convexity


Outline

  • Caratheodory's theorem
  • polarity and duality
  • the Farkas Lemma
  • convex hulls and intersections of halfspaces
  • faces and the face lattice
  • faces and polarity We'll be using the following terms:
    polytope the convex hull conv(S) of a finite set S.
    H-polyhedron the intersection P(H) of a set of halfspaces.
    V-polyhedron a Minkowski sum conv(S)+cone(S'), where S and S' are finite.
    We'll prove the Representation Theorem, that a set is an H-polyhedron iff it is a V-polyhedron.

    We'll show that a polyhedron is bounded iff it is a polytope.

    Cones and Convex Sets, Homogeneous coordinates

    Statements about convex sets can be translated into statements about cones in one higher dimension. That is, define
    lift(P) to be {[x 1] | x is in P}, and
    slice(P') to be {x | [x 1] is in P'}.
    Fact: conv(S)=slice(cone(lift(S))).

    Proof: Let Y=lift(S).

    A point x is in slice(cone(Y))

    iff [x 1] is in cone(Y),
    iff [x 1] = sump in Y cp p, where p=[p' 1].
    iff x = sump in Y cp p' and sump in Y cp = 1
    iff x is in conv(S). QED

    This can be viewed as using homogeneous coordinates: regard any point [y yd+1] as representing point x if [y yd+1] = t[x 1] for some t>0. That is, cone(Y) is the set of all [y yd+1] that represent conv(S) in homogeneous coordinates.

    Statements about flats can be translated into statements about linear subspaces in one higher dimension, because:

    aff(P)=slice(span(lift(P))).

    A set P is affinely dependent iff lift(P) is linearly dependent.

    A similar relation holds between cones and H-polyhedra: suppose P(H) is such a polyhedron.
    For a halfspace

    h={x | a·x <=b},
    let h' be the halfspace in one dimension up with
    h':={ [x xd+1] | a·x - bxd+1 <= 0},
    and H' the set of h', together with the halfspace {x | xd+1 >= 0}. Then P(H) = slice(P(H')), and P(H') is a cone.

    Caratheodory's theorem

    Every linear subspace L has a basis : a small set B in L with L=span(B).

    As will be shown, the vertices of a bounded polyhedral set P are like a basis for convex combinations: P=conv(vert(P)).

    However, there's no bound on the number of vertices, as a function of dim(P), as there is for a linear subspace. But:

    Theorem.
    1. Given a set S, for any point p in conv(S) there is a subset T with p in conv(T), with |T| = dim(S)+1, and the points of S' are affinely independent.
    2. Given a set S, for any point p in cone(S), there is a subset T of S with p in cone(T), with |T|=dim(S), and the points of T are linearly independent.
    Proof. Part (ii): Suppose T' is a subset of S such that:
    p is in cone(T'),
    the size |T'| is as small as possible,
    but |T'| > dim(S).
    Suppose p=sums in T' cs s. Then T' is linearly dependent, so for some coefficients ds,
    sums in T' ds cs s = 0.
    Pick the element smax of T' with the largest ds, and write
    css max = sums in T'\{smax} -ds/dmax cs s.
    Note that that each coefficient on the right is greater than -cs.

    Now substitute this expression for smax into the sum for p. This eliminates the appearence of smax in the sum, and keeps all other coefficients nonnegative. This contradicts the choice of T'.

    Part (i) follows from conv(S)=slice(cone(lift(S))) and using QED

    A Farkas Lemma

    The Farkas Lemma is fundamental to the theory of polytopes; it is a form of linear programming duality, and takes many forms.
    One form says:
    Given a set S and a point p, either
    1. p is in conv(S), or
    2. there is a hyperplane h such that p is on one side of h, and S is on the other,
    but not both (i) and (ii).

    It will be useful to have a version of this lemma for cones; it's possible to say more about the separating hyperplane, also: it can be the affine hull (in the convex case) or the linear span (in the cone case) of a subset of S.

    Farkas Lemma. Given a set S and a point p, either
    1. p is in cone(S), or
    2. there is a linear subspace span(T), such that p is on one side of span(T), and S is on the other, where
      T is a subset of S,
      |T| is no more than dim(S)-1, and
      T is linearly independent,
    but not both (i) and (ii).

    This can be viewed as a "theorem of the alternative": either one system of inequalities holds, expressing that (i) holds, or another system does, expressing that (ii) holds.

    The Lemma can be viewed as showing that there is a "witness", span(T), to p not being in cone(S): an easy-to-check proof that p is not in cone(S).

    Here we use it to show the relation between V-polyhedral sets, given as convex hulls, and H-polyhedral sets, given as halfspace intersections.

    Proof sketch of the Farkas Lemma

    If p is in cone(S), then there can be no a with
    a·p > 0 and a·s <= 0 for all s in S,
    because p in cone(S) means p = sums in S cs s, with cs >= 0 for all s. But then a·s <= 0 for all s implies
    0 > a·p = a·sums in S cs s = sums in S cs a·s >= 0,
    contradiction.

    Suppose p is not in cone(S). Then by Caratheodory's theorem, p is not in any simplicial cone cone(S'), having |S'| = dim(S), and with S' a subset of S.

    Pick a point q inside one such simplicial cone, and consider the intersections of the line qp with all such simplicial cones arising from S. Let q' be the intersection point closest to p. Then q' is in some cone(T), where |T|=dim(S)-1, and span(T) separates S and p: suppose there is some point s on the same side of span(T) as p; Then, as can be shown, the intersection of L and cone(T union s) has an endpoint closer to p than q'.

    Put another way: pick a cone(T) with |T|=dim(S)-1, with q a point in cone(T), and suppose a point s of S is on the same side of span(T) as p. Then for some s' in T, cone(T union s \ s') has intersection with qp closer the p than the intersection of qp with cone(T). Reset T to be T union s \ s', and repeat until either a separating plane is found, or p is in some cone. QED

    This proof is really a disguised form of the simplex algorithm for linear programming, of which more later.

    It is not hard to prove the "as can be shown" condition, using the linear independence of the sets T yielding the cones.

    Polarity

    Polarity, and more generally duality, are key concepts of convexity.

    Suppose P(H) is a cone, with all bounding hyperplanes passing through the origin.

    From the definition of P(H), we have

    h*·x <= 0 for every h in H and every x in P(H),
    where h* is any vector perpendicular to h and not in it. That is, every x in P(H) lies in every halfspace associated with each h*. However, the above also says that each h* lies in the intersection of a set of halfspaces, namely, those bounded by planes perpendicular to x.

    We'll define the polar P(H)* of P(H) as the intersection of all those halfspaces, so that, parallel to the above,

    y·x <= 0 for every y in P(H)* and every x in P(H),
    This may motivate the following definitions:
    h* := for a halfspace h, the ray of all vectors a with so that h = {x | a·x <= 0}.
    r* := for a ray r, the halfspace of all vectors x with b·x <= 0 for b in r.
    H* := {h* | h in H}.
    P(H)* := {y | y·x <= 0 for all x in P(H)}, the polar of P(H).
    It will be convenient to confuse a ray h* and a member of it, so we will write h*·x to mean that b·x for b in h* of unit length.

    Note that if H is a single halfspace h, then P(H)*=h*, so this notation is consistent. Also h**=h.

    The Farkas lemma for cones says that if p is not in cone(S), then there is some w with w·s <= 0 for s in S, but w·y > 0. That is, w is a member of cone(S)*, and w·y > 0.

    Polarity can be used to show that halfspace intersection is algorithmically equivalent to convex hull. Dual transforms like polarity can be used to illuminate the relationship between Delaunay triangulations and Voronoi diagrams.

    Theorem. P(H)* = cone(H*).
    Proof. Suppose y is in cone(H*). Then for any x in P(H),
    y·x = sumh in H ch h*·x,
    for some nonnegative values ch. But this is no more than 0, since x is in P(H), and so y is in P(H)*.

    Suppose y is not in cone(H*). Then by the Farkas lemma, there is a vector w with y·w > 0, and with w·x <= 0 for all x in cone(H*). But the latter implies w is in P(H), and so y·w > 0 implies y is not in P(H)*. QED

    Theorem. P(H)** = P(H).
    Proof. That is, the polar of the polar is the original set. We have
    P(H)** = { x | y·x <= 0 for all y in P(H)*}.
    Suppose x is in P(H)**. Then since P(H)*=cone(H*), which contains H*, x·y <=0 for y in H*, but that implies x is in P(H). Now suppose x is in P(H). This implies y·x <= 0 for any y in P(H)*. Hence x is in P(H)**. QED

    H-cones and V-cones

    Theorem. (Representation Theorem for Cones.) A cone C has the form cone(S) for some finite set S iff C has the form P(H) for a finite set H of halfspaces.
    Proof. Given cone(S), suppose p is not in cone(S). Then by the Farkas lemma, there is some span(T), with T a subset of S of size dim(S)-1, that separates p and S. So if HS is the set of halfspaces
    HS := {h | h is bounded by span(T), T subset S, |T| = dim(S)-1, h contains S},
    then p not in cone(S) implies that p is not in P(HS). That is, P(HS) is a subset of cone(S). But P(HS) contains S, and so contains cone(S), and so cone(S)=P(HS).

    Given P(H), consider P(H)*=cone(H*). As just seen, there is a finite set of halfspaces Hc such that

    P(H)* = cone(H*) = P(Hc).
    But then
    P(H)=P(H)** = P(Hc)* = cone(Hc),
    using the previous two theorems, and so P(H) can be written as cone generated by Hc. QED
    Theorem. A convex set C has the form P(H) for a finite set H of halfspaces if and only if it has the form conv(S1)+cone(S0) for some finite sets S1 and S0.
    Proof. Pass from P(H) to the corresponding cone P(H') in one dimension higher, as discussed above. By the Representation Theorem for cones, the cone P(H') is equal to cone(T), for some finite set T. A point x' in T has the form [x xd+1], and since we're only interested in cone(T), we can change T to T', where T'= T1 union T0, with
    T1 := {[x/xd+1 1] | [x xd+1] in T, xd+1!=0},
    and T0 := T \ T1, that is, all the members of T with xd+1=0. Then cone(T)=cone(T1) + cone(T0); if we let
    S1 := {x | [x 1] is in T1}, and
    S0 := {x | [x 0] is in T0},
    then
    conv(S1)= {x | [x 1] in cone(T1)}, and
    cone(S0) = {x | [x 0] in cone(T0)},
    and
    conv(S1) + cone(S0) = slice(cone(T)) = P(H).
    Showing that cone(S1) + cone(S0) is an H-polyhedron will probably be an exercise. QED

    From this, it follows that a polyhedron is a polytope iff it is bounded: that is, a polyhedron conv(S1)+cone(S0) is bounded iff cone(S0) is empty.

    Corollaries

    Here are some facts that follow easily from these results. Notice that the first two are easy for H-polyhedra, and the rest are easier for V-polyhedra.
    The intersection of two polyhedra is a polyhedron.

    Since a flat is a polyhedron, the intersection of a polyhedron with a flat is a polyhedron.

    The projection of a polyhedron is a polyhedron.

    The Minkowski sum of two polyhedra is a polyhedron.

    Polarity for Polyhedra

    So far, the definition of polarity has only been for the case of cones. To extend this concept to a polyhedron P, we define
    P* := {y | y·x <= 1 for all x in P}.
    This defintion is the same for cones as the previous one: if y·x <= 1 for all x in a cone, then y·x <= 0 for all x.

    Any supporting halfspace h = {x | a·x <= b} can also be decribed with b=1, as long as b!=0. If P contains 0 in its interior, then all its supporting halfspaces can be put in a form that has b=1. Also, P* always contains 0. So, for theorems like P**=P, the additional condition that 0 is in the interior of P is needed.

    If h={x | y·x <= 1}, define h* as y and y* as h.

    We have:

    Facts When P, P(H), and conv(S) are polytopes containing the origin, then their polars are also, and:
    P**=P;
    P(H)* = conv(H*).
    conv(S)* = P(S*).
    Proof. The last two can be proven using the mapping to cones and back.

    Faces

    Supporting
    halfspace:     		A closed halfspace h is a supporting halfspace of a polyhedron P if h contains P.
    Face: A face f of a polyhedron P is the intersection of P with the plane bounding a supporting halfspace h. We will say that h is a witness for f.

    Note that if h is a supporting halfspace of a cone C, then h* is in C*.

    For completeness, we include the polyhedron itself as a face. Notice that the empty set is a face. The remaining faces are called proper.

    Let
    faces(P) denote the set of faces of a polyhedron P.
    vertices: faces of P of dimension 0 (single points); the set of vertices is denoted vert(P).
    edges: faces of P of dimension 1 (line segments).
    facets: faces of P of dimension dim(P)-1.
    ridges: faces of P of dimension dim(P)-2.

    In Lecture 1, vertices were defined as points in the convex hull that could not be written as convex combinations of other points in the hull. The two definitions are equivalent:

    Lemma. If v is in conv(S), then:
    v is in vert(conv(S)) iff v is not in conv(S\{v}).
    Proof. Suppose v is a vertex, so there is some halfspace h={x | a·x <=b} with S a subset of h, a·v = b, and a·x < b for all x in conv(S)\{v}. Then any convex combination
    sump in S\{v} cp p
    will have
    a·sump in S\{v} cp p = sump in S\{v} cp a·p < b,
    and so v is not in conv(S\{v}). On the other hand, suppose v is in conv(S) but not conv(S\{v}). Then by the Farkas lemma, there a halfspace
    h' := {x | a'·x <= b'}
    with v not in h' but conv(S\{v}) a subset of h'. It follows that
    h'' := {x | a'·x <= a'·v}
    is a supporting halfspace with v on its bounding plane. Hence v is a vertex. QED

    From this it follows that:

    Lemma. If P=conv(S) is a polytope, then
    vert(P) is a subset of S, and P=conv(vert(P)).
    Proof. Suppose v is a vertex of P; then conv(S\{v}) is not equal to conv(S), and so v must be in S.

    So vert(P) is a subset of S, and so P=conv(S) contains conv(vert(P)).

    If x is in S but not in vert(P), then conv(S)=conv(S\{x}), and so by induction on the size of S\vert(P), conv(S)=conv(vert(P)). QED

    Lemma. If P is a polyhedron, the intersection of two faces of P is a face of P.

    Proof. Suppose f and g are faces, so there are supporting halfspaces

    hf := {x | a·x <= b}, and
    hg := {x | a'·x <= b'}
    whose bounding planes intersect P at f and g. Clearly the halfspace
    h := {x | (a+a')·x <= b+b'},
    has P a subset of h, and for any x in P,
    (a+a')·x = b+b'
    only when both
    a·x = b and a'·x = b';
    hence the intersection of f and g is the intersection of P with the bounding plane of h, and so is a face. QED
    Lemma. Let P be a polyhedron. If g is in faces(P), and f is in faces(g), then f is in faces(P).
    Proof. Suppose
    hg := {x | ag·x <= bg}
    witnesses that g is a face of P: that is, hg is supporting and g is the intersection of hg with P. Suppose
    hf := {x | af·x <= bf}
    is a witness that f is a face of g.

    Notice that hf does not necessarily contain P. Now for value z, consider

    hz := {x | (ag + zaf)x <= bg + zbf}.
    That is, h0=hg. Notice that f is in the bounding plane of hz, for any z.

    Suppose P=conv(S1)+cone(S0). Now pick z>0, but small enough that all S1 and S0 are included in hz. Then P is in hz, but the intersection of P with the bounding plane of hz is f. Hence f is a face of P. QED

    Corollary. Let P be a polyhedron. If g is in faces(P), then
    faces(g)={f in faces(P) | f is a subset of g}.

    Proof. The previous lemma implies that the faces of g are a subset of the faces of P.

    Suppose f is a face of P that lies in g. If h witnesses that f is a face of P, then h also witnesses that f is a face of g. QED

    In particular, the vertices of f in vert(P) are a subset of the vertices of P, and so if P=conv(S), then vert(f) is a subset S, and f=conv(f intersect S).

    Faces of Cones

    When v is a vertex of a polyhedron P, cone({v}) is an extreme ray of C:=cone(lift(P)); that is, cone({v}) is a 1-dimensional face of C. The set of extreme rays of a cone C is denote extr(C), and it can be shown that C=cone(extr(C)), which is analogous to P=conv(vert(P)) for a polytope P.

    Faces and lattices

    We've seen that for a polyhedron P and a,b,c in faces(P):

    P is a face of P; if a is a face of b is a face of c, then a is a face of c.
    and easily:
    if a is a face of b and b is a face of a, then a=b.

    That is, the faces can be partially ordered under the "is a face of" relation. The fact that the intersection of two faces is a face implies also that the faces form a mathematical structure called a lattice.

    Faces of Cones

    When v is a vertex of a polyhedron P, cone({v}) is an extreme ray of C:=cone(lift(P)); that is, cone({v}) is a 1-dimensional face of C. The set of extreme rays of a cone C is denoted extr(C), and it can be shown that C=cone(extr(C)), which is analogous to P=conv(vert(P)) for a polytope P.

    Faces, Cones, and Polarity

    We've seen that the polar of a cone is cone. There is a fundamental relation between the faces of a cone C and its polar C*.

    Suppose f is a face of C, and h={x | h*·x <= 0} is a witness to this. Since h is supporting, h* is a member of C*. Let fo be the subset of C* comprising all h* for which h is a witness for f. That is,

    fo := {y | y·x <0 for all x in C\f, y·x = 0 for all x in f}.
    Moreover,
    fo = {y | y·x <0 for all x in extr(C)\extr(f), y·x = 0 for all x in extr(f)},
    and so fo is a face of C*: it is the intersection of C* with the a set of planes associated with the vertices of f.

    From the description of fo, it's immediate that

    f is a face of g iff go is a face of fo.

    Is fo=f*?

    What is fo if C is given as an intersection of halfspaces? We suppose for now that f is determined by the bounding planes of some subset Hf of H.

    Lemma. If C=P(H), and f is a face of C given by
    f = {x | h*·x <0 for h in H\Hf, h*·x = 0 for h in Hf},
    then fo=cone(Hf*).

    Proof. Any member y of Hf* has

    y·x = 0 for all x in f, and
    y·x < 0 for all x in C\f,
    and any positive combinations of such y's preserves these conditions, so cone(Hf*) is a subset of fo.

    On the other hand, if y is in fo, then y is in cone(H*), so y=sumh* in H* ch h*, with all ch>=0. If ch>0 for h* not in Hf*, then y·x < 0 for x in f, which cannot happen for y in fo. Hence y is in cone(H<fsup>*). QED

    Finally:

    Lemma. If C is a cone and f is a face of C, then foo=f.

    Proof. If C=cone(S), and f= cone(Sf), then

    fo = {y | y·h* <0 for all h in (S\Sf)*, y·h* = 0 for all h in Sf*},
    and foo = cone(Sf**)= cone(Sf)=f, using the previous lemma. QED

    Thus, the mapping f-->fo is a 1-1 correspondence between the faces of C and the faces of C*, and reverses the "is a face of" relation.