]>
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 ``-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())