]>
gitweb.michael.orlitzky.com - sage.d.git/blob - mjo/cone/tests.py
2 Additional tests for the mjo.cone.cone module. These are extra
3 properties that we'd like to check, but which are overkill for inclusion
7 # Sage doesn't load ~/.sage/init.sage during testing (sage -t), so we
8 # have to explicitly mangle our sitedir here so that "mjo.cone"
10 from os
.path
import abspath
11 from site
import addsitedir
12 addsitedir(abspath('../../'))
14 from sage
.all
import *
16 # The double-import is needed to get the underscore methods.
17 from mjo
.cone
.cone
import *
20 def _restrict_to_subspace(K
, W
):
22 Restrict ``K`` (up to linear isomorphism) to a vector subspace.
24 This operation not only restricts the cone to a subspace of its
25 ambient space, but also represents the rays of the cone in a new
26 (smaller) lattice corresponding to the subspace. The resulting
27 cone will be linearly isomorphic (but not equal) to the
28 desired restriction, since it has likely undergone a change of
31 To explain the difficulty, consider the cone ``K =
32 Cone([(1,1,1)])`` having a single ray. The span of ``K`` is a
33 one-dimensional subspace containing ``K``, yet we have no way to
34 perform operations like "dual of" in the subspace. To represent
35 ``K`` in the space ``K.span()``, we must perform a change of basis
36 and write its sole ray as ``(1,0,0)``. Now the restricted
37 ``Cone([(1,)])`` is linearly isomorphic (but of course not equal) to
38 ``K`` interpreted as living in ``K.span()``.
42 - ``K`` -- The cone to restrict.
44 - ``W`` -- The subspace into which ``K`` will be restricted.
48 A new cone in a sublattice corresponding to ``W``.
52 M. Orlitzky. The Lyapunov rank of an improper cone.
53 http://www.optimization-online.org/DB_HTML/2015/10/5135.html
57 Restricting a solid cone to its own span returns a cone linearly
58 isomorphic to the original::
60 sage: K = Cone([(1,2,3),(-1,1,0),(9,0,-2)])
63 sage: _restrict_to_subspace(K, K.span()).rays()
69 A single ray restricted to its own span has the same
70 representation regardless of the ambient space::
72 sage: K = Cone([(1,0)])
73 sage: K_S = _restrict_to_subspace(K, K.span()).rays()
77 sage: K = Cone([(1,1,1)])
78 sage: K_S = _restrict_to_subspace(K, K.span()).rays()
83 Restricting to a trivial space gives the trivial cone::
85 sage: K = Cone([(8,3,-1,0),(9,2,2,0),(-4,6,7,0)])
86 sage: trivial_space = K.lattice().vector_space().span([])
87 sage: _restrict_to_subspace(K, trivial_space)
88 0-d cone in 0-d lattice N
92 Restricting a cone to its own span results in a solid cone::
94 sage: set_random_seed()
95 sage: K = random_cone(max_ambient_dim = 8)
96 sage: K_S = _restrict_to_subspace(K, K.span())
100 Restricting a cone to its span should not affect the number of
103 sage: set_random_seed()
104 sage: K = random_cone(max_ambient_dim = 8)
105 sage: K_S = _restrict_to_subspace(K, K.span())
106 sage: K.nrays() == K_S.nrays()
109 Restricting a cone to its span should not affect its dimension::
111 sage: set_random_seed()
112 sage: K = random_cone(max_ambient_dim = 8)
113 sage: K_S = _restrict_to_subspace(K, K.span())
114 sage: K.dim() == K_S.dim()
117 Restricting a cone to its span should not affects its lineality::
119 sage: set_random_seed()
120 sage: K = random_cone(max_ambient_dim = 8)
121 sage: K_S = _restrict_to_subspace(K, K.span())
122 sage: K.lineality() == K_S.lineality()
125 Restricting a cone to its span should not affect the number of
128 sage: set_random_seed()
129 sage: K = random_cone(max_ambient_dim = 8)
130 sage: K_S = _restrict_to_subspace(K, K.span())
131 sage: len(K.facets()) == len(K_S.facets())
134 Restricting a solid cone to its span is a linear isomorphism
135 and should not affect the dimension of its ambient space::
137 sage: set_random_seed()
138 sage: K = random_cone(max_ambient_dim = 8, solid = True)
139 sage: K_S = _restrict_to_subspace(K, K.span())
140 sage: K.lattice_dim() == K_S.lattice_dim()
143 Restricting a solid cone to its span is a linear isomorphism
144 that establishes a one-to-one correspondence of discrete
145 complementarity sets::
147 sage: set_random_seed()
148 sage: K = random_cone(max_ambient_dim = 8, solid = True)
149 sage: K_S = _restrict_to_subspace(K, K.span())
150 sage: dcs1 = K.discrete_complementarity_set()
151 sage: dcs2 = K_S.discrete_complementarity_set()
152 sage: len(dcs1) == len(dcs2)
155 Restricting a solid cone to its span is a linear isomorphism
156 under which Lyapunov rank (the length of a Lyapunov-like basis)
159 sage: set_random_seed()
160 sage: K = random_cone(max_ambient_dim = 8, solid = True)
161 sage: K_S = _restrict_to_subspace(K, K.span())
162 sage: LL1 = K.lyapunov_like_basis()
163 sage: LL2 = K_S.lyapunov_like_basis()
164 sage: len(LL1) == len(LL2)
167 If we restrict a cone to a subspace of its span, the resulting
168 cone should have the same dimension as the subspace::
170 sage: set_random_seed()
171 sage: K = random_cone(max_ambient_dim = 8)
172 sage: W_basis = random_sublist(K.rays(), 0.5)
173 sage: W = K.lattice().vector_space().span(W_basis)
174 sage: K_W = _restrict_to_subspace(K,W)
175 sage: K_W.lattice_dim() == W.dimension()
178 Through a series of restrictions, any closed convex cone can be
179 reduced to a cartesian product with a proper factor [Orlitzky]_::
181 sage: set_random_seed()
182 sage: K = random_cone(max_ambient_dim = 8)
183 sage: K_S = _restrict_to_subspace(K, K.span())
184 sage: P = K_S.dual().span()
185 sage: K_SP = _restrict_to_subspace(K_S, P)
186 sage: K_SP.is_proper()
189 # We want to intersect this cone with ``W``. We can do that via
190 # cone intersection, so we first turn the space ``W`` into a cone.
191 W_rays
= W
.basis() + [ -b
for b
in W
.basis() ]
192 W_cone
= Cone(W_rays
, lattice
=K
.lattice())
193 K
= K
.intersection(W_cone
)
195 # Now every generator of ``K`` should belong to ``W``.
196 K_W_rays
= [ W
.coordinate_vector(r
) for r
in K
.rays() ]
198 L
= ToricLattice(W
.dimension())
199 return Cone(K_W_rays
, lattice
=L
)
204 # Tests for _restrict_to_subspace.
206 def _look_isomorphic(K1
, K2
):
208 Test whether or not ``K1`` and ``K2`` look linearly isomorphic.
210 This is a hack to get around the fact that it's difficult to tell
211 when two cones are linearly isomorphic. Instead, we check a list of
212 properties that should be preserved under linear isomorphism.
216 ``True`` if ``K1`` and ``K2`` look isomorphic, or ``False``
217 if we can prove that they are not isomorphic.
221 Any proper cone with three generators in `\mathbb{R}^{3}` is
222 isomorphic to the nonnegative orthant::
224 sage: K1 = Cone([(1,0,0), (0,1,0), (0,0,1)])
225 sage: K2 = Cone([(1,2,3), (3, 18, 4), (66, 51, 0)])
226 sage: _look_isomorphic(K1, K2)
229 Negating a cone gives you an isomorphic cone::
231 sage: K = Cone([(0,2,-5), (-6, 2, 4), (0, 51, 0)])
232 sage: _look_isomorphic(K, -K)
237 Any cone is isomorphic to itself::
239 sage: K = random_cone(max_ambient_dim = 8)
240 sage: _look_isomorphic(K, K)
243 After applying an invertible matrix to the rows of a cone, the
244 result should is isomorphic to the cone we started with::
246 sage: K1 = random_cone(max_ambient_dim = 8)
247 sage: A = random_matrix(QQ, K1.lattice_dim(), algorithm='unimodular')
248 sage: K2 = Cone( [ A*r for r in K1.rays() ], lattice=K1.lattice())
249 sage: _look_isomorphic(K1, K2)
253 if K1
.lattice_dim() != K2
.lattice_dim():
256 if K1
.nrays() != K2
.nrays():
259 if K1
.dim() != K2
.dim():
262 if K1
.lineality() != K2
.lineality():
265 if K1
.is_solid() != K2
.is_solid():
268 if K1
.is_strictly_convex() != K2
.is_strictly_convex():
271 if len(K1
.lyapunov_like_basis()) != len(K2
.lyapunov_like_basis()):
274 C_of_K1
= K1
.discrete_complementarity_set()
275 C_of_K2
= K2
.discrete_complementarity_set()
276 if len(C_of_K1
) != len(C_of_K2
):
279 if len(K1
.facets()) != len(K2
.facets()):
286 Apply _restrict_to_subspace according to our paper (to obtain our main
287 result). Test all four parameter combinations::
289 sage: set_random_seed()
290 sage: K = random_cone(max_ambient_dim = 8,
291 ....: strictly_convex=False,
293 sage: K_S = _restrict_to_subspace(K, K.span())
294 sage: K_S2 = K.solid_restriction()
295 sage: _look_isomorphic(K_S, K_S2)
297 sage: K_SP = _restrict_to_subspace(K_S.dual(), K_S.dual().span()).dual()
298 sage: K_SP2 = K_S.strict_quotient()
299 sage: K_SP.is_proper()
301 sage: K_SP2.is_proper()
303 sage: _look_isomorphic(K_SP, K_SP2)
305 sage: K_SP = _restrict_to_subspace(K_S, K_S.dual().span())
306 sage: K_SP.is_proper()
308 sage: _look_isomorphic(K_SP, K_SP2)
313 sage: set_random_seed()
314 sage: K = random_cone(max_ambient_dim = 8,
315 ....: strictly_convex=False,
317 sage: K_S = _restrict_to_subspace(K, K.span())
318 sage: K_S2 = K.solid_restriction()
319 sage: _look_isomorphic(K_S, K_S2)
321 sage: K_SP = _restrict_to_subspace(K_S.dual(), K_S.dual().span()).dual()
322 sage: K_SP2 = K_S.strict_quotient()
323 sage: K_SP.is_proper()
325 sage: K_SP2.is_proper()
327 sage: _look_isomorphic(K_SP, K_SP2)
329 sage: K_SP = _restrict_to_subspace(K_S, K_S.dual().span())
330 sage: K_SP.is_proper()
332 sage: _look_isomorphic(K_SP, K_SP2)
337 sage: set_random_seed()
338 sage: K = random_cone(max_ambient_dim = 8,
339 ....: strictly_convex=True,
341 sage: K_S = _restrict_to_subspace(K, K.span())
342 sage: K_S2 = K.solid_restriction()
343 sage: _look_isomorphic(K_S, K_S2)
345 sage: K_SP = _restrict_to_subspace(K_S.dual(), K_S.dual().span()).dual()
346 sage: K_SP2 = K_S.strict_quotient()
347 sage: K_SP.is_proper()
349 sage: K_SP2.is_proper()
351 sage: _look_isomorphic(K_SP, K_SP2)
353 sage: K_SP = _restrict_to_subspace(K_S, K_S.dual().span())
354 sage: K_SP.is_proper()
356 sage: _look_isomorphic(K_SP, K_SP2)
361 sage: set_random_seed()
362 sage: K = random_cone(max_ambient_dim = 8,
363 ....: strictly_convex=True,
365 sage: K_S = _restrict_to_subspace(K, K.span())
366 sage: K_S2 = K.solid_restriction()
367 sage: _look_isomorphic(K_S, K_S2)
369 sage: K_SP = _restrict_to_subspace(K_S.dual(), K_S.dual().span()).dual()
370 sage: K_SP2 = K_S.strict_quotient()
371 sage: K_SP.is_proper()
373 sage: K_SP2.is_proper()
375 sage: _look_isomorphic(K_SP, K_SP2)
377 sage: K_SP = _restrict_to_subspace(K_S, K_S.dual().span())
378 sage: K_SP.is_proper()
380 sage: _look_isomorphic(K_SP, K_SP2)
383 Test the proposition in our paper concerning the duals and
384 restrictions. Generate a random cone, then create a subcone of
385 it. The operation of dual-taking should then commute with rho. Test
386 all parameter combinations::
388 sage: set_random_seed()
389 sage: J = random_cone(max_ambient_dim = 8,
391 ....: strictly_convex=False)
392 sage: K = Cone(random_sublist(J.rays(), 0.5), lattice=J.lattice())
393 sage: K_W_star = _restrict_to_subspace(K, J.span()).dual()
394 sage: K_star_W = _restrict_to_subspace(K.dual(), J.span())
395 sage: _look_isomorphic(K_W_star, K_star_W)
400 sage: set_random_seed()
401 sage: J = random_cone(max_ambient_dim = 8,
403 ....: strictly_convex=False)
404 sage: K = Cone(random_sublist(J.rays(), 0.5), lattice=J.lattice())
405 sage: K_W_star = _restrict_to_subspace(K, J.span()).dual()
406 sage: K_star_W = _restrict_to_subspace(K.dual(), J.span())
407 sage: _look_isomorphic(K_W_star, K_star_W)
412 sage: set_random_seed()
413 sage: J = random_cone(max_ambient_dim = 8,
415 ....: strictly_convex=True)
416 sage: K = Cone(random_sublist(J.rays(), 0.5), lattice=J.lattice())
417 sage: K_W_star = _restrict_to_subspace(K, J.span()).dual()
418 sage: K_star_W = _restrict_to_subspace(K.dual(), J.span())
419 sage: _look_isomorphic(K_W_star, K_star_W)
424 sage: set_random_seed()
425 sage: J = random_cone(max_ambient_dim = 8,
427 ....: strictly_convex=True)
428 sage: K = Cone(random_sublist(J.rays(), 0.5), lattice=J.lattice())
429 sage: K_W_star = _restrict_to_subspace(K, J.span()).dual()
430 sage: K_star_W = _restrict_to_subspace(K.dual(), J.span())
431 sage: _look_isomorphic(K_W_star, K_star_W)
434 Ensure that ``__restrict_to_subspace(K, K.span())`` and
435 ``K.solid_restriction()`` are actually equivalent::
437 sage: set_random_seed()
438 sage: K = random_cone(max_ambient_dim=8)
439 sage: K1 = _restrict_to_subspace(K, K.span())
440 sage: K2 = K.solid_restriction()
441 sage: _look_isomorphic(K1,K2)
444 Ensure that ``K.__restrict_to_subspace(K,K.dual().span())`` and
445 ``strict_quotient`` are actually equivalent::
447 sage: set_random_seed()
448 sage: K = random_cone(max_ambient_dim=6)
449 sage: K1 = _restrict_to_subspace(K, K.dual().span())
450 sage: K2 = K.strict_quotient()
451 sage: _look_isomorphic(K1,K2)
457 # Lyapunov rank tests
461 The Lyapunov rank is invariant under a linear isomorphism. Check all
462 combinations of parameters::
464 sage: K1 = random_cone(max_ambient_dim=8,
465 ....: strictly_convex=True,
467 sage: A = random_matrix(QQ, K1.lattice_dim(), algorithm='unimodular')
468 sage: K2 = Cone( [ A*r for r in K1.rays() ], lattice=K1.lattice())
469 sage: K1.lyapunov_rank() == K2.lyapunov_rank()
474 sage: K1 = random_cone(max_ambient_dim=8,
475 ....: strictly_convex=True,
477 sage: A = random_matrix(QQ, K1.lattice_dim(), algorithm='unimodular')
478 sage: K2 = Cone( [ A*r for r in K1.rays() ], lattice=K1.lattice())
479 sage: K1.lyapunov_rank() == K2.lyapunov_rank()
484 sage: K1 = random_cone(max_ambient_dim=8,
485 ....: strictly_convex=False,
487 sage: A = random_matrix(QQ, K1.lattice_dim(), algorithm='unimodular')
488 sage: K2 = Cone( [ A*r for r in K1.rays() ], lattice=K1.lattice())
489 sage: K1.lyapunov_rank() == K2.lyapunov_rank()
494 sage: K1 = random_cone(max_ambient_dim=8,
495 ....: strictly_convex=False,
497 sage: A = random_matrix(QQ, K1.lattice_dim(), algorithm='unimodular')
498 sage: K2 = Cone( [ A*r for r in K1.rays() ], lattice=K1.lattice())
499 sage: K1.lyapunov_rank() == K2.lyapunov_rank()
502 The Lyapunov rank of a dual cone should be the same as the original
503 cone. Check all combinations of parameters::
505 sage: set_random_seed()
506 sage: K = random_cone(max_ambient_dim=8,
507 ....: strictly_convex=False,
509 sage: K.lyapunov_rank() == K.dual().lyapunov_rank()
514 sage: set_random_seed()
515 sage: K = random_cone(max_ambient_dim=8,
516 ....: strictly_convex=False,
518 sage: K.lyapunov_rank() == K.dual().lyapunov_rank()
523 sage: set_random_seed()
524 sage: K = random_cone(max_ambient_dim=8,
525 ....: strictly_convex=True,
527 sage: K.lyapunov_rank() == K.dual().lyapunov_rank()
532 sage: set_random_seed()
533 sage: K = random_cone(max_ambient_dim=8,
534 ....: strictly_convex=True,
536 sage: K.lyapunov_rank() == K.dual().lyapunov_rank()
539 The Lyapunov rank of a cone ``K`` is the dimension of
540 ``K.lyapunov_like_basis()``. Check all combinations of parameters::
542 sage: set_random_seed()
543 sage: K = random_cone(max_ambient_dim=8,
544 ....: strictly_convex=True,
546 sage: K.lyapunov_rank() == len(K.lyapunov_like_basis())
551 sage: set_random_seed()
552 sage: K = random_cone(max_ambient_dim=8,
553 ....: strictly_convex=True,
555 sage: K.lyapunov_rank() == len(K.lyapunov_like_basis())
560 sage: set_random_seed()
561 sage: K = random_cone(max_ambient_dim=8,
562 ....: strictly_convex=False,
564 sage: K.lyapunov_rank() == len(K.lyapunov_like_basis())
569 sage: set_random_seed()
570 sage: K = random_cone(max_ambient_dim=8,
571 ....: strictly_convex=False,
573 sage: K.lyapunov_rank() == len(K.lyapunov_like_basis())