# The double-import is needed to get the underscore methods.
from mjo.cone.cone import *
-from mjo.cone.cone import _basically_the_same, _rho
+
+
+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 _rho.
+# 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 _rho according to our paper (to obtain our main result). Test all
-four parameter combinations::
+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 = _rho(K)
- sage: K_SP = _rho(K_S.dual()).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 = _rho(K_S, K_S.dual())
+ 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 = _rho(K)
- sage: K_SP = _rho(K_S.dual()).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 = _rho(K_S, K_S.dual())
+ 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 = _rho(K)
- sage: K_SP = _rho(K_S.dual()).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 = _rho(K_S, K_S.dual())
+ 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: K = random_cone(max_ambient_dim = 8,
....: strictly_convex=True,
....: solid=True)
- sage: K_S = _rho(K)
- sage: K_SP = _rho(K_S.dual()).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 = _rho(K_S, K_S.dual())
+ 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 = _rho(K, J).dual()
- sage: K_star_W = _rho(K.dual(), J)
- 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
::
....: solid=True,
....: strictly_convex=False)
sage: K = Cone(random_sublist(J.rays(), 0.5), lattice=J.lattice())
- sage: K_W_star = _rho(K, J).dual()
- sage: K_star_W = _rho(K.dual(), J)
- 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
::
....: solid=False,
....: strictly_convex=True)
sage: K = Cone(random_sublist(J.rays(), 0.5), lattice=J.lattice())
- sage: K_W_star = _rho(K, J).dual()
- sage: K_star_W = _rho(K.dual(), J)
- 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
::
....: solid=True,
....: strictly_convex=True)
sage: K = Cone(random_sublist(J.rays(), 0.5), lattice=J.lattice())
- sage: K_W_star = _rho(K, J).dual()
- sage: K_star_W = _rho(K.dual(), J)
- 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
"""
....: 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
::
....: 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
::
....: 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
::
....: 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
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
::
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
::
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
::
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 ``LL(K)``. Check
-all combinations of parameters::
+The Lyapunov rank of a cone ``K`` is the dimension of
+``K.lyapunov_like_basis()``. Check all combinations of parameters::
sage: set_random_seed()
sage: K = random_cone(max_ambient_dim=8,
....: strictly_convex=True,
....: solid=True)
- sage: lyapunov_rank(K) == len(LL(K))
+ sage: K.lyapunov_rank() == len(K.lyapunov_like_basis())
True
::
sage: K = random_cone(max_ambient_dim=8,
....: strictly_convex=True,
....: solid=False)
- sage: lyapunov_rank(K) == len(LL(K))
+ sage: K.lyapunov_rank() == len(K.lyapunov_like_basis())
True
::
sage: K = random_cone(max_ambient_dim=8,
....: strictly_convex=False,
....: solid=True)
- sage: lyapunov_rank(K) == len(LL(K))
+ sage: K.lyapunov_rank() == len(K.lyapunov_like_basis())
True
::
sage: K = random_cone(max_ambient_dim=8,
....: strictly_convex=False,
....: solid=False)
- sage: lyapunov_rank(K) == len(LL(K))
+ sage: K.lyapunov_rank() == len(K.lyapunov_like_basis())
True
"""
projects / sage.d.git / blobdiff