]> gitweb.michael.orlitzky.com - sage.d.git/blob - mjo/cone/cone.py
Cite Stoer & Witzgall for the Motzkin decomposition.
[sage.d.git] / mjo / cone / cone.py
1 from sage.all import *
2
3 def is_lyapunov_like(L,K):
4 r"""
5 Determine whether or not ``L`` is Lyapunov-like on ``K``.
6
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.
12
13 INPUT:
14
15 - ``L`` -- A linear transformation or matrix.
16
17 - ``K`` -- A polyhedral closed convex cone.
18
19 OUTPUT:
20
21 ``True`` if it can be proven that ``L`` is Lyapunov-like on ``K``,
22 and ``False`` otherwise.
23
24 .. WARNING::
25
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
31 product is zero.
32
33 REFERENCES:
34
35 M. Orlitzky. The Lyapunov rank of an improper cone.
36 http://www.optimization-online.org/DB_HTML/2015/10/5135.html
37
38 EXAMPLES:
39
40 The identity is always Lyapunov-like in a nontrivial space::
41
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)
46 True
47
48 As is the "zero" transformation::
49
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)
54 True
55
56 Everything in ``K.lyapunov_like_basis()`` should be Lyapunov-like
57 on ``K``::
58
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() ])
61 True
62
63 """
64 return all([(L*x).inner_product(s) == 0
65 for (x,s) in K.discrete_complementarity_set()])
66
67
68 def motzkin_decomposition(K):
69 r"""
70 Return the pair of components in the Motzkin decomposition of this cone.
71
72 Every convex cone is the direct sum of a strictly convex cone and a
73 linear subspace [Stoer-Witzgall]_. Return a pair ``(P,S)`` of cones
74 such that ``P`` is strictly convex, ``S`` is a subspace, and ``K``
75 is the direct sum of ``P`` and ``S``.
76
77 OUTPUT:
78
79 An ordered pair ``(P,S)`` of closed convex polyhedral cones where
80 ``P`` is strictly convex, ``S`` is a subspace, and ``K`` is the
81 direct sum of ``P`` and ``S``.
82
83 REFERENCES:
84
85 .. [Stoer-Witzgall] J. Stoer and C. Witzgall. Convexity and
86 Optimization in Finite Dimensions I. Springer-Verlag, New
87 York, 1970.
88
89 EXAMPLES:
90
91 The nonnegative orthant is strictly convex, so it is its own
92 strictly convex component and its subspace component is trivial::
93
94 sage: K = Cone([(1,0,0),(0,1,0),(0,0,1)])
95 sage: (P,S) = motzkin_decomposition(K)
96 sage: K.is_equivalent(P)
97 True
98 sage: S.is_trivial()
99 True
100
101 Likewise, full spaces are their own subspace components::
102
103 sage: K = Cone([(1,0),(-1,0),(0,1),(0,-1)])
104 sage: K.is_full_space()
105 True
106 sage: (P,S) = motzkin_decomposition(K)
107 sage: K.is_equivalent(S)
108 True
109 sage: P.is_trivial()
110 True
111
112 TESTS:
113
114 A random point in the cone should belong to either the strictly
115 convex component or the subspace component. If the point is nonzero,
116 it cannot be in both::
117
118 sage: set_random_seed()
119 sage: K = random_cone(max_ambient_dim=8)
120 sage: (P,S) = motzkin_decomposition(K)
121 sage: x = K.random_element()
122 sage: P.contains(x) or S.contains(x)
123 True
124 sage: x.is_zero() or (P.contains(x) != S.contains(x))
125 True
126
127 The strictly convex component should always be strictly convex, and
128 the subspace component should always be a subspace::
129
130 sage: set_random_seed()
131 sage: K = random_cone(max_ambient_dim=8)
132 sage: (P,S) = motzkin_decomposition(K)
133 sage: P.is_strictly_convex()
134 True
135 sage: S.lineality() == S.dim()
136 True
137
138 The generators of the components are obtained from orthogonal
139 projections of the original generators [Stoer-Witzgall]_::
140
141 sage: set_random_seed()
142 sage: K = random_cone(max_ambient_dim=8)
143 sage: (P,S) = motzkin_decomposition(K)
144 sage: A = S.linear_subspace().complement().matrix()
145 sage: proj_S_perp = A.transpose() * (A*A.transpose()).inverse() * A
146 sage: expected_P = Cone([ proj_S_perp*g for g in K ], K.lattice())
147 sage: P.is_equivalent(expected_P)
148 True
149 sage: A = S.linear_subspace().matrix()
150 sage: proj_S = A.transpose() * (A*A.transpose()).inverse() * A
151 sage: expected_S = Cone([ proj_S*g for g in K ], K.lattice())
152 sage: S.is_equivalent(expected_S)
153 True
154 """
155 linspace_gens = [ copy(b) for b in K.linear_subspace().basis() ]
156 linspace_gens += [ -b for b in linspace_gens ]
157
158 S = Cone(linspace_gens, K.lattice())
159
160 # Since ``S`` is a subspace, its dual is its orthogonal complement
161 # (albeit in the wrong lattice).
162 S_perp = Cone(S.dual(), K.lattice())
163 P = K.intersection(S_perp)
164
165 return (P,S)
166
167 def positive_operator_gens(K):
168 r"""
169 Compute generators of the cone of positive operators on this cone.
170
171 OUTPUT:
172
173 A list of `n`-by-``n`` matrices where ``n == K.lattice_dim()``.
174 Each matrix ``P`` in the list should have the property that ``P*x``
175 is an element of ``K`` whenever ``x`` is an element of
176 ``K``. Moreover, any nonnegative linear combination of these
177 matrices shares the same property.
178
179 EXAMPLES:
180
181 The trivial cone in a trivial space has no positive operators::
182
183 sage: K = Cone([], ToricLattice(0))
184 sage: positive_operator_gens(K)
185 []
186
187 Positive operators on the nonnegative orthant are nonnegative matrices::
188
189 sage: K = Cone([(1,)])
190 sage: positive_operator_gens(K)
191 [[1]]
192
193 sage: K = Cone([(1,0),(0,1)])
194 sage: positive_operator_gens(K)
195 [
196 [1 0] [0 1] [0 0] [0 0]
197 [0 0], [0 0], [1 0], [0 1]
198 ]
199
200 Every operator is positive on the ambient vector space::
201
202 sage: K = Cone([(1,),(-1,)])
203 sage: K.is_full_space()
204 True
205 sage: positive_operator_gens(K)
206 [[1], [-1]]
207
208 sage: K = Cone([(1,0),(-1,0),(0,1),(0,-1)])
209 sage: K.is_full_space()
210 True
211 sage: positive_operator_gens(K)
212 [
213 [1 0] [-1 0] [0 1] [ 0 -1] [0 0] [ 0 0] [0 0] [ 0 0]
214 [0 0], [ 0 0], [0 0], [ 0 0], [1 0], [-1 0], [0 1], [ 0 -1]
215 ]
216
217 TESTS:
218
219 A positive operator on a cone should send its generators into the cone::
220
221 sage: set_random_seed()
222 sage: K = random_cone(max_ambient_dim=5)
223 sage: pi_of_K = positive_operator_gens(K)
224 sage: all([K.contains(p*x) for p in pi_of_K for x in K.rays()])
225 True
226
227 The dimension of the cone of positive operators is given by the
228 corollary in my paper::
229
230 sage: set_random_seed()
231 sage: K = random_cone(max_ambient_dim=5)
232 sage: n = K.lattice_dim()
233 sage: m = K.dim()
234 sage: l = K.lineality()
235 sage: pi_of_K = positive_operator_gens(K)
236 sage: L = ToricLattice(n**2)
237 sage: actual = Cone([p.list() for p in pi_of_K], lattice=L).dim()
238 sage: expected = n**2 - l*(m - l) - (n - m)*m
239 sage: actual == expected
240 True
241
242 The lineality of the cone of positive operators is given by the
243 corollary in my paper::
244
245 sage: set_random_seed()
246 sage: K = random_cone(max_ambient_dim=5)
247 sage: n = K.lattice_dim()
248 sage: pi_of_K = positive_operator_gens(K)
249 sage: L = ToricLattice(n**2)
250 sage: actual = Cone([p.list() for p in pi_of_K], lattice=L).lineality()
251 sage: expected = n**2 - K.dim()*K.dual().dim()
252 sage: actual == expected
253 True
254
255 The cone ``K`` is proper if and only if the cone of positive
256 operators on ``K`` is proper::
257
258 sage: set_random_seed()
259 sage: K = random_cone(max_ambient_dim=5)
260 sage: pi_of_K = positive_operator_gens(K)
261 sage: L = ToricLattice(K.lattice_dim()**2)
262 sage: pi_cone = Cone([p.list() for p in pi_of_K], lattice=L)
263 sage: K.is_proper() == pi_cone.is_proper()
264 True
265 """
266 # Matrices are not vectors in Sage, so we have to convert them
267 # to vectors explicitly before we can find a basis. We need these
268 # two values to construct the appropriate "long vector" space.
269 F = K.lattice().base_field()
270 n = K.lattice_dim()
271
272 tensor_products = [ s.tensor_product(x) for x in K for s in K.dual() ]
273
274 # Convert those tensor products to long vectors.
275 W = VectorSpace(F, n**2)
276 vectors = [ W(tp.list()) for tp in tensor_products ]
277
278 # Create the *dual* cone of the positive operators, expressed as
279 # long vectors..
280 pi_dual = Cone(vectors, ToricLattice(W.dimension()))
281
282 # Now compute the desired cone from its dual...
283 pi_cone = pi_dual.dual()
284
285 # And finally convert its rays back to matrix representations.
286 M = MatrixSpace(F, n)
287 return [ M(v.list()) for v in pi_cone.rays() ]
288
289
290 def Z_transformation_gens(K):
291 r"""
292 Compute generators of the cone of Z-transformations on this cone.
293
294 OUTPUT:
295
296 A list of `n`-by-``n`` matrices where ``n == K.lattice_dim()``.
297 Each matrix ``L`` in the list should have the property that
298 ``(L*x).inner_product(s) <= 0`` whenever ``(x,s)`` is an element the
299 discrete complementarity set of ``K``. Moreover, any nonnegative
300 linear combination of these matrices shares the same property.
301
302 EXAMPLES:
303
304 Z-transformations on the nonnegative orthant are just Z-matrices.
305 That is, matrices whose off-diagonal elements are nonnegative::
306
307 sage: K = Cone([(1,0),(0,1)])
308 sage: Z_transformation_gens(K)
309 [
310 [ 0 -1] [ 0 0] [-1 0] [1 0] [ 0 0] [0 0]
311 [ 0 0], [-1 0], [ 0 0], [0 0], [ 0 -1], [0 1]
312 ]
313 sage: K = Cone([(1,0,0,0),(0,1,0,0),(0,0,1,0),(0,0,0,1)])
314 sage: all([ z[i][j] <= 0 for z in Z_transformation_gens(K)
315 ....: for i in range(z.nrows())
316 ....: for j in range(z.ncols())
317 ....: if i != j ])
318 True
319
320 The trivial cone in a trivial space has no Z-transformations::
321
322 sage: K = Cone([], ToricLattice(0))
323 sage: Z_transformation_gens(K)
324 []
325
326 Z-transformations on a subspace are Lyapunov-like and vice-versa::
327
328 sage: K = Cone([(1,0),(-1,0),(0,1),(0,-1)])
329 sage: K.is_full_space()
330 True
331 sage: lls = span([ vector(l.list()) for l in K.lyapunov_like_basis() ])
332 sage: zs = span([ vector(z.list()) for z in Z_transformation_gens(K) ])
333 sage: zs == lls
334 True
335
336 TESTS:
337
338 The Z-property is possessed by every Z-transformation::
339
340 sage: set_random_seed()
341 sage: K = random_cone(max_ambient_dim=6)
342 sage: Z_of_K = Z_transformation_gens(K)
343 sage: dcs = K.discrete_complementarity_set()
344 sage: all([(z*x).inner_product(s) <= 0 for z in Z_of_K
345 ....: for (x,s) in dcs])
346 True
347
348 The lineality space of Z is LL::
349
350 sage: set_random_seed()
351 sage: K = random_cone(min_ambient_dim=1, max_ambient_dim=6)
352 sage: lls = span([ vector(l.list()) for l in K.lyapunov_like_basis() ])
353 sage: z_cone = Cone([ z.list() for z in Z_transformation_gens(K) ])
354 sage: z_cone.linear_subspace() == lls
355 True
356
357 And thus, the lineality of Z is the Lyapunov rank::
358
359 sage: set_random_seed()
360 sage: K = random_cone(max_ambient_dim=6)
361 sage: Z_of_K = Z_transformation_gens(K)
362 sage: L = ToricLattice(K.lattice_dim()**2)
363 sage: z_cone = Cone([ z.list() for z in Z_of_K ], lattice=L)
364 sage: z_cone.lineality() == K.lyapunov_rank()
365 True
366
367 The lineality spaces of pi-star and Z-star are equal:
368
369 sage: set_random_seed()
370 sage: K = random_cone(max_ambient_dim=5)
371 sage: pi_of_K = positive_operator_gens(K)
372 sage: Z_of_K = Z_transformation_gens(K)
373 sage: L = ToricLattice(K.lattice_dim()**2)
374 sage: pi_star = Cone([p.list() for p in pi_of_K], lattice=L).dual()
375 sage: z_star = Cone([ z.list() for z in Z_of_K], lattice=L).dual()
376 sage: pi_star.linear_subspace() == z_star.linear_subspace()
377 True
378 """
379 # Matrices are not vectors in Sage, so we have to convert them
380 # to vectors explicitly before we can find a basis. We need these
381 # two values to construct the appropriate "long vector" space.
382 F = K.lattice().base_field()
383 n = K.lattice_dim()
384
385 # These tensor products contain generators for the dual cone of
386 # the cross-positive transformations.
387 tensor_products = [ s.tensor_product(x)
388 for (x,s) in K.discrete_complementarity_set() ]
389
390 # Turn our matrices into long vectors...
391 W = VectorSpace(F, n**2)
392 vectors = [ W(m.list()) for m in tensor_products ]
393
394 # Create the *dual* cone of the cross-positive operators,
395 # expressed as long vectors..
396 Sigma_dual = Cone(vectors, lattice=ToricLattice(W.dimension()))
397
398 # Now compute the desired cone from its dual...
399 Sigma_cone = Sigma_dual.dual()
400
401 # And finally convert its rays back to matrix representations.
402 # But first, make them negative, so we get Z-transformations and
403 # not cross-positive ones.
404 M = MatrixSpace(F, n)
405 return [ -M(v.list()) for v in Sigma_cone.rays() ]
406
407
408 def Z_cone(K):
409 gens = Z_transformation_gens(K)
410 L = None
411 if len(gens) == 0:
412 L = ToricLattice(0)
413 return Cone([ g.list() for g in gens ], lattice=L)
414
415 def pi_cone(K):
416 gens = positive_operator_gens(K)
417 L = None
418 if len(gens) == 0:
419 L = ToricLattice(0)
420 return Cone([ g.list() for g in gens ], lattice=L)