]>
gitweb.michael.orlitzky.com - sage.d.git/blob - mjo/cone/cone.py
702472c30466f7cba79d4a79f1bf47a552079364
3 def is_lyapunov_like(L
,K
):
5 Determine whether or not ``L`` is Lyapunov-like on ``K``.
7 We say that ``L`` is Lyapunov-like on ``K`` if `\left\langle
8 L\left\lparenx\right\rparen,s\right\rangle = 0` for all pairs
9 `\left\langle x,s \right\rangle` in the complementarity set of
10 ``K``. It is known [Orlitzky]_ that this property need only be
11 checked for generators of ``K`` and its dual.
15 - ``L`` -- A linear transformation or matrix.
17 - ``K`` -- A polyhedral closed convex cone.
21 ``True`` if it can be proven that ``L`` is Lyapunov-like on ``K``,
22 and ``False`` otherwise.
26 If this function returns ``True``, then ``L`` is Lyapunov-like
27 on ``K``. However, if ``False`` is returned, that could mean one
28 of two things. The first is that ``L`` is definitely not
29 Lyapunov-like on ``K``. The second is more of an "I don't know"
30 answer, returned (for example) if we cannot prove that an inner
35 M. Orlitzky. The Lyapunov rank of an improper cone.
36 http://www.optimization-online.org/DB_HTML/2015/10/5135.html
40 The identity is always Lyapunov-like in a nontrivial space::
42 sage: set_random_seed()
43 sage: K = random_cone(min_ambient_dim = 1, max_ambient_dim = 8)
44 sage: L = identity_matrix(K.lattice_dim())
45 sage: is_lyapunov_like(L,K)
48 As is the "zero" transformation::
50 sage: K = random_cone(min_ambient_dim = 1, max_ambient_dim = 8)
51 sage: R = K.lattice().vector_space().base_ring()
52 sage: L = zero_matrix(R, K.lattice_dim())
53 sage: is_lyapunov_like(L,K)
56 Everything in ``K.lyapunov_like_basis()`` should be Lyapunov-like
59 sage: K = random_cone(min_ambient_dim = 1, max_ambient_dim = 6)
60 sage: all([ is_lyapunov_like(L,K) for L in K.lyapunov_like_basis() ])
64 return all([(L
*x
).inner_product(s
) == 0
65 for (x
,s
) in K
.discrete_complementarity_set()])
68 def random_element(K
):
70 Return a random element of ``K`` from its ambient vector space.
74 The cone ``K`` is specified in terms of its generators, so that
75 ``K`` is equal to the convex conic combination of those generators.
76 To choose a random element of ``K``, we assign random nonnegative
77 coefficients to each generator of ``K`` and construct a new vector
80 A vector, rather than a ray, is returned so that the element may
81 have non-integer coordinates. Thus the element may have an
82 arbitrarily small norm.
86 A random element of the trivial cone is zero::
88 sage: set_random_seed()
89 sage: K = Cone([], ToricLattice(0))
90 sage: random_element(K)
92 sage: K = Cone([(0,)])
93 sage: random_element(K)
95 sage: K = Cone([(0,0)])
96 sage: random_element(K)
98 sage: K = Cone([(0,0,0)])
99 sage: random_element(K)
104 Any cone should contain an element of itself::
106 sage: set_random_seed()
107 sage: K = random_cone(max_rays = 8)
108 sage: K.contains(random_element(K))
112 V
= K
.lattice().vector_space()
114 coefficients
= [ F
.random_element().abs() for i
in range(K
.nrays()) ]
115 vector_gens
= map(V
, K
.rays())
116 scaled_gens
= [ coefficients
[i
]*vector_gens
[i
]
117 for i
in range(len(vector_gens
)) ]
119 # Make sure we return a vector. Without the coercion, we might
120 # return ``0`` when ``K`` has no rays.
121 v
= V(sum(scaled_gens
))
125 def positive_operator_gens(K
):
127 Compute generators of the cone of positive operators on this cone.
131 A list of `n`-by-``n`` matrices where ``n == K.lattice_dim()``.
132 Each matrix ``P`` in the list should have the property that ``P*x``
133 is an element of ``K`` whenever ``x`` is an element of
134 ``K``. Moreover, any nonnegative linear combination of these
135 matrices shares the same property.
139 The trivial cone in a trivial space has no positive operators::
141 sage: K = Cone([], ToricLattice(0))
142 sage: positive_operator_gens(K)
145 Positive operators on the nonnegative orthant are nonnegative matrices::
147 sage: K = Cone([(1,)])
148 sage: positive_operator_gens(K)
151 sage: K = Cone([(1,0),(0,1)])
152 sage: positive_operator_gens(K)
154 [1 0] [0 1] [0 0] [0 0]
155 [0 0], [0 0], [1 0], [0 1]
158 Every operator is positive on the ambient vector space::
160 sage: K = Cone([(1,),(-1,)])
161 sage: K.is_full_space()
163 sage: positive_operator_gens(K)
166 sage: K = Cone([(1,0),(-1,0),(0,1),(0,-1)])
167 sage: K.is_full_space()
169 sage: positive_operator_gens(K)
171 [1 0] [-1 0] [0 1] [ 0 -1] [0 0] [ 0 0] [0 0] [ 0 0]
172 [0 0], [ 0 0], [0 0], [ 0 0], [1 0], [-1 0], [0 1], [ 0 -1]
177 A positive operator on a cone should send its generators into the cone::
179 sage: set_random_seed()
180 sage: K = random_cone(max_ambient_dim=5)
181 sage: pi_of_K = positive_operator_gens(K)
182 sage: all([K.contains(p*x) for p in pi_of_K for x in K.rays()])
185 The dimension of the cone of positive operators is given by the
186 corollary in my paper::
188 sage: set_random_seed()
189 sage: K = random_cone(max_ambient_dim = 5)
190 sage: n = K.lattice_dim()
192 sage: l = K.lineality()
193 sage: pi_of_K = positive_operator_gens(K)
194 sage: L = ToricLattice(n**2)
195 sage: actual = Cone([p.list() for p in pi_of_K], lattice=L).dim()
196 sage: expected = n**2 - l*(m - l) - (n - m)*m
197 sage: actual == expected
200 The lineality of the cone of positive operators is given by the
201 corollary in my paper::
203 sage: set_random_seed()
204 sage: K = random_cone(max_ambient_dim=5)
205 sage: n = K.lattice_dim()
206 sage: pi_of_K = positive_operator_gens(K)
207 sage: L = ToricLattice(n**2)
208 sage: actual = Cone([p.list() for p in pi_of_K], lattice=L).lineality()
209 sage: expected = n**2 - K.dim()*K.dual().dim()
210 sage: actual == expected
213 The cone ``K`` is proper if and only if the cone of positive
214 operators on ``K`` is proper::
216 sage: set_random_seed()
217 sage: K = random_cone(max_ambient_dim=5)
218 sage: pi_of_K = positive_operator_gens(K)
219 sage: L = ToricLattice(K.lattice_dim()**2)
220 sage: pi_cone = Cone([p.list() for p in pi_of_K], lattice=L)
221 sage: K.is_proper() == pi_cone.is_proper()
224 # Matrices are not vectors in Sage, so we have to convert them
225 # to vectors explicitly before we can find a basis. We need these
226 # two values to construct the appropriate "long vector" space.
227 F
= K
.lattice().base_field()
230 tensor_products
= [ s
.tensor_product(x
) for x
in K
for s
in K
.dual() ]
232 # Convert those tensor products to long vectors.
233 W
= VectorSpace(F
, n
**2)
234 vectors
= [ W(tp
.list()) for tp
in tensor_products
]
236 # Create the *dual* cone of the positive operators, expressed as
238 pi_dual
= Cone(vectors
, ToricLattice(W
.dimension()))
240 # Now compute the desired cone from its dual...
241 pi_cone
= pi_dual
.dual()
243 # And finally convert its rays back to matrix representations.
244 M
= MatrixSpace(F
, n
)
245 return [ M(v
.list()) for v
in pi_cone
.rays() ]
248 def Z_transformation_gens(K
):
250 Compute generators of the cone of Z-transformations on this cone.
254 A list of `n`-by-``n`` matrices where ``n == K.lattice_dim()``.
255 Each matrix ``L`` in the list should have the property that
256 ``(L*x).inner_product(s) <= 0`` whenever ``(x,s)`` is an element the
257 discrete complementarity set of ``K``. Moreover, any nonnegative
258 linear combination of these matrices shares the same property.
262 Z-transformations on the nonnegative orthant are just Z-matrices.
263 That is, matrices whose off-diagonal elements are nonnegative::
265 sage: K = Cone([(1,0),(0,1)])
266 sage: Z_transformation_gens(K)
268 [ 0 -1] [ 0 0] [-1 0] [1 0] [ 0 0] [0 0]
269 [ 0 0], [-1 0], [ 0 0], [0 0], [ 0 -1], [0 1]
271 sage: K = Cone([(1,0,0,0),(0,1,0,0),(0,0,1,0),(0,0,0,1)])
272 sage: all([ z[i][j] <= 0 for z in Z_transformation_gens(K)
273 ....: for i in range(z.nrows())
274 ....: for j in range(z.ncols())
278 The trivial cone in a trivial space has no Z-transformations::
280 sage: K = Cone([], ToricLattice(0))
281 sage: Z_transformation_gens(K)
284 Z-transformations on a subspace are Lyapunov-like and vice-versa::
286 sage: K = Cone([(1,0),(-1,0),(0,1),(0,-1)])
287 sage: K.is_full_space()
289 sage: lls = span([ vector(l.list()) for l in K.lyapunov_like_basis() ])
290 sage: zs = span([ vector(z.list()) for z in Z_transformation_gens(K) ])
296 The Z-property is possessed by every Z-transformation::
298 sage: set_random_seed()
299 sage: K = random_cone(max_ambient_dim = 6)
300 sage: Z_of_K = Z_transformation_gens(K)
301 sage: dcs = K.discrete_complementarity_set()
302 sage: all([(z*x).inner_product(s) <= 0 for z in Z_of_K
303 ....: for (x,s) in dcs])
306 The lineality space of Z is LL::
308 sage: set_random_seed()
309 sage: K = random_cone(min_ambient_dim = 1, max_ambient_dim = 6)
310 sage: lls = span([ vector(l.list()) for l in K.lyapunov_like_basis() ])
311 sage: z_cone = Cone([ z.list() for z in Z_transformation_gens(K) ])
312 sage: z_cone.linear_subspace() == lls
315 And thus, the lineality of Z is the Lyapunov rank::
317 sage: set_random_seed()
318 sage: K = random_cone(max_ambient_dim=6)
319 sage: Z_of_K = Z_transformation_gens(K)
320 sage: L = ToricLattice(K.lattice_dim()**2)
321 sage: z_cone = Cone([ z.list() for z in Z_of_K ], lattice=L)
322 sage: z_cone.lineality() == K.lyapunov_rank()
325 The lineality spaces of pi-star and Z-star are equal:
327 sage: set_random_seed()
328 sage: K = random_cone(max_ambient_dim=5)
329 sage: pi_of_K = positive_operator_gens(K)
330 sage: Z_of_K = Z_transformation_gens(K)
331 sage: L = ToricLattice(K.lattice_dim()**2)
332 sage: pi_star = Cone([p.list() for p in pi_of_K], lattice=L).dual()
333 sage: z_star = Cone([ z.list() for z in Z_of_K], lattice=L).dual()
334 sage: pi_star.linear_subspace() == z_star.linear_subspace()
337 # Matrices are not vectors in Sage, so we have to convert them
338 # to vectors explicitly before we can find a basis. We need these
339 # two values to construct the appropriate "long vector" space.
340 F
= K
.lattice().base_field()
343 # These tensor products contain generators for the dual cone of
344 # the cross-positive transformations.
345 tensor_products
= [ s
.tensor_product(x
)
346 for (x
,s
) in K
.discrete_complementarity_set() ]
348 # Turn our matrices into long vectors...
349 W
= VectorSpace(F
, n
**2)
350 vectors
= [ W(m
.list()) for m
in tensor_products
]
352 # Create the *dual* cone of the cross-positive operators,
353 # expressed as long vectors..
354 Sigma_dual
= Cone(vectors
, lattice
=ToricLattice(W
.dimension()))
356 # Now compute the desired cone from its dual...
357 Sigma_cone
= Sigma_dual
.dual()
359 # And finally convert its rays back to matrix representations.
360 # But first, make them negative, so we get Z-transformations and
361 # not cross-positive ones.
362 M
= MatrixSpace(F
, n
)
363 return [ -M(v
.list()) for v
in Sigma_cone
.rays() ]
367 gens
= Z_transformation_gens(K
)
371 return Cone([ g
.list() for g
in gens
], lattice
=L
)
374 gens
= positive_operator_gens(K
)
378 return Cone([ g
.list() for g
in gens
], lattice
=L
)