from sage.all import * def face_generated_by(K,S): r""" Return the intersection of all faces of ``K`` that contain ``S``. REFERENCES: .. [Tam] Bit-Shun Tam. On the duality operator of a convex cone. Linear Algebra and its Applications, 64:33-56, 1985, doi:10.1016/0024-3795(85) 90265-4. SETUP:: sage: from mjo.cone.faces import face_generated_by EXAMPLES: The face generated by a standard basis vector in the nonnegative orthant should be the cone consisting of all nonnegative multiples of that standard basis vector:: sage: K = Cone([(1,0,0),(0,1,0),(0,0,1)]) sage: F = Cone([(1,0,0)]) sage: face_generated_by(K,F) == F True If we take a nontrivial combination of standard basis vectors in the nonnegative orthant, then the face that the combination generates should be the cone generated by those two basis vectors:: sage: e1 = vector(QQ, [1,0,0]) sage: e2 = vector(QQ, [0,1,0]) sage: e3 = vector(QQ, [0,0,1]) sage: K = Cone([e1,e2,e2]) sage: F = [e1/2 + e2/2] sage: face_generated_by(K,F).is_equivalent(Cone([e1,e2])) True An error is raised if ``S`` is not contained in ``K``:: sage: K = Cone([(1,0),(0,1)]) sage: S = [(1,1), (-1,3)] sage: face_generated_by(K,S) Traceback (most recent call last): ... ValueError: S is not a subset of the cone TESTS: The face generated by should be a face:: sage: set_random_seed() sage: K = random_cone(max_ambient_dim=8, max_rays=10) sage: S = ( K.random_element() for idx in range(5) ) sage: F = face_generated_by(K, S) sage: F.is_face_of(K) True The face generated by a set should always contain that set:: sage: set_random_seed() sage: K = random_cone(max_ambient_dim=8, max_rays=10) sage: S = ( K.random_element() for idx in range(5) ) sage: F = face_generated_by(K, S) sage: all(F.contains(x) for x in S) True The generators of a proper cone are all extreme vectors of the cone, and therefore generate their own faces:: sage: set_random_seed() sage: K = random_cone(max_ambient_dim=8, ....: max_rays=10, ....: strictly_convex=True, ....: solid=True) sage: all(face_generated_by(K, [r]) == Cone([r]) for r in K) True For any point ``x`` in ``K`` and any face ``F`` of ``K``, we have that ``x`` is in the relative interior of ``F`` if and only if ``F`` is the face generated by ``x`` [Tam]_:: sage: set_random_seed() sage: K = random_cone(max_ambient_dim=8, max_rays=10) sage: x = K.random_element() sage: S = [x] sage: F = K.face_lattice().random_element() sage: expected = F.relative_interior_contains(x) sage: actual = (F == face_generated_by(K, S)) sage: actual == expected True If ``F`` and ``G`` are two faces of ``K``, then the join of ``F`` and ``G`` in the face lattice is equal to the face generated by ``F + G`` (in the Minkowski sense) [Tam]_:: sage: set_random_seed() sage: K = random_cone(max_ambient_dim=8, max_rays=10) sage: L = K.face_lattice() sage: F = L.random_element() sage: G = L.random_element() sage: expected = L.join(F,G) sage: actual = face_generated_by(K, F.rays() + G.rays()) sage: actual == expected True Combining Proposition 3.1 and Corollary 3.9 in [Tam]_ gives the following equality for any ``y`` in ``K``:: sage: set_random_seed() sage: K = random_cone(max_ambient_dim=8, max_rays=10) sage: y = K.random_element() sage: S = [y] sage: phi_y = face_generated_by(K,S) sage: points_cone_gens = list(K.rays()) + [-z for z in phi_y.rays()] sage: points_cone = Cone(points_cone_gens, K.lattice()) sage: actual = phi_y.span(QQ) sage: expected = points_cone.linear_subspace() sage: actual == expected True """ face_lattice = K.face_lattice() candidates = [F for F in face_lattice if all(F.contains(x) for x in S)] # K itself is a face of K, so unless we were given a set S that # isn't a subset of K, the candidates list will be nonempty. if len(candidates) == 0: raise ValueError('S is not a subset of the cone') else: return face_lattice.sorted(candidates)[0] def dual_face(K,F): r""" Return the dual face of ``F`` with respect to the cone ``K``. OUTPUT: A face of ``K.dual()``. REFERENCES: .. [HilgertHofmannLawson] Joachim Hilgert, Karl Heinrich Hofmann, and Jimmie D. Lawson. Lie groups, convex cones and semigroups. Oxford Mathematical Monographs. Clarendon Press, Oxford, 1989. ISBN 9780198535690. .. [Tam] Bit-Shun Tam. On the duality operator of a convex cone. Linear Algebra and its Applications, 64:33-56, 1985, doi:10.1016/0024-3795(85) 90265-4. SETUP:: sage: from mjo.cone.faces import (dual_face, face_generated_by) EXAMPLES: The dual face of the first standard basis vector in three dimensions is the face generated by the other two standard basis vectors:: sage: K = Cone([(1,0,0),(0,1,0),(0,0,1)]) sage: F = Cone([(1,0,0)]) sage: dual_face(K,F).rays() M(0, 0, 1), M(0, 1, 0) in 3-d lattice M TESTS: The dual face of ``K`` with respect to itself should be the lineality space of its dual [Tam]_:: sage: set_random_seed() sage: K = random_cone(max_ambient_dim=8, max_rays=10) sage: K_dual = K.dual() sage: lKd_gens = ( dir*l for dir in [1,-1] for l in K_dual.lines() ) sage: linspace_K_dual = Cone(lKd_gens, K_dual.lattice()) sage: dual_face(K,K).is_equivalent(linspace_K_dual) True If ``K`` is proper, then the dual face of its trivial face is the dual of ``K`` [Tam]_:: sage: set_random_seed() sage: K = random_cone(max_ambient_dim=8, ....: max_rays=10, ....: strictly_convex=True, ....: solid=True) sage: L = K.lattice() sage: trivial_face = Cone([L.zero()], L) sage: dual_face(K,trivial_face).is_equivalent(K.dual()) True The dual of the cone of ``K`` at ``y`` is the dual face of the face of ``K`` generated by ``y`` ([Tam]_ Corollary 3.2):: sage: set_random_seed() sage: K = random_cone(max_ambient_dim=8, max_rays=10) sage: y = K.random_element() sage: S = [y] sage: phi_y = face_generated_by(K,S) sage: points_cone_gens = list(K.rays()) + [-z for z in phi_y.rays()] sage: points_cone = Cone(points_cone_gens, K.lattice()) sage: points_cone.dual().is_equivalent(dual_face(K, phi_y)) True Since all faces of a polyhedral cone are exposed, the dual face of a dual face should be the original face [HilgertHofmannLawson]_:: sage: set_random_seed() sage: def check_prop(K,F): ....: return dual_face(K.dual(), dual_face(K,F)).is_equivalent(F) sage: K = random_cone(max_ambient_dim=8, max_rays=10) sage: all(check_prop(K,F) for F in K.face_lattice()) True """ # Ensure that F is actually a face of K before continuing. if not F.is_face_of(K): raise ValueError("%s is not a face of %s" % (F,K)) span_F = Cone((c*g for c in [1,-1] for g in F), F.lattice()) return K.dual().intersection(span_F.dual())