]>
gitweb.michael.orlitzky.com - dunshire.git/blob - test/randomgen.py
2 Random thing generators used in the rest of the test suite.
4 from random
import randint
, uniform
7 from cvxopt
import matrix
8 from dunshire
.cones
import NonnegativeOrthant
, IceCream
9 from dunshire
.games
import SymmetricLinearGame
10 from dunshire
.matrices
import (append_col
, append_row
, identity
)
14 The maximum condition number of a randomly-generated game. When the
15 condition number of the games gets too high, we start to see
16 :class:`PoorScalingException` being thrown. There's no science to
17 choosing the upper bound -- it got lowered until those exceptions
18 stopped popping up. It's at ``125`` because ``129`` doesn't work.
23 When generating random real numbers or integers, this is used as the
24 largest allowed magnitude. It keeps our condition numbers down and other
25 properties within reason.
30 Generate a random scalar.
36 A random real number between negative and positive
37 :const:`RANDOM_MAX`, inclusive.
42 >>> abs(random_scalar()) <= RANDOM_MAX
46 return uniform(-RANDOM_MAX
, RANDOM_MAX
)
49 def random_nn_scalar():
51 Generate a random nonnegative scalar.
57 A random nonnegative real number between zero and
58 :const:`RANDOM_MAX`, inclusive.
63 >>> 0 <= random_nn_scalar() <= RANDOM_MAX
67 return abs(random_scalar())
72 Generate a random natural number.
78 A random natural number between ``1`` and :const:`RANDOM_MAX`,
84 >>> 1 <= random_natural() <= RANDOM_MAX
88 return randint(1, RANDOM_MAX
)
91 def random_matrix(row_count
, column_count
=None):
93 Generate a random matrix.
99 The number of rows you want in the returned matrix.
102 The number of columns you want in the returned matrix (default:
103 the same as ``row_count``).
109 A new matrix whose entries are random floats chosen uniformly
110 between negative and positive :const:`RANDOM_MAX`.
115 >>> A = random_matrix(3)
119 >>> A = random_matrix(3,2)
124 if column_count
is None:
125 column_count
= row_count
127 entries
= [random_scalar() for _
in range(row_count
*column_count
)]
128 return matrix(entries
, (row_count
, column_count
))
131 def random_nonnegative_matrix(row_count
, column_count
=None):
133 Generate a random matrix with nonnegative entries.
139 The number of rows you want in the returned matrix.
142 The number of columns you want in the returned matrix (default:
143 the same as ``row_count``).
149 A new matrix whose entries are chosen by :func:`random_nn_scalar`.
154 >>> A = random_nonnegative_matrix(3)
157 >>> all([entry >= 0 for entry in A])
160 >>> A = random_nonnegative_matrix(3,2)
163 >>> all([entry >= 0 for entry in A])
167 if column_count
is None:
168 column_count
= row_count
170 entries
= [random_nn_scalar() for _
in range(row_count
*column_count
)]
171 return matrix(entries
, (row_count
, column_count
))
174 def random_diagonal_matrix(dims
):
176 Generate a random square matrix with zero off-diagonal entries.
178 These matrices are Lyapunov-like on the nonnegative orthant, as is
185 The number of rows/columns you want in the returned matrix.
191 A new matrix whose diagonal entries are random floats chosen
192 using :func:`random_scalar` and whose off-diagonal entries are
198 >>> A = random_diagonal_matrix(3)
201 >>> A[0,1] == A[0,2] == A[1,0] == A[2,0] == A[1,2] == A[2,1] == 0
205 return matrix([[random_scalar()*int(i
== j
)
206 for i
in range(dims
)]
207 for j
in range(dims
)])
210 def random_skew_symmetric_matrix(dims
):
212 Generate a random skew-symmetrix matrix.
218 The number of rows/columns you want in the returned matrix.
224 A new skew-matrix whose strictly above-diagonal entries are
225 random floats chosen with :func:`random_scalar`.
230 >>> A = random_skew_symmetric_matrix(3)
234 >>> from dunshire.options import ABS_TOL
235 >>> from dunshire.matrices import norm
236 >>> A = random_skew_symmetric_matrix(random_natural())
237 >>> norm(A + A.trans()) < ABS_TOL
241 strict_ut
= [[random_scalar()*int(i
< j
)
242 for i
in range(dims
)]
243 for j
in range(dims
)]
245 strict_ut
= matrix(strict_ut
, (dims
, dims
))
246 return strict_ut
- strict_ut
.trans()
249 def random_lyapunov_like_icecream(dims
):
251 Generate a random matrix Lyapunov-like on the ice-cream cone.
253 The form of these matrices is cited in Gowda and Tao
254 [GowdaTao]_. The scalar ``a`` and the vector ``b`` (using their
255 notation) are easy to generate. The submatrix ``D`` is a little
256 trickier, but it can be found noticing that :math:`C + C^{T} = 0`
257 for a skew-symmetric matrix :math:`C` implying that :math:`C + C^{T}
258 + \left(2a\right)I = \left(2a\right)I`. Thus we can stick an
259 :math:`aI` with each of :math:`C,C^{T}` and let those be our
266 The dimension of the ice-cream cone (not of the matrix you want!)
267 on which the returned matrix should be Lyapunov-like.
273 A new matrix, Lyapunov-like on the ice-cream cone in ``dims``
274 dimensions, whose free entries are random floats chosen uniformly
275 between negative and positive :const:`RANDOM_MAX`.
280 .. [GowdaTao] M. S. Gowda and J. Tao. On the bilinearity rank of a
281 proper cone and Lyapunov-like transformations. Mathematical
282 Programming, 147:155-170, 2014.
287 >>> L = random_lyapunov_like_icecream(3)
291 >>> from dunshire.options import ABS_TOL
292 >>> from dunshire.matrices import inner_product
293 >>> x = matrix([1,1,0])
294 >>> s = matrix([1,-1,0])
295 >>> abs(inner_product(L*x, s)) < ABS_TOL
299 a
= matrix([random_scalar()], (1, 1))
300 b
= matrix([random_scalar() for _
in range(dims
-1)], (dims
-1, 1))
301 D
= random_skew_symmetric_matrix(dims
-1) + a
*identity(dims
-1)
302 row1
= append_col(a
, b
.trans())
303 row2
= append_col(b
, D
)
304 return append_row(row1
, row2
)
307 def random_orthant_game():
309 Generate a random game over the nonnegative orthant.
311 We generate each of ``L``, ``K``, ``e1``, and ``e2`` randomly within
312 the constraints of the nonnegative orthant, and then construct a
313 game from them. The process is repeated until we generate a game with
314 a condition number under :const:`MAX_COND`.
320 A random game over some nonnegative orthant.
325 >>> random_orthant_game()
326 <dunshire.games.SymmetricLinearGame object at 0x...>
329 ambient_dim
= random_natural() + 1
330 K
= NonnegativeOrthant(ambient_dim
)
331 e1
= [0.1 + random_nn_scalar() for _
in range(K
.dimension())]
332 e2
= [0.1 + random_nn_scalar() for _
in range(K
.dimension())]
333 L
= random_matrix(K
.dimension())
334 G
= SymmetricLinearGame(L
, K
, e1
, e2
)
336 if G
.condition() <= MAX_COND
:
339 return random_orthant_game()
342 def random_icecream_game():
344 Generate a random game over the ice-cream cone.
346 We generate each of ``L``, ``K``, ``e1``, and ``e2`` randomly within
347 the constraints of the ice-cream cone, and then construct a game
348 from them. The process is repeated until we generate a game with a
349 condition number under :const:`MAX_COND`.
355 A random game over some ice-cream cone.
360 >>> random_icecream_game()
361 <dunshire.games.SymmetricLinearGame object at 0x...>
364 # Use a minimum dimension of two to avoid divide-by-zero in
365 # the fudge factor we make up later.
366 ambient_dim
= random_natural() + 1
367 K
= IceCream(ambient_dim
)
368 e1
= [1] # Set the "height" of e1 to one
369 e2
= [1] # And the same for e2
371 # If we choose the rest of the components of e1,e2 randomly
372 # between 0 and 1, then the largest the squared norm of the
373 # non-height part of e1,e2 could be is the 1*(dim(K) - 1). We
374 # need to make it less than one (the height of the cone) so
375 # that the whole thing is in the cone. The norm of the
376 # non-height part is sqrt(dim(K) - 1), and we can divide by
378 fudge_factor
= 1.0 / (2.0*sqrt(K
.dimension() - 1.0))
379 e1
+= [fudge_factor
*uniform(0, 1) for _
in range(K
.dimension() - 1)]
380 e2
+= [fudge_factor
*uniform(0, 1) for _
in range(K
.dimension() - 1)]
381 L
= random_matrix(K
.dimension())
382 G
= SymmetricLinearGame(L
, K
, e1
, e2
)
384 if G
.condition() <= MAX_COND
:
387 return random_icecream_game()
392 Return a random game.
394 One of the functions,
396 1. :func:`random_orthant_game`
397 2. :func:`random_icecream_game`
399 is chosen at random and used to generate a random game.
411 <dunshire.games.SymmetricLinearGame object at 0x...>
414 cone_type
= randint(0,1)
416 return random_orthant_game()
418 return random_icecream_game()
421 def random_ll_orthant_game():
423 Return a random Lyapunov game over some nonnegative orthant.
425 We first construct a :func:`random_orthant_game` and then modify it
426 to have a :func:`random_diagonal_matrix` as its operator. Such
427 things are Lyapunov-like on the nonnegative orthant. That process is
428 repeated until the condition number of the resulting game is within
436 A random game over some nonnegative orthant whose
437 :meth:`dunshire.games.SymmetricLinearGame.payoff` method is
438 based on a Lyapunov-like
439 :meth:`dunshire.games.SymmetricLinearGame.L` operator.
444 >>> random_ll_orthant_game()
445 <dunshire.games.SymmetricLinearGame object at 0x...>
448 G
= random_orthant_game()
449 L
= random_diagonal_matrix(G
.dimension())
451 # Replace the totally-random ``L`` with random Lyapunov-like one.
452 G
= SymmetricLinearGame(L
, G
.K(), G
.e1(), G
.e2())
454 while G
.condition() > MAX_COND
:
455 # Try again until the condition number is satisfactory.
456 G
= random_orthant_game()
457 L
= random_diagonal_matrix(G
.dimension())
458 G
= SymmetricLinearGame(L
, G
.K(), G
.e1(), G
.e2())
463 def random_ll_icecream_game():
465 Return a random Lyapunov game over some ice-cream cone.
467 We first construct a :func:`random_icecream_game` and then modify it
468 to have a :func:`random_lyapunov_like_icecream` operator. That
469 process is repeated until the condition number of the resulting game
470 is within :const:`MAX_COND`.
476 A random game over some ice-cream cone whose
477 :meth:`dunshire.games.SymmetricLinearGame.payoff` method
478 is based on a Lyapunov-like
479 :meth:`dunshire.games.SymmetricLinearGame.L` operator.
484 >>> random_ll_icecream_game()
485 <dunshire.games.SymmetricLinearGame object at 0x...>
488 G
= random_icecream_game()
489 L
= random_lyapunov_like_icecream(G
.dimension())
491 # Replace the totally-random ``L`` with random Lyapunov-like one.
492 G
= SymmetricLinearGame(L
, G
.K(), G
.e1(), G
.e2())
494 while G
.condition() > MAX_COND
:
495 # Try again until the condition number is satisfactory.
496 G
= random_icecream_game()
497 L
= random_lyapunov_like_icecream(G
.dimension())
498 G
= SymmetricLinearGame(L
, G
.K(), G
.e1(), G
.e2())
503 def random_ll_game():
505 Return a random Lyapunov-like game.
507 One of the functions,
509 1. :func:`random_ll_orthant_game`
510 2. :func:`random_ll_icecream_game`
512 is chosen at random and used to generate a random game.
518 A random Lyapunov-like game.
524 <dunshire.games.SymmetricLinearGame object at 0x...>
527 cone_type
= randint(0,1)
529 return random_ll_orthant_game()
531 return random_ll_icecream_game()
534 def random_positive_orthant_game():
536 Return a random game over the nonnegative orthant with a positive
539 We first construct a :func:`random_orthant_game` and then modify it
540 to have a :func:`random_nonnegative_matrix` as its operator. That
541 process is repeated until the condition number of the resulting game
542 is within :const:`MAX_COND`.
548 A random game over some nonnegative orthant whose
549 :meth:`dunshire.games.SymmetricLinearGame.payoff` method
550 is based on a positive
551 :meth:`dunshire.games.SymmetricLinearGame.L` operator.
556 >>> random_positive_orthant_game()
557 <dunshire.games.SymmetricLinearGame object at 0x...>
561 G
= random_orthant_game()
562 L
= random_nonnegative_matrix(G
.dimension())
564 # Replace the totally-random ``L`` with the random nonnegative one.
565 G
= SymmetricLinearGame(L
, G
.K(), G
.e1(), G
.e2())
567 while G
.condition() > MAX_COND
:
568 # Try again until the condition number is satisfactory.
569 G
= random_orthant_game()
570 L
= random_nonnegative_matrix(G
.dimension())
571 G
= SymmetricLinearGame(L
, G
.K(), G
.e1(), G
.e2())
576 def random_nn_scaling(G
):
578 Scale the given game by a random nonnegative amount.
580 We re-attempt the scaling with a new random number until the
581 resulting scaled game has an acceptable condition number.
586 G : SymmetricLinearGame
587 The game that you would like to scale.
591 (float, SymmetricLinearGame)
592 A pair containing the both the scaling factor and the new scaled game.
597 >>> from dunshire.matrices import norm
598 >>> from dunshire.options import ABS_TOL
599 >>> G = random_orthant_game()
600 >>> (alpha, H) = random_nn_scaling(G)
605 >>> norm(G.e1() - H.e1()) < ABS_TOL
607 >>> norm(G.e2() - H.e2()) < ABS_TOL
611 alpha
= random_nn_scalar()
612 H
= SymmetricLinearGame(alpha
*G
.L().trans(), G
.K(), G
.e1(), G
.e2())
614 while H
.condition() > MAX_COND
:
615 # Loop until the condition number of H doesn't suck.
616 alpha
= random_nn_scalar()
617 H
= SymmetricLinearGame(alpha
*G
.L().trans(), G
.K(), G
.e1(), G
.e2())
622 def random_translation(G
):
624 Translate the given game by a random amount.
626 We re-attempt the translation with new random scalars until the
627 resulting translated game has an acceptable condition number.
632 G : SymmetricLinearGame
633 The game that you would like to translate.
637 (float, SymmetricLinearGame)
638 A pair containing the both the translation distance and the new
644 >>> from dunshire.matrices import norm
645 >>> from dunshire.options import ABS_TOL
646 >>> G = random_orthant_game()
647 >>> (alpha, H) = random_translation(G)
650 >>> norm(G.e1() - H.e1()) < ABS_TOL
652 >>> norm(G.e2() - H.e2()) < ABS_TOL
656 alpha
= random_scalar()
657 tensor_prod
= G
.e1() * G
.e2().trans()
658 M
= G
.L() + alpha
*tensor_prod
660 H
= SymmetricLinearGame(M
.trans(), G
.K(), G
.e1(), G
.e2())
661 while H
.condition() > MAX_COND
:
662 # Loop until the condition number of H doesn't suck.
663 alpha
= random_scalar()
664 M
= G
.L() + alpha
*tensor_prod
665 H
= SymmetricLinearGame(M
.trans(), G
.K(), G
.e1(), G
.e2())