]>
gitweb.michael.orlitzky.com - sage.d.git/blob - mjo/cone/cone.py
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.
13 There are faster ways of checking this property. For example, we
14 could compute a `lyapunov_like_basis` of the cone, and then test
15 whether or not the given matrix is contained in the span of that
16 basis. The value of this function is that it works on symbolic
21 - ``L`` -- A linear transformation or matrix.
23 - ``K`` -- A polyhedral closed convex cone.
27 ``True`` if it can be proven that ``L`` is Lyapunov-like on ``K``,
28 and ``False`` otherwise.
32 If this function returns ``True``, then ``L`` is Lyapunov-like
33 on ``K``. However, if ``False`` is returned, that could mean one
34 of two things. The first is that ``L`` is definitely not
35 Lyapunov-like on ``K``. The second is more of an "I don't know"
36 answer, returned (for example) if we cannot prove that an inner
41 M. Orlitzky. The Lyapunov rank of an improper cone.
42 http://www.optimization-online.org/DB_HTML/2015/10/5135.html
46 The identity is always Lyapunov-like in a nontrivial space::
48 sage: set_random_seed()
49 sage: K = random_cone(min_ambient_dim=1, max_ambient_dim=8)
50 sage: L = identity_matrix(K.lattice_dim())
51 sage: is_lyapunov_like(L,K)
54 As is the "zero" transformation::
56 sage: K = random_cone(min_ambient_dim=1, max_ambient_dim=8)
57 sage: R = K.lattice().vector_space().base_ring()
58 sage: L = zero_matrix(R, K.lattice_dim())
59 sage: is_lyapunov_like(L,K)
62 Everything in ``K.lyapunov_like_basis()`` should be Lyapunov-like
65 sage: K = random_cone(min_ambient_dim=1, max_ambient_dim=6)
66 sage: all([ is_lyapunov_like(L,K) for L in K.lyapunov_like_basis() ])
70 return all([(L
*x
).inner_product(s
) == 0
71 for (x
,s
) in K
.discrete_complementarity_set()])
74 def positive_operator_gens(K1
, K2
= None):
76 Compute generators of the cone of positive operators on this cone. A
77 linear operator on a cone is positive if the image of the cone under
78 the operator is a subset of the cone. This concept can be extended
79 to two cones, where the image of the first cone under a positive
80 operator is a subset of the second cone.
84 - ``K2`` -- (default: ``K1``) the codomain cone; the image of this
85 cone under the returned operators is a subset of ``K2``.
89 A list of `m`-by-``n`` matrices where ``m == K2.lattice_dim()`` and
90 ``n == K1.lattice_dim()``. Each matrix ``P`` in the list should have
91 the property that ``P*x`` is an element of ``K2`` whenever ``x`` is
92 an element of ``K1``. Moreover, any nonnegative linear combination of
93 these matrices shares the same property.
97 :meth:`cross_positive_operator_gens`, :meth:`Z_operator_gens`,
103 Some results of polyhedral cones and simplicial cones.
104 Linear and Multilinear Algebra, 4:4 (1977) 281--284.
108 Positive operators on the nonnegative orthant are nonnegative matrices::
110 sage: K = Cone([(1,)])
111 sage: positive_operator_gens(K)
114 sage: K = Cone([(1,0),(0,1)])
115 sage: positive_operator_gens(K)
117 [1 0] [0 1] [0 0] [0 0]
118 [0 0], [0 0], [1 0], [0 1]
121 The trivial cone in a trivial space has no positive operators::
123 sage: K = Cone([], ToricLattice(0))
124 sage: positive_operator_gens(K)
127 Every operator is positive on the trivial cone::
129 sage: K = Cone([(0,)])
130 sage: positive_operator_gens(K)
133 sage: K = Cone([(0,0)])
136 sage: positive_operator_gens(K)
138 [1 0] [-1 0] [0 1] [ 0 -1] [0 0] [ 0 0] [0 0] [ 0 0]
139 [0 0], [ 0 0], [0 0], [ 0 0], [1 0], [-1 0], [0 1], [ 0 -1]
142 Every operator is positive on the ambient vector space::
144 sage: K = Cone([(1,),(-1,)])
145 sage: K.is_full_space()
147 sage: positive_operator_gens(K)
150 sage: K = Cone([(1,0),(-1,0),(0,1),(0,-1)])
151 sage: K.is_full_space()
153 sage: positive_operator_gens(K)
155 [1 0] [-1 0] [0 1] [ 0 -1] [0 0] [ 0 0] [0 0] [ 0 0]
156 [0 0], [ 0 0], [0 0], [ 0 0], [1 0], [-1 0], [0 1], [ 0 -1]
159 A non-obvious application is to find the positive operators on the
162 sage: K = Cone([(1,0),(0,1),(0,-1)])
163 sage: positive_operator_gens(K)
165 [1 0] [0 0] [ 0 0] [0 0] [ 0 0]
166 [0 0], [1 0], [-1 0], [0 1], [ 0 -1]
171 Each positive operator generator should send the generators of one
172 cone into the other cone::
174 sage: set_random_seed()
175 sage: K1 = random_cone(max_ambient_dim=4)
176 sage: K2 = random_cone(max_ambient_dim=4)
177 sage: pi_K1_K2 = positive_operator_gens(K1,K2)
178 sage: all([ K2.contains(P*x) for P in pi_K1_K2 for x in K1 ])
181 Each positive operator generator should send a random element of one
182 cone into the other cone::
184 sage: set_random_seed()
185 sage: K1 = random_cone(max_ambient_dim=4)
186 sage: K2 = random_cone(max_ambient_dim=4)
187 sage: pi_K1_K2 = positive_operator_gens(K1,K2)
188 sage: all([ K2.contains(P*K1.random_element(QQ)) for P in pi_K1_K2 ])
191 A random element of the positive operator cone should send the
192 generators of one cone into the other cone::
194 sage: set_random_seed()
195 sage: K1 = random_cone(max_ambient_dim=4)
196 sage: K2 = random_cone(max_ambient_dim=4)
197 sage: pi_K1_K2 = positive_operator_gens(K1,K2)
198 sage: L = ToricLattice(K1.lattice_dim() * K2.lattice_dim())
199 sage: pi_cone = Cone([ g.list() for g in pi_K1_K2 ],
202 sage: P = matrix(K2.lattice_dim(),
203 ....: K1.lattice_dim(),
204 ....: pi_cone.random_element(QQ).list())
205 sage: all([ K2.contains(P*x) for x in K1 ])
208 A random element of the positive operator cone should send a random
209 element of one cone into the other cone::
211 sage: set_random_seed()
212 sage: K1 = random_cone(max_ambient_dim=4)
213 sage: K2 = random_cone(max_ambient_dim=4)
214 sage: pi_K1_K2 = positive_operator_gens(K1,K2)
215 sage: L = ToricLattice(K1.lattice_dim() * K2.lattice_dim())
216 sage: pi_cone = Cone([ g.list() for g in pi_K1_K2 ],
219 sage: P = matrix(K2.lattice_dim(),
220 ....: K1.lattice_dim(),
221 ....: pi_cone.random_element(QQ).list())
222 sage: K2.contains(P*K1.random_element(ring=QQ))
225 The lineality space of the dual of the cone of positive operators
226 can be computed from the lineality spaces of the cone and its dual::
228 sage: set_random_seed()
229 sage: K = random_cone(max_ambient_dim=4)
230 sage: pi_of_K = positive_operator_gens(K)
231 sage: L = ToricLattice(K.lattice_dim()**2)
232 sage: pi_cone = Cone([ g.list() for g in pi_of_K ],
235 sage: actual = pi_cone.dual().linear_subspace()
236 sage: U1 = [ vector((s.tensor_product(x)).list())
237 ....: for x in K.lines()
238 ....: for s in K.dual() ]
239 sage: U2 = [ vector((s.tensor_product(x)).list())
241 ....: for s in K.dual().lines() ]
242 sage: expected = pi_cone.lattice().vector_space().span(U1 + U2)
243 sage: actual == expected
246 The lineality of the dual of the cone of positive operators
247 is known from its lineality space::
249 sage: set_random_seed()
250 sage: K = random_cone(max_ambient_dim=4)
251 sage: n = K.lattice_dim()
253 sage: l = K.lineality()
254 sage: pi_of_K = positive_operator_gens(K)
255 sage: L = ToricLattice(n**2)
256 sage: pi_cone = Cone([p.list() for p in pi_of_K],
259 sage: actual = pi_cone.dual().lineality()
260 sage: expected = l*(m - l) + m*(n - m)
261 sage: actual == expected
264 The dimension of the cone of positive operators is given by the
265 corollary in my paper::
267 sage: set_random_seed()
268 sage: K = random_cone(max_ambient_dim=4)
269 sage: n = K.lattice_dim()
271 sage: l = K.lineality()
272 sage: pi_of_K = positive_operator_gens(K)
273 sage: L = ToricLattice(n**2)
274 sage: pi_cone = Cone([p.list() for p in pi_of_K],
277 sage: actual = pi_cone.dim()
278 sage: expected = n**2 - l*(m - l) - (n - m)*m
279 sage: actual == expected
282 The trivial cone, full space, and half-plane all give rise to the
283 expected dimensions::
285 sage: n = ZZ.random_element().abs()
286 sage: K = Cone([[0] * n], ToricLattice(n))
289 sage: L = ToricLattice(n^2)
290 sage: pi_of_K = positive_operator_gens(K)
291 sage: pi_cone = Cone([p.list() for p in pi_of_K],
294 sage: actual = pi_cone.dim()
298 sage: K.is_full_space()
300 sage: pi_of_K = positive_operator_gens(K)
301 sage: pi_cone = Cone([p.list() for p in pi_of_K],
304 sage: actual = pi_cone.dim()
307 sage: K = Cone([(1,0),(0,1),(0,-1)])
308 sage: pi_of_K = positive_operator_gens(K)
309 sage: actual = Cone([p.list() for p in pi_of_K], check=False).dim()
313 The lineality of the cone of positive operators follows from the
314 description of its generators::
316 sage: set_random_seed()
317 sage: K = random_cone(max_ambient_dim=4)
318 sage: n = K.lattice_dim()
319 sage: pi_of_K = positive_operator_gens(K)
320 sage: L = ToricLattice(n**2)
321 sage: pi_cone = Cone([p.list() for p in pi_of_K],
324 sage: actual = pi_cone.lineality()
325 sage: expected = n**2 - K.dim()*K.dual().dim()
326 sage: actual == expected
329 The trivial cone, full space, and half-plane all give rise to the
330 expected linealities::
332 sage: n = ZZ.random_element().abs()
333 sage: K = Cone([[0] * n], ToricLattice(n))
336 sage: L = ToricLattice(n^2)
337 sage: pi_of_K = positive_operator_gens(K)
338 sage: pi_cone = Cone([p.list() for p in pi_of_K],
341 sage: actual = pi_cone.lineality()
345 sage: K.is_full_space()
347 sage: pi_of_K = positive_operator_gens(K)
348 sage: pi_cone = Cone([p.list() for p in pi_of_K], lattice=L)
349 sage: pi_cone.lineality() == n^2
351 sage: K = Cone([(1,0),(0,1),(0,-1)])
352 sage: pi_of_K = positive_operator_gens(K)
353 sage: pi_cone = Cone([p.list() for p in pi_of_K], check=False)
354 sage: actual = pi_cone.lineality()
358 A cone is proper if and only if its cone of positive operators
361 sage: set_random_seed()
362 sage: K = random_cone(max_ambient_dim=4)
363 sage: pi_of_K = positive_operator_gens(K)
364 sage: L = ToricLattice(K.lattice_dim()**2)
365 sage: pi_cone = Cone([p.list() for p in pi_of_K],
368 sage: K.is_proper() == pi_cone.is_proper()
371 The positive operators of a permuted cone can be obtained by
374 sage: set_random_seed()
375 sage: K = random_cone(max_ambient_dim=4)
376 sage: L = ToricLattice(K.lattice_dim()**2)
377 sage: p = SymmetricGroup(K.lattice_dim()).random_element().matrix()
378 sage: pK = Cone([ p*k for k in K ], K.lattice(), check=False)
379 sage: pi_of_pK = positive_operator_gens(pK)
380 sage: actual = Cone([t.list() for t in pi_of_pK],
383 sage: pi_of_K = positive_operator_gens(K)
384 sage: expected = Cone([(p*t*p.inverse()).list() for t in pi_of_K],
387 sage: actual.is_equivalent(expected)
390 A transformation is positive on a cone if and only if its adjoint is
391 positive on the dual of that cone::
393 sage: set_random_seed()
394 sage: K = random_cone(max_ambient_dim=4)
395 sage: F = K.lattice().vector_space().base_field()
396 sage: n = K.lattice_dim()
397 sage: L = ToricLattice(n**2)
398 sage: W = VectorSpace(F, n**2)
399 sage: pi_of_K = positive_operator_gens(K)
400 sage: pi_of_K_star = positive_operator_gens(K.dual())
401 sage: pi_cone = Cone([p.list() for p in pi_of_K],
404 sage: pi_star = Cone([p.list() for p in pi_of_K_star],
407 sage: M = MatrixSpace(F, n)
408 sage: L = M(pi_cone.random_element(ring=QQ).list())
409 sage: pi_star.contains(W(L.transpose().list()))
412 sage: L = W.random_element()
413 sage: L_star = W(M(L.list()).transpose().list())
414 sage: pi_cone.contains(L) == pi_star.contains(L_star)
417 The Lyapunov rank of the positive operator cone is the product of
418 the Lyapunov ranks of the associated cones if they're all proper::
420 sage: K1 = random_cone(max_ambient_dim=4,
421 ....: strictly_convex=True,
423 sage: K2 = random_cone(max_ambient_dim=4,
424 ....: strictly_convex=True,
426 sage: pi_K1_K2 = positive_operator_gens(K1,K2)
427 sage: L = ToricLattice(K1.lattice_dim() * K2.lattice_dim())
428 sage: pi_cone = Cone([ g.list() for g in pi_K1_K2 ],
431 sage: beta1 = K1.lyapunov_rank()
432 sage: beta2 = K2.lyapunov_rank()
433 sage: pi_cone.lyapunov_rank() == beta1*beta2
436 The Lyapunov-like operators on a proper polyhedral positive operator
437 cone can be computed from the Lyapunov-like operators on the cones
438 with respect to which the operators are positive::
440 sage: K1 = random_cone(max_ambient_dim=4,
441 ....: strictly_convex=True,
443 sage: K2 = random_cone(max_ambient_dim=4,
444 ....: strictly_convex=True,
446 sage: pi_K1_K2 = positive_operator_gens(K1,K2)
447 sage: F = K1.lattice().base_field()
448 sage: m = K1.lattice_dim()
449 sage: n = K2.lattice_dim()
450 sage: L = ToricLattice(m*n)
451 sage: M1 = MatrixSpace(F, m, m)
452 sage: M2 = MatrixSpace(F, n, n)
453 sage: LL_K1 = [ M1(x.list()) for x in K1.dual().lyapunov_like_basis() ]
454 sage: LL_K2 = [ M2(x.list()) for x in K2.lyapunov_like_basis() ]
455 sage: tps = [ s.tensor_product(x) for x in LL_K1 for s in LL_K2 ]
456 sage: W = VectorSpace(F, (m**2)*(n**2))
457 sage: expected = span(F, [ W(x.list()) for x in tps ])
458 sage: pi_cone = Cone([p.list() for p in pi_K1_K2],
461 sage: LL_pi = pi_cone.lyapunov_like_basis()
462 sage: actual = span(F, [ W(x.list()) for x in LL_pi ])
463 sage: actual == expected
470 # Matrices are not vectors in Sage, so we have to convert them
471 # to vectors explicitly before we can find a basis. We need these
472 # two values to construct the appropriate "long vector" space.
473 F
= K1
.lattice().base_field()
477 tensor_products
= [ s
.tensor_product(x
) for x
in K1
for s
in K2
.dual() ]
479 # Convert those tensor products to long vectors.
480 W
= VectorSpace(F
, n
*m
)
481 vectors
= [ W(tp
.list()) for tp
in tensor_products
]
484 if K1
.is_proper() and K2
.is_proper():
485 # All of the generators involved are extreme vectors and
486 # therefore minimal. If this cone is neither solid nor
487 # strictly convex, then the tensor product of ``s`` and ``x``
488 # is the same as that of ``-s`` and ``-x``. However, as a
489 # /set/, ``tensor_products`` may still be minimal.
492 # Create the dual cone of the positive operators, expressed as
494 pi_dual
= Cone(vectors
, ToricLattice(W
.dimension()), check
=check
)
496 # Now compute the desired cone from its dual...
497 pi_cone
= pi_dual
.dual()
499 # And finally convert its rays back to matrix representations.
500 M
= MatrixSpace(F
, m
, n
)
501 return [ M(v
.list()) for v
in pi_cone
]
504 def cross_positive_operator_gens(K
):
506 Compute generators of the cone of cross-positive operators on this
511 A list of `n`-by-``n`` matrices where ``n == K.lattice_dim()``.
512 Each matrix ``L`` in the list should have the property that
513 ``(L*x).inner_product(s) >= 0`` whenever ``(x,s)`` is an element of
514 this cone's :meth:`discrete_complementarity_set`. Moreover, any
515 conic (nonnegative linear) combination of these matrices shares the
520 :meth:`positive_operator_gens`, :meth:`Z_operator_gens`,
524 Cross-positive operators on the nonnegative orthant are negations
525 of Z-matrices; that is, matrices whose off-diagonal elements are
528 sage: K = Cone([(1,0),(0,1)])
529 sage: cross_positive_operator_gens(K)
531 [0 1] [0 0] [1 0] [-1 0] [0 0] [ 0 0]
532 [0 0], [1 0], [0 0], [ 0 0], [0 1], [ 0 -1]
534 sage: K = Cone([(1,0,0,0),(0,1,0,0),(0,0,1,0),(0,0,0,1)])
535 sage: all([ c[i][j] >= 0 for c in cross_positive_operator_gens(K)
536 ....: for i in range(c.nrows())
537 ....: for j in range(c.ncols())
541 The trivial cone in a trivial space has no cross-positive operators::
543 sage: K = Cone([], ToricLattice(0))
544 sage: cross_positive_operator_gens(K)
547 Every operator is a cross-positive operator on the ambient vector
550 sage: K = Cone([(1,),(-1,)])
551 sage: K.is_full_space()
553 sage: cross_positive_operator_gens(K)
556 sage: K = Cone([(1,0),(-1,0),(0,1),(0,-1)])
557 sage: K.is_full_space()
559 sage: cross_positive_operator_gens(K)
561 [1 0] [-1 0] [0 1] [ 0 -1] [0 0] [ 0 0] [0 0] [ 0 0]
562 [0 0], [ 0 0], [0 0], [ 0 0], [1 0], [-1 0], [0 1], [ 0 -1]
565 A non-obvious application is to find the cross-positive operators
566 on the right half-plane::
568 sage: K = Cone([(1,0),(0,1),(0,-1)])
569 sage: cross_positive_operator_gens(K)
571 [1 0] [-1 0] [0 0] [ 0 0] [0 0] [ 0 0]
572 [0 0], [ 0 0], [1 0], [-1 0], [0 1], [ 0 -1]
575 Cross-positive operators on a subspace are Lyapunov-like and
578 sage: K = Cone([(1,0),(-1,0),(0,1),(0,-1)])
579 sage: K.is_full_space()
581 sage: lls = span([ vector(l.list()) for l in K.lyapunov_like_basis() ])
582 sage: cs = span([ vector(c.list()) for c in cross_positive_operator_gens(K) ])
588 The cross-positive property is possessed by every cross-positive
591 sage: set_random_seed()
592 sage: K = random_cone(max_ambient_dim=4)
593 sage: Sigma_of_K = cross_positive_operator_gens(K)
594 sage: dcs = K.discrete_complementarity_set()
595 sage: all([(c*x).inner_product(s) >= 0 for c in Sigma_of_K
596 ....: for (x,s) in dcs])
599 The lineality space of the cone of cross-positive operators is the
600 space of Lyapunov-like operators::
602 sage: set_random_seed()
603 sage: K = random_cone(max_ambient_dim=4)
604 sage: L = ToricLattice(K.lattice_dim()**2)
605 sage: Sigma_cone = Cone([ c.list() for c in cross_positive_operator_gens(K) ],
608 sage: ll_basis = [ vector(l.list()) for l in K.lyapunov_like_basis() ]
609 sage: lls = L.vector_space().span(ll_basis)
610 sage: Sigma_cone.linear_subspace() == lls
613 The lineality of the cross-positive operators on a cone is the
614 Lyapunov rank of that cone::
616 sage: set_random_seed()
617 sage: K = random_cone(max_ambient_dim=4)
618 sage: Sigma_of_K = cross_positive_operator_gens(K)
619 sage: L = ToricLattice(K.lattice_dim()**2)
620 sage: Sigma_cone = Cone([ c.list() for c in Sigma_of_K ],
623 sage: Sigma_cone.lineality() == K.lyapunov_rank()
626 The lineality spaces of the duals of the positive and cross-positive
627 operator cones are equal. From this it follows that the dimensions of
628 the cross-positive operator cone and positive operator cone are equal::
630 sage: set_random_seed()
631 sage: K = random_cone(max_ambient_dim=4)
632 sage: pi_of_K = positive_operator_gens(K)
633 sage: Sigma_of_K = cross_positive_operator_gens(K)
634 sage: L = ToricLattice(K.lattice_dim()**2)
635 sage: pi_cone = Cone([p.list() for p in pi_of_K],
638 sage: Sigma_cone = Cone([ c.list() for c in Sigma_of_K],
641 sage: pi_cone.dim() == Sigma_cone.dim()
643 sage: pi_star = pi_cone.dual()
644 sage: sigma_star = Sigma_cone.dual()
645 sage: pi_star.linear_subspace() == sigma_star.linear_subspace()
648 The trivial cone, full space, and half-plane all give rise to the
649 expected dimensions::
651 sage: n = ZZ.random_element().abs()
652 sage: K = Cone([[0] * n], ToricLattice(n))
655 sage: L = ToricLattice(n^2)
656 sage: Sigma_of_K = cross_positive_operator_gens(K)
657 sage: Sigma_cone = Cone([c.list() for c in Sigma_of_K],
660 sage: actual = Sigma_cone.dim()
664 sage: K.is_full_space()
666 sage: Sigma_of_K = cross_positive_operator_gens(K)
667 sage: Sigma_cone = Cone([ c.list() for c in Sigma_of_K ],
670 sage: actual = Sigma_cone.dim()
673 sage: K = Cone([(1,0),(0,1),(0,-1)])
674 sage: Sigma_of_K = cross_positive_operator_gens(K)
675 sage: Sigma_cone = Cone([ c.list() for c in Sigma_of_K ], check=False)
676 sage: Sigma_cone.dim() == 3
679 The cross-positive operators of a permuted cone can be obtained by
682 sage: set_random_seed()
683 sage: K = random_cone(max_ambient_dim=4)
684 sage: L = ToricLattice(K.lattice_dim()**2)
685 sage: p = SymmetricGroup(K.lattice_dim()).random_element().matrix()
686 sage: pK = Cone([ p*k for k in K ], K.lattice(), check=False)
687 sage: Sigma_of_pK = cross_positive_operator_gens(pK)
688 sage: actual = Cone([t.list() for t in Sigma_of_pK],
691 sage: Sigma_of_K = cross_positive_operator_gens(K)
692 sage: expected = Cone([ (p*t*p.inverse()).list() for t in Sigma_of_K ],
695 sage: actual.is_equivalent(expected)
698 An operator is cross-positive on a cone if and only if its
699 adjoint is cross-positive on the dual of that cone::
701 sage: set_random_seed()
702 sage: K = random_cone(max_ambient_dim=4)
703 sage: F = K.lattice().vector_space().base_field()
704 sage: n = K.lattice_dim()
705 sage: L = ToricLattice(n**2)
706 sage: W = VectorSpace(F, n**2)
707 sage: Sigma_of_K = cross_positive_operator_gens(K)
708 sage: Sigma_of_K_star = cross_positive_operator_gens(K.dual())
709 sage: Sigma_cone = Cone([ p.list() for p in Sigma_of_K ],
712 sage: Sigma_star = Cone([ p.list() for p in Sigma_of_K_star ],
715 sage: M = MatrixSpace(F, n)
716 sage: L = M(Sigma_cone.random_element(ring=QQ).list())
717 sage: Sigma_star.contains(W(L.transpose().list()))
720 sage: L = W.random_element()
721 sage: L_star = W(M(L.list()).transpose().list())
722 sage: Sigma_cone.contains(L) == Sigma_star.contains(L_star)
725 # Matrices are not vectors in Sage, so we have to convert them
726 # to vectors explicitly before we can find a basis. We need these
727 # two values to construct the appropriate "long vector" space.
728 F
= K
.lattice().base_field()
731 # These tensor products contain generators for the dual cone of
732 # the cross-positive operators.
733 tensor_products
= [ s
.tensor_product(x
)
734 for (x
,s
) in K
.discrete_complementarity_set() ]
736 # Turn our matrices into long vectors...
737 W
= VectorSpace(F
, n
**2)
738 vectors
= [ W(m
.list()) for m
in tensor_products
]
742 # All of the generators involved are extreme vectors and
743 # therefore minimal. If this cone is neither solid nor
744 # strictly convex, then the tensor product of ``s`` and ``x``
745 # is the same as that of ``-s`` and ``-x``. However, as a
746 # /set/, ``tensor_products`` may still be minimal.
749 # Create the dual cone of the cross-positive operators,
750 # expressed as long vectors.
751 Sigma_dual
= Cone(vectors
, lattice
=ToricLattice(W
.dimension()), check
=check
)
753 # Now compute the desired cone from its dual...
754 Sigma_cone
= Sigma_dual
.dual()
756 # And finally convert its rays back to matrix representations.
757 M
= MatrixSpace(F
, n
)
758 return [ M(v
.list()) for v
in Sigma_cone
]
761 def Z_operator_gens(K
):
763 Compute generators of the cone of Z-operators on this cone.
765 The Z-operators on a cone generalize the Z-matrices over the
766 nonnegative orthant. They are simply negations of the
767 :meth:`cross_positive_operators`.
771 A list of `n`-by-``n`` matrices where ``n == K.lattice_dim()``.
772 Each matrix ``L`` in the list should have the property that
773 ``(L*x).inner_product(s) <= 0`` whenever ``(x,s)`` is an element of
774 this cone's :meth:`discrete_complementarity_set`. Moreover, any
775 conic (nonnegative linear) combination of these matrices shares the
780 :meth:`positive_operator_gens`, :meth:`cross_positive_operator_gens`,
784 The Z-property is possessed by every Z-operator::
786 sage: set_random_seed()
787 sage: K = random_cone(max_ambient_dim=4)
788 sage: Z_of_K = Z_operator_gens(K)
789 sage: dcs = K.discrete_complementarity_set()
790 sage: all([(z*x).inner_product(s) <= 0 for z in Z_of_K
791 ....: for (x,s) in dcs])
794 return [ -cp
for cp
in cross_positive_operator_gens(K
) ]
798 gens
= K
.lyapunov_like_basis()
799 L
= ToricLattice(K
.lattice_dim()**2)
800 return Cone([ g
.list() for g
in gens
], lattice
=L
, check
=False)
803 gens
= cross_positive_operator_gens(K
)
804 L
= ToricLattice(K
.lattice_dim()**2)
805 return Cone([ g
.list() for g
in gens
], lattice
=L
, check
=False)
808 gens
= Z_operator_gens(K
)
809 L
= ToricLattice(K
.lattice_dim()**2)
810 return Cone([ g
.list() for g
in gens
], lattice
=L
, check
=False)
813 gens
= positive_operator_gens(K
)
814 L
= ToricLattice(K
.lattice_dim()**2)
815 return Cone([ g
.list() for g
in gens
], lattice
=L
, check
=False)