mjo/cone/faces.py

   1 from sage.all import *
   2
   3
   4 def face_generated_by(K,S):
   5     r"""
   6     Return the intersection of all faces of ``K`` that contain ``S``.
   7
   8     REFERENCES:
   9
  10     .. [Tam] Bit-Shun Tam. On the duality operator of a convex cone. Linear
  11        Algebra and its Applications, 64:33-56, 1985, doi:10.1016/0024-3795(85)
  12        90265-4.
  13
  14     SETUP::
  15
  16         sage: from mjo.cone.faces import face_generated_by
  17
  18     EXAMPLES:
  19
  20     The face generated by a standard basis vector in the nonnegative
  21     orthant should be the cone consisting of all nonnegative multiples
  22     of that standard basis vector::
  23
  24         sage: K = Cone([(1,0,0),(0,1,0),(0,0,1)])
  25         sage: F = Cone([(1,0,0)])
  26         sage: face_generated_by(K,F) == F
  27         True
  28
  29     If we take a nontrivial combination of standard basis vectors in the
  30     nonnegative orthant, then the face that the combination generates
  31     should be the cone generated by those two basis vectors::
  32
  33         sage: e1 = vector(QQ, [1,0,0])
  34         sage: e2 = vector(QQ, [0,1,0])
  35         sage: e3 = vector(QQ, [0,0,1])
  36         sage: K = Cone([e1,e2,e2])
  37         sage: F = [e1/2 + e2/2]
  38         sage: face_generated_by(K,F).is_equivalent(Cone([e1,e2]))
  39         True
  40
  41      An error is raised if ``S`` is not contained in ``K``::
  42
  43         sage: K = Cone([(1,0),(0,1)])
  44         sage: S = [(1,1), (-1,3)]
  45         sage: face_generated_by(K,S)
  46         Traceback (most recent call last):
  47         ...
  48         ValueError: S is not a subset of the cone
  49
  50     TESTS:
  51
  52     The face generated by <whatever> should be a face::
  53
  54         sage: set_random_seed()
  55         sage: K = random_cone(max_ambient_dim=8, max_rays=10)
  56         sage: S = ( K.random_element() for idx in range(5) )
  57         sage: F = face_generated_by(K, S)
  58         sage: F.is_face_of(K)
  59         True
  60
  61     The face generated by a set should always contain that set::
  62
  63         sage: set_random_seed()
  64         sage: K = random_cone(max_ambient_dim=8, max_rays=10)
  65         sage: S = ( K.random_element() for idx in range(5) )
  66         sage: F = face_generated_by(K, S)
  67         sage: all(F.contains(x) for x in S)
  68         True
  69
  70     The generators of a proper cone are all extreme vectors of the cone,
  71     and therefore generate their own faces::
  72
  73         sage: set_random_seed()
  74         sage: K = random_cone(max_ambient_dim=8,
  75         ....:                 max_rays=10,
  76         ....:                 strictly_convex=True,
  77         ....:                 solid=True)
  78         sage: all(face_generated_by(K, [r]) == Cone([r]) for r in K)
  79         True
  80
  81     For any point ``x`` in ``K`` and any face ``F`` of ``K``, we have
  82     that ``x`` is in the relative interior of ``F`` if and only if
  83     ``F`` is the face generated by ``x`` [Tam]_::
  84
  85         sage: set_random_seed()
  86         sage: K = random_cone(max_ambient_dim=8, max_rays=10)
  87         sage: x = K.random_element()
  88         sage: S = [x]
  89         sage: F = K.face_lattice().random_element()
  90         sage: expected = F.relative_interior_contains(x)
  91         sage: actual = (F == face_generated_by(K, S))
  92         sage: actual == expected
  93         True
  94
  95     If ``F`` and ``G`` are two faces of ``K``, then the join of ``F``
  96     and ``G`` in the face lattice is equal to the face generated by
  97     ``F + G`` (in the Minkowski sense) [Tam]_::
  98
  99         sage: set_random_seed()
 100         sage: K = random_cone(max_ambient_dim=8, max_rays=10)
 101         sage: L = K.face_lattice()
 102         sage: F = L.random_element()
 103         sage: G = L.random_element()
 104         sage: expected = L.join(F,G)
 105         sage: actual = face_generated_by(K, F.rays() + G.rays())
 106         sage: actual == expected
 107         True
 108
 109     Combining Proposition 3.1 and Corollary 3.9 in [Tam]_ gives the
 110     following equality for any ``y`` in ``K``::
 111
 112         sage: set_random_seed()
 113         sage: K = random_cone(max_ambient_dim=8, max_rays=10)
 114         sage: y = K.random_element()
 115         sage: S = [y]
 116         sage: phi_y = face_generated_by(K,S)
 117         sage: points_cone_gens = list(K.rays()) + [-z for z in phi_y.rays()]
 118         sage: points_cone = Cone(points_cone_gens, K.lattice())
 119         sage: actual = phi_y.span(QQ)
 120         sage: expected = points_cone.linear_subspace()
 121         sage: actual == expected
 122         True
 123
 124     """
 125     face_lattice = K.face_lattice()
 126     candidates = [F for F in face_lattice if all(F.contains(x) for x in S)]
 127
 128     # K itself is a face of K, so unless we were given a set S that
 129     # isn't a subset of K, the candidates list will be nonempty.
 130     if len(candidates) == 0:
 131         raise ValueError('S is not a subset of the cone')
 132     else:
 133         return face_lattice.sorted(candidates)[0]
 134
 135
 136 def dual_face(K,F):
 137     r"""
 138     Return the dual face of ``F`` with respect to the cone ``K``.
 139
 140     OUTPUT:
 141
 142     A face of ``K.dual()``.
 143
 144     REFERENCES:
 145
 146     .. [HilgertHofmannLawson] Joachim Hilgert, Karl Heinrich Hofmann, and Jimmie
 147        D. Lawson. Lie groups, convex cones and semigroups. Oxford Mathematical
 148        Monographs. Clarendon Press, Oxford, 1989. ISBN 9780198535690.
 149
 150     .. [Tam] Bit-Shun Tam. On the duality operator of a convex cone. Linear
 151        Algebra and its Applications, 64:33-56, 1985, doi:10.1016/0024-3795(85)
 152        90265-4.
 153
 154     SETUP::
 155
 156         sage: from mjo.cone.faces import (dual_face, face_generated_by)
 157
 158     EXAMPLES:
 159
 160     The dual face of the first standard basis vector in three dimensions
 161     is the face generated by the other two standard basis vectors::
 162
 163         sage: K = Cone([(1,0,0),(0,1,0),(0,0,1)])
 164         sage: F = Cone([(1,0,0)])
 165         sage: dual_face(K,F).rays()
 166         M(0, 0, 1),
 167         M(0, 1, 0)
 168         in 3-d lattice M
 169
 170     TESTS:
 171
 172     The dual face of ``K`` with respect to itself should be the
 173     lineality space of its dual [Tam]_::
 174
 175         sage: set_random_seed()
 176         sage: K = random_cone(max_ambient_dim=8, max_rays=10)
 177         sage: K_dual = K.dual()
 178         sage: lKd_gens = ( dir*l for dir in [1,-1] for l in K_dual.lines() )
 179         sage: linspace_K_dual = Cone(lKd_gens, K_dual.lattice())
 180         sage: dual_face(K,K).is_equivalent(linspace_K_dual)
 181         True
 182
 183     If ``K`` is proper, then the dual face of its trivial face is the
 184     dual of ``K`` [Tam]_::
 185
 186         sage: set_random_seed()
 187         sage: K = random_cone(max_ambient_dim=8,
 188         ....:                 max_rays=10,
 189         ....:                 strictly_convex=True,
 190         ....:                 solid=True)
 191         sage: L = K.lattice()
 192         sage: trivial_face = Cone([L.zero()], L)
 193         sage: dual_face(K,trivial_face).is_equivalent(K.dual())
 194         True
 195
 196     The dual of the cone of ``K`` at ``y`` is the dual face of the face
 197     of ``K`` generated by ``y`` ([Tam]_ Corollary 3.2)::
 198
 199         sage: set_random_seed()
 200         sage: K = random_cone(max_ambient_dim=8, max_rays=10)
 201         sage: y = K.random_element()
 202         sage: S = [y]
 203         sage: phi_y = face_generated_by(K,S)
 204         sage: points_cone_gens = list(K.rays()) + [-z for z in phi_y.rays()]
 205         sage: points_cone = Cone(points_cone_gens, K.lattice())
 206         sage: points_cone.dual().is_equivalent(dual_face(K, phi_y))
 207         True
 208
 209     Since all faces of a polyhedral cone are exposed, the dual face of a
 210     dual face should be the original face [HilgertHofmannLawson]_::
 211
 212         sage: set_random_seed()
 213         sage: def check_prop(K,F):
 214         ....:     return dual_face(K.dual(), dual_face(K,F)).is_equivalent(F)
 215         sage: K = random_cone(max_ambient_dim=8, max_rays=10)
 216         sage: all(check_prop(K,F) for F in K.face_lattice())
 217         True
 218
 219     """
 220     # Ensure that F is actually a face of K before continuing.
 221     if not F.is_face_of(K):
 222         raise ValueError("%s is not a face of %s" % (F,K))
 223
 224     span_F = Cone((c*g for c in [1,-1] for g in F), F.lattice())
 225     return K.dual().intersection(span_F.dual())