]>
gitweb.michael.orlitzky.com - dunshire.git/blob - test/randomgen.py
97dd0b93157a7b534c7cb4c6acb5de1740de661e
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.
19 When generating random real numbers or integers, this is used as the
20 largest allowed magnitude. It keeps our condition numbers down and other
21 properties within reason.
26 Generate a random scalar.
32 A random real number between ``-RANDOM_MAX`` and ``RANDOM_MAX``,
38 >>> abs(random_scalar()) <= RANDOM_MAX
42 return uniform(-RANDOM_MAX
, RANDOM_MAX
)
45 def random_nn_scalar():
47 Generate a random nonnegative scalar.
53 A random nonnegative real number between zero and ``RANDOM_MAX``,
59 >>> 0 <= random_nn_scalar() <= RANDOM_MAX
63 return abs(random_scalar())
68 Generate a random natural number.
74 A random natural number between ``1`` and ``RANDOM_MAX`` inclusive.
79 >>> 1 <= random_natural() <= RANDOM_MAX
83 return randint(1, RANDOM_MAX
)
86 def random_matrix(row_count
, column_count
=None):
88 Generate a random matrix.
94 The number of rows you want in the returned matrix.
97 The number of columns you want in the returned matrix (default:
98 the same as ``row_count``).
104 A new matrix whose entries are random floats chosen uniformly from
105 the interval ``[-RANDOM_MAX, RANDOM_MAX]``.
110 >>> A = random_matrix(3)
114 >>> A = random_matrix(3,2)
119 if column_count
is None:
120 column_count
= row_count
122 entries
= [random_scalar() for _
in range(row_count
*column_count
)]
123 return matrix(entries
, (row_count
, column_count
))
126 def random_nonnegative_matrix(row_count
, column_count
=None):
128 Generate a random matrix with nonnegative entries.
134 The number of rows you want in the returned matrix.
137 The number of columns you want in the returned matrix (default:
138 the same as ``row_count``).
144 A new matrix whose entries are chosen by :func:`random_nn_scalar`.
149 >>> A = random_nonnegative_matrix(3)
152 >>> all([entry >= 0 for entry in A])
155 >>> A = random_nonnegative_matrix(3,2)
158 >>> all([entry >= 0 for entry in A])
162 if column_count
is None:
163 column_count
= row_count
165 entries
= [random_nn_scalar() for _
in range(row_count
*column_count
)]
166 return matrix(entries
, (row_count
, column_count
))
169 def random_diagonal_matrix(dims
):
171 Generate a random square matrix with zero off-diagonal entries.
173 These matrices are Lyapunov-like on the nonnegative orthant, as is
180 The number of rows/columns you want in the returned matrix.
186 A new matrix whose diagonal entries are random floats chosen
187 using func:`random_scalar` and whose off-diagonal entries are
193 >>> A = random_diagonal_matrix(3)
196 >>> A[0,1] == A[0,2] == A[1,0] == A[2,0] == A[1,2] == A[2,1] == 0
200 return matrix([[random_scalar()*int(i
== j
)
201 for i
in range(dims
)]
202 for j
in range(dims
)])
205 def random_skew_symmetric_matrix(dims
):
207 Generate a random skew-symmetrix matrix.
213 The number of rows/columns you want in the returned matrix.
219 A new skew-matrix whose strictly above-diagonal entries are
220 random floats chosen with :func:`random_scalar`.
225 >>> A = random_skew_symmetric_matrix(3)
229 >>> from dunshire.options import ABS_TOL
230 >>> from dunshire.matrices import norm
231 >>> A = random_skew_symmetric_matrix(random_natural())
232 >>> norm(A + A.trans()) < ABS_TOL
236 strict_ut
= [[random_scalar()*int(i
< j
)
237 for i
in range(dims
)]
238 for j
in range(dims
)]
240 strict_ut
= matrix(strict_ut
, (dims
, dims
))
241 return strict_ut
- strict_ut
.trans()
244 def random_lyapunov_like_icecream(dims
):
246 Generate a random matrix Lyapunov-like on the ice-cream cone.
248 The form of these matrices is cited in Gowda and Tao
249 [GowdaTao]_. The scalar ``a`` and the vector ``b`` (using their
250 notation) are easy to generate. The submatrix ``D`` is a little
251 trickier, but it can be found noticing that :math:`C + C^{T} = 0`
252 for a skew-symmetric matrix :math:`C` implying that :math:`C + C^{T}
253 + \left(2a\right)I = \left(2a\right)I`. Thus we can stick an
254 :math:`aI` with each of :math:`C,C^{T}` and let those be our
261 The dimension of the ice-cream cone (not of the matrix you want!)
262 on which the returned matrix should be Lyapunov-like.
268 A new matrix, Lyapunov-like on the ice-cream cone in ``dims``
269 dimensions, whose free entries are random floats chosen uniformly
270 from the interval ``[-RANDOM_MAX, RANDOM_MAX]``.
275 .. [GowdaTao] M. S. Gowda and J. Tao. On the bilinearity rank of a
276 proper cone and Lyapunov-like transformations. Mathematical
277 Programming, 147:155-170, 2014.
282 >>> L = random_lyapunov_like_icecream(3)
286 >>> from dunshire.options import ABS_TOL
287 >>> from dunshire.matrices import inner_product
288 >>> x = matrix([1,1,0])
289 >>> s = matrix([1,-1,0])
290 >>> abs(inner_product(L*x, s)) < ABS_TOL
294 a
= matrix([random_scalar()], (1, 1))
295 b
= matrix([random_scalar() for _
in range(dims
-1)], (dims
-1, 1))
296 D
= random_skew_symmetric_matrix(dims
-1) + a
*identity(dims
-1)
297 row1
= append_col(a
, b
.trans())
298 row2
= append_col(b
, D
)
299 return append_row(row1
, row2
)
302 def random_orthant_game():
304 Generate a random game over the nonnegative orthant.
306 We generate each of ``L``, ``K``, ``e1``, and ``e2`` randomly within
307 the constraints of the nonnegative orthant, and then construct a
308 game from them. The process is repeated until we generate a game with
309 a condition number under ``MAX_COND``.
315 A random game over some nonnegative orthant.
320 >>> random_orthant_game()
321 <dunshire.games.SymmetricLinearGame object at 0x...>
324 ambient_dim
= random_natural() + 1
325 K
= NonnegativeOrthant(ambient_dim
)
326 e1
= [0.1 + random_nn_scalar() for _
in range(K
.dimension())]
327 e2
= [0.1 + random_nn_scalar() for _
in range(K
.dimension())]
328 L
= random_matrix(K
.dimension())
329 G
= SymmetricLinearGame(L
, K
, e1
, e2
)
331 if G
.condition() <= MAX_COND
:
334 return random_orthant_game()
337 def random_icecream_game():
339 Generate a random game over the ice-cream cone.
341 We generate each of ``L``, ``K``, ``e1``, and ``e2`` randomly within
342 the constraints of the ice-cream cone, and then construct a game
343 from them. The process is repeated until we generate a game with a
344 condition number under ``MAX_COND``.
350 A random game over some ice-cream cone.
355 >>> random_icecream_game()
356 <dunshire.games.SymmetricLinearGame object at 0x...>
359 # Use a minimum dimension of two to avoid divide-by-zero in
360 # the fudge factor we make up later.
361 ambient_dim
= random_natural() + 1
362 K
= IceCream(ambient_dim
)
363 e1
= [1] # Set the "height" of e1 to one
364 e2
= [1] # And the same for e2
366 # If we choose the rest of the components of e1,e2 randomly
367 # between 0 and 1, then the largest the squared norm of the
368 # non-height part of e1,e2 could be is the 1*(dim(K) - 1). We
369 # need to make it less than one (the height of the cone) so
370 # that the whole thing is in the cone. The norm of the
371 # non-height part is sqrt(dim(K) - 1), and we can divide by
373 fudge_factor
= 1.0 / (2.0*sqrt(K
.dimension() - 1.0))
374 e1
+= [fudge_factor
*uniform(0, 1) for _
in range(K
.dimension() - 1)]
375 e2
+= [fudge_factor
*uniform(0, 1) for _
in range(K
.dimension() - 1)]
376 L
= random_matrix(K
.dimension())
377 G
= SymmetricLinearGame(L
, K
, e1
, e2
)
379 if G
.condition() <= MAX_COND
:
382 return random_icecream_game()
385 def random_ll_orthant_game():
387 Return a random Lyapunov game over some nonnegative orthant.
389 We first construct a :func:`random_orthant_game` and then modify it
390 to have a :func:`random_diagonal_matrix` as its operator. Such
391 things are Lyapunov-like on the nonnegative orthant. That process is
392 repeated until the condition number of the resulting game is within
399 A random game over some nonnegative orthant whose ``payoff`` method
400 is based on a Lyapunov-like ``L`` operator.
405 >>> random_ll_orthant_game()
406 <dunshire.games.SymmetricLinearGame object at 0x...>
409 G
= random_orthant_game()
410 L
= random_diagonal_matrix(G
._K
.dimension())
412 # Replace the totally-random ``L`` with random Lyapunov-like one.
413 G
= SymmetricLinearGame(L
, G
._K
, G
._e
1, G
._e
2)
415 while G
.condition() > MAX_COND
:
416 # Try again until the condition number is satisfactory.
417 G
= random_orthant_game()
418 L
= random_diagonal_matrix(G
._K
.dimension())
419 G
= SymmetricLinearGame(L
, G
._K
, G
._e
1, G
._e
2)
424 def random_ll_icecream_game():
426 Return a random Lyapunov game over some ice-cream cone.
428 We first construct a :func:`random_icecream_game` and then modify it
429 to have a :func:`random_lyapunov_like_icecream` operator. That
430 process is repeated until the condition number of the resulting game
431 is within ``MAX_COND``.
437 A random game over some ice-cream cone whose ``payoff`` method
438 is based on a Lyapunov-like ``L`` operator.
443 >>> random_ll_icecream_game()
444 <dunshire.games.SymmetricLinearGame object at 0x...>
447 G
= random_icecream_game()
448 L
= random_lyapunov_like_icecream(G
._K
.dimension())
450 # Replace the totally-random ``L`` with random Lyapunov-like one.
451 G
= SymmetricLinearGame(L
, G
._K
, G
._e
1, G
._e
2)
453 while G
.condition() > MAX_COND
:
454 # Try again until the condition number is satisfactory.
455 G
= random_icecream_game()
456 L
= random_lyapunov_like_icecream(G
._K
.dimension())
457 G
= SymmetricLinearGame(L
, G
._K
, G
._e
1, G
._e
2)
462 def random_positive_orthant_game():
464 Return a random game over the nonnegative orthant with a positive
467 We first construct a :func:`random_orthant_game` and then modify it
468 to have a :func:`random_nonnegative_matrix` as its operator. That
469 process is repeated until the condition number of the resulting game
470 is within ``MAX_COND``.
476 A random game over some nonnegative orthant whose ``payoff`` method
477 is based on a positive ``L`` operator.
482 >>> random_positive_orthant_game()
483 <dunshire.games.SymmetricLinearGame object at 0x...>
487 G
= random_orthant_game()
488 L
= random_nonnegative_matrix(G
._K
.dimension())
490 # Replace the totally-random ``L`` with the random nonnegative one.
491 G
= SymmetricLinearGame(L
, G
._K
, G
._e
1, G
._e
2)
493 while G
.condition() > MAX_COND
:
494 # Try again until the condition number is satisfactory.
495 G
= random_orthant_game()
496 L
= random_nonnegative_matrix(G
._K
.dimension())
497 G
= SymmetricLinearGame(L
, G
._K
, G
._e
1, G
._e
2)
502 def random_nn_scaling(G
):
504 Scale the given game by a random nonnegative amount.
506 We re-attempt the scaling with a new random number until the
507 resulting scaled game has an acceptable condition number.
512 G : SymmetricLinearGame
513 The game that you would like to scale.
517 (float, SymmetricLinearGame)
518 A pair containing the both the scaling factor and the new scaled game.
523 >>> from dunshire.matrices import norm
524 >>> from dunshire.options import ABS_TOL
525 >>> G = random_orthant_game()
526 >>> (alpha, H) = random_nn_scaling(G)
531 >>> norm(G._e1 - H._e1) < ABS_TOL
533 >>> norm(G._e2 - H._e2) < ABS_TOL
537 alpha
= random_nn_scalar()
538 H
= SymmetricLinearGame(alpha
*G
._L.trans(), G
._K
, G
._e
1, G
._e
2)
540 while H
.condition() > MAX_COND
:
541 # Loop until the condition number of H doesn't suck.
542 alpha
= random_nn_scalar()
543 H
= SymmetricLinearGame(alpha
*G
._L.trans(), G
._K
, G
._e
1, G
._e
2)
548 def random_translation(G
):
550 Translate the given game by a random amount.
552 We re-attempt the translation with new random scalars until the
553 resulting translated game has an acceptable condition number.
558 G : SymmetricLinearGame
559 The game that you would like to translate.
563 (float, SymmetricLinearGame)
564 A pair containing the both the translation distance and the new
570 >>> from dunshire.matrices import norm
571 >>> from dunshire.options import ABS_TOL
572 >>> G = random_orthant_game()
573 >>> (alpha, H) = random_translation(G)
576 >>> norm(G._e1 - H._e1) < ABS_TOL
578 >>> norm(G._e2 - H._e2) < ABS_TOL
582 alpha
= random_scalar()
583 tensor_prod
= G
._e
1 * G
._e
2.trans()
584 M
= G
._L + alpha
*tensor_prod
586 H
= SymmetricLinearGame(M
.trans(), G
._K
, G
._e
1, G
._e
2)
587 while H
.condition() > MAX_COND
:
588 # Loop until the condition number of H doesn't suck.
589 alpha
= random_scalar()
590 M
= G
._L + alpha
*tensor_prod
591 H
= SymmetricLinearGame(M
.trans(), G
._K
, G
._e
1, G
._e
2)