X-Git-Url: http://gitweb.michael.orlitzky.com/?a=blobdiff_plain;f=mjo%2Fcone%2Ffaces.py;h=acd9802c0ee953d28723da484c148ccd7b4a0b6d;hb=1bbade9f41ffbfe366b15d0db657f666bc1f025d;hp=70ecc20d31577d74a59a6d2655d3b93ccc3f710d;hpb=bcdc6431e034e6f7a9d6ddcb3282cecadfab597b;p=sage.d.git diff --git a/mjo/cone/faces.py b/mjo/cone/faces.py index 70ecc20..acd9802 100644 --- a/mjo/cone/faces.py +++ b/mjo/cone/faces.py @@ -1,5 +1,6 @@ from sage.all import * + def face_generated_by(K,S): r""" Return the intersection of all faces of ``K`` that contain ``S``. @@ -52,7 +53,7 @@ def face_generated_by(K,S): sage: set_random_seed() sage: K = random_cone(max_ambient_dim=8, max_rays=10) - sage: S = [K.random_element() for idx in range(0,5)] + sage: S = ( K.random_element() for idx in range(5) ) sage: F = face_generated_by(K, S) sage: F.is_face_of(K) True @@ -61,9 +62,9 @@ def face_generated_by(K,S): sage: set_random_seed() sage: K = random_cone(max_ambient_dim=8, max_rays=10) - sage: S = [K.random_element() for idx in range(0,5)] + 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]) + sage: all(F.contains(x) for x in S) True The generators of a proper cone are all extreme vectors of the cone, @@ -74,7 +75,7 @@ def face_generated_by(K,S): ....: max_rays=10, ....: strictly_convex=True, ....: solid=True) - sage: all([face_generated_by(K, [r]) == Cone([r]) for r in K]) + 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 @@ -105,9 +106,24 @@ def face_generated_by(K,S): 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])] + 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. @@ -115,3 +131,95 @@ def face_generated_by(K,S): 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())