]>
gitweb.michael.orlitzky.com - sage.d.git/blob - mjo/cone/cone.py
a5f5f2f4fcf1ac603a9d8d48a75a0924003bd8cf
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)
102 A random element of the nonnegative orthant should have all
103 components nonnegative::
105 sage: set_random_seed()
106 sage: K = Cone([(1,0,0),(0,1,0),(0,0,1)])
107 sage: all([ x >= 0 for x in random_element(K) ])
112 Any cone should contain a random element of itself::
114 sage: set_random_seed()
115 sage: K = random_cone(max_ambient_dim=8)
116 sage: K.contains(random_element(K))
119 A strictly convex cone contains no lines, and thus no negative
120 multiples of any of its elements besides zero::
122 sage: set_random_seed()
123 sage: K = random_cone(max_ambient_dim=8, strictly_convex=True)
124 sage: x = random_element(K)
125 sage: x.is_zero() or not K.contains(-x)
128 The sum of random elements of a cone lies in the cone::
130 sage: set_random_seed()
131 sage: K = random_cone(max_ambient_dim=8)
132 sage: K.contains(sum([random_element(K) for i in range(10)]))
136 V
= K
.lattice().vector_space()
137 scaled_gens
= [ V
.base_field().random_element().abs()*V(r
) for r
in K
]
139 # Make sure we return a vector. Without the coercion, we might
140 # return ``0`` when ``K`` has no rays.
141 return V(sum(scaled_gens
))
144 def positive_operator_gens(K
):
146 Compute generators of the cone of positive operators on this cone.
150 A list of `n`-by-``n`` matrices where ``n == K.lattice_dim()``.
151 Each matrix ``P`` in the list should have the property that ``P*x``
152 is an element of ``K`` whenever ``x`` is an element of
153 ``K``. Moreover, any nonnegative linear combination of these
154 matrices shares the same property.
158 The trivial cone in a trivial space has no positive operators::
160 sage: K = Cone([], ToricLattice(0))
161 sage: positive_operator_gens(K)
164 Positive operators on the nonnegative orthant are nonnegative matrices::
166 sage: K = Cone([(1,)])
167 sage: positive_operator_gens(K)
170 sage: K = Cone([(1,0),(0,1)])
171 sage: positive_operator_gens(K)
173 [1 0] [0 1] [0 0] [0 0]
174 [0 0], [0 0], [1 0], [0 1]
177 Every operator is positive on the ambient vector space::
179 sage: K = Cone([(1,),(-1,)])
180 sage: K.is_full_space()
182 sage: positive_operator_gens(K)
185 sage: K = Cone([(1,0),(-1,0),(0,1),(0,-1)])
186 sage: K.is_full_space()
188 sage: positive_operator_gens(K)
190 [1 0] [-1 0] [0 1] [ 0 -1] [0 0] [ 0 0] [0 0] [ 0 0]
191 [0 0], [ 0 0], [0 0], [ 0 0], [1 0], [-1 0], [0 1], [ 0 -1]
196 A positive operator on a cone should send its generators into the cone::
198 sage: set_random_seed()
199 sage: K = random_cone(max_ambient_dim=5)
200 sage: pi_of_K = positive_operator_gens(K)
201 sage: all([K.contains(p*x) for p in pi_of_K for x in K.rays()])
204 The dimension of the cone of positive operators is given by the
205 corollary in my paper::
207 sage: set_random_seed()
208 sage: K = random_cone(max_ambient_dim=5)
209 sage: n = K.lattice_dim()
211 sage: l = K.lineality()
212 sage: pi_of_K = positive_operator_gens(K)
213 sage: L = ToricLattice(n**2)
214 sage: actual = Cone([p.list() for p in pi_of_K], lattice=L).dim()
215 sage: expected = n**2 - l*(m - l) - (n - m)*m
216 sage: actual == expected
219 The lineality of the cone of positive operators is given by the
220 corollary in my paper::
222 sage: set_random_seed()
223 sage: K = random_cone(max_ambient_dim=5)
224 sage: n = K.lattice_dim()
225 sage: pi_of_K = positive_operator_gens(K)
226 sage: L = ToricLattice(n**2)
227 sage: actual = Cone([p.list() for p in pi_of_K], lattice=L).lineality()
228 sage: expected = n**2 - K.dim()*K.dual().dim()
229 sage: actual == expected
232 The cone ``K`` is proper if and only if the cone of positive
233 operators on ``K`` is proper::
235 sage: set_random_seed()
236 sage: K = random_cone(max_ambient_dim=5)
237 sage: pi_of_K = positive_operator_gens(K)
238 sage: L = ToricLattice(K.lattice_dim()**2)
239 sage: pi_cone = Cone([p.list() for p in pi_of_K], lattice=L)
240 sage: K.is_proper() == pi_cone.is_proper()
243 # Matrices are not vectors in Sage, so we have to convert them
244 # to vectors explicitly before we can find a basis. We need these
245 # two values to construct the appropriate "long vector" space.
246 F
= K
.lattice().base_field()
249 tensor_products
= [ s
.tensor_product(x
) for x
in K
for s
in K
.dual() ]
251 # Convert those tensor products to long vectors.
252 W
= VectorSpace(F
, n
**2)
253 vectors
= [ W(tp
.list()) for tp
in tensor_products
]
255 # Create the *dual* cone of the positive operators, expressed as
257 pi_dual
= Cone(vectors
, ToricLattice(W
.dimension()))
259 # Now compute the desired cone from its dual...
260 pi_cone
= pi_dual
.dual()
262 # And finally convert its rays back to matrix representations.
263 M
= MatrixSpace(F
, n
)
264 return [ M(v
.list()) for v
in pi_cone
.rays() ]
267 def Z_transformation_gens(K
):
269 Compute generators of the cone of Z-transformations on this cone.
273 A list of `n`-by-``n`` matrices where ``n == K.lattice_dim()``.
274 Each matrix ``L`` in the list should have the property that
275 ``(L*x).inner_product(s) <= 0`` whenever ``(x,s)`` is an element the
276 discrete complementarity set of ``K``. Moreover, any nonnegative
277 linear combination of these matrices shares the same property.
281 Z-transformations on the nonnegative orthant are just Z-matrices.
282 That is, matrices whose off-diagonal elements are nonnegative::
284 sage: K = Cone([(1,0),(0,1)])
285 sage: Z_transformation_gens(K)
287 [ 0 -1] [ 0 0] [-1 0] [1 0] [ 0 0] [0 0]
288 [ 0 0], [-1 0], [ 0 0], [0 0], [ 0 -1], [0 1]
290 sage: K = Cone([(1,0,0,0),(0,1,0,0),(0,0,1,0),(0,0,0,1)])
291 sage: all([ z[i][j] <= 0 for z in Z_transformation_gens(K)
292 ....: for i in range(z.nrows())
293 ....: for j in range(z.ncols())
297 The trivial cone in a trivial space has no Z-transformations::
299 sage: K = Cone([], ToricLattice(0))
300 sage: Z_transformation_gens(K)
303 Z-transformations on a subspace are Lyapunov-like and vice-versa::
305 sage: K = Cone([(1,0),(-1,0),(0,1),(0,-1)])
306 sage: K.is_full_space()
308 sage: lls = span([ vector(l.list()) for l in K.lyapunov_like_basis() ])
309 sage: zs = span([ vector(z.list()) for z in Z_transformation_gens(K) ])
315 The Z-property is possessed by every Z-transformation::
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: dcs = K.discrete_complementarity_set()
321 sage: all([(z*x).inner_product(s) <= 0 for z in Z_of_K
322 ....: for (x,s) in dcs])
325 The lineality space of Z is LL::
327 sage: set_random_seed()
328 sage: K = random_cone(min_ambient_dim=1, max_ambient_dim=6)
329 sage: lls = span([ vector(l.list()) for l in K.lyapunov_like_basis() ])
330 sage: z_cone = Cone([ z.list() for z in Z_transformation_gens(K) ])
331 sage: z_cone.linear_subspace() == lls
334 And thus, the lineality of Z is the Lyapunov rank::
336 sage: set_random_seed()
337 sage: K = random_cone(max_ambient_dim=6)
338 sage: Z_of_K = Z_transformation_gens(K)
339 sage: L = ToricLattice(K.lattice_dim()**2)
340 sage: z_cone = Cone([ z.list() for z in Z_of_K ], lattice=L)
341 sage: z_cone.lineality() == K.lyapunov_rank()
344 The lineality spaces of pi-star and Z-star are equal:
346 sage: set_random_seed()
347 sage: K = random_cone(max_ambient_dim=5)
348 sage: pi_of_K = positive_operator_gens(K)
349 sage: Z_of_K = Z_transformation_gens(K)
350 sage: L = ToricLattice(K.lattice_dim()**2)
351 sage: pi_star = Cone([p.list() for p in pi_of_K], lattice=L).dual()
352 sage: z_star = Cone([ z.list() for z in Z_of_K], lattice=L).dual()
353 sage: pi_star.linear_subspace() == z_star.linear_subspace()
356 # Matrices are not vectors in Sage, so we have to convert them
357 # to vectors explicitly before we can find a basis. We need these
358 # two values to construct the appropriate "long vector" space.
359 F
= K
.lattice().base_field()
362 # These tensor products contain generators for the dual cone of
363 # the cross-positive transformations.
364 tensor_products
= [ s
.tensor_product(x
)
365 for (x
,s
) in K
.discrete_complementarity_set() ]
367 # Turn our matrices into long vectors...
368 W
= VectorSpace(F
, n
**2)
369 vectors
= [ W(m
.list()) for m
in tensor_products
]
371 # Create the *dual* cone of the cross-positive operators,
372 # expressed as long vectors..
373 Sigma_dual
= Cone(vectors
, lattice
=ToricLattice(W
.dimension()))
375 # Now compute the desired cone from its dual...
376 Sigma_cone
= Sigma_dual
.dual()
378 # And finally convert its rays back to matrix representations.
379 # But first, make them negative, so we get Z-transformations and
380 # not cross-positive ones.
381 M
= MatrixSpace(F
, n
)
382 return [ -M(v
.list()) for v
in Sigma_cone
.rays() ]
386 gens
= Z_transformation_gens(K
)
390 return Cone([ g
.list() for g
in gens
], lattice
=L
)
393 gens
= positive_operator_gens(K
)
397 return Cone([ g
.list() for g
in gens
], lattice
=L
)