From ca8899446fdb5c212410beffac677143f0785f5f Mon Sep 17 00:00:00 2001 From: Michael Orlitzky Date: Fri, 9 Oct 2015 17:16:22 -0400 Subject: [PATCH] Begin cleaning up lyapunov_rank(). --- mjo/cone/cone.py | 82 ++++++++++++++++++++++-------------------------- 1 file changed, 38 insertions(+), 44 deletions(-) diff --git a/mjo/cone/cone.py b/mjo/cone/cone.py index cd835a7..c1b7ffd 100644 --- a/mjo/cone/cone.py +++ b/mjo/cone/cone.py @@ -213,26 +213,21 @@ def _restrict_to_space(K, W): def lyapunov_rank(K): r""" - Compute the Lyapunov rank (or bilinearity rank) of this cone. + Compute the Lyapunov rank of this cone. - The Lyapunov rank of a cone can be thought of in (mainly) two ways: - - 1. The dimension of the Lie algebra of the automorphism group of the - cone. - - 2. The dimension of the linear space of all Lyapunov-like - transformations on the cone. - - INPUT: - - A closed, convex polyhedral cone. + The Lyapunov rank of a cone is the dimension of the space of its + Lyapunov-like transformations -- that is, the length of a + :meth:`lyapunov_like_basis`. Equivalently, the Lyapunov rank is the + dimension of the Lie algebra of the automorphism group of the cone. OUTPUT: - 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 [Orlitzky/Gowda]_). + A nonnegative integer representing the Lyapunov rank of this cone. + + If the ambient space is trivial, the Lyapunov rank will be zero. + Otherwise, if the dimension of the ambient vector space is `n`, then + the resulting Lyapunov rank will be between `1` and `n` inclusive. A + Lyapunov rank of `n-1` is not possible [Orlitzky]_. ALGORITHM: @@ -245,21 +240,21 @@ def lyapunov_rank(K): REFERENCES: - .. [Gowda/Tao] M.S. Gowda and J. Tao. On the bilinearity rank of a proper - cone and Lyapunov-like transformations, Mathematical Programming, 147 - (2014) 155-170. + .. [Gowda/Tao] M.S. Gowda and J. Tao. On the bilinearity rank of + a proper cone and Lyapunov-like transformations. Mathematical + Programming, 147 (2014) 155-170. - .. [Orlitzky/Gowda] M. Orlitzky and M. S. Gowda. The Lyapunov Rank of an - Improper Cone. Work in-progress. + M. Orlitzky. The Lyapunov rank of an improper cone. + http://www.optimization-online.org/DB_HTML/2015/10/5135.html - .. [Rudolf et al.] 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. + 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. EXAMPLES: The nonnegative orthant in `\mathbb{R}^{n}` always has rank `n` - [Rudolf et al.]_:: + [Rudolf]_:: sage: positives = Cone([(1,)]) sage: lyapunov_rank(positives) @@ -272,7 +267,7 @@ def lyapunov_rank(K): 3 The full space `\mathbb{R}^{n}` has Lyapunov rank `n^{2}` - [Orlitzky/Gowda]_:: + [Orlitzky]_:: sage: R5 = VectorSpace(QQ, 5) sage: gs = R5.basis() + [ -r for r in R5.basis() ] @@ -281,20 +276,20 @@ def lyapunov_rank(K): 25 The `L^{3}_{1}` cone is known to have a Lyapunov rank of one - [Rudolf et al.]_:: + [Rudolf]_:: sage: L31 = Cone([(1,0,1), (0,-1,1), (-1,0,1), (0,1,1)]) sage: lyapunov_rank(L31) 1 - Likewise for the `L^{3}_{\infty}` cone [Rudolf et al.]_:: + Likewise for the `L^{3}_{\infty}` cone [Rudolf]_:: sage: L3infty = Cone([(0,1,1), (1,0,1), (0,-1,1), (-1,0,1)]) sage: lyapunov_rank(L3infty) 1 A single ray in `n` dimensions should have Lyapunov rank `n^{2} - n - + 1` [Orlitzky/Gowda]_:: + + 1` [Orlitzky]_:: sage: K = Cone([(1,0,0,0,0)]) sage: lyapunov_rank(K) @@ -303,7 +298,7 @@ def lyapunov_rank(K): 21 A subspace (of dimension `m`) in `n` dimensions should have a - Lyapunov rank of `n^{2} - m\left(n - m)` [Orlitzky/Gowda]_:: + Lyapunov rank of `n^{2} - m\left(n - m)` [Orlitzky]_:: sage: e1 = (1,0,0,0,0) sage: neg_e1 = (-1,0,0,0,0) @@ -317,7 +312,7 @@ def lyapunov_rank(K): 19 The Lyapunov rank should be additive on a product of proper cones - [Rudolf et al.]_:: + [Rudolf]_:: 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)]) @@ -325,7 +320,7 @@ def lyapunov_rank(K): sage: lyapunov_rank(K) == lyapunov_rank(L31) + lyapunov_rank(octant) True - Two isomorphic cones should have the same Lyapunov rank [Rudolf et al.]_. + Two isomorphic cones should have the same Lyapunov rank [Rudolf]_. The cone ``K`` in the following example is isomorphic to the nonnegative octant in `\mathbb{R}^{3}`:: @@ -334,7 +329,7 @@ def lyapunov_rank(K): 3 The dual cone `K^{*}` of ``K`` should have the same Lyapunov rank as ``K`` - itself [Rudolf et al.]_:: + itself [Rudolf]_:: sage: K = Cone([(2,2,4), (-1,9,0), (2,0,6)]) sage: lyapunov_rank(K) == lyapunov_rank(K.dual()) @@ -343,7 +338,7 @@ def lyapunov_rank(K): TESTS: The Lyapunov rank should be additive on a product of proper cones - [Rudolf et al.]_:: + [Rudolf]_:: sage: set_random_seed() sage: K1 = random_cone(max_ambient_dim=8, @@ -357,7 +352,7 @@ def lyapunov_rank(K): True The Lyapunov rank is invariant under a linear isomorphism - [Orlitzky/Gowda]_:: + [Orlitzky]_:: sage: K1 = random_cone(max_ambient_dim = 8) sage: A = random_matrix(QQ, K1.lattice_dim(), algorithm='unimodular') @@ -366,7 +361,7 @@ def lyapunov_rank(K): True The dual cone `K^{*}` of ``K`` should have the same Lyapunov rank as ``K`` - itself [Rudolf et al.]_:: + itself [Rudolf]_:: sage: set_random_seed() sage: K = random_cone(max_ambient_dim=8) @@ -390,7 +385,7 @@ def lyapunov_rank(K): sage: b == n-1 False - In fact [Orlitzky/Gowda]_, no closed convex polyhedral cone can have + In fact [Orlitzky]_, no closed convex polyhedral cone can have Lyapunov rank `n-1` in `n` dimensions:: sage: set_random_seed() @@ -401,7 +396,7 @@ def lyapunov_rank(K): False The calculation of the Lyapunov rank of an improper cone can be - reduced to that of a proper cone [Orlitzky/Gowda]_:: + reduced to that of a proper cone [Orlitzky]_:: sage: set_random_seed() sage: K = random_cone(max_ambient_dim=8) @@ -414,8 +409,7 @@ def lyapunov_rank(K): sage: actual == expected True - The Lyapunov rank of any cone is just the dimension of - ``K.lyapunov_like_basis()``:: + The Lyapunov rank of a cone is the size of a :meth:`lyapunov_like_basis`:: sage: set_random_seed() sage: K = random_cone(max_ambient_dim=8) @@ -423,7 +417,7 @@ def lyapunov_rank(K): True We can make an imperfect cone perfect by adding a slack variable - (a Theorem in [Orlitzky/Gowda]_):: + (a Theorem in [Orlitzky]_):: sage: set_random_seed() sage: K = random_cone(max_ambient_dim=8, @@ -435,7 +429,7 @@ def lyapunov_rank(K): True """ - beta = 0 + beta = 0 # running tally of the Lyapunov rank m = K.dim() n = K.lattice_dim() @@ -494,8 +488,8 @@ def is_lyapunov_like(L,K): REFERENCES: - .. [Orlitzky] M. Orlitzky. The Lyapunov rank of an - improper cone (preprint). + M. Orlitzky. The Lyapunov rank of an improper cone. + http://www.optimization-online.org/DB_HTML/2015/10/5135.html EXAMPLES: -- 2.44.2