From 9aea9a588808849ed2f01d0a2887fa9dffca9f36 Mon Sep 17 00:00:00 2001 From: Michael Orlitzky Date: Sun, 12 Feb 2017 16:17:41 -0500 Subject: [PATCH] Add positive/Z tests and update code for upstream changes. --- mjo/cone/cone.py | 213 +++++++++++++++++++++++++++++++++++++++-------- 1 file changed, 178 insertions(+), 35 deletions(-) diff --git a/mjo/cone/cone.py b/mjo/cone/cone.py index be05f5e..a7c16a5 100644 --- a/mjo/cone/cone.py +++ b/mjo/cone/cone.py @@ -1,14 +1,88 @@ from sage.all import * -def is_cross_positive(L,K): +def is_positive_on(L,K): + r""" + Determine whether or not ``L`` is positive on ``K``. + + 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``. + + INPUT: + + - ``L`` -- A linear transformation or matrix. + + - ``K`` -- A polyhedral closed convex cone. + + OUTPUT: + + ``True`` if it can be proven that ``L`` is positive on ``K``, + and ``False`` otherwise. + + .. WARNING:: + + 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. + + EXAMPLES: + + The identity is always positive in a nontrivial space:: + + 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: + + Everything in ``K.positive_operators_gens()`` should be + positive on ``K``:: + + 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 + + """ + 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``. We say that ``L`` is cross-positive on ``K`` if `\left\langle - L\left\lparenx\right\rparen,s\right\rangle >= 0` for all pairs + 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``. It is known that this property need only be - checked for generators of ``K`` and its dual. + ``K``. This property need only be checked for generators of + ``K`` and its dual. INPUT: @@ -37,7 +111,7 @@ def is_cross_positive(L,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_cross_positive(L,K) + sage: is_cross_positive_on(L,K) True As is the "zero" transformation:: @@ -45,15 +119,20 @@ def is_cross_positive(L,K): 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(L,K) + sage: is_cross_positive_on(L,K) True - Everything in ``K.cross_positive_operator_gens()`` should be - cross-positive on ``K``:: + TESTS: + + Everything in ``K.cross_positive_operators_gens()`` should be + cross-positive on ``K``:: sage: K = random_cone(min_ambient_dim=1, max_ambient_dim=6) - sage: all([ is_cross_positive(L,K) - ....: for L in K.cross_positive_operator_gens() ]) + 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 """ @@ -67,21 +146,83 @@ def is_cross_positive(L,K): raise ValueError('base ring of operator L is neither SR nor exact') -def is_lyapunov_like(L,K): +def is_Z_on(L,K): + r""" + Determine whether or not ``L`` is a Z-operator on ``K``. + + 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. + + A matrix is a Z-operator on ``K`` if and only if its negation is a + cross-positive operator on ``K``. + + INPUT: + + - ``L`` -- A linear transformation or matrix. + + - ``K`` -- A polyhedral closed convex cone. + + OUTPUT: + + ``True`` if it can be proven that ``L`` is a Z-operator on ``K``, + and ``False`` otherwise. + + .. WARNING:: + + 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. + + EXAMPLES: + + The identity is always a Z-operator in a nontrivial space:: + + 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 + + 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_Z_on(L,K) + True + + TESTS: + + Everything in ``K.Z_operators_gens()`` should be a Z-operator + on ``K``:: + + 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 + sage: all([ is_Z_on(L.change_ring(SR),K) + ....: for L in K.Z_operators_gens() ]) + True + + """ + 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``. It is known [Orlitzky]_ that this property need only be - checked for generators of ``K`` and its dual. - - There are faster ways of checking this property. For example, we - could compute a `lyapunov_like_basis` of the cone, and then test - whether or not the given matrix is contained in the span of that - basis. The value of this function is that it works on symbolic - matrices. + ``K``. This property need only be checked for generators of + ``K`` and its dual. INPUT: @@ -103,11 +244,6 @@ def is_lyapunov_like(L,K): answer, returned (for example) if we cannot prove that an inner product is zero. - REFERENCES: - - M. Orlitzky. The Lyapunov rank of an improper cone. - http://www.optimization-online.org/DB_HTML/2015/10/5135.html - EXAMPLES: The identity is always Lyapunov-like in a nontrivial space:: @@ -115,7 +251,7 @@ def is_lyapunov_like(L,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(L,K) + sage: is_lyapunov_like_on(L,K) True As is the "zero" transformation:: @@ -123,21 +259,28 @@ def is_lyapunov_like(L,K): 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(L,K) + sage: is_lyapunov_like_on(L,K) True - Everything in ``K.lyapunov_like_basis()`` should be Lyapunov-like - on ``K``:: + TESTS: + + Everything in ``K.lyapunov_like_basis()`` should be Lyapunov-like + on ``K``:: sage: K = random_cone(min_ambient_dim=1, max_ambient_dim=6) - sage: all([ is_lyapunov_like(L,K) for L in K.lyapunov_like_basis() ]) + 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: - V = VectorSpace(K.lattice().base_field(), K.lattice_dim()**2) - LL_of_K = V.span([ V(m.list()) for m in K.lyapunov_like_basis() ]) - return V(L.list()) in LL_of_K + # 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 @@ -150,18 +293,18 @@ def LL_cone(K): return Cone([ g.list() for g in gens ], lattice=L, check=False) def Sigma_cone(K): - gens = K.cross_positive_operator_gens() + 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_operator_gens() + 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_operator_gens(K2) + 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) -- 2.43.2