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

diff --git a/mjo/cone/tests.py b/mjo/cone/tests.py
index 1758f8b..5a910f0 100644
--- a/mjo/cone/tests.py
+++ b/mjo/cone/tests.py
@@ -15,54 +15,346 @@ from sage.all import *
 
 # The double-import is needed to get the underscore methods.
 from mjo.cone.cone import *
-from mjo.cone.cone import _basically_the_same, _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"""
+    Test whether or not ``K1`` and ``K2`` look linearly isomorphic.
+
+    This is a hack to get around the fact that it's difficult to tell
+    when two cones are linearly isomorphic. Instead, we check a list of
+    properties that should be preserved under linear isomorphism.
+
+    OUTPUT:
+
+    ``True`` if ``K1`` and ``K2`` look isomorphic, or ``False``
+    if we can prove that they are not isomorphic.
+
+    EXAMPLES:
+
+    Any proper cone with three generators in `\mathbb{R}^{3}` is
+    isomorphic to the nonnegative orthant::
+
+        sage: K1 = Cone([(1,0,0), (0,1,0), (0,0,1)])
+        sage: K2 = Cone([(1,2,3), (3, 18, 4), (66, 51, 0)])
+        sage: _look_isomorphic(K1, K2)
+        True
+
+    Negating a cone gives you an isomorphic cone::
+
+        sage: K = Cone([(0,2,-5), (-6, 2, 4), (0, 51, 0)])
+        sage: _look_isomorphic(K, -K)
+        True
+
+    TESTS:
+
+    Any cone is isomorphic to itself::
+
+        sage: K = random_cone(max_ambient_dim = 8)
+        sage: _look_isomorphic(K, K)
+        True
+
+    After applying an invertible matrix to the rows of a cone, the
+    result should is isomorphic to the cone we started with::
+
+        sage: K1 = random_cone(max_ambient_dim = 8)
+        sage: A = random_matrix(QQ, K1.lattice_dim(), algorithm='unimodular')
+        sage: K2 = Cone( [ A*r for r in K1.rays() ], lattice=K1.lattice())
+        sage: _look_isomorphic(K1, K2)
+        True
+
+    """
+    if K1.lattice_dim() != K2.lattice_dim():
+        return False
+
+    if K1.nrays() != K2.nrays():
+        return False
+
+    if K1.dim() != K2.dim():
+        return False
+
+    if K1.lineality() != K2.lineality():
+        return False
+
+    if K1.is_solid() != K2.is_solid():
+        return False
+
+    if K1.is_strictly_convex() != K2.is_strictly_convex():
+        return False
+
+    if len(K1.lyapunov_like_basis()) != len(K2.lyapunov_like_basis()):
+        return False
+
+    C_of_K1 = K1.discrete_complementarity_set()
+    C_of_K2 = K2.discrete_complementarity_set()
+    if len(C_of_K1) != len(C_of_K2):
+        return False
+
+    if len(K1.facets()) != len(K2.facets()):
+        return False
+
+    return True
+
+
 """
-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
 
 ::
 
@@ -70,28 +362,37 @@ 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: _basically_the_same(K_W_star, K_star_W)
+    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
 
 ::
@@ -101,9 +402,9 @@ 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: _basically_the_same(K_W_star, K_star_W)
+    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
 
 ::
@@ -113,9 +414,9 @@ 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: _basically_the_same(K_W_star, K_star_W)
+    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
 
 ::
@@ -125,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: _basically_the_same(K_W_star, K_star_W)
+    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
 """
 
 
@@ -146,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
 
 ::
@@ -156,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
 
 ::
@@ -166,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
 
 ::
@@ -176,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
@@ -186,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
 
 ::
@@ -195,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
 
 ::
@@ -204,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
 
 ::
@@ -213,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
@@ -223,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
 
 ::
@@ -232,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
 
 ::
@@ -241,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
 
 ::
@@ -250,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
 
 """