]> gitweb.michael.orlitzky.com - sage.d.git/blob - mjo/cone/faces.py
makefile: add --long to the test command.
[sage.d.git] / 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())