]>
gitweb.michael.orlitzky.com - dunshire.git/blob - test/symmetric_linear_game_test.py
2 Unit tests for the :class:`SymmetricLinearGame` class.
7 The maximum condition number of a randomly-generated game.
12 When generating uniform random real numbers, this will be used as the
13 largest allowed magnitude. It keeps our condition numbers down and other
14 properties within reason.
18 from random
import randint
, uniform
19 from unittest
import TestCase
21 from cvxopt
import matrix
22 from dunshire
.cones
import NonnegativeOrthant
, IceCream
23 from dunshire
.games
import SymmetricLinearGame
24 from dunshire
.matrices
import (append_col
, append_row
, eigenvalues_re
,
25 identity
, inner_product
)
26 from dunshire
import options
29 def random_matrix(dims
):
31 Generate a random square matrix.
37 The number of rows/columns you want in the returned matrix.
43 A new matrix whose entries are random floats chosen uniformly from
44 the interval [-RANDOM_MAX, RANDOM_MAX].
49 >>> A = random_matrix(3)
54 return matrix([[uniform(-RANDOM_MAX
, RANDOM_MAX
) for _
in range(dims
)]
55 for _
in range(dims
)])
58 def random_nonnegative_matrix(dims
):
60 Generate a random square matrix with nonnegative entries.
66 The number of rows/columns you want in the returned matrix.
72 A new matrix whose entries are random floats chosen uniformly from
73 the interval [0, RANDOM_MAX].
78 >>> A = random_nonnegative_matrix(3)
81 >>> all([entry >= 0 for entry in A])
85 L
= random_matrix(dims
)
86 return matrix([abs(entry
) for entry
in L
], (dims
, dims
))
89 def random_diagonal_matrix(dims
):
91 Generate a random square matrix with zero off-diagonal entries.
93 These matrices are Lyapunov-like on the nonnegative orthant, as is
100 The number of rows/columns you want in the returned matrix.
106 A new matrix whose diagonal entries are random floats chosen
107 uniformly from the interval [-RANDOM_MAX, RANDOM_MAX] and whose
108 off-diagonal entries are zero.
113 >>> A = random_diagonal_matrix(3)
116 >>> A[0,1] == A[0,2] == A[1,0] == A[2,0] == A[1,2] == A[2,1] == 0
120 return matrix([[uniform(-RANDOM_MAX
, RANDOM_MAX
)*int(i
== j
)
121 for i
in range(dims
)]
122 for j
in range(dims
)])
125 def random_skew_symmetric_matrix(dims
):
127 Generate a random skew-symmetrix matrix.
133 The number of rows/columns you want in the returned matrix.
139 A new skew-matrix whose strictly above-diagonal entries are
140 random floats chosen uniformly from the interval
141 [-RANDOM_MAX, RANDOM_MAX].
146 >>> A = random_skew_symmetric_matrix(3)
150 >>> from dunshire.matrices import norm
151 >>> A = random_skew_symmetric_matrix(randint(1, 10))
152 >>> norm(A + A.trans()) < options.ABS_TOL
156 strict_ut
= [[uniform(-10, 10)*int(i
< j
) for i
in range(dims
)]
157 for j
in range(dims
)]
159 strict_ut
= matrix(strict_ut
, (dims
, dims
))
160 return strict_ut
- strict_ut
.trans()
163 def random_lyapunov_like_icecream(dims
):
165 Generate a random matrix Lyapunov-like on the ice-cream cone.
167 The form of these matrices is cited in Gowda and Tao
168 [GowdaTao]_. The scalar ``a`` and the vector ``b`` (using their
169 notation) are easy to generate. The submatrix ``D`` is a little
170 trickier, but it can be found noticing that :math:`C + C^{T} = 0`
171 for a skew-symmetric matrix :math:`C` implying that :math:`C + C^{T}
172 + \left(2a\right)I = \left(2a\right)I`. Thus we can stick an
173 :math:`aI` with each of :math:`C,C^{T}` and let those be our
180 The dimension of the ice-cream cone (not of the matrix you want!)
181 on which the returned matrix should be Lyapunov-like.
187 A new matrix, Lyapunov-like on the ice-cream cone in ``dims``
188 dimensions, whose free entries are random floats chosen uniformly
189 from the interval [-10, 10].
194 .. [GowdaTao] M. S. Gowda and J. Tao. On the bilinearity rank of a
195 proper cone and Lyapunov-like transformations. Mathematical
196 Programming, 147:155-170, 2014.
201 >>> L = random_lyapunov_like_icecream(3)
204 >>> x = matrix([1,1,0])
205 >>> s = matrix([1,-1,0])
206 >>> abs(inner_product(L*x, s)) < options.ABS_TOL
210 a
= matrix([uniform(-10, 10)], (1, 1))
211 b
= matrix([uniform(-10, 10) for _
in range(dims
-1)], (dims
-1, 1))
212 D
= random_skew_symmetric_matrix(dims
-1) + a
*identity(dims
-1)
213 row1
= append_col(a
, b
.trans())
214 row2
= append_col(b
, D
)
215 return append_row(row1
, row2
)
218 def random_orthant_game():
220 Generate the ``L``, ``K``, ``e1``, and ``e2`` parameters for a
221 random game over the nonnegative orthant, and return the
222 corresponding :class:`SymmetricLinearGame`.
224 We keep going until we generate a game with a condition number under
227 ambient_dim
= randint(1, 10)
228 K
= NonnegativeOrthant(ambient_dim
)
229 e1
= [uniform(0.5, 10) for _
in range(K
.dimension())]
230 e2
= [uniform(0.5, 10) for _
in range(K
.dimension())]
231 L
= random_matrix(K
.dimension())
232 G
= SymmetricLinearGame(L
, K
, e1
, e2
)
234 if G
._condition
() <= MAX_COND
:
237 return random_orthant_game()
240 def random_icecream_game():
242 Generate the ``L``, ``K``, ``e1``, and ``e2`` parameters for a
243 random game over the ice-cream cone, and return the corresponding
244 :class:`SymmetricLinearGame`.
246 # Use a minimum dimension of two to avoid divide-by-zero in
247 # the fudge factor we make up later.
248 ambient_dim
= randint(2, 10)
249 K
= IceCream(ambient_dim
)
250 e1
= [1] # Set the "height" of e1 to one
251 e2
= [1] # And the same for e2
253 # If we choose the rest of the components of e1,e2 randomly
254 # between 0 and 1, then the largest the squared norm of the
255 # non-height part of e1,e2 could be is the 1*(dim(K) - 1). We
256 # need to make it less than one (the height of the cone) so
257 # that the whole thing is in the cone. The norm of the
258 # non-height part is sqrt(dim(K) - 1), and we can divide by
260 fudge_factor
= 1.0 / (2.0*sqrt(K
.dimension() - 1.0))
261 e1
+= [fudge_factor
*uniform(0, 1) for _
in range(K
.dimension() - 1)]
262 e2
+= [fudge_factor
*uniform(0, 1) for _
in range(K
.dimension() - 1)]
263 L
= random_matrix(K
.dimension())
264 G
= SymmetricLinearGame(L
, K
, e1
, e2
)
266 if G
._condition
() <= MAX_COND
:
269 return random_icecream_game()
272 # Tell pylint to shut up about the large number of methods.
273 class SymmetricLinearGameTest(TestCase
): # pylint: disable=R0904
275 Tests for the SymmetricLinearGame and Solution classes.
277 def assert_within_tol(self
, first
, second
):
279 Test that ``first`` and ``second`` are equal within a multiple of
280 our default tolerances.
282 The factor of two is because if we compare two solutions, both
283 of which may be off by ``ABS_TOL``, then the result could be off
284 by ``2*ABS_TOL``. The factor of ``RANDOM_MAX`` allows for
285 scaling a result (by ``RANDOM_MAX``) that may be off by
286 ``ABS_TOL``. The final factor of two is to allow for the edge
287 cases where we get an "unknown" result and need to lower the
288 CVXOPT tolerance by a factor of two.
290 self
.assertTrue(abs(first
- second
) < 2*2*RANDOM_MAX
*options
.ABS_TOL
)
293 def assert_solution_exists(self
, G
):
295 Given a SymmetricLinearGame, ensure that it has a solution.
299 expected
= inner_product(G
._L*soln
.player1_optimal(),
300 soln
.player2_optimal())
301 self
.assert_within_tol(soln
.game_value(), expected
)
305 def test_condition_lower_bound(self
):
307 Ensure that the condition number of a game is greater than or
310 It should be safe to compare these floats directly: we compute
311 the condition number as the ratio of one nonnegative real number
312 to a smaller nonnegative real number.
314 G
= random_orthant_game()
315 self
.assertTrue(G
._condition
() >= 1.0)
316 G
= random_icecream_game()
317 self
.assertTrue(G
._condition
() >= 1.0)
320 def test_solution_exists_orthant(self
):
322 Every linear game has a solution, so we should be able to solve
323 every symmetric linear game over the NonnegativeOrthant. Pick
324 some parameters randomly and give it a shot. The resulting
325 optimal solutions should give us the optimal game value when we
326 apply the payoff operator to them.
328 G
= random_orthant_game()
329 self
.assert_solution_exists(G
)
332 def test_solution_exists_icecream(self
):
334 Like :meth:`test_solution_exists_nonnegative_orthant`, except
335 over the ice cream cone.
337 G
= random_icecream_game()
338 self
.assert_solution_exists(G
)
341 def test_negative_value_z_operator(self
):
343 Test the example given in Gowda/Ravindran of a Z-matrix with
344 negative game value on the nonnegative orthant.
346 K
= NonnegativeOrthant(2)
349 L
= [[1, -2], [-2, 1]]
350 G
= SymmetricLinearGame(L
, K
, e1
, e2
)
351 self
.assertTrue(G
.solution().game_value() < -options
.ABS_TOL
)
354 def assert_scaling_works(self
, game1
):
356 Test that scaling ``L`` by a nonnegative number scales the value
357 of the game by the same number.
359 value1
= game1
.solution().game_value()
361 alpha
= uniform(0.1, 10)
362 game2
= SymmetricLinearGame(alpha
*game1
._L
.trans(),
367 while game2
._condition() > MAX_COND
:
368 # Loop until the condition number of game2 doesn't suck.
369 alpha
= uniform(0.1, 10)
370 game2
= SymmetricLinearGame(alpha
*game1
._L
.trans(),
375 value2
= game2
.solution().game_value()
376 self
.assert_within_tol(alpha
*value1
, value2
)
379 def test_scaling_orthant(self
):
381 Test that scaling ``L`` by a nonnegative number scales the value
382 of the game by the same number over the nonnegative orthant.
384 G
= random_orthant_game()
385 self
.assert_scaling_works(G
)
388 def test_scaling_icecream(self
):
390 The same test as :meth:`test_nonnegative_scaling_orthant`,
391 except over the ice cream cone.
393 G
= random_icecream_game()
394 self
.assert_scaling_works(G
)
397 def assert_translation_works(self
, game1
):
399 Check that translating ``L`` by alpha*(e1*e2.trans()) increases
400 the value of the associated game by alpha.
402 # We need to use ``L`` later, so make sure we transpose it
403 # before passing it in as a column-indexed matrix.
404 soln1
= game1
.solution()
405 value1
= soln1
.game_value()
406 x_bar
= soln1
.player1_optimal()
407 y_bar
= soln1
.player2_optimal()
408 tensor_prod
= game1
._e1
*game1
._e2
.trans()
410 # This is the "correct" representation of ``M``, but COLUMN
412 alpha
= uniform(-10, 10)
413 M
= game1
._L
+ alpha
*tensor_prod
415 # so we have to transpose it when we feed it to the constructor.
416 game2
= SymmetricLinearGame(M
.trans(), game1
._K
, game1
._e1
, game1
._e2
)
417 while game2
._condition() > MAX_COND
:
418 # Loop until the condition number of game2 doesn't suck.
419 alpha
= uniform(-10, 10)
420 M
= game1
._L
+ alpha
*tensor_prod
421 game2
= SymmetricLinearGame(M
.trans(),
426 value2
= game2
.solution().game_value()
428 self
.assert_within_tol(value1
+ alpha
, value2
)
430 # Make sure the same optimal pair works.
431 self
.assert_within_tol(value2
, inner_product(M
*x_bar
, y_bar
))
434 def test_translation_orthant(self
):
436 Test that translation works over the nonnegative orthant.
438 G
= random_orthant_game()
439 self
.assert_translation_works(G
)
442 def test_translation_icecream(self
):
444 The same as :meth:`test_translation_orthant`, except over the
447 G
= random_icecream_game()
448 self
.assert_translation_works(G
)
451 def assert_opposite_game_works(self
, game1
):
453 Check the value of the "opposite" game that gives rise to a
454 value that is the negation of the original game. Comes from
457 # This is the "correct" representation of ``M``, but
459 M
= -game1
._L
.trans()
461 # so we have to transpose it when we feed it to the constructor.
462 # Note: the condition number of game2 should be comparable to game1.
463 game2
= SymmetricLinearGame(M
.trans(), game1
._K
, game1
._e2
, game1
._e1
)
465 soln1
= game1
.solution()
466 x_bar
= soln1
.player1_optimal()
467 y_bar
= soln1
.player2_optimal()
468 soln2
= game2
.solution()
470 self
.assert_within_tol(-soln1
.game_value(), soln2
.game_value())
472 # Make sure the switched optimal pair works.
473 self
.assert_within_tol(soln2
.game_value(),
474 inner_product(M
*y_bar
, x_bar
))
477 def test_opposite_game_orthant(self
):
479 Test the value of the "opposite" game over the nonnegative
482 G
= random_orthant_game()
483 self
.assert_opposite_game_works(G
)
486 def test_opposite_game_icecream(self
):
488 Like :meth:`test_opposite_game_orthant`, except over the
491 G
= random_icecream_game()
492 self
.assert_opposite_game_works(G
)
495 def assert_orthogonality(self
, G
):
497 Two orthogonality relations hold at an optimal solution, and we
501 x_bar
= soln
.player1_optimal()
502 y_bar
= soln
.player2_optimal()
503 value
= soln
.game_value()
505 ip1
= inner_product(y_bar
, G
._L*x_bar
- value
*G
._e
1)
506 self
.assert_within_tol(ip1
, 0)
508 ip2
= inner_product(value
*G
._e
2 - G
._L.trans()*y_bar
, x_bar
)
509 self
.assert_within_tol(ip2
, 0)
512 def test_orthogonality_orthant(self
):
514 Check the orthgonality relationships that hold for a solution
515 over the nonnegative orthant.
517 G
= random_orthant_game()
518 self
.assert_orthogonality(G
)
521 def test_orthogonality_icecream(self
):
523 Check the orthgonality relationships that hold for a solution
524 over the ice-cream cone.
526 G
= random_icecream_game()
527 self
.assert_orthogonality(G
)
530 def test_positive_operator_value(self
):
532 Test that a positive operator on the nonnegative orthant gives
533 rise to a a game with a nonnegative value.
535 This test theoretically applies to the ice-cream cone as well,
536 but we don't know how to make positive operators on that cone.
538 G
= random_orthant_game()
539 L
= random_nonnegative_matrix(G
._K
.dimension())
541 # Replace the totally-random ``L`` with the random nonnegative one.
542 G
= SymmetricLinearGame(L
, G
._K
, G
._e
1, G
._e
2)
544 while G
._condition
() > MAX_COND
:
545 # Try again until the condition number is satisfactory.
546 G
= random_orthant_game()
547 L
= random_nonnegative_matrix(G
._K
.dimension())
548 G
= SymmetricLinearGame(L
, G
._K
, G
._e
1, G
._e
2)
550 self
.assertTrue(G
.solution().game_value() >= -options
.ABS_TOL
)
553 def assert_lyapunov_works(self
, G
):
555 Check that Lyapunov games act the way we expect.
559 # We only check for positive/negative stability if the game
560 # value is not basically zero. If the value is that close to
561 # zero, we just won't check any assertions.
563 # See :meth:`assert_within_tol` for an explanation of the
565 eigs
= eigenvalues_re(G
._L)
566 epsilon
= 2*2*RANDOM_MAX
*options
.ABS_TOL
567 if soln
.game_value() > epsilon
:
568 # L should be positive stable
569 positive_stable
= all([eig
> -options
.ABS_TOL
for eig
in eigs
])
570 if not positive_stable
:
572 self
.assertTrue(positive_stable
)
573 elif soln
.game_value() < -epsilon
:
574 # L should be negative stable
575 negative_stable
= all([eig
< options
.ABS_TOL
for eig
in eigs
])
576 if not negative_stable
:
578 self
.assertTrue(negative_stable
)
580 # The dual game's value should always equal the primal's.
581 dualsoln
= G
.dual().solution()
582 self
.assert_within_tol(dualsoln
.game_value(), soln
.game_value())
585 def test_lyapunov_orthant(self
):
587 Test that a Lyapunov game on the nonnegative orthant works.
589 G
= random_orthant_game()
590 L
= random_diagonal_matrix(G
._K
.dimension())
592 # Replace the totally-random ``L`` with random Lyapunov-like one.
593 G
= SymmetricLinearGame(L
, G
._K
, G
._e
1, G
._e
2)
595 while G
._condition
() > MAX_COND
:
596 # Try again until the condition number is satisfactory.
597 G
= random_orthant_game()
598 L
= random_diagonal_matrix(G
._K
.dimension())
599 G
= SymmetricLinearGame(L
, G
._K
, G
._e
1, G
._e
2)
601 self
.assert_lyapunov_works(G
)
604 def test_lyapunov_icecream(self
):
606 Test that a Lyapunov game on the ice-cream cone works.
608 G
= random_icecream_game()
609 L
= random_lyapunov_like_icecream(G
._K
.dimension())
611 # Replace the totally-random ``L`` with random Lyapunov-like one.
612 G
= SymmetricLinearGame(L
, G
._K
, G
._e
1, G
._e
2)
614 while G
._condition
() > MAX_COND
:
615 # Try again until the condition number is satisfactory.
616 G
= random_orthant_game()
617 L
= random_lyapunov_like_icecream(G
._K
.dimension())
618 G
= SymmetricLinearGame(L
, G
._K
, G
._e
1, G
._e
2)
620 self
.assert_lyapunov_works(G
)