mjo/cone/faces.py

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