]>
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
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 ``-RANDOM_MAX`` and ``RANDOM_MAX``,
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 ``RANDOM_MAX``,
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 ``RANDOM_MAX`` inclusive.
83 >>> 1 <= random_natural() <= RANDOM_MAX
87 return randint(1, RANDOM_MAX
)
90 def random_matrix(row_count
, column_count
=None):
92 Generate a random matrix.
98 The number of rows you want in the returned matrix.
101 The number of columns you want in the returned matrix (default:
102 the same as ``row_count``).
108 A new matrix whose entries are random floats chosen uniformly from
109 the interval ``[-RANDOM_MAX, RANDOM_MAX]``.
114 >>> A = random_matrix(3)
118 >>> A = random_matrix(3,2)
123 if column_count
is None:
124 column_count
= row_count
126 entries
= [random_scalar() for _
in range(row_count
*column_count
)]
127 return matrix(entries
, (row_count
, column_count
))
130 def random_nonnegative_matrix(row_count
, column_count
=None):
132 Generate a random matrix with nonnegative entries.
138 The number of rows you want in the returned matrix.
141 The number of columns you want in the returned matrix (default:
142 the same as ``row_count``).
148 A new matrix whose entries are chosen by :func:`random_nn_scalar`.
153 >>> A = random_nonnegative_matrix(3)
156 >>> all([entry >= 0 for entry in A])
159 >>> A = random_nonnegative_matrix(3,2)
162 >>> all([entry >= 0 for entry in A])
166 if column_count
is None:
167 column_count
= row_count
169 entries
= [random_nn_scalar() for _
in range(row_count
*column_count
)]
170 return matrix(entries
, (row_count
, column_count
))
173 def random_diagonal_matrix(dims
):
175 Generate a random square matrix with zero off-diagonal entries.
177 These matrices are Lyapunov-like on the nonnegative orthant, as is
184 The number of rows/columns you want in the returned matrix.
190 A new matrix whose diagonal entries are random floats chosen
191 using func:`random_scalar` and whose off-diagonal entries are
197 >>> A = random_diagonal_matrix(3)
200 >>> A[0,1] == A[0,2] == A[1,0] == A[2,0] == A[1,2] == A[2,1] == 0
204 return matrix([[random_scalar()*int(i
== j
)
205 for i
in range(dims
)]
206 for j
in range(dims
)])
209 def random_skew_symmetric_matrix(dims
):
211 Generate a random skew-symmetrix matrix.
217 The number of rows/columns you want in the returned matrix.
223 A new skew-matrix whose strictly above-diagonal entries are
224 random floats chosen with :func:`random_scalar`.
229 >>> A = random_skew_symmetric_matrix(3)
233 >>> from dunshire.options import ABS_TOL
234 >>> from dunshire.matrices import norm
235 >>> A = random_skew_symmetric_matrix(random_natural())
236 >>> norm(A + A.trans()) < ABS_TOL
240 strict_ut
= [[random_scalar()*int(i
< j
)
241 for i
in range(dims
)]
242 for j
in range(dims
)]
244 strict_ut
= matrix(strict_ut
, (dims
, dims
))
245 return strict_ut
- strict_ut
.trans()
248 def random_lyapunov_like_icecream(dims
):
250 Generate a random matrix Lyapunov-like on the ice-cream cone.
252 The form of these matrices is cited in Gowda and Tao
253 [GowdaTao]_. The scalar ``a`` and the vector ``b`` (using their
254 notation) are easy to generate. The submatrix ``D`` is a little
255 trickier, but it can be found noticing that :math:`C + C^{T} = 0`
256 for a skew-symmetric matrix :math:`C` implying that :math:`C + C^{T}
257 + \left(2a\right)I = \left(2a\right)I`. Thus we can stick an
258 :math:`aI` with each of :math:`C,C^{T}` and let those be our
265 The dimension of the ice-cream cone (not of the matrix you want!)
266 on which the returned matrix should be Lyapunov-like.
272 A new matrix, Lyapunov-like on the ice-cream cone in ``dims``
273 dimensions, whose free entries are random floats chosen uniformly
274 from the interval ``[-RANDOM_MAX, RANDOM_MAX]``.
279 .. [GowdaTao] M. S. Gowda and J. Tao. On the bilinearity rank of a
280 proper cone and Lyapunov-like transformations. Mathematical
281 Programming, 147:155-170, 2014.
286 >>> L = random_lyapunov_like_icecream(3)
290 >>> from dunshire.options import ABS_TOL
291 >>> from dunshire.matrices import inner_product
292 >>> x = matrix([1,1,0])
293 >>> s = matrix([1,-1,0])
294 >>> abs(inner_product(L*x, s)) < ABS_TOL
298 a
= matrix([random_scalar()], (1, 1))
299 b
= matrix([random_scalar() for _
in range(dims
-1)], (dims
-1, 1))
300 D
= random_skew_symmetric_matrix(dims
-1) + a
*identity(dims
-1)
301 row1
= append_col(a
, b
.trans())
302 row2
= append_col(b
, D
)
303 return append_row(row1
, row2
)
306 def random_orthant_game():
308 Generate a random game over the nonnegative orthant.
310 We generate each of ``L``, ``K``, ``e1``, and ``e2`` randomly within
311 the constraints of the nonnegative orthant, and then construct a
312 game from them. The process is repeated until we generate a game with
313 a condition number under ``MAX_COND``.
319 A random game over some nonnegative orthant.
324 >>> random_orthant_game()
325 <dunshire.games.SymmetricLinearGame object at 0x...>
328 ambient_dim
= random_natural() + 1
329 K
= NonnegativeOrthant(ambient_dim
)
330 e1
= [0.1 + random_nn_scalar() for _
in range(K
.dimension())]
331 e2
= [0.1 + random_nn_scalar() for _
in range(K
.dimension())]
332 L
= random_matrix(K
.dimension())
333 G
= SymmetricLinearGame(L
, K
, e1
, e2
)
335 if G
.condition() <= MAX_COND
:
338 return random_orthant_game()
341 def random_icecream_game():
343 Generate a random game over the ice-cream cone.
345 We generate each of ``L``, ``K``, ``e1``, and ``e2`` randomly within
346 the constraints of the ice-cream cone, and then construct a game
347 from them. The process is repeated until we generate a game with a
348 condition number under ``MAX_COND``.
354 A random game over some ice-cream cone.
359 >>> random_icecream_game()
360 <dunshire.games.SymmetricLinearGame object at 0x...>
363 # Use a minimum dimension of two to avoid divide-by-zero in
364 # the fudge factor we make up later.
365 ambient_dim
= random_natural() + 1
366 K
= IceCream(ambient_dim
)
367 e1
= [1] # Set the "height" of e1 to one
368 e2
= [1] # And the same for e2
370 # If we choose the rest of the components of e1,e2 randomly
371 # between 0 and 1, then the largest the squared norm of the
372 # non-height part of e1,e2 could be is the 1*(dim(K) - 1). We
373 # need to make it less than one (the height of the cone) so
374 # that the whole thing is in the cone. The norm of the
375 # non-height part is sqrt(dim(K) - 1), and we can divide by
377 fudge_factor
= 1.0 / (2.0*sqrt(K
.dimension() - 1.0))
378 e1
+= [fudge_factor
*uniform(0, 1) for _
in range(K
.dimension() - 1)]
379 e2
+= [fudge_factor
*uniform(0, 1) for _
in range(K
.dimension() - 1)]
380 L
= random_matrix(K
.dimension())
381 G
= SymmetricLinearGame(L
, K
, e1
, e2
)
383 if G
.condition() <= MAX_COND
:
386 return random_icecream_game()
389 def random_ll_orthant_game():
391 Return a random Lyapunov game over some nonnegative orthant.
393 We first construct a :func:`random_orthant_game` and then modify it
394 to have a :func:`random_diagonal_matrix` as its operator. Such
395 things are Lyapunov-like on the nonnegative orthant. That process is
396 repeated until the condition number of the resulting game is within
403 A random game over some nonnegative orthant whose ``payoff`` method
404 is based on a Lyapunov-like ``L`` operator.
409 >>> random_ll_orthant_game()
410 <dunshire.games.SymmetricLinearGame object at 0x...>
413 G
= random_orthant_game()
414 L
= random_diagonal_matrix(G
.dimension())
416 # Replace the totally-random ``L`` with random Lyapunov-like one.
417 G
= SymmetricLinearGame(L
, G
.K(), G
.e1(), G
.e2())
419 while G
.condition() > MAX_COND
:
420 # Try again until the condition number is satisfactory.
421 G
= random_orthant_game()
422 L
= random_diagonal_matrix(G
.dimension())
423 G
= SymmetricLinearGame(L
, G
.K(), G
.e1(), G
.e2())
428 def random_ll_icecream_game():
430 Return a random Lyapunov game over some ice-cream cone.
432 We first construct a :func:`random_icecream_game` and then modify it
433 to have a :func:`random_lyapunov_like_icecream` operator. That
434 process is repeated until the condition number of the resulting game
435 is within ``MAX_COND``.
441 A random game over some ice-cream cone whose ``payoff`` method
442 is based on a Lyapunov-like ``L`` operator.
447 >>> random_ll_icecream_game()
448 <dunshire.games.SymmetricLinearGame object at 0x...>
451 G
= random_icecream_game()
452 L
= random_lyapunov_like_icecream(G
.dimension())
454 # Replace the totally-random ``L`` with random Lyapunov-like one.
455 G
= SymmetricLinearGame(L
, G
.K(), G
.e1(), G
.e2())
457 while G
.condition() > MAX_COND
:
458 # Try again until the condition number is satisfactory.
459 G
= random_icecream_game()
460 L
= random_lyapunov_like_icecream(G
.dimension())
461 G
= SymmetricLinearGame(L
, G
.K(), G
.e1(), G
.e2())
466 def random_positive_orthant_game():
468 Return a random game over the nonnegative orthant with a positive
471 We first construct a :func:`random_orthant_game` and then modify it
472 to have a :func:`random_nonnegative_matrix` as its operator. That
473 process is repeated until the condition number of the resulting game
474 is within ``MAX_COND``.
480 A random game over some nonnegative orthant whose ``payoff`` method
481 is based on a positive ``L`` operator.
486 >>> random_positive_orthant_game()
487 <dunshire.games.SymmetricLinearGame object at 0x...>
491 G
= random_orthant_game()
492 L
= random_nonnegative_matrix(G
.dimension())
494 # Replace the totally-random ``L`` with the random nonnegative one.
495 G
= SymmetricLinearGame(L
, G
.K(), G
.e1(), G
.e2())
497 while G
.condition() > MAX_COND
:
498 # Try again until the condition number is satisfactory.
499 G
= random_orthant_game()
500 L
= random_nonnegative_matrix(G
.dimension())
501 G
= SymmetricLinearGame(L
, G
.K(), G
.e1(), G
.e2())
506 def random_nn_scaling(G
):
508 Scale the given game by a random nonnegative amount.
510 We re-attempt the scaling with a new random number until the
511 resulting scaled game has an acceptable condition number.
516 G : SymmetricLinearGame
517 The game that you would like to scale.
521 (float, SymmetricLinearGame)
522 A pair containing the both the scaling factor and the new scaled game.
527 >>> from dunshire.matrices import norm
528 >>> from dunshire.options import ABS_TOL
529 >>> G = random_orthant_game()
530 >>> (alpha, H) = random_nn_scaling(G)
535 >>> norm(G.e1() - H.e1()) < ABS_TOL
537 >>> norm(G.e2() - H.e2()) < ABS_TOL
541 alpha
= random_nn_scalar()
542 H
= SymmetricLinearGame(alpha
*G
.L().trans(), G
.K(), G
.e1(), G
.e2())
544 while H
.condition() > MAX_COND
:
545 # Loop until the condition number of H doesn't suck.
546 alpha
= random_nn_scalar()
547 H
= SymmetricLinearGame(alpha
*G
.L().trans(), G
.K(), G
.e1(), G
.e2())
552 def random_translation(G
):
554 Translate the given game by a random amount.
556 We re-attempt the translation with new random scalars until the
557 resulting translated game has an acceptable condition number.
562 G : SymmetricLinearGame
563 The game that you would like to translate.
567 (float, SymmetricLinearGame)
568 A pair containing the both the translation distance and the new
574 >>> from dunshire.matrices import norm
575 >>> from dunshire.options import ABS_TOL
576 >>> G = random_orthant_game()
577 >>> (alpha, H) = random_translation(G)
580 >>> norm(G.e1() - H.e1()) < ABS_TOL
582 >>> norm(G.e2() - H.e2()) < ABS_TOL
586 alpha
= random_scalar()
587 tensor_prod
= G
.e1() * G
.e2().trans()
588 M
= G
.L() + alpha
*tensor_prod
590 H
= SymmetricLinearGame(M
.trans(), G
.K(), G
.e1(), G
.e2())
591 while H
.condition() > MAX_COND
:
592 # Loop until the condition number of H doesn't suck.
593 alpha
= random_scalar()
594 M
= G
.L() + alpha
*tensor_prod
595 H
= SymmetricLinearGame(M
.trans(), G
.K(), G
.e1(), G
.e2())