From f23aede43c0ff4fed3b33f3c8723e7ff7bd79953 Mon Sep 17 00:00:00 2001 From: Michael Orlitzky Date: Sat, 14 Nov 2015 19:03:29 -0500 Subject: [PATCH] Add restrict_to_subspace function and use it to test the sage lyapunov_rank(). --- mjo/cone/tests.py | 296 +++++++++++++++++++++++++++++++++++++++++----- 1 file changed, 269 insertions(+), 27 deletions(-) diff --git a/mjo/cone/tests.py b/mjo/cone/tests.py index 816215c..33e5687 100644 --- a/mjo/cone/tests.py +++ b/mjo/cone/tests.py @@ -16,8 +16,192 @@ from sage.all import * # The double-import is needed to get the underscore methods. from mjo.cone.cone import * + +def _restrict_to_subspace(K, W): + r""" + Restrict ``K`` (up to linear isomorphism) to a vector subspace. + + This operation not only restricts the cone to a subspace of its + ambient space, but also represents the rays of the cone in a new + (smaller) lattice corresponding to the subspace. The resulting + cone will be linearly isomorphic (but not equal) to the + desired restriction, since it has likely undergone a change of + basis. + + To explain the difficulty, consider the cone ``K = + Cone([(1,1,1)])`` having a single ray. The span of ``K`` is a + one-dimensional subspace containing ``K``, yet we have no way to + perform operations like "dual of" in the subspace. To represent + ``K`` in the space ``K.span()``, we must perform a change of basis + and write its sole ray as ``(1,0,0)``. Now the restricted + ``Cone([(1,)])`` is linearly isomorphic (but of course not equal) to + ``K`` interpreted as living in ``K.span()``. + + INPUT: + + - ``K`` -- The cone to restrict. + + - ``W`` -- The subspace into which ``K`` will be restricted. + + OUTPUT: + + A new cone in a sublattice corresponding to ``W``. + + REFERENCES: + + M. Orlitzky. The Lyapunov rank of an improper cone. + http://www.optimization-online.org/DB_HTML/2015/10/5135.html + + EXAMPLES: + + Restricting a solid cone to its own span returns a cone linearly + isomorphic to the original:: + + sage: K = Cone([(1,2,3),(-1,1,0),(9,0,-2)]) + sage: K.is_solid() + True + sage: _restrict_to_subspace(K, K.span()).rays() + N(-1, 1, 0), + N( 1, 0, 0), + N( 9, -6, -1) + in 3-d lattice N + + A single ray restricted to its own span has the same + representation regardless of the ambient space:: + + sage: K = Cone([(1,0)]) + sage: K_S = _restrict_to_subspace(K, K.span()).rays() + sage: K_S + N(1) + in 1-d lattice N + sage: K = Cone([(1,1,1)]) + sage: K_S = _restrict_to_subspace(K, K.span()).rays() + sage: K_S + N(1) + in 1-d lattice N + + Restricting to a trivial space gives the trivial cone:: + + sage: K = Cone([(8,3,-1,0),(9,2,2,0),(-4,6,7,0)]) + sage: trivial_space = K.lattice().vector_space().span([]) + sage: _restrict_to_subspace(K, trivial_space) + 0-d cone in 0-d lattice N + + TESTS: + + Restricting a cone to its own span results in a solid cone:: + + sage: set_random_seed() + sage: K = random_cone(max_ambient_dim = 8) + sage: K_S = _restrict_to_subspace(K, K.span()) + sage: K_S.is_solid() + True + + Restricting a cone to its span should not affect the number of + rays in the cone:: + + sage: set_random_seed() + sage: K = random_cone(max_ambient_dim = 8) + sage: K_S = _restrict_to_subspace(K, K.span()) + sage: K.nrays() == K_S.nrays() + True + + Restricting a cone to its span should not affect its dimension:: + + sage: set_random_seed() + sage: K = random_cone(max_ambient_dim = 8) + sage: K_S = _restrict_to_subspace(K, K.span()) + sage: K.dim() == K_S.dim() + True + + Restricting a cone to its span should not affects its lineality:: + + sage: set_random_seed() + sage: K = random_cone(max_ambient_dim = 8) + sage: K_S = _restrict_to_subspace(K, K.span()) + sage: K.lineality() == K_S.lineality() + True + + Restricting a cone to its span should not affect the number of + facets it has:: + + sage: set_random_seed() + sage: K = random_cone(max_ambient_dim = 8) + sage: K_S = _restrict_to_subspace(K, K.span()) + sage: len(K.facets()) == len(K_S.facets()) + True + + Restricting a solid cone to its span is a linear isomorphism + and should not affect the dimension of its ambient space:: + + sage: set_random_seed() + sage: K = random_cone(max_ambient_dim = 8, solid = True) + sage: K_S = _restrict_to_subspace(K, K.span()) + sage: K.lattice_dim() == K_S.lattice_dim() + True + + Restricting a solid cone to its span is a linear isomorphism + that establishes a one-to-one correspondence of discrete + complementarity sets:: + + sage: set_random_seed() + sage: K = random_cone(max_ambient_dim = 8, solid = True) + sage: K_S = _restrict_to_subspace(K, K.span()) + sage: dcs1 = K.discrete_complementarity_set() + sage: dcs2 = K_S.discrete_complementarity_set() + sage: len(dcs1) == len(dcs2) + True + + Restricting a solid cone to its span is a linear isomorphism + under which Lyapunov rank (the length of a Lyapunov-like basis) + is invariant:: + + sage: set_random_seed() + sage: K = random_cone(max_ambient_dim = 8, solid = True) + sage: K_S = _restrict_to_subspace(K, K.span()) + sage: LL1 = K.lyapunov_like_basis() + sage: LL2 = K_S.lyapunov_like_basis() + sage: len(LL1) == len(LL2) + True + + If we restrict a cone to a subspace of its span, the resulting + cone should have the same dimension as the subspace:: + + sage: set_random_seed() + sage: K = random_cone(max_ambient_dim = 8) + sage: W_basis = random_sublist(K.rays(), 0.5) + sage: W = K.lattice().vector_space().span(W_basis) + sage: K_W = _restrict_to_subspace(K,W) + sage: K_W.lattice_dim() == W.dimension() + True + + Through a series of restrictions, any closed convex cone can be + reduced to a cartesian product with a proper factor [Orlitzky]_:: + + sage: set_random_seed() + sage: K = random_cone(max_ambient_dim = 8) + sage: K_S = _restrict_to_subspace(K, K.span()) + sage: P = K_S.dual().span() + sage: K_SP = _restrict_to_subspace(K_S, P) + sage: K_SP.is_proper() + True + """ + # We want to intersect this cone with ``W``. We can do that via + # cone intersection, so we first turn the space ``W`` into a cone. + W_rays = W.basis() + [ -b for b in W.basis() ] + W_cone = Cone(W_rays, lattice=K.lattice()) + K = K.intersection(W_cone) + + # Now every generator of ``K`` should belong to ``W``. + K_W_rays = [ W.coordinate_vector(r) for r in K.rays() ] + + L = ToricLattice(W.dimension()) + return Cone(K_W_rays, lattice=L) + + + # -# Tests for _restrict_to_space. +# Tests for _restrict_to_subspace. # def _look_isomorphic(K1, K2): r""" @@ -99,48 +283,78 @@ def _look_isomorphic(K1, K2): """ -Apply _restrict_to_space according to our paper (to obtain our main +Apply _restrict_to_subspace according to our paper (to obtain our main result). Test all four parameter combinations:: sage: set_random_seed() sage: K = random_cone(max_ambient_dim = 8, ....: strictly_convex=False, ....: solid=False) - sage: K_S = K._restrict_to_space(K.span()) - sage: K_SP = K_S.dual()._restrict_to_space(K_S.dual().span()).dual() + sage: K_S = _restrict_to_subspace(K, K.span()) + sage: K_S2 = K.solid_quotient() + sage: _look_isomorphic(K_S, K_S2) + True + sage: K_SP = _restrict_to_subspace(K_S.dual(), K_S.dual().span()).dual() + sage: K_SP2 = K_S.strict_quotient() sage: K_SP.is_proper() True - sage: K_SP = K_S._restrict_to_space(K_S.dual().span()) + sage: K_SP2.is_proper() + True + sage: _look_isomorphic(K_SP, K_SP2) + True + sage: K_SP = _restrict_to_subspace(K_S, K_S.dual().span()) sage: K_SP.is_proper() True + sage: _look_isomorphic(K_SP, K_SP2) + True :: sage: set_random_seed() sage: K = random_cone(max_ambient_dim = 8, - ....: strictly_convex=True, - ....: solid=False) - sage: K_S = K._restrict_to_space(K.span()) - sage: K_SP = K_S.dual()._restrict_to_space(K_S.dual().span()).dual() + ....: strictly_convex=False, + ....: solid=True) + sage: K_S = _restrict_to_subspace(K, K.span()) + sage: K_S2 = K.solid_quotient() + sage: _look_isomorphic(K_S, K_S2) + True + sage: K_SP = _restrict_to_subspace(K_S.dual(), K_S.dual().span()).dual() + sage: K_SP2 = K_S.strict_quotient() sage: K_SP.is_proper() True - sage: K_SP = K_S._restrict_to_space(K_S.dual().span()) + sage: K_SP2.is_proper() + True + sage: _look_isomorphic(K_SP, K_SP2) + True + sage: K_SP = _restrict_to_subspace(K_S, K_S.dual().span()) sage: K_SP.is_proper() True + sage: _look_isomorphic(K_SP, K_SP2) + True :: sage: set_random_seed() sage: K = random_cone(max_ambient_dim = 8, - ....: strictly_convex=False, - ....: solid=True) - sage: K_S = K._restrict_to_space(K.span()) - sage: K_SP = K_S.dual()._restrict_to_space(K_S.dual().span()).dual() + ....: strictly_convex=True, + ....: solid=False) + sage: K_S = _restrict_to_subspace(K, K.span()) + sage: K_S2 = K.solid_quotient() + sage: _look_isomorphic(K_S, K_S2) + True + sage: K_SP = _restrict_to_subspace(K_S.dual(), K_S.dual().span()).dual() + sage: K_SP2 = K_S.strict_quotient() sage: K_SP.is_proper() True - sage: K_SP = K_S._restrict_to_space(K_S.dual().span()) + sage: K_SP2.is_proper() + True + sage: _look_isomorphic(K_SP, K_SP2) + True + sage: K_SP = _restrict_to_subspace(K_S, K_S.dual().span()) sage: K_SP.is_proper() True + sage: _look_isomorphic(K_SP, K_SP2) + True :: @@ -148,27 +362,36 @@ result). Test all four parameter combinations:: sage: K = random_cone(max_ambient_dim = 8, ....: strictly_convex=True, ....: solid=True) - sage: K_S = K._restrict_to_space(K.span()) - sage: K_SP = K_S.dual()._restrict_to_space(K_S.dual().span()).dual() + sage: K_S = _restrict_to_subspace(K, K.span()) + sage: K_S2 = K.solid_quotient() + sage: _look_isomorphic(K_S, K_S2) + True + sage: K_SP = _restrict_to_subspace(K_S.dual(), K_S.dual().span()).dual() + sage: K_SP2 = K_S.strict_quotient() sage: K_SP.is_proper() True - sage: K_SP = K_S._restrict_to_space(K_S.dual().span()) + sage: K_SP2.is_proper() + True + sage: _look_isomorphic(K_SP, K_SP2) + True + sage: K_SP = _restrict_to_subspace(K_S, K_S.dual().span()) sage: K_SP.is_proper() True + sage: _look_isomorphic(K_SP, K_SP2) + True Test the proposition in our paper concerning the duals and restrictions. Generate a random cone, then create a subcone of it. The operation of dual-taking should then commute with rho. Test all parameter combinations:: - sage: set_random_seed() sage: J = random_cone(max_ambient_dim = 8, ....: solid=False, ....: strictly_convex=False) sage: K = Cone(random_sublist(J.rays(), 0.5), lattice=J.lattice()) - sage: K_W_star = K._restrict_to_space(J.span()).dual() - sage: K_star_W = K.dual()._restrict_to_space(J.span()) + sage: K_W_star = _restrict_to_subspace(K, J.span()).dual() + sage: K_star_W = _restrict_to_subspace(K.dual(), J.span()) sage: _look_isomorphic(K_W_star, K_star_W) True @@ -179,8 +402,8 @@ all parameter combinations:: ....: solid=True, ....: strictly_convex=False) sage: K = Cone(random_sublist(J.rays(), 0.5), lattice=J.lattice()) - sage: K_W_star = K._restrict_to_space(J.span()).dual() - sage: K_star_W = K.dual()._restrict_to_space(J.span()) + sage: K_W_star = _restrict_to_subspace(K, J.span()).dual() + sage: K_star_W = _restrict_to_subspace(K.dual(), J.span()) sage: _look_isomorphic(K_W_star, K_star_W) True @@ -191,8 +414,8 @@ all parameter combinations:: ....: solid=False, ....: strictly_convex=True) sage: K = Cone(random_sublist(J.rays(), 0.5), lattice=J.lattice()) - sage: K_W_star = K._restrict_to_space(J.span()).dual() - sage: K_star_W = K.dual()._restrict_to_space(J.span()) + sage: K_W_star = _restrict_to_subspace(K, J.span()).dual() + sage: K_star_W = _restrict_to_subspace(K.dual(), J.span()) sage: _look_isomorphic(K_W_star, K_star_W) True @@ -203,11 +426,30 @@ all parameter combinations:: ....: solid=True, ....: strictly_convex=True) sage: K = Cone(random_sublist(J.rays(), 0.5), lattice=J.lattice()) - sage: K_W_star = K._restrict_to_space(J.span()).dual() - sage: K_star_W = K.dual()._restrict_to_space(J.span()) + sage: K_W_star = _restrict_to_subspace(K, J.span()).dual() + sage: K_star_W = _restrict_to_subspace(K.dual(), J.span()) sage: _look_isomorphic(K_W_star, K_star_W) True +Ensure that ``__restrict_to_subspace(K, K.span())`` and +``K.solid_quotient()`` are actually equivalent:: + + sage: set_random_seed() + sage: K = random_cone(max_ambient_dim=8) + sage: K1 = _restrict_to_subspace(K, K.span()) + sage: K2 = K.solid_quotient() + sage: _look_isomorphic(K1,K2) + True + +Ensure that ``K.__restrict_to_subspace(K,K.dual().span())`` and +``strict_quotient`` are actually equivalent:: + + sage: set_random_seed() + sage: K = random_cone(max_ambient_dim=6) + sage: K1 = _restrict_to_subspace(K, K.dual().span()) + sage: K2 = K.strict_quotient() + sage: _look_isomorphic(K1,K2) + True """ -- 2.44.2