X-Git-Url: http://gitweb.michael.orlitzky.com/?a=blobdiff_plain;f=mjo%2Fcone%2Ftests.py;h=5a910f0e255e4feefd485fdc5514f28576b1e8ee;hb=fdc03da648dd989527ff4c12ccce04c990869e3b;hp=550beb38744f1d399f492aa5d3ef2f7fcc23febb;hpb=805b61b3751065f9c7d36280ce22d961d207553c;p=sage.d.git

diff --git a/mjo/cone/tests.py b/mjo/cone/tests.py
index 550beb3..5a910f0 100644
--- a/mjo/cone/tests.py
+++ b/mjo/cone/tests.py
@@ -15,10 +15,193 @@ from sage.all import *
 
 # The double-import is needed to get the underscore methods.
 from mjo.cone.cone import *
-from mjo.cone.cone import _restrict_to_space
+
+
+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"""
@@ -100,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 = _restrict_to_space(K, K.span())
-    sage: K_SP = _restrict_to_space(K_S.dual(), K_S.dual().span()).dual()
+    sage: K_S = _restrict_to_subspace(K, K.span())
+    sage: K_S2 = K.solid_restriction()
+    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 = _restrict_to_space(K_S, 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 = _restrict_to_space(K, K.span())
-    sage: K_SP = _restrict_to_space(K_S.dual(), K_S.dual().span()).dual()
+    ....:                 strictly_convex=False,
+    ....:                 solid=True)
+    sage: K_S = _restrict_to_subspace(K, K.span())
+    sage: K_S2 = K.solid_restriction()
+    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 = _restrict_to_space(K_S, 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 = _restrict_to_space(K, K.span())
-    sage: K_SP = _restrict_to_space(K_S.dual(), K_S.dual().span()).dual()
+    ....:                 strictly_convex=True,
+    ....:                 solid=False)
+    sage: K_S = _restrict_to_subspace(K, K.span())
+    sage: K_S2 = K.solid_restriction()
+    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 = _restrict_to_space(K_S, 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
 
 ::
 
@@ -149,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 = _restrict_to_space(K, K.span())
-    sage: K_SP = _restrict_to_space(K_S.dual(), K_S.dual().span()).dual()
+    sage: K_S = _restrict_to_subspace(K, K.span())
+    sage: K_S2 = K.solid_restriction()
+    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 = _restrict_to_space(K_S, 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 = _restrict_to_space(K, J.span()).dual()
-    sage: K_star_W = _restrict_to_space(K.dual(), 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
 
@@ -180,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 = _restrict_to_space(K, J.span()).dual()
-    sage: K_star_W = _restrict_to_space(K.dual(), 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
 
@@ -192,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 = _restrict_to_space(K, J.span()).dual()
-    sage: K_star_W = _restrict_to_space(K.dual(), 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
 
@@ -204,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 = _restrict_to_space(K, J.span()).dual()
-    sage: K_star_W = _restrict_to_space(K.dual(), 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_restriction()`` 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_restriction()
+    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
 """
 
 
@@ -225,7 +466,7 @@ combinations of parameters::
     ....:                  solid=True)
     sage: A = random_matrix(QQ, K1.lattice_dim(), algorithm='unimodular')
     sage: K2 = Cone( [ A*r for r in K1.rays() ], lattice=K1.lattice())
-    sage: lyapunov_rank(K1) == lyapunov_rank(K2)
+    sage: K1.lyapunov_rank() == K2.lyapunov_rank()
     True
 
 ::
@@ -235,7 +476,7 @@ combinations of parameters::
     ....:                  solid=False)
     sage: A = random_matrix(QQ, K1.lattice_dim(), algorithm='unimodular')
     sage: K2 = Cone( [ A*r for r in K1.rays() ], lattice=K1.lattice())
-    sage: lyapunov_rank(K1) == lyapunov_rank(K2)
+    sage: K1.lyapunov_rank() == K2.lyapunov_rank()
     True
 
 ::
@@ -245,7 +486,7 @@ combinations of parameters::
     ....:                  solid=True)
     sage: A = random_matrix(QQ, K1.lattice_dim(), algorithm='unimodular')
     sage: K2 = Cone( [ A*r for r in K1.rays() ], lattice=K1.lattice())
-    sage: lyapunov_rank(K1) == lyapunov_rank(K2)
+    sage: K1.lyapunov_rank() == K2.lyapunov_rank()
     True
 
 ::
@@ -255,7 +496,7 @@ combinations of parameters::
     ....:                  solid=False)
     sage: A = random_matrix(QQ, K1.lattice_dim(), algorithm='unimodular')
     sage: K2 = Cone( [ A*r for r in K1.rays() ], lattice=K1.lattice())
-    sage: lyapunov_rank(K1) == lyapunov_rank(K2)
+    sage: K1.lyapunov_rank() == K2.lyapunov_rank()
     True
 
 The Lyapunov rank of a dual cone should be the same as the original
@@ -265,7 +506,7 @@ cone. Check all combinations of parameters::
     sage: K = random_cone(max_ambient_dim=8,
     ....:                 strictly_convex=False,
     ....:                 solid=False)
-    sage: lyapunov_rank(K) == lyapunov_rank(K.dual())
+    sage: K.lyapunov_rank() == K.dual().lyapunov_rank()
     True
 
 ::
@@ -274,7 +515,7 @@ cone. Check all combinations of parameters::
     sage: K = random_cone(max_ambient_dim=8,
     ....:                 strictly_convex=False,
     ....:                 solid=True)
-    sage: lyapunov_rank(K) == lyapunov_rank(K.dual())
+    sage: K.lyapunov_rank() == K.dual().lyapunov_rank()
     True
 
 ::
@@ -283,7 +524,7 @@ cone. Check all combinations of parameters::
     sage: K = random_cone(max_ambient_dim=8,
     ....:                 strictly_convex=True,
     ....:                 solid=False)
-    sage: lyapunov_rank(K) == lyapunov_rank(K.dual())
+    sage: K.lyapunov_rank() == K.dual().lyapunov_rank()
     True
 
 ::
@@ -292,7 +533,7 @@ cone. Check all combinations of parameters::
     sage: K = random_cone(max_ambient_dim=8,
     ....:                 strictly_convex=True,
     ....:                 solid=True)
-    sage: lyapunov_rank(K) == lyapunov_rank(K.dual())
+    sage: K.lyapunov_rank() == K.dual().lyapunov_rank()
     True
 
 The Lyapunov rank of a cone ``K`` is the dimension of
@@ -302,7 +543,7 @@ The Lyapunov rank of a cone ``K`` is the dimension of
     sage: K = random_cone(max_ambient_dim=8,
     ....:                 strictly_convex=True,
     ....:                 solid=True)
-    sage: lyapunov_rank(K) == len(K.lyapunov_like_basis())
+    sage: K.lyapunov_rank() == len(K.lyapunov_like_basis())
     True
 
 ::
@@ -311,7 +552,7 @@ The Lyapunov rank of a cone ``K`` is the dimension of
     sage: K = random_cone(max_ambient_dim=8,
     ....:                 strictly_convex=True,
     ....:                 solid=False)
-    sage: lyapunov_rank(K) == len(K.lyapunov_like_basis())
+    sage: K.lyapunov_rank() == len(K.lyapunov_like_basis())
     True
 
 ::
@@ -320,7 +561,7 @@ The Lyapunov rank of a cone ``K`` is the dimension of
     sage: K = random_cone(max_ambient_dim=8,
     ....:                 strictly_convex=False,
     ....:                 solid=True)
-    sage: lyapunov_rank(K) == len(K.lyapunov_like_basis())
+    sage: K.lyapunov_rank() == len(K.lyapunov_like_basis())
     True
 
 ::
@@ -329,7 +570,7 @@ The Lyapunov rank of a cone ``K`` is the dimension of
     sage: K = random_cone(max_ambient_dim=8,
     ....:                 strictly_convex=False,
     ....:                 solid=False)
-    sage: lyapunov_rank(K) == len(K.lyapunov_like_basis())
+    sage: K.lyapunov_rank() == len(K.lyapunov_like_basis())
     True
 
 """