]>
gitweb.michael.orlitzky.com - sage.d.git/blob - mjo/cone/cone.py
3d74b5f17adc095dc43c7e421f511ab84308c4ac
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 positive_operator_gens(K
):
70 Compute generators of the cone of positive operators on this cone.
74 A list of `n`-by-``n`` matrices where ``n == K.lattice_dim()``.
75 Each matrix ``P`` in the list should have the property that ``P*x``
76 is an element of ``K`` whenever ``x`` is an element of
77 ``K``. Moreover, any nonnegative linear combination of these
78 matrices shares the same property.
84 Positive operators and Z-transformations on closed convex cones.
88 Some results of polyhedral cones and simplicial cones.
89 Linear and Multilinear Algebra, 4:4 (1977) 281--284.
93 Positive operators on the nonnegative orthant are nonnegative matrices::
95 sage: K = Cone([(1,)])
96 sage: positive_operator_gens(K)
99 sage: K = Cone([(1,0),(0,1)])
100 sage: positive_operator_gens(K)
102 [1 0] [0 1] [0 0] [0 0]
103 [0 0], [0 0], [1 0], [0 1]
106 The trivial cone in a trivial space has no positive operators::
108 sage: K = Cone([], ToricLattice(0))
109 sage: positive_operator_gens(K)
112 Every operator is positive on the trivial cone::
114 sage: K = Cone([(0,)])
115 sage: positive_operator_gens(K)
118 sage: K = Cone([(0,0)])
121 sage: positive_operator_gens(K)
123 [1 0] [-1 0] [0 1] [ 0 -1] [0 0] [ 0 0] [0 0] [ 0 0]
124 [0 0], [ 0 0], [0 0], [ 0 0], [1 0], [-1 0], [0 1], [ 0 -1]
127 Every operator is positive on the ambient vector space::
129 sage: K = Cone([(1,),(-1,)])
130 sage: K.is_full_space()
132 sage: positive_operator_gens(K)
135 sage: K = Cone([(1,0),(-1,0),(0,1),(0,-1)])
136 sage: K.is_full_space()
138 sage: positive_operator_gens(K)
140 [1 0] [-1 0] [0 1] [ 0 -1] [0 0] [ 0 0] [0 0] [ 0 0]
141 [0 0], [ 0 0], [0 0], [ 0 0], [1 0], [-1 0], [0 1], [ 0 -1]
144 A non-obvious application is to find the positive operators on the
147 sage: K = Cone([(1,0),(0,1),(0,-1)])
148 sage: positive_operator_gens(K)
150 [1 0] [0 0] [ 0 0] [0 0] [ 0 0]
151 [0 0], [1 0], [-1 0], [0 1], [ 0 -1]
156 Each positive operator generator should send the generators of the
159 sage: set_random_seed()
160 sage: K = random_cone(max_ambient_dim=4)
161 sage: pi_of_K = positive_operator_gens(K)
162 sage: all([ K.contains(P*x) for P in pi_of_K for x in K ])
165 Each positive operator generator should send a random element of the
168 sage: set_random_seed()
169 sage: K = random_cone(max_ambient_dim=4)
170 sage: pi_of_K = positive_operator_gens(K)
171 sage: all([ K.contains(P*K.random_element(QQ)) for P in pi_of_K ])
174 A random element of the positive operator cone should send the
175 generators of the cone into the cone::
177 sage: set_random_seed()
178 sage: K = random_cone(max_ambient_dim=4)
179 sage: pi_of_K = positive_operator_gens(K)
180 sage: L = ToricLattice(K.lattice_dim()**2)
181 sage: pi_cone = Cone([ g.list() for g in pi_of_K ],
184 sage: P = matrix(K.lattice_dim(), pi_cone.random_element(QQ).list())
185 sage: all([ K.contains(P*x) for x in K ])
188 A random element of the positive operator cone should send a random
189 element of the cone into the cone::
191 sage: set_random_seed()
192 sage: K = random_cone(max_ambient_dim=4)
193 sage: pi_of_K = positive_operator_gens(K)
194 sage: L = ToricLattice(K.lattice_dim()**2)
195 sage: pi_cone = Cone([ g.list() for g in pi_of_K ],
198 sage: P = matrix(K.lattice_dim(), pi_cone.random_element(QQ).list())
199 sage: K.contains(P*K.random_element(ring=QQ))
202 The lineality space of the dual of the cone of positive operators
203 can be computed from the lineality spaces of the cone and its dual::
205 sage: set_random_seed()
206 sage: K = random_cone(max_ambient_dim=4)
207 sage: pi_of_K = positive_operator_gens(K)
208 sage: L = ToricLattice(K.lattice_dim()**2)
209 sage: pi_cone = Cone([ g.list() for g in pi_of_K ],
212 sage: actual = pi_cone.dual().linear_subspace()
213 sage: U1 = [ vector((s.tensor_product(x)).list())
214 ....: for x in K.lines()
215 ....: for s in K.dual() ]
216 sage: U2 = [ vector((s.tensor_product(x)).list())
218 ....: for s in K.dual().lines() ]
219 sage: expected = pi_cone.lattice().vector_space().span(U1 + U2)
220 sage: actual == expected
223 The lineality of the dual of the cone of positive operators
224 is known from its lineality space::
226 sage: set_random_seed()
227 sage: K = random_cone(max_ambient_dim=4)
228 sage: n = K.lattice_dim()
230 sage: l = K.lineality()
231 sage: pi_of_K = positive_operator_gens(K)
232 sage: L = ToricLattice(n**2)
233 sage: pi_cone = Cone([p.list() for p in pi_of_K],
236 sage: actual = pi_cone.dual().lineality()
237 sage: expected = l*(m - l) + m*(n - m)
238 sage: actual == expected
241 The dimension of the cone of positive operators is given by the
242 corollary in my paper::
244 sage: set_random_seed()
245 sage: K = random_cone(max_ambient_dim=4)
246 sage: n = K.lattice_dim()
248 sage: l = K.lineality()
249 sage: pi_of_K = positive_operator_gens(K)
250 sage: L = ToricLattice(n**2)
251 sage: pi_cone = Cone([p.list() for p in pi_of_K],
254 sage: actual = pi_cone.dim()
255 sage: expected = n**2 - l*(m - l) - (n - m)*m
256 sage: actual == expected
259 The trivial cone, full space, and half-plane all give rise to the
260 expected dimensions::
262 sage: n = ZZ.random_element().abs()
263 sage: K = Cone([[0] * n], ToricLattice(n))
266 sage: L = ToricLattice(n^2)
267 sage: pi_of_K = positive_operator_gens(K)
268 sage: pi_cone = Cone([p.list() for p in pi_of_K],
271 sage: actual = pi_cone.dim()
275 sage: K.is_full_space()
277 sage: pi_of_K = positive_operator_gens(K)
278 sage: pi_cone = Cone([p.list() for p in pi_of_K],
281 sage: actual = pi_cone.dim()
284 sage: K = Cone([(1,0),(0,1),(0,-1)])
285 sage: pi_of_K = positive_operator_gens(K)
286 sage: actual = Cone([p.list() for p in pi_of_K], check=False).dim()
290 The lineality of the cone of positive operators follows from the
291 description of its generators::
293 sage: set_random_seed()
294 sage: K = random_cone(max_ambient_dim=4)
295 sage: n = K.lattice_dim()
296 sage: pi_of_K = positive_operator_gens(K)
297 sage: L = ToricLattice(n**2)
298 sage: pi_cone = Cone([p.list() for p in pi_of_K],
301 sage: actual = pi_cone.lineality()
302 sage: expected = n**2 - K.dim()*K.dual().dim()
303 sage: actual == expected
306 The trivial cone, full space, and half-plane all give rise to the
307 expected linealities::
309 sage: n = ZZ.random_element().abs()
310 sage: K = Cone([[0] * n], ToricLattice(n))
313 sage: L = ToricLattice(n^2)
314 sage: pi_of_K = positive_operator_gens(K)
315 sage: pi_cone = Cone([p.list() for p in pi_of_K],
318 sage: actual = pi_cone.lineality()
322 sage: K.is_full_space()
324 sage: pi_of_K = positive_operator_gens(K)
325 sage: pi_cone = Cone([p.list() for p in pi_of_K], lattice=L)
326 sage: pi_cone.lineality() == n^2
328 sage: K = Cone([(1,0),(0,1),(0,-1)])
329 sage: pi_of_K = positive_operator_gens(K)
330 sage: pi_cone = Cone([p.list() for p in pi_of_K], check=False)
331 sage: actual = pi_cone.lineality()
335 A cone is proper if and only if its cone of positive operators
338 sage: set_random_seed()
339 sage: K = random_cone(max_ambient_dim=4)
340 sage: pi_of_K = positive_operator_gens(K)
341 sage: L = ToricLattice(K.lattice_dim()**2)
342 sage: pi_cone = Cone([p.list() for p in pi_of_K],
345 sage: K.is_proper() == pi_cone.is_proper()
348 The positive operators of a permuted cone can be obtained by
351 sage: set_random_seed()
352 sage: K = random_cone(max_ambient_dim=4)
353 sage: L = ToricLattice(K.lattice_dim()**2)
354 sage: p = SymmetricGroup(K.lattice_dim()).random_element().matrix()
355 sage: pK = Cone([ p*k for k in K ], K.lattice(), check=False)
356 sage: pi_of_pK = positive_operator_gens(pK)
357 sage: actual = Cone([t.list() for t in pi_of_pK],
360 sage: pi_of_K = positive_operator_gens(K)
361 sage: expected = Cone([(p*t*p.inverse()).list() for t in pi_of_K],
364 sage: actual.is_equivalent(expected)
367 A transformation is positive on a cone if and only if its adjoint is
368 positive on the dual of that cone::
370 sage: set_random_seed()
371 sage: K = random_cone(max_ambient_dim=4)
372 sage: F = K.lattice().vector_space().base_field()
373 sage: n = K.lattice_dim()
374 sage: L = ToricLattice(n**2)
375 sage: W = VectorSpace(F, n**2)
376 sage: pi_of_K = positive_operator_gens(K)
377 sage: pi_of_K_star = positive_operator_gens(K.dual())
378 sage: pi_cone = Cone([p.list() for p in pi_of_K],
381 sage: pi_star = Cone([p.list() for p in pi_of_K_star],
384 sage: M = MatrixSpace(F, n)
385 sage: L = M(pi_cone.random_element(ring=QQ).list())
386 sage: pi_star.contains(W(L.transpose().list()))
389 sage: L = W.random_element()
390 sage: L_star = W(M(L.list()).transpose().list())
391 sage: pi_cone.contains(L) == pi_star.contains(L_star)
394 # Matrices are not vectors in Sage, so we have to convert them
395 # to vectors explicitly before we can find a basis. We need these
396 # two values to construct the appropriate "long vector" space.
397 F
= K
.lattice().base_field()
400 tensor_products
= [ s
.tensor_product(x
) for x
in K
for s
in K
.dual() ]
402 # Convert those tensor products to long vectors.
403 W
= VectorSpace(F
, n
**2)
404 vectors
= [ W(tp
.list()) for tp
in tensor_products
]
408 # All of the generators involved are extreme vectors and
409 # therefore minimal [Tam]_. If this cone is neither solid nor
410 # strictly convex, then the tensor product of ``s`` and ``x``
411 # is the same as that of ``-s`` and ``-x``. However, as a
412 # /set/, ``tensor_products`` may still be minimal.
415 # Create the dual cone of the positive operators, expressed as
417 pi_dual
= Cone(vectors
, ToricLattice(W
.dimension()), check
=check
)
419 # Now compute the desired cone from its dual...
420 pi_cone
= pi_dual
.dual()
422 # And finally convert its rays back to matrix representations.
423 M
= MatrixSpace(F
, n
)
424 return [ M(v
.list()) for v
in pi_cone
]
427 def Z_transformation_gens(K
):
429 Compute generators of the cone of Z-transformations on this cone.
433 A list of `n`-by-``n`` matrices where ``n == K.lattice_dim()``.
434 Each matrix ``L`` in the list should have the property that
435 ``(L*x).inner_product(s) <= 0`` whenever ``(x,s)`` is an element of
436 this cone's :meth:`discrete_complementarity_set`. Moreover, any
437 conic (nonnegative linear) combination of these matrices shares the
443 Positive operators and Z-transformations on closed convex cones.
447 Z-transformations on the nonnegative orthant are just Z-matrices.
448 That is, matrices whose off-diagonal elements are nonnegative::
450 sage: K = Cone([(1,0),(0,1)])
451 sage: Z_transformation_gens(K)
453 [ 0 -1] [ 0 0] [-1 0] [1 0] [ 0 0] [0 0]
454 [ 0 0], [-1 0], [ 0 0], [0 0], [ 0 -1], [0 1]
456 sage: K = Cone([(1,0,0,0),(0,1,0,0),(0,0,1,0),(0,0,0,1)])
457 sage: all([ z[i][j] <= 0 for z in Z_transformation_gens(K)
458 ....: for i in range(z.nrows())
459 ....: for j in range(z.ncols())
463 The trivial cone in a trivial space has no Z-transformations::
465 sage: K = Cone([], ToricLattice(0))
466 sage: Z_transformation_gens(K)
469 Every operator is a Z-transformation on the ambient vector space::
471 sage: K = Cone([(1,),(-1,)])
472 sage: K.is_full_space()
474 sage: Z_transformation_gens(K)
477 sage: K = Cone([(1,0),(-1,0),(0,1),(0,-1)])
478 sage: K.is_full_space()
480 sage: Z_transformation_gens(K)
482 [-1 0] [1 0] [ 0 -1] [0 1] [ 0 0] [0 0] [ 0 0] [0 0]
483 [ 0 0], [0 0], [ 0 0], [0 0], [-1 0], [1 0], [ 0 -1], [0 1]
486 A non-obvious application is to find the Z-transformations on the
489 sage: K = Cone([(1,0),(0,1),(0,-1)])
490 sage: Z_transformation_gens(K)
492 [-1 0] [1 0] [ 0 0] [0 0] [ 0 0] [0 0]
493 [ 0 0], [0 0], [-1 0], [1 0], [ 0 -1], [0 1]
496 Z-transformations on a subspace are Lyapunov-like and vice-versa::
498 sage: K = Cone([(1,0),(-1,0),(0,1),(0,-1)])
499 sage: K.is_full_space()
501 sage: lls = span([ vector(l.list()) for l in K.lyapunov_like_basis() ])
502 sage: zs = span([ vector(z.list()) for z in Z_transformation_gens(K) ])
508 The Z-property is possessed by every Z-transformation::
510 sage: set_random_seed()
511 sage: K = random_cone(max_ambient_dim=4)
512 sage: Z_of_K = Z_transformation_gens(K)
513 sage: dcs = K.discrete_complementarity_set()
514 sage: all([(z*x).inner_product(s) <= 0 for z in Z_of_K
515 ....: for (x,s) in dcs])
518 The lineality space of the cone of Z-transformations is the space of
519 Lyapunov-like transformations::
521 sage: set_random_seed()
522 sage: K = random_cone(max_ambient_dim=4)
523 sage: L = ToricLattice(K.lattice_dim()**2)
524 sage: Z_cone = Cone([ z.list() for z in Z_transformation_gens(K) ],
527 sage: ll_basis = [ vector(l.list()) for l in K.lyapunov_like_basis() ]
528 sage: lls = L.vector_space().span(ll_basis)
529 sage: Z_cone.linear_subspace() == lls
532 The lineality of the Z-transformations on a cone is the Lyapunov
535 sage: set_random_seed()
536 sage: K = random_cone(max_ambient_dim=4)
537 sage: Z_of_K = Z_transformation_gens(K)
538 sage: L = ToricLattice(K.lattice_dim()**2)
539 sage: Z_cone = Cone([ z.list() for z in Z_of_K ],
542 sage: Z_cone.lineality() == K.lyapunov_rank()
545 The lineality spaces of the duals of the positive operator and
546 Z-transformation cones are equal. From this it follows that the
547 dimensions of the Z-transformation cone and positive operator cone
550 sage: set_random_seed()
551 sage: K = random_cone(max_ambient_dim=4)
552 sage: pi_of_K = positive_operator_gens(K)
553 sage: Z_of_K = Z_transformation_gens(K)
554 sage: L = ToricLattice(K.lattice_dim()**2)
555 sage: pi_cone = Cone([p.list() for p in pi_of_K],
558 sage: Z_cone = Cone([ z.list() for z in Z_of_K],
561 sage: pi_cone.dim() == Z_cone.dim()
563 sage: pi_star = pi_cone.dual()
564 sage: z_star = Z_cone.dual()
565 sage: pi_star.linear_subspace() == z_star.linear_subspace()
568 The trivial cone, full space, and half-plane all give rise to the
569 expected dimensions::
571 sage: n = ZZ.random_element().abs()
572 sage: K = Cone([[0] * n], ToricLattice(n))
575 sage: L = ToricLattice(n^2)
576 sage: Z_of_K = Z_transformation_gens(K)
577 sage: Z_cone = Cone([z.list() for z in Z_of_K],
580 sage: actual = Z_cone.dim()
584 sage: K.is_full_space()
586 sage: Z_of_K = Z_transformation_gens(K)
587 sage: Z_cone = Cone([z.list() for z in Z_of_K],
590 sage: actual = Z_cone.dim()
593 sage: K = Cone([(1,0),(0,1),(0,-1)])
594 sage: Z_of_K = Z_transformation_gens(K)
595 sage: Z_cone = Cone([z.list() for z in Z_of_K], check=False)
596 sage: Z_cone.dim() == 3
599 The Z-transformations of a permuted cone can be obtained by
602 sage: set_random_seed()
603 sage: K = random_cone(max_ambient_dim=4)
604 sage: L = ToricLattice(K.lattice_dim()**2)
605 sage: p = SymmetricGroup(K.lattice_dim()).random_element().matrix()
606 sage: pK = Cone([ p*k for k in K ], K.lattice(), check=False)
607 sage: Z_of_pK = Z_transformation_gens(pK)
608 sage: actual = Cone([t.list() for t in Z_of_pK],
611 sage: Z_of_K = Z_transformation_gens(K)
612 sage: expected = Cone([(p*t*p.inverse()).list() for t in Z_of_K],
615 sage: actual.is_equivalent(expected)
618 A transformation is a Z-transformation on a cone if and only if its
619 adjoint is a Z-transformation on the dual of that cone::
621 sage: set_random_seed()
622 sage: K = random_cone(max_ambient_dim=4)
623 sage: F = K.lattice().vector_space().base_field()
624 sage: n = K.lattice_dim()
625 sage: L = ToricLattice(n**2)
626 sage: W = VectorSpace(F, n**2)
627 sage: Z_of_K = Z_transformation_gens(K)
628 sage: Z_of_K_star = Z_transformation_gens(K.dual())
629 sage: Z_cone = Cone([p.list() for p in Z_of_K],
632 sage: Z_star = Cone([p.list() for p in Z_of_K_star],
635 sage: M = MatrixSpace(F, n)
636 sage: L = M(Z_cone.random_element(ring=QQ).list())
637 sage: Z_star.contains(W(L.transpose().list()))
640 sage: L = W.random_element()
641 sage: L_star = W(M(L.list()).transpose().list())
642 sage: Z_cone.contains(L) == Z_star.contains(L_star)
645 # Matrices are not vectors in Sage, so we have to convert them
646 # to vectors explicitly before we can find a basis. We need these
647 # two values to construct the appropriate "long vector" space.
648 F
= K
.lattice().base_field()
651 # These tensor products contain generators for the dual cone of
652 # the cross-positive transformations.
653 tensor_products
= [ s
.tensor_product(x
)
654 for (x
,s
) in K
.discrete_complementarity_set() ]
656 # Turn our matrices into long vectors...
657 W
= VectorSpace(F
, n
**2)
658 vectors
= [ W(m
.list()) for m
in tensor_products
]
662 # All of the generators involved are extreme vectors and
663 # therefore minimal. If this cone is neither solid nor
664 # strictly convex, then the tensor product of ``s`` and ``x``
665 # is the same as that of ``-s`` and ``-x``. However, as a
666 # /set/, ``tensor_products`` may still be minimal.
669 # Create the dual cone of the cross-positive operators,
670 # expressed as long vectors.
671 Sigma_dual
= Cone(vectors
, lattice
=ToricLattice(W
.dimension()), check
=check
)
673 # Now compute the desired cone from its dual...
674 Sigma_cone
= Sigma_dual
.dual()
676 # And finally convert its rays back to matrix representations.
677 # But first, make them negative, so we get Z-transformations and
678 # not cross-positive ones.
679 M
= MatrixSpace(F
, n
)
680 return [ -M(v
.list()) for v
in Sigma_cone
]
684 gens
= Z_transformation_gens(K
)
685 L
= ToricLattice(K
.lattice_dim()**2)
686 return Cone([ g
.list() for g
in gens
], lattice
=L
, check
=False)
689 gens
= positive_operator_gens(K
)
690 L
= ToricLattice(K
.lattice_dim()**2)
691 return Cone([ g
.list() for g
in gens
], lattice
=L
, check
=False)