mjo/cone/faces.py

   1 from sage.all import *
   2
   3 def face_generated_by(K,S):
   4     r"""
   5     Return the intersection of all faces of ``K`` that contain ``S``.
   6
   7     REFERENCES:
   8
   9     .. [Tam] Bit-Shun Tam. On the duality operator of a convex cone. Linear
  10        Algebra and its Applications, 64:33-56, 1985, doi:10.1016/0024-3795(85)
  11        90265-4.
  12
  13     SETUP::
  14
  15         sage: from mjo.cone.faces import face_generated_by
  16
  17     EXAMPLES:
  18
  19     The face generated by a standard basis vector in the nonnegative
  20     orthant should be the cone consisting of all nonnegative multiples
  21     of that standard basis vector::
  22
  23         sage: K = Cone([(1,0,0),(0,1,0),(0,0,1)])
  24         sage: F = Cone([(1,0,0)])
  25         sage: face_generated_by(K,F) == F
  26         True
  27
  28     If we take a nontrivial combination of standard basis vectors in the
  29     nonnegative orthant, then the face that the combination generates
  30     should be the cone generated by those two basis vectors::
  31
  32         sage: e1 = vector(QQ, [1,0,0])
  33         sage: e2 = vector(QQ, [0,1,0])
  34         sage: e3 = vector(QQ, [0,0,1])
  35         sage: K = Cone([e1,e2,e2])
  36         sage: F = [e1/2 + e2/2]
  37         sage: face_generated_by(K,F).is_equivalent(Cone([e1,e2]))
  38         True
  39
  40      An error is raised if ``S`` is not contained in ``K``::
  41
  42         sage: K = Cone([(1,0),(0,1)])
  43         sage: S = [(1,1), (-1,3)]
  44         sage: face_generated_by(K,S)
  45         Traceback (most recent call last):
  46         ...
  47         ValueError: S is not a subset of the cone
  48
  49     TESTS:
  50
  51     The face generated by <whatever> should be a face::
  52
  53         sage: set_random_seed()
  54         sage: K = random_cone(max_ambient_dim=8, max_rays=10)
  55         sage: S = [K.random_element() for idx in range(0,5)]
  56         sage: F = face_generated_by(K, S)
  57         sage: F.is_face_of(K)
  58         True
  59
  60     The face generated by a set should always contain that set::
  61
  62         sage: set_random_seed()
  63         sage: K = random_cone(max_ambient_dim=8, max_rays=10)
  64         sage: S = [K.random_element() for idx in range(0,5)]
  65         sage: F = face_generated_by(K, S)
  66         sage: all([F.contains(x) for x in S])
  67         True
  68
  69     The generators of a proper cone are all extreme vectors of the cone,
  70     and therefore generate their own faces::
  71
  72         sage: set_random_seed()
  73         sage: K = random_cone(max_ambient_dim=8,
  74         ....:                 max_rays=10,
  75         ....:                 strictly_convex=True,
  76         ....:                 solid=True)
  77         sage: all([face_generated_by(K, [r]) == Cone([r]) for r in K])
  78         True
  79
  80     For any point ``x`` in ``K`` and any face ``F`` of ``K``, we have
  81     that ``x`` is in the relative interior of ``F`` if and only if
  82     ``F`` is the face generated by ``x`` [Tam]_::
  83
  84         sage: set_random_seed()
  85         sage: K = random_cone(max_ambient_dim=8, max_rays=10)
  86         sage: x = K.random_element()
  87         sage: S = [x]
  88         sage: F = K.face_lattice().random_element()
  89         sage: expected = F.relative_interior_contains(x)
  90         sage: actual = (F == face_generated_by(K, S))
  91         sage: actual == expected
  92         True
  93
  94     """
  95     face_lattice = K.face_lattice()
  96     candidates = [F for F in face_lattice if all([F.contains(x) for x in S])]
  97
  98     # K itself is a face of K, so unless we were given a set S that
  99     # isn't a subset of K, the candidates list will be nonempty.
 100     if len(candidates) == 0:
 101         raise ValueError('S is not a subset of the cone')
 102     else:
 103         return face_lattice.sorted(candidates)[0]