-# Sage doesn't load ~/.sage/init.sage during testing (sage -t), so we
-# have to explicitly mangle our sitedir here so that "mjo.cone"
-# resolves.
-from os.path import abspath
-from site import addsitedir
-addsitedir(abspath('../../'))
-
from sage.all import *
-
-def discrete_complementarity_set(K):
+def is_positive_on(L,K):
r"""
- Compute the discrete complementarity set of this cone.
+ Determine whether or not ``L`` is positive on ``K``.
- The complementarity set of this cone is the set of all orthogonal
- pairs `(x,s)` such that `x` is in this cone, and `s` is in its
- dual. The discrete complementarity set restricts `x` and `s` to be
- generators of their respective cones.
+ We say that ``L`` is positive on ``K`` if `L\left\lparen x
+ \right\rparen` belongs to ``K`` for all `x` in ``K``. This
+ property need only be checked for generators of ``K``.
- OUTPUT:
+ INPUT:
- A list of pairs `(x,s)` such that,
+ - ``L`` -- A linear transformation or matrix.
- * `x` is in this cone.
- * `x` is a generator of this cone.
- * `s` is in this cone's dual.
- * `s` is a generator of this cone's dual.
- * `x` and `s` are orthogonal.
+ - ``K`` -- A polyhedral closed convex cone.
- EXAMPLES:
+ OUTPUT:
- The discrete complementarity set of the nonnegative orthant consists
- of pairs of standard basis vectors::
+ ``True`` if it can be proven that ``L`` is positive on ``K``,
+ and ``False`` otherwise.
- sage: K = Cone([(1,0),(0,1)])
- sage: discrete_complementarity_set(K)
- [((1, 0), (0, 1)), ((0, 1), (1, 0))]
+ .. WARNING::
- If the cone consists of a single ray, the second components of the
- discrete complementarity set should generate the orthogonal
- complement of that ray::
+ If this function returns ``True``, then ``L`` is positive
+ on ``K``. However, if ``False`` is returned, that could mean one
+ of two things. The first is that ``L`` is definitely not
+ positive on ``K``. The second is more of an "I don't know"
+ answer, returned (for example) if we cannot prove that an inner
+ product is nonnegative.
- sage: K = Cone([(1,0)])
- sage: discrete_complementarity_set(K)
- [((1, 0), (0, 1)), ((1, 0), (0, -1))]
- sage: K = Cone([(1,0,0)])
- sage: discrete_complementarity_set(K)
- [((1, 0, 0), (0, 1, 0)),
- ((1, 0, 0), (0, -1, 0)),
- ((1, 0, 0), (0, 0, 1)),
- ((1, 0, 0), (0, 0, -1))]
+ EXAMPLES:
- When the cone is the entire space, its dual is the trivial cone, so
- the discrete complementarity set is empty::
+ The identity is always positive in a nontrivial space::
- sage: K = Cone([(1,0),(-1,0),(0,1),(0,-1)])
- sage: discrete_complementarity_set(K)
- []
+ sage: set_random_seed()
+ sage: K = random_cone(min_ambient_dim=1, max_ambient_dim=8)
+ sage: L = identity_matrix(K.lattice_dim())
+ sage: is_positive_on(L,K)
+ True
+
+ As is the "zero" transformation::
+
+ sage: K = random_cone(min_ambient_dim=1, max_ambient_dim=8)
+ sage: R = K.lattice().vector_space().base_ring()
+ sage: L = zero_matrix(R, K.lattice_dim())
+ sage: is_positive_on(L,K)
+ True
TESTS:
- The complementarity set of the dual can be obtained by switching the
- components of the complementarity set of the original cone::
+ Everything in ``K.positive_operators_gens()`` should be
+ positive on ``K``::
- sage: K1 = random_cone(max_dim=10, max_rays=10)
- sage: K2 = K1.dual()
- sage: expected = [(x,s) for (s,x) in discrete_complementarity_set(K2)]
- sage: actual = discrete_complementarity_set(K1)
- sage: actual == expected
+ sage: K = random_cone(min_ambient_dim=1, max_ambient_dim=6)
+ sage: all([ is_positive_on(L,K)
+ ....: for L in K.positive_operators_gens() ])
+ True
+ sage: all([ is_positive_on(L.change_ring(SR),K)
+ ....: for L in K.positive_operators_gens() ])
True
"""
- V = K.lattice().vector_space()
+ if L.base_ring().is_exact():
+ # This could potentially be extended to other types of ``K``...
+ return all([ L*x in K for x in K ])
+ elif L.base_ring() is SR:
+ # Fall back to inequality-checking when the entries of ``L``
+ # might be symbolic.
+ return all([ s*(L*x) >= 0 for x in K for s in K ])
+ else:
+ # The only inexact ring that we're willing to work with is SR,
+ # since it can still be exact when working with symbolic
+ # constants like pi and e.
+ raise ValueError('base ring of operator L is neither SR nor exact')
+
+
+def is_cross_positive_on(L,K):
+ r"""
+ Determine whether or not ``L`` is cross-positive on ``K``.
- # Convert the rays to vectors so that we can compute inner
- # products.
- xs = [V(x) for x in K.rays()]
- ss = [V(s) for s in K.dual().rays()]
+ We say that ``L`` is cross-positive on ``K`` if `\left\langle
+ L\left\lparenx\right\rparen,s\right\rangle \ge 0` for all pairs
+ `\left\langle x,s \right\rangle` in the complementarity set of
+ ``K``. This property need only be checked for generators of
+ ``K`` and its dual.
- return [(x,s) for x in xs for s in ss if x.inner_product(s) == 0]
+ INPUT:
+ - ``L`` -- A linear transformation or matrix.
-def lyapunov_rank(K):
- r"""
- Compute the Lyapunov (or bilinearity) rank of this cone.
+ - ``K`` -- A polyhedral closed convex cone.
- The Lyapunov rank of a cone can be thought of in (mainly) two ways:
+ OUTPUT:
- 1. The dimension of the Lie algebra of the automorphism group of the
- cone.
+ ``True`` if it can be proven that ``L`` is cross-positive on ``K``,
+ and ``False`` otherwise.
- 2. The dimension of the linear space of all Lyapunov-like
- transformations on the cone.
+ .. WARNING::
- INPUT:
+ If this function returns ``True``, then ``L`` is cross-positive
+ on ``K``. However, if ``False`` is returned, that could mean one
+ of two things. The first is that ``L`` is definitely not
+ cross-positive on ``K``. The second is more of an "I don't know"
+ answer, returned (for example) if we cannot prove that an inner
+ product is nonnegative.
- A closed, convex polyhedral cone.
+ EXAMPLES:
- OUTPUT:
+ The identity is always cross-positive in a nontrivial space::
- An integer representing the Lyapunov rank of the cone. If the
- dimension of the ambient vector space is `n`, then the Lyapunov rank
- will be between `1` and `n` inclusive; however a rank of `n-1` is
- not possible (see the first reference).
+ sage: set_random_seed()
+ sage: K = random_cone(min_ambient_dim=1, max_ambient_dim=8)
+ sage: L = identity_matrix(K.lattice_dim())
+ sage: is_cross_positive_on(L,K)
+ True
- .. note::
+ As is the "zero" transformation::
- In the references, the cones are always assumed to be proper. We
- do not impose this restriction.
+ sage: K = random_cone(min_ambient_dim=1, max_ambient_dim=8)
+ sage: R = K.lattice().vector_space().base_ring()
+ sage: L = zero_matrix(R, K.lattice_dim())
+ sage: is_cross_positive_on(L,K)
+ True
- .. seealso::
+ TESTS:
- :meth:`is_proper`
+ Everything in ``K.cross_positive_operators_gens()`` should be
+ cross-positive on ``K``::
- ALGORITHM:
+ sage: K = random_cone(min_ambient_dim=1, max_ambient_dim=6)
+ sage: all([ is_cross_positive_on(L,K)
+ ....: for L in K.cross_positive_operators_gens() ])
+ True
+ sage: all([ is_cross_positive_on(L.change_ring(SR),K)
+ ....: for L in K.cross_positive_operators_gens() ])
+ True
- The codimension formula from the second reference is used. We find
- all pairs `(x,s)` in the complementarity set of `K` such that `x`
- and `s` are rays of our cone. It is known that these vectors are
- sufficient to apply the codimension formula. Once we have all such
- pairs, we "brute force" the codimension formula by finding all
- linearly-independent `xs^{T}`.
+ """
+ if L.base_ring().is_exact() or L.base_ring() is SR:
+ return all([ s*(L*x) >= 0
+ for (x,s) in K.discrete_complementarity_set() ])
+ else:
+ # The only inexact ring that we're willing to work with is SR,
+ # since it can still be exact when working with symbolic
+ # constants like pi and e.
+ raise ValueError('base ring of operator L is neither SR nor exact')
- REFERENCES:
- 1. M.S. Gowda and J. Tao. On the bilinearity rank of a proper cone
- and Lyapunov-like transformations, Mathematical Programming, 147
- (2014) 155-170.
+def is_Z_on(L,K):
+ r"""
+ Determine whether or not ``L`` is a Z-operator on ``K``.
- 2. G. Rudolf, N. Noyan, D. Papp, and F. Alizadeh, Bilinear
- optimality constraints for the cone of positive polynomials,
- Mathematical Programming, Series B, 129 (2011) 5-31.
+ We say that ``L`` is a Z-operator on ``K`` if `\left\langle
+ L\left\lparenx\right\rparen,s\right\rangle \le 0` for all pairs
+ `\left\langle x,s \right\rangle` in the complementarity set of
+ ``K``. It is known that this property need only be
+ checked for generators of ``K`` and its dual.
- EXAMPLES:
+ A matrix is a Z-operator on ``K`` if and only if its negation is a
+ cross-positive operator on ``K``.
- The nonnegative orthant in `\mathbb{R}^{n}` always has rank `n`::
+ INPUT:
- sage: positives = Cone([(1,)])
- sage: lyapunov_rank(positives)
- 1
- sage: quadrant = Cone([(1,0), (0,1)])
- sage: lyapunov_rank(quadrant)
- 2
- sage: octant = Cone([(1,0,0), (0,1,0), (0,0,1)])
- sage: lyapunov_rank(octant)
- 3
+ - ``L`` -- A linear transformation or matrix.
- The `L^{3}_{1}` cone is known to have a Lyapunov rank of one::
+ - ``K`` -- A polyhedral closed convex cone.
- sage: L31 = Cone([(1,0,1), (0,-1,1), (-1,0,1), (0,1,1)])
- sage: lyapunov_rank(L31)
- 1
+ OUTPUT:
- Likewise for the `L^{3}_{\infty}` cone::
+ ``True`` if it can be proven that ``L`` is a Z-operator on ``K``,
+ and ``False`` otherwise.
- sage: L3infty = Cone([(0,1,1), (1,0,1), (0,-1,1), (-1,0,1)])
- sage: lyapunov_rank(L3infty)
- 1
+ .. WARNING::
- The Lyapunov rank should be additive on a product of cones::
+ If this function returns ``True``, then ``L`` is a Z-operator
+ on ``K``. However, if ``False`` is returned, that could mean one
+ of two things. The first is that ``L`` is definitely not
+ a Z-operator on ``K``. The second is more of an "I don't know"
+ answer, returned (for example) if we cannot prove that an inner
+ product is nonnegative.
- sage: L31 = Cone([(1,0,1), (0,-1,1), (-1,0,1), (0,1,1)])
- sage: octant = Cone([(1,0,0), (0,1,0), (0,0,1)])
- sage: K = L31.cartesian_product(octant)
- sage: lyapunov_rank(K) == lyapunov_rank(L31) + lyapunov_rank(octant)
- True
+ EXAMPLES:
- Two isomorphic cones should have the same Lyapunov rank. The cone
- ``K`` in the following example is isomorphic to the nonnegative
- octant in `\mathbb{R}^{3}`::
+ The identity is always a Z-operator in a nontrivial space::
- sage: K = Cone([(1,2,3), (-1,1,0), (1,0,6)])
- sage: lyapunov_rank(K)
- 3
+ sage: set_random_seed()
+ sage: K = random_cone(min_ambient_dim=1, max_ambient_dim=8)
+ sage: L = identity_matrix(K.lattice_dim())
+ sage: is_Z_on(L,K)
+ True
- The dual cone `K^{*}` of ``K`` should have the same Lyapunov rank as ``K``
- itself::
+ As is the "zero" transformation::
- sage: K = Cone([(2,2,4), (-1,9,0), (2,0,6)])
- sage: lyapunov_rank(K) == lyapunov_rank(K.dual())
+ sage: K = random_cone(min_ambient_dim=1, max_ambient_dim=8)
+ sage: R = K.lattice().vector_space().base_ring()
+ sage: L = zero_matrix(R, K.lattice_dim())
+ sage: is_Z_on(L,K)
True
TESTS:
- The Lyapunov rank should be additive on a product of cones::
+ Everything in ``K.Z_operators_gens()`` should be a Z-operator
+ on ``K``::
- sage: K1 = random_cone(max_dim=10, max_rays=10)
- sage: K2 = random_cone(max_dim=10, max_rays=10)
- sage: K = K1.cartesian_product(K2)
- sage: lyapunov_rank(K) == lyapunov_rank(K1) + lyapunov_rank(K2)
+ sage: K = random_cone(min_ambient_dim=1, max_ambient_dim=6)
+ sage: all([ is_Z_on(L,K)
+ ....: for L in K.Z_operators_gens() ])
True
-
- The dual cone `K^{*}` of ``K`` should have the same Lyapunov rank as ``K``
- itself::
-
- sage: K = random_cone(max_dim=10, max_rays=10)
- sage: lyapunov_rank(K) == lyapunov_rank(K.dual())
+ sage: all([ is_Z_on(L.change_ring(SR),K)
+ ....: for L in K.Z_operators_gens() ])
True
"""
- V = K.lattice().vector_space()
+ return is_cross_positive_on(-L,K)
+
+
+def is_lyapunov_like_on(L,K):
+ r"""
+ Determine whether or not ``L`` is Lyapunov-like on ``K``.
+
+ We say that ``L`` is Lyapunov-like on ``K`` if `\left\langle
+ L\left\lparenx\right\rparen,s\right\rangle = 0` for all pairs
+ `\left\langle x,s \right\rangle` in the complementarity set of
+ ``K``. This property need only be checked for generators of
+ ``K`` and its dual.
+
+ INPUT:
+
+ - ``L`` -- A linear transformation or matrix.
+
+ - ``K`` -- A polyhedral closed convex cone.
+
+ OUTPUT:
+
+ ``True`` if it can be proven that ``L`` is Lyapunov-like on ``K``,
+ and ``False`` otherwise.
+
+ .. WARNING::
+
+ If this function returns ``True``, then ``L`` is Lyapunov-like
+ on ``K``. However, if ``False`` is returned, that could mean one
+ of two things. The first is that ``L`` is definitely not
+ Lyapunov-like on ``K``. The second is more of an "I don't know"
+ answer, returned (for example) if we cannot prove that an inner
+ product is zero.
+
+ EXAMPLES:
+
+ The identity is always Lyapunov-like in a nontrivial space::
- C_of_K = discrete_complementarity_set(K)
+ sage: set_random_seed()
+ sage: K = random_cone(min_ambient_dim=1, max_ambient_dim=8)
+ sage: L = identity_matrix(K.lattice_dim())
+ sage: is_lyapunov_like_on(L,K)
+ True
- matrices = [x.tensor_product(s) for (x,s) in C_of_K]
+ As is the "zero" transformation::
- # Sage doesn't think matrices are vectors, so we have to convert
- # our matrices to vectors explicitly before we can figure out how
- # many are linearly-indepenedent.
- #
- # The space W has the same base ring as V, but dimension
- # dim(V)^2. So it has the same dimension as the space of linear
- # transformations on V. In other words, it's just the right size
- # to create an isomorphism between it and our matrices.
- W = VectorSpace(V.base_ring(), V.dimension()**2)
+ sage: K = random_cone(min_ambient_dim=1, max_ambient_dim=8)
+ sage: R = K.lattice().vector_space().base_ring()
+ sage: L = zero_matrix(R, K.lattice_dim())
+ sage: is_lyapunov_like_on(L,K)
+ True
- def phi(m):
- r"""
- Convert a matrix to a vector isomorphically.
- """
- return W(m.list())
+ TESTS:
- vectors = [phi(m) for m in matrices]
+ Everything in ``K.lyapunov_like_basis()`` should be Lyapunov-like
+ on ``K``::
- return (W.dimension() - W.span(vectors).rank())
+ sage: K = random_cone(min_ambient_dim=1, max_ambient_dim=6)
+ sage: all([ is_lyapunov_like_on(L,K)
+ ....: for L in K.lyapunov_like_basis() ])
+ True
+ sage: all([ is_lyapunov_like_on(L.change_ring(SR),K)
+ ....: for L in K.lyapunov_like_basis() ])
+ True
+
+ """
+ if L.base_ring().is_exact() or L.base_ring() is SR:
+ # The "fast method" of creating a vector space based on a
+ # ``lyapunov_like_basis`` is actually slower than this.
+ return all([ s*(L*x) == 0
+ for (x,s) in K.discrete_complementarity_set() ])
+ else:
+ # The only inexact ring that we're willing to work with is SR,
+ # since it can still be exact when working with symbolic
+ # constants like pi and e.
+ raise ValueError('base ring of operator L is neither SR nor exact')
+
+def LL_cone(K):
+ gens = K.lyapunov_like_basis()
+ L = ToricLattice(K.lattice_dim()**2)
+ return Cone([ g.list() for g in gens ], lattice=L, check=False)
+
+def Sigma_cone(K):
+ gens = K.cross_positive_operators_gens()
+ L = ToricLattice(K.lattice_dim()**2)
+ return Cone([ g.list() for g in gens ], lattice=L, check=False)
+
+def Z_cone(K):
+ gens = K.Z_operators_gens()
+ L = ToricLattice(K.lattice_dim()**2)
+ return Cone([ g.list() for g in gens ], lattice=L, check=False)
+
+def pi_cone(K1, K2=None):
+ if K2 is None:
+ K2 = K1
+ gens = K1.positive_operators_gens(K2)
+ L = ToricLattice(K1.lattice_dim()*K2.lattice_dim())
+ return Cone([ g.list() for g in gens ], lattice=L, check=False)