]>
gitweb.michael.orlitzky.com - sage.d.git/blob - mjo/cone/cone.py
1 # Sage doesn't load ~/.sage/init.sage during testing (sage -t), so we
2 # have to explicitly mangle our sitedir here so that "mjo.cone"
4 from os
.path
import abspath
5 from site
import addsitedir
6 addsitedir(abspath('../../'))
13 Return whether or not this cone is equal to its ambient vector space.
17 ``True`` if this cone is the entire vector space and ``False``
22 A ray in two dimensions is not equal to the entire space::
24 sage: K = Cone([(1,0)])
25 sage: is_full_space(K)
28 Neither is the nonnegative orthant::
30 sage: K = Cone([(1,0),(0,1)])
31 sage: is_full_space(K)
34 The right half-space contains a vector subspace, but it is still not
35 equal to the entire plane::
37 sage: K = Cone([(1,0),(-1,0),(0,1)])
38 sage: is_full_space(K)
41 But if we include nonnegative sums from both axes, then the resulting
42 cone is the entire two-dimensional space::
44 sage: K = Cone([(1,0),(-1,0),(0,1),(0,-1)])
45 sage: is_full_space(K)
49 return K
.linear_subspace() == K
.lattice().vector_space()
52 def random_cone(min_dim
=0, max_dim
=None, min_rays
=0, max_rays
=None):
54 Generate a random rational convex polyhedral cone.
56 Lower and upper bounds may be provided for both the dimension of the
57 ambient space and the number of generating rays of the cone. If a
58 lower bound is left unspecified, it defaults to zero. Unspecified
59 upper bounds will be chosen randomly.
61 The lower bound on the number of rays is limited to twice the
62 maximum dimension of the ambient vector space. To see why, consider
63 the space $\mathbb{R}^{2}$, and suppose we have generated four rays,
64 $\left\{ \pm e_{1}, \pm e_{2} \right\}$. Clearly any other ray in
65 the space is a nonnegative linear combination of those four,
66 so it is hopeless to generate more. It is therefore an error
67 to request more in the form of ``min_rays``.
71 If you do not explicitly request more than ``2 * max_dim`` rays,
72 a larger number may still be randomly generated. In that case,
73 the returned cone will simply be equal to the entire space.
77 - ``min_dim`` (default: zero) -- A nonnegative integer representing the
78 minimum dimension of the ambient lattice.
80 - ``max_dim`` (default: random) -- A nonnegative integer representing
81 the maximum dimension of the ambient
84 - ``min_rays`` (default: zero) -- A nonnegative integer representing the
85 minimum number of generating rays of the
88 - ``max_rays`` (default: random) -- A nonnegative integer representing the
89 maximum number of generating rays of
94 A new, randomly generated cone.
96 A ``ValueError` will be thrown under the following conditions:
98 * Any of ``min_dim``, ``max_dim``, ``min_rays``, or ``max_rays``
101 * ``max_dim`` is less than ``min_dim``.
103 * ``max_rays`` is less than ``min_rays``.
105 * ``min_rays`` is greater than twice ``max_dim``.
109 If we set the lower/upper bounds to zero, then our result is
112 sage: random_cone(0,0,0,0)
113 0-d cone in 0-d lattice N
115 We can predict the dimension when ``min_dim == max_dim``::
117 sage: random_cone(min_dim=4, max_dim=4, min_rays=0, max_rays=0)
118 0-d cone in 4-d lattice N
120 Likewise for the number of rays when ``min_rays == max_rays``::
122 sage: random_cone(min_dim=10, max_dim=10, min_rays=10, max_rays=10)
123 10-d cone in 10-d lattice N
127 It's hard to test the output of a random process, but we can at
128 least make sure that we get a cone back::
130 sage: from sage.geometry.cone import is_Cone # long time
131 sage: K = random_cone() # long time
132 sage: is_Cone(K) # long time
135 The upper/lower bounds are respected::
137 sage: K = random_cone(min_dim=5, max_dim=10, min_rays=3, max_rays=4)
138 sage: 5 <= K.lattice_dim() and K.lattice_dim() <= 10
140 sage: 3 <= K.nrays() and K.nrays() <= 4
143 Ensure that an exception is raised when either lower bound is greater
144 than its respective upper bound::
146 sage: random_cone(min_dim=5, max_dim=2)
147 Traceback (most recent call last):
149 ValueError: max_dim cannot be less than min_dim.
151 sage: random_cone(min_rays=5, max_rays=2)
152 Traceback (most recent call last):
154 ValueError: max_rays cannot be less than min_rays.
156 And if we request too many rays::
158 sage: random_cone(min_rays=5, max_dim=1)
159 Traceback (most recent call last):
161 ValueError: min_rays cannot be larger than twice max_dim.
165 # Catch obvious mistakes so that we can generate clear error
169 raise ValueError('min_dim must be nonnegative.')
172 raise ValueError('min_rays must be nonnegative.')
174 if max_dim
is not None:
176 raise ValueError('max_dim must be nonnegative.')
177 if (max_dim
< min_dim
):
178 raise ValueError('max_dim cannot be less than min_dim.')
179 if min_rays
> 2*max_dim
:
180 raise ValueError('min_rays cannot be larger than twice max_dim.')
182 if max_rays
is not None:
184 raise ValueError('max_rays must be nonnegative.')
185 if (max_rays
< min_rays
):
186 raise ValueError('max_rays cannot be less than min_rays.')
189 def random_min_max(l
,u
):
191 We need to handle two cases for the upper bounds, and we need to do
192 the same thing for max_dim/max_rays. So we consolidate the logic here.
195 # The upper bound is unspecified; return a random integer
197 return l
+ ZZ
.random_element().abs()
199 # We have an upper bound, and it's greater than or equal
200 # to our lower bound. So we generate a random integer in
201 # [0,u-l], and then add it to l to get something in
202 # [l,u]. To understand the "+1", check the
203 # ZZ.random_element() docs.
204 return l
+ ZZ
.random_element(u
- l
+ 1)
206 d
= random_min_max(min_dim
, max_dim
)
207 r
= random_min_max(min_rays
, max_rays
)
211 # The rays are trickier to generate, since we could generate v and
212 # 2*v as our "two rays." In that case, the resuting cone would
213 # have one generating ray. To avoid such a situation, we start by
214 # generating ``r`` rays where ``r`` is the number we want to end
216 rays
= [L
.random_element() for i
in range(0, r
)]
218 # (The lattice parameter is required when no rays are given, so we
219 # pass it just in case ``r == 0``).
220 K
= Cone(rays
, lattice
=L
)
222 # Now if we generated two of the "same" rays, we'll have fewer
223 # generating rays than ``r``. In that case, we keep making up new
224 # rays and recreating the cone until we get the right number of
225 # independent generators. We can obviously stop if ``K`` is the
226 # entire ambient vector space.
227 while r
> K
.nrays() and not is_full_space(K
):
228 rays
.append(L
.random_element())
234 def discrete_complementarity_set(K
):
236 Compute the discrete complementarity set of this cone.
238 The complementarity set of this cone is the set of all orthogonal
239 pairs `(x,s)` such that `x` is in this cone, and `s` is in its
240 dual. The discrete complementarity set restricts `x` and `s` to be
241 generators of their respective cones.
245 A list of pairs `(x,s)` such that,
247 * `x` is in this cone.
248 * `x` is a generator of this cone.
249 * `s` is in this cone's dual.
250 * `s` is a generator of this cone's dual.
251 * `x` and `s` are orthogonal.
255 The discrete complementarity set of the nonnegative orthant consists
256 of pairs of standard basis vectors::
258 sage: K = Cone([(1,0),(0,1)])
259 sage: discrete_complementarity_set(K)
260 [((1, 0), (0, 1)), ((0, 1), (1, 0))]
262 If the cone consists of a single ray, the second components of the
263 discrete complementarity set should generate the orthogonal
264 complement of that ray::
266 sage: K = Cone([(1,0)])
267 sage: discrete_complementarity_set(K)
268 [((1, 0), (0, 1)), ((1, 0), (0, -1))]
269 sage: K = Cone([(1,0,0)])
270 sage: discrete_complementarity_set(K)
271 [((1, 0, 0), (0, 1, 0)),
272 ((1, 0, 0), (0, -1, 0)),
273 ((1, 0, 0), (0, 0, 1)),
274 ((1, 0, 0), (0, 0, -1))]
276 When the cone is the entire space, its dual is the trivial cone, so
277 the discrete complementarity set is empty::
279 sage: K = Cone([(1,0),(-1,0),(0,1),(0,-1)])
280 sage: discrete_complementarity_set(K)
285 The complementarity set of the dual can be obtained by switching the
286 components of the complementarity set of the original cone::
288 sage: K1 = random_cone(max_dim=10, max_rays=10)
290 sage: expected = [(x,s) for (s,x) in discrete_complementarity_set(K2)]
291 sage: actual = discrete_complementarity_set(K1)
292 sage: actual == expected
296 V
= K
.lattice().vector_space()
298 # Convert the rays to vectors so that we can compute inner
300 xs
= [V(x
) for x
in K
.rays()]
301 ss
= [V(s
) for s
in K
.dual().rays()]
303 return [(x
,s
) for x
in xs
for s
in ss
if x
.inner_product(s
) == 0]
306 def lyapunov_rank(K
):
308 Compute the Lyapunov (or bilinearity) rank of this cone.
310 The Lyapunov rank of a cone can be thought of in (mainly) two ways:
312 1. The dimension of the Lie algebra of the automorphism group of the
315 2. The dimension of the linear space of all Lyapunov-like
316 transformations on the cone.
320 A closed, convex polyhedral cone.
324 An integer representing the Lyapunov rank of the cone. If the
325 dimension of the ambient vector space is `n`, then the Lyapunov rank
326 will be between `1` and `n` inclusive; however a rank of `n-1` is
327 not possible (see the first reference).
331 In the references, the cones are always assumed to be proper. We
332 do not impose this restriction.
340 The codimension formula from the second reference is used. We find
341 all pairs `(x,s)` in the complementarity set of `K` such that `x`
342 and `s` are rays of our cone. It is known that these vectors are
343 sufficient to apply the codimension formula. Once we have all such
344 pairs, we "brute force" the codimension formula by finding all
345 linearly-independent `xs^{T}`.
349 1. M.S. Gowda and J. Tao. On the bilinearity rank of a proper cone
350 and Lyapunov-like transformations, Mathematical Programming, 147
353 2. G. Rudolf, N. Noyan, D. Papp, and F. Alizadeh, Bilinear
354 optimality constraints for the cone of positive polynomials,
355 Mathematical Programming, Series B, 129 (2011) 5-31.
359 The nonnegative orthant in `\mathbb{R}^{n}` always has rank `n`::
361 sage: positives = Cone([(1,)])
362 sage: lyapunov_rank(positives)
364 sage: quadrant = Cone([(1,0), (0,1)])
365 sage: lyapunov_rank(quadrant)
367 sage: octant = Cone([(1,0,0), (0,1,0), (0,0,1)])
368 sage: lyapunov_rank(octant)
371 The `L^{3}_{1}` cone is known to have a Lyapunov rank of one::
373 sage: L31 = Cone([(1,0,1), (0,-1,1), (-1,0,1), (0,1,1)])
374 sage: lyapunov_rank(L31)
377 Likewise for the `L^{3}_{\infty}` cone::
379 sage: L3infty = Cone([(0,1,1), (1,0,1), (0,-1,1), (-1,0,1)])
380 sage: lyapunov_rank(L3infty)
383 The Lyapunov rank should be additive on a product of cones::
385 sage: L31 = Cone([(1,0,1), (0,-1,1), (-1,0,1), (0,1,1)])
386 sage: octant = Cone([(1,0,0), (0,1,0), (0,0,1)])
387 sage: K = L31.cartesian_product(octant)
388 sage: lyapunov_rank(K) == lyapunov_rank(L31) + lyapunov_rank(octant)
391 Two isomorphic cones should have the same Lyapunov rank. The cone
392 ``K`` in the following example is isomorphic to the nonnegative
393 octant in `\mathbb{R}^{3}`::
395 sage: K = Cone([(1,2,3), (-1,1,0), (1,0,6)])
396 sage: lyapunov_rank(K)
399 The dual cone `K^{*}` of ``K`` should have the same Lyapunov rank as ``K``
402 sage: K = Cone([(2,2,4), (-1,9,0), (2,0,6)])
403 sage: lyapunov_rank(K) == lyapunov_rank(K.dual())
408 The Lyapunov rank should be additive on a product of cones::
410 sage: K1 = random_cone(max_dim=10, max_rays=10)
411 sage: K2 = random_cone(max_dim=10, max_rays=10)
412 sage: K = K1.cartesian_product(K2)
413 sage: lyapunov_rank(K) == lyapunov_rank(K1) + lyapunov_rank(K2)
416 The dual cone `K^{*}` of ``K`` should have the same Lyapunov rank as ``K``
419 sage: K = random_cone(max_dim=10, max_rays=10)
420 sage: lyapunov_rank(K) == lyapunov_rank(K.dual())
424 V
= K
.lattice().vector_space()
426 C_of_K
= discrete_complementarity_set(K
)
428 matrices
= [x
.tensor_product(s
) for (x
,s
) in C_of_K
]
430 # Sage doesn't think matrices are vectors, so we have to convert
431 # our matrices to vectors explicitly before we can figure out how
432 # many are linearly-indepenedent.
434 # The space W has the same base ring as V, but dimension
435 # dim(V)^2. So it has the same dimension as the space of linear
436 # transformations on V. In other words, it's just the right size
437 # to create an isomorphism between it and our matrices.
438 W
= VectorSpace(V
.base_ring(), V
.dimension()**2)
442 Convert a matrix to a vector isomorphically.
446 vectors
= [phi(m
) for m
in matrices
]
448 return (W
.dimension() - W
.span(vectors
).rank())